nsz Git - cparser/blob - type_hash.c

   1 #include <config.h>
   2
   3 #include <stdbool.h>
   4
   5 #include "type_hash.h"
   6
   7 #include "adt/error.h"
   8 #include "type_t.h"
   9
  10 #include <assert.h>
  11
  12 #define HashSet         type_hash_t
  13 #define HashSetIterator type_hash_iterator_t
  14 #define ValueType       type_t*
  15 #include "adt/hashset.h"
  16 #undef ValueType
  17 #undef HashSetIterator
  18 #undef HashSet
  19
  20 /* TODO: ^= is a bad way of combining hashes since most addresses are very
  21  * similar */
  22
  23 static unsigned hash_ptr(const void *ptr)
  24 {
  25         unsigned ptr_int = ((char*) ptr - (char*) NULL);
  26         return ptr_int >> 3;
  27 }
  28
  29 static unsigned hash_atomic_type(const type_t *type)
  30 {
  31         unsigned some_prime = 27644437;
  32         unsigned result     = type->v.atomic_type.atype * some_prime;
  33
  34         return result;
  35 }
  36
  37 static unsigned hash_pointer_type(const type_t *type)
  38 {
  39         return hash_ptr(type->v.pointer_type.points_to);
  40 }
  41
  42 static unsigned hash_array_type(const type_t *type)
  43 {
  44         return hash_ptr(type->v.array_type.element_type);
  45 }
  46
  47 static unsigned hash_compound_type(const type_t *type)
  48 {
  49         return hash_ptr(type->v.compound_type.declaration);
  50 }
  51
  52 static unsigned hash_type(const type_t *type);
  53
  54 static unsigned hash_function_type(const type_t *type)
  55 {
  56         unsigned result = hash_ptr(type->v.function_type.result_type);
  57
  58         function_parameter_t *parameter = type->v.function_type.parameters;
  59         while(parameter != NULL) {
  60                 result   ^= hash_ptr(parameter->type);
  61                 parameter = parameter->next;
  62         }
  63
  64         return result;
  65 }
  66
  67 static unsigned hash_enum_type(const type_t *type)
  68 {
  69         return hash_ptr(type->v.enum_type.declaration);
  70 }
  71
  72 static unsigned hash_typeof_type(const type_t *type)
  73 {
  74         unsigned result = hash_ptr(type->v.typeof_type.expression);
  75         result         ^= hash_ptr(type->v.typeof_type.typeof_type);
  76
  77         return result;
  78 }
  79
  80 static unsigned hash_type(const type_t *type)
  81 {
  82         unsigned hash = 0;
  83
  84         switch(type->type) {
  85         case TYPE_INVALID:
  86                 panic("internalizing void or invalid types not possible");
  87                 return 0;
  88         case TYPE_ATOMIC:
  89                 hash = hash_atomic_type(type);
  90                 break;
  91         case TYPE_ENUM:
  92                 hash = hash_enum_type(type);
  93                 break;
  94         case TYPE_COMPOUND_STRUCT:
  95         case TYPE_COMPOUND_UNION:
  96                 hash = hash_compound_type(type);
  97                 break;
  98         case TYPE_FUNCTION:
  99                 hash = hash_function_type(type);
 100                 break;
 101         case TYPE_POINTER:
 102                 hash = hash_pointer_type(type);
 103                 break;
 104         case TYPE_ARRAY:
 105                 hash = hash_array_type(type);
 106                 break;
 107         case TYPE_BUILTIN:
 108                 hash = hash_ptr(type->v.builtin_type.symbol);
 109                 break;
 110         case TYPE_TYPEDEF:
 111                 hash = hash_ptr(type->v.typedef_type.declaration);
 112                 break;
 113         case TYPE_TYPEOF:
 114                 hash = hash_typeof_type(type);
 115                 break;
 116         }
 117
 118         unsigned some_prime = 99991;
 119         hash ^= some_prime * type->qualifiers;
 120
 121         return hash;
 122 }
 123
 124 static bool atomic_types_equal(const type_t *type1,
 125                                const type_t *type2)
 126 {
 127         return type1->v.atomic_type.atype == type2->v.atomic_type.atype;
 128 }
 129
 130 static bool function_types_equal(const type_t *type1,
 131                                  const type_t *type2)
 132 {
 133         if(type1->v.function_type.result_type != type2->v.function_type.result_type)
 134                 return false;
 135         if(type1->v.function_type.variadic != type2->v.function_type.variadic)
 136                 return false;
 137         if(type1->v.function_type.unspecified_parameters !=
 138            type2->v.function_type.unspecified_parameters)
 139                 return false;
 140
 141         function_parameter_t *param1 = type1->v.function_type.parameters;
 142         function_parameter_t *param2 = type2->v.function_type.parameters;
 143         while(param1 != NULL && param2 != NULL) {
 144                 if(param1->type != param2->type)
 145                         return false;
 146                 param1 = param1->next;
 147                 param2 = param2->next;
 148         }
 149         if(param1 != NULL || param2 != NULL)
 150                 return false;
 151
 152         return true;
 153 }
 154
 155 static bool pointer_types_equal(const type_t *type1,
 156                                 const type_t *type2)
 157 {
 158         return type1->v.pointer_type.points_to == type2->v.pointer_type.points_to;
 159 }
 160
 161 static bool array_types_equal(const type_t *type1,
 162                               const type_t *type2)
 163 {
 164         if(type1->v.array_type.element_type != type2->v.array_type.element_type)
 165                 return false;
 166         if(type1->v.array_type.is_variable != type2->v.array_type.is_variable)
 167                 return false;
 168         if(type1->v.array_type.is_static != type2->v.array_type.is_static)
 169                 return false;
 170         /* TODO: compare expressions for equality... */
 171         if(type1->v.array_type.size != type2->v.array_type.size)
 172                 return false;
 173
 174         return true;
 175 }
 176
 177 static bool builtin_types_equal(const type_t *type1,
 178                                 const type_t *type2)
 179 {
 180         return type1->v.builtin_type.symbol == type2->v.builtin_type.symbol;
 181 }
 182
 183 static bool compound_types_equal(const type_t *type1,
 184                                  const type_t *type2)
 185 {
 186         return type1->v.compound_type.declaration == type2->v.compound_type.declaration;
 187 }
 188
 189 static bool enum_types_equal(const type_t *type1,
 190                              const type_t *type2)
 191 {
 192         return type1->v.enum_type.declaration == type2->v.enum_type.declaration;
 193 }
 194
 195 static bool typedef_types_equal(const type_t *type1,
 196                                 const type_t *type2)
 197 {
 198         return type1->v.typedef_type.declaration == type2->v.typedef_type.declaration;
 199 }
 200
 201 static bool typeof_types_equal(const type_t *type1,
 202                                const type_t *type2)
 203 {
 204         if(type1->v.typeof_type.expression != type2->v.typeof_type.expression)
 205                 return false;
 206         if(type1->v.typeof_type.typeof_type != type2->v.typeof_type.typeof_type)
 207                 return false;
 208
 209         return true;
 210 }
 211
 212 static bool types_equal(const type_t *type1, const type_t *type2)
 213 {
 214         if(type1 == type2)
 215                 return true;
 216         if(type1->type != type2->type)
 217                 return false;
 218         if(type1->qualifiers != type2->qualifiers)
 219                 return false;
 220
 221         switch(type1->type) {
 222         case TYPE_INVALID:
 223                 return false;
 224         case TYPE_ATOMIC:
 225                 return atomic_types_equal(type1, type2);
 226         case TYPE_ENUM:
 227                 return enum_types_equal(type1, type2);
 228         case TYPE_COMPOUND_STRUCT:
 229         case TYPE_COMPOUND_UNION:
 230                 return compound_types_equal(type1, type2);
 231         case TYPE_FUNCTION:
 232                 return function_types_equal(type1, type2);
 233         case TYPE_POINTER:
 234                 return pointer_types_equal(type1, type2);
 235         case TYPE_ARRAY:
 236                 return array_types_equal(type1, type2);
 237         case TYPE_BUILTIN:
 238                 return builtin_types_equal(type1, type2);
 239         case TYPE_TYPEOF:
 240                 return typeof_types_equal(type1, type2);
 241         case TYPE_TYPEDEF:
 242                 return typedef_types_equal(type1, type2);
 243         }
 244
 245         abort();
 246 }
 247
 248 #define HashSet                    type_hash_t
 249 #define HashSetIterator            type_hash_iterator_t
 250 #define ValueType                  type_t*
 251 #define NullValue                  NULL
 252 #define DeletedValue               ((type_t*)-1)
 253 #define Hash(this, key)            hash_type(key)
 254 #define KeysEqual(this,key1,key2)  types_equal(key1, key2)
 255 #define SetRangeEmpty(ptr,size)    memset(ptr, 0, (size) * sizeof(*(ptr)))
 256
 257 #define hashset_init             _typehash_init
 258 #define hashset_init_size        _typehash_init_size
 259 #define hashset_destroy          _typehash_destroy
 260 #define hashset_insert           _typehash_insert
 261 #define hashset_remove           typehash_remove
 262 #define hashset_find             typehash_find
 263 #define hashset_size             typehash_size
 264 #define hashset_iterator_init    typehash_iterator_init
 265 #define hashset_iterator_next    typehash_iterator_next
 266 #define hashset_remove_iterator  typehash_remove_iterator
 267
 268 #include "adt/hashset.c"
 269
 270 static type_hash_t typehash;
 271
 272 void init_typehash(void)
 273 {
 274         _typehash_init(&typehash);
 275 }
 276
 277 void exit_typehash(void)
 278 {
 279         _typehash_destroy(&typehash);
 280 }
 281
 282 type_t *typehash_insert(type_t *type)
 283 {
 284         return _typehash_insert(&typehash, type);
 285 }