hphp/neo/neo_hash.c

   1 /*
   2  * Copyright 2003-2004 Brandon Long
   3  * All Rights Reserved.
   4  *
   5  * ClearSilver Templating System
   6  *
   7  * This code is made available under the terms of the ClearSilver License.
   8  * http://www.clearsilver.net/license.hdf
   9  *
  10  */
  11
  12 #include "cs_config.h"
  13
  14 #include <stdlib.h>
  15 #include <string.h>
  16
  17 #include "neo_misc.h"
  18 #include "neo_err.h"
  19 #include "neo_hash.h"
  20
  21 static NEOERR *_hash_resize(NE_HASH *hash);
  22 static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *hashv);
  23
  24 NEOERR *ne_hash_init (NE_HASH **hash, NE_HASH_FUNC hash_func, NE_COMP_FUNC comp_func)
  25 {
  26   NE_HASH *my_hash = NULL;
  27
  28   my_hash = (NE_HASH *) calloc(1, sizeof(NE_HASH));
  29   if (my_hash == NULL)
  30     return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASH");
  31
  32   my_hash->size = 256;
  33   my_hash->num = 0;
  34   my_hash->hash_func = hash_func;
  35   my_hash->comp_func = comp_func;
  36
  37   my_hash->nodes = (NE_HASHNODE **) calloc (my_hash->size, sizeof(NE_HASHNODE *));
  38   if (my_hash->nodes == NULL)
  39   {
  40     free(my_hash);
  41     return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASHNODES");
  42   }
  43
  44   *hash = my_hash;
  45
  46   return STATUS_OK;
  47 }
  48
  49 void ne_hash_destroy (NE_HASH **hash)
  50 {
  51   NE_HASH *my_hash;
  52   NE_HASHNODE *node, *next;
  53   int x;
  54
  55   if (hash == NULL || *hash == NULL)
  56     return;
  57
  58   my_hash = *hash;
  59
  60   for (x = 0; x < my_hash->size; x++)
  61   {
  62     node = my_hash->nodes[x];
  63     while (node)
  64     {
  65       next = node->next;
  66       free(node);
  67       node = next;
  68     }
  69   }
  70   free(my_hash->nodes);
  71   my_hash->nodes = NULL;
  72   free(my_hash);
  73   *hash = NULL;
  74 }
  75
  76 NEOERR *ne_hash_insert(NE_HASH *hash, void *key, void *value)
  77 {
  78   UINT32 hashv;
  79   NE_HASHNODE **node;
  80
  81   node = _hash_lookup_node(hash, key, &hashv);
  82
  83   if (*node)
  84   {
  85     (*node)->value = value;
  86   }
  87   else
  88   {
  89     *node = (NE_HASHNODE *) malloc(sizeof(NE_HASHNODE));
  90     if (node == NULL)
  91       return nerr_raise(NERR_NOMEM, "Unable to allocate NE_HASHNODE");
  92
  93     (*node)->hashv = hashv;
  94     (*node)->key = key;
  95     (*node)->value = value;
  96     (*node)->next = NULL;
  97   }
  98   hash->num++;
  99
 100   return _hash_resize(hash);
 101 }
 102
 103 void *ne_hash_lookup(NE_HASH *hash, void *key)
 104 {
 105   NE_HASHNODE *node;
 106
 107   node = *_hash_lookup_node(hash, key, NULL);
 108
 109   return (node) ? node->value : NULL;
 110 }
 111
 112 void *ne_hash_remove(NE_HASH *hash, void *key)
 113 {
 114   NE_HASHNODE **node, *rem;
 115   void *value = NULL;
 116
 117   node = _hash_lookup_node(hash, key, NULL);
 118   if (*node)
 119   {
 120     rem = *node;
 121     *node = rem->next;
 122     value = rem->value;
 123     free(rem);
 124     hash->num--;
 125   }
 126   return value;
 127 }
 128
 129 int ne_hash_has_key(NE_HASH *hash, void *key)
 130 {
 131   NE_HASHNODE *node;
 132
 133   node = *_hash_lookup_node(hash, key, NULL);
 134
 135   if (node) return 1;
 136   return 0;
 137 }
 138
 139 void *ne_hash_next(NE_HASH *hash, void **key)
 140 {
 141   NE_HASHNODE **node = 0;
 142   UINT32 hashv, bucket;
 143
 144   if (*key)
 145   {
 146     node = _hash_lookup_node(hash, key, NULL);
 147
 148     if (*node)
 149     {
 150       bucket = (*node)->hashv & (hash->size - 1);
 151     }
 152     else
 153     {
 154       hashv = hash->hash_func(*key);
 155       bucket = hashv & (hash->size - 1);
 156     }
 157   }
 158   else
 159   {
 160     bucket = 0;
 161   }
 162
 163   if (*node)
 164   {
 165     if ((*node)->next)
 166     {
 167       *key = (*node)->next->key;
 168       return (*node)->next->value;
 169     }
 170     bucket++;
 171   }
 172
 173   while (bucket < hash->size)
 174   {
 175     if (hash->nodes[bucket])
 176     {
 177       *key = hash->nodes[bucket]->key;
 178       return hash->nodes[bucket]->value;
 179     }
 180     bucket++;
 181   }
 182
 183   return NULL;
 184 }
 185
 186 static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *o_hashv)
 187 {
 188   UINT32 hashv, bucket;
 189   NE_HASHNODE **node;
 190
 191   hashv = hash->hash_func(key);
 192   if (o_hashv) *o_hashv = hashv;
 193   bucket = hashv & (hash->size - 1);
 194   /* ne_warn("Lookup %s %d %d", key, hashv, bucket); */
 195
 196   node = &(hash->nodes[bucket]);
 197
 198   if (hash->comp_func)
 199   {
 200     while (*node && !(hash->comp_func((*node)->key, key)))
 201       node = &(*node)->next;
 202   }
 203   else
 204   {
 205     /* No comp_func means we're doing pointer comparisons */
 206     while (*node && (*node)->key != key)
 207       node = &(*node)->next;
 208   }
 209
 210   /* ne_warn("Node %x", node); */
 211   return node;
 212 }
 213
 214 /* Ok, we're doing some weirdness here... */
 215 static NEOERR *_hash_resize(NE_HASH *hash)
 216 {
 217   NE_HASHNODE **new_nodes;
 218   NE_HASHNODE *entry, *prev;
 219   int x, next_bucket;
 220   int orig_size = hash->size;
 221   UINT32 hash_mask;
 222
 223   if (hash->size > hash->num)
 224     return STATUS_OK;
 225
 226   /* We always double in size */
 227   new_nodes = (NE_HASHNODE **) realloc (hash->nodes, (hash->size*2) * sizeof(NE_HASHNODE));
 228   if (new_nodes == NULL)
 229     return nerr_raise(NERR_NOMEM, "Unable to allocate memory to resize NE_HASH");
 230
 231   hash->nodes = new_nodes;
 232   orig_size = hash->size;
 233   hash->size = hash->size*2;
 234
 235   /* Initialize new parts */
 236   for (x = orig_size; x < hash->size; x++)
 237   {
 238     hash->nodes[x] = NULL;
 239   }
 240
 241   hash_mask = hash->size - 1;
 242
 243   for (x = 0; x < orig_size; x++)
 244   {
 245     prev = NULL;
 246     next_bucket = x + orig_size;
 247     for (entry = hash->nodes[x];
 248          entry;
 249          entry = prev ? prev->next : hash->nodes[x])
 250     {
 251       if ((entry->hashv & hash_mask) != x)
 252       {
 253         if (prev)
 254         {
 255           prev->next = entry->next;
 256         }
 257         else
 258         {
 259           hash->nodes[x] = entry->next;
 260         }
 261         entry->next = hash->nodes[next_bucket];
 262         hash->nodes[next_bucket] = entry;
 263       }
 264       else
 265       {
 266         prev = entry;
 267       }
 268     }
 269   }
 270
 271   return STATUS_OK;
 272 }
 273
 274 int ne_hash_str_comp(const void *a, const void *b)
 275 {
 276   return !strcmp((const char *)a, (const char *)b);
 277 }
 278
 279 UINT32 ne_hash_str_hash(const void *a)
 280 {
 281   return ne_crc((unsigned char *)a, strlen((const char *)a));
 282 }
 283
 284 int ne_hash_int_comp(const void *a, const void *b)
 285 {
 286   if (a == b) return 1;
 287   return 0;
 288 }
 289
 290 UINT32 ne_hash_int_hash(const void *a)
 291 {
 292   return (UINT32)(long)(a);
 293 }