nsz Git - cparser/blob - type_hash.c

   1 /*
   2  * This file is part of cparser.
   3  * Copyright (C) 2012 Matthias Braun <matze@braunis.de>
   4  */
   5 #include <config.h>
   6
   7 #include <stdbool.h>
   8
   9 #include "type_hash.h"
  10 #include "type_t.h"
  11
  12 #include <assert.h>
  13
  14 #define HashSet         type_hash_t
  15 #define ValueType       type_t*
  16 #include "adt/hashset.h"
  17 #undef ValueType
  18 #undef HashSet
  19
  20 typedef struct type_hash_iterator_t  type_hash_iterator_t;
  21 typedef struct type_hash_t           type_hash_t;
  22
  23 /* TODO: ^= is a bad way of combining hashes since most addresses are very
  24  * similar */
  25
  26 static unsigned hash_ptr(const void *ptr)
  27 {
  28         unsigned ptr_int = ((char*) ptr - (char*) NULL);
  29         return ptr_int >> 3;
  30 }
  31
  32 static unsigned hash_atomic_type(const atomic_type_t *type)
  33 {
  34         unsigned some_prime = 27644437;
  35         unsigned result     = type->akind * some_prime;
  36
  37         return result;
  38 }
  39
  40 static unsigned hash_pointer_type(const pointer_type_t *type)
  41 {
  42         return hash_ptr(type->points_to) ^ hash_ptr(type->base_variable);
  43 }
  44
  45 static unsigned hash_reference_type(const reference_type_t *type)
  46 {
  47         return hash_ptr(type->refers_to);
  48 }
  49
  50 static unsigned hash_array_type(const array_type_t *type)
  51 {
  52         return hash_ptr(type->element_type);
  53 }
  54
  55 static unsigned hash_compound_type(const compound_type_t *type)
  56 {
  57         return hash_ptr(type->compound);
  58 }
  59
  60 static unsigned hash_function_type(const function_type_t *type)
  61 {
  62         unsigned result = hash_ptr(type->return_type);
  63
  64         function_parameter_t *parameter = type->parameters;
  65         while (parameter != NULL) {
  66                 result   ^= hash_ptr(parameter->type);
  67                 parameter = parameter->next;
  68         }
  69         result += type->modifiers;
  70         result += type->linkage;
  71         result += type->calling_convention;
  72
  73         return result;
  74 }
  75
  76 static unsigned hash_enum_type(const enum_type_t *type)
  77 {
  78         return hash_ptr(type->enume);
  79 }
  80
  81 static unsigned hash_typeof_type(const typeof_type_t *type)
  82 {
  83         unsigned result = hash_ptr(type->expression);
  84         result         ^= hash_ptr(type->typeof_type);
  85
  86         return result;
  87 }
  88
  89 static unsigned hash_type(const type_t *type)
  90 {
  91         unsigned hash = 0;
  92
  93         switch (type->kind) {
  94         case TYPE_ERROR:
  95                 return 0;
  96         case TYPE_IMAGINARY:
  97         case TYPE_COMPLEX:
  98         case TYPE_ATOMIC:
  99                 hash = hash_atomic_type(&type->atomic);
 100                 break;
 101         case TYPE_ENUM:
 102                 hash = hash_enum_type(&type->enumt);
 103                 break;
 104         case TYPE_COMPOUND_STRUCT:
 105         case TYPE_COMPOUND_UNION:
 106                 hash = hash_compound_type(&type->compound);
 107                 break;
 108         case TYPE_FUNCTION:
 109                 hash = hash_function_type(&type->function);
 110                 break;
 111         case TYPE_POINTER:
 112                 hash = hash_pointer_type(&type->pointer);
 113                 break;
 114         case TYPE_REFERENCE:
 115                 hash = hash_reference_type(&type->reference);
 116                 break;
 117         case TYPE_ARRAY:
 118                 hash = hash_array_type(&type->array);
 119                 break;
 120         case TYPE_TYPEDEF:
 121                 hash = hash_ptr(type->typedeft.typedefe);
 122                 break;
 123         case TYPE_TYPEOF:
 124                 hash = hash_typeof_type(&type->typeoft);
 125                 break;
 126         }
 127
 128         unsigned some_prime = 99991;
 129         hash ^= some_prime * type->base.qualifiers;
 130
 131         return hash;
 132 }
 133
 134 static bool atomic_types_equal(const atomic_type_t *type1,
 135                                                            const atomic_type_t *type2)
 136 {
 137         return type1->akind == type2->akind;
 138 }
 139
 140 static bool function_types_equal(const function_type_t *type1,
 141                                  const function_type_t *type2)
 142 {
 143         if (type1->return_type != type2->return_type)
 144                 return false;
 145         if (type1->variadic != type2->variadic)
 146                 return false;
 147         if (type1->unspecified_parameters != type2->unspecified_parameters)
 148                 return false;
 149         if (type1->kr_style_parameters != type2->kr_style_parameters)
 150                 return false;
 151         if (type1->linkage != type2->linkage)
 152                 return false;
 153         if (type1->modifiers != type2->modifiers)
 154                 return false;
 155         if (type1->calling_convention != type2->calling_convention)
 156                 return false;
 157
 158         function_parameter_t *param1 = type1->parameters;
 159         function_parameter_t *param2 = type2->parameters;
 160         while (param1 != NULL && param2 != NULL) {
 161                 if (param1->type != param2->type)
 162                         return false;
 163                 param1 = param1->next;
 164                 param2 = param2->next;
 165         }
 166         if (param1 != NULL || param2 != NULL)
 167                 return false;
 168
 169         return true;
 170 }
 171
 172 static bool pointer_types_equal(const pointer_type_t *type1,
 173                                 const pointer_type_t *type2)
 174 {
 175         return type1->points_to     == type2->points_to &&
 176                type1->base_variable == type2->base_variable;
 177 }
 178
 179 static bool reference_types_equal(const reference_type_t *type1,
 180                                   const reference_type_t *type2)
 181 {
 182         return type1->refers_to == type2->refers_to;
 183 }
 184
 185 static bool array_types_equal(const array_type_t *type1,
 186                               const array_type_t *type2)
 187 {
 188         if (type1->element_type != type2->element_type)
 189                 return false;
 190         if (type1->is_variable != type2->is_variable)
 191                 return false;
 192         if (type1->is_static != type2->is_static)
 193                 return false;
 194         if (type1->size_constant != type2->size_constant)
 195                 return false;
 196
 197         /* never identify vla types, because we need them for caching calculated
 198          * sizes later in ast2firm */
 199         if (type1->is_vla || type2->is_vla)
 200                 return false;
 201
 202         /* TODO: compare size expressions for equality... */
 203
 204         return false;
 205 }
 206
 207 static bool compound_types_equal(const compound_type_t *type1,
 208                                  const compound_type_t *type2)
 209 {
 210         return type1->compound == type2->compound;
 211 }
 212
 213 static bool enum_types_equal(const enum_type_t *type1,
 214                              const enum_type_t *type2)
 215 {
 216         return type1->enume == type2->enume;
 217 }
 218
 219 static bool typedef_types_equal(const typedef_type_t *type1,
 220                                 const typedef_type_t *type2)
 221 {
 222         return type1->typedefe == type2->typedefe;
 223 }
 224
 225 static bool typeof_types_equal(const typeof_type_t *type1,
 226                                const typeof_type_t *type2)
 227 {
 228         if (type1->expression != type2->expression)
 229                 return false;
 230         if (type1->typeof_type != type2->typeof_type)
 231                 return false;
 232
 233         return true;
 234 }
 235
 236 static bool types_equal(const type_t *type1, const type_t *type2)
 237 {
 238         if (type1 == type2)
 239                 return true;
 240         if (type1->kind != type2->kind)
 241                 return false;
 242         if (type1->base.qualifiers != type2->base.qualifiers)
 243                 return false;
 244
 245         switch (type1->kind) {
 246         case TYPE_ERROR:
 247                 return true;
 248         case TYPE_ATOMIC:
 249         case TYPE_IMAGINARY:
 250         case TYPE_COMPLEX:
 251                 return atomic_types_equal(&type1->atomic, &type2->atomic);
 252         case TYPE_ENUM:
 253                 return enum_types_equal(&type1->enumt, &type2->enumt);
 254         case TYPE_COMPOUND_STRUCT:
 255         case TYPE_COMPOUND_UNION:
 256                 return compound_types_equal(&type1->compound, &type2->compound);
 257         case TYPE_FUNCTION:
 258                 return function_types_equal(&type1->function, &type2->function);
 259         case TYPE_POINTER:
 260                 return pointer_types_equal(&type1->pointer, &type2->pointer);
 261         case TYPE_REFERENCE:
 262                 return reference_types_equal(&type1->reference, &type2->reference);
 263         case TYPE_ARRAY:
 264                 return array_types_equal(&type1->array, &type2->array);
 265         case TYPE_TYPEOF:
 266                 return typeof_types_equal(&type1->typeoft, &type2->typeoft);
 267         case TYPE_TYPEDEF:
 268                 return typedef_types_equal(&type1->typedeft, &type2->typedeft);
 269         }
 270
 271         abort();
 272 }
 273
 274 #define HashSet                    type_hash_t
 275 #define ValueType                  type_t*
 276 #define NullValue                  NULL
 277 #define DeletedValue               ((type_t*)-1)
 278 #define Hash(this, key)            hash_type(key)
 279 #define KeysEqual(this,key1,key2)  types_equal(key1, key2)
 280 #define SetRangeEmpty(ptr,size)    memset(ptr, 0, (size) * sizeof(*(ptr)))
 281
 282 void _typehash_init(type_hash_t *hash);
 283 #define hashset_init             _typehash_init
 284 void _typehash_destroy(type_hash_t *hash);
 285 #define hashset_destroy          _typehash_destroy
 286 type_t *_typehash_insert(type_hash_t *hash, type_t *type);
 287 #define hashset_insert           _typehash_insert
 288 #define SCALAR_RETURN
 289
 290 #include "adt/hashset.c.inl"
 291
 292 static type_hash_t typehash;
 293
 294 void init_typehash(void)
 295 {
 296         _typehash_init(&typehash);
 297 }
 298
 299 void exit_typehash(void)
 300 {
 301         _typehash_destroy(&typehash);
 302 }
 303
 304 type_t *typehash_insert(type_t *type)
 305 {
 306         return _typehash_insert(&typehash, type);
 307 }