hash-table.c

   1 #ifndef CGPERF_HASH_TABLE_C
   2 #define CGPERF_HASH_TABLE_C
   3 #include <stdbool.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #include <stdio.h>
   7 #include "c_fixing.h"
   8 #include "keyword.h"
   9 #include "hash-table.h"
  10 #include "hash.h"
  11 /*------------------------------------------------------------------------------------------------*/
  12 #include "namespace/hash-table.h"
  13 #include "namespace/keyword.h"
  14 #include "namespace/hash.h"
  15 /*------------------------------------------------------------------------------------------------*/
  16 /*{{{ ht_new */
  17 /*
  18  * We make the size of the hash table a power of 2. This allows for two optimizations: It eliminates
  19  * the modulo instruction, and allows for an easy secondary hashing function.
  20  */
  21 static struct Hash_Table *ht_new(u32 size, bool ignore_length)
  22 {
  23         struct Hash_Table *t;
  24         u32 shift;
  25
  26         t = calloc(1, sizeof(*t));
  27         t->ignore_length = ignore_length;
  28
  29         /* there need to be enough spare entries */
  30         size = size * (u32)ht_size_factor;
  31
  32         /* find smallest power of 2 that is >= size */
  33         shift = 0;
  34         if ((size >> 16) > 0) {
  35                 size = size >> 16;
  36                 shift += 16;
  37         }
  38         if ((size >> 8) > 0) {
  39                 size = size >> 8;
  40                 shift += 8;
  41         }
  42         if ((size >> 4) > 0) {
  43                 size = size >> 4;
  44                 shift += 4;
  45         }
  46         if ((size >> 2) > 0) {
  47                 size = size >> 2;
  48                 shift += 2;
  49         }
  50         if ((size >> 1) > 0) {
  51                 size = size >> 1;
  52                 shift += 1;
  53         }
  54         t->log_size = shift;
  55         t->size = 1 << shift;
  56
  57         t->table = calloc(t->size, sizeof(*(t->table)));
  58         return t;
  59 }/*}}}*/
  60 /*{{{ ht_del */
  61 static void ht_del(struct Hash_Table *t)
  62 {
  63         free(t->table);
  64         free(t);
  65 }/*}}}*/
  66 /*{{{ ht_insert */
  67 /*
  68  * Attempts to insert ITEM in the table. If there is already an equal entry in it, returns it.
  69  * Otherwise inserts ITEM and returns NULL.
  70  */
  71 static struct Keyword *ht_insert(struct Hash_Table *t, struct Keyword *item)
  72 {
  73         u32 hash_val;
  74         u32 probe;
  75         u32 increment;
  76
  77         hash_val = hashpjw((u8*)item->selchars, item->selchars_length * sizeof(u32));
  78         probe = hash_val & (t->size - 1);
  79         increment = (((hash_val >> t->log_size) ^ (t->ignore_length ?  0 : item->allchars_length))
  80                                                                                         << 1) + 1;
  81         /*
  82          * note that because _size is a power of 2 and increment is odd, we have
  83          * gcd(increment,_size) = 1, which guarantees that we'll find an empty entry during the loop
  84          */
  85         loop {
  86                 if (t->table[probe] == 0)
  87                         break;
  88                 if (ht_equal(t, t->table[probe], item))
  89                         return t->table[probe];
  90                 ++(t->collisions);
  91                 probe = (probe + increment) & (t->size - 1);
  92         }
  93         t->table[probe] = item;
  94         return 0;
  95 }/*}}}*/
  96 /*{{{ ht_equal */
  97 static bool ht_equal(struct Hash_Table *t, struct Keyword *item1, struct Keyword *item2)
  98 {
  99         return item1->selchars_length == item2->selchars_length
 100                 && memcmp(item1->selchars, item2->selchars, item1->selchars_length * sizeof(u32))
 101                                                                                         == 0
 102                 && (t->ignore_length || item1->allchars_length == item2->allchars_length);
 103 }/*}}}*/
 104 /*{{{ ht_dump */
 105 static void ht_dump(struct Hash_Table *t)
 106 {
 107         s32 field_width;
 108         s32 i;
 109
 110         field_width = 0;
 111         {
 112                 s32 i;
 113
 114                 i = t->size - 1;
 115                 loop {
 116                         if (i < 0)
 117                                 break;
 118                         if (t->table[i] != 0)
 119                                 if (field_width < t->table[i]->selchars_length)
 120                                         field_width = t->table[i]->selchars_length;
 121                         i--;
 122                 }
 123         }
 124         fprintf(stderr, "\ndumping the hash table\ntotal available table slots = %d, total bytes = %d, total collisions = %d\nlocation, %*s, keyword\n", t->size, t->size * (u32)(sizeof(*(t->table))), t->collisions, field_width, "keysig");
 125
 126         i = t->size - 1;
 127         loop {
 128                 if (i < 0)
 129                         break;
 130                 if (t->table[i] != 0) {
 131                         s32 j;
 132
 133                         fprintf(stderr, "%8d, ", i);
 134                         if (field_width > t->table[i]->selchars_length)
 135                                 fprintf(stderr, "%*s", field_width - t->table[i]->selchars_length, "");
 136                         j = 0;
 137                         loop {
 138                                 if (j >= t->table[i]->selchars_length)
 139                                         break;
 140                                 putc(t->table[i]->selchars[j], stderr);
 141                                 ++j;
 142                         }
 143                         fprintf(stderr, ", %.*s\n", t->table[i]->allchars_length, t->table[i]->allchars);
 144                 }
 145                 i--;
 146         }
 147         fprintf(stderr, "\nend dumping hash table\n\n");
 148 }/*}}}*/
 149 /*------------------------------------------------------------------------------------------------*/
 150 #define EPILOG
 151 #include "namespace/hash-table.h"
 152 #include "namespace/keyword.h"
 153 #include "namespace/hash.h"
 154 #undef EPILOG
 155 /*------------------------------------------------------------------------------------------------*/
 156 #endif