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