nsz Git - cparser/blob - type_hash.c

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