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 static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *o_hashv)
 130 {
 131   UINT32 hashv, bucket;
 132   NE_HASHNODE **node;
 133
 134   hashv = hash->hash_func(key);
 135   if (o_hashv) *o_hashv = hashv;
 136   bucket = hashv & (hash->size - 1);
 137   /* ne_warn("Lookup %s %d %d", key, hashv, bucket); */
 138
 139   node = &(hash->nodes[bucket]);
 140
 141   if (hash->comp_func)
 142   {
 143     while (*node && !(hash->comp_func((*node)->key, key)))
 144       node = &(*node)->next;
 145   }
 146   else
 147   {
 148     /* No comp_func means we're doing pointer comparisons */
 149     while (*node && (*node)->key != key)
 150       node = &(*node)->next;
 151   }
 152
 153   /* ne_warn("Node %x", node); */
 154   return node;
 155 }
 156
 157 /* Ok, we're doing some weirdness here... */
 158 static NEOERR *_hash_resize(NE_HASH *hash)
 159 {
 160   NE_HASHNODE **new_nodes;
 161   NE_HASHNODE *entry, *prev;
 162   int x, next_bucket;
 163   int orig_size = hash->size;
 164   UINT32 hash_mask;
 165
 166   if (hash->size > hash->num)
 167     return STATUS_OK;
 168
 169   /* We always double in size */
 170   new_nodes = (NE_HASHNODE **) realloc (hash->nodes, (hash->size*2) * sizeof(NE_HASHNODE *));
 171   if (new_nodes == NULL)
 172     return nerr_raise(NERR_NOMEM, "Unable to allocate memory to resize NE_HASH");
 173
 174   hash->nodes = new_nodes;
 175   orig_size = hash->size;
 176   hash->size = hash->size*2;
 177
 178   /* Initialize new parts */
 179   for (x = orig_size; x < hash->size; x++)
 180   {
 181     hash->nodes[x] = NULL;
 182   }
 183
 184   hash_mask = hash->size - 1;
 185
 186   for (x = 0; x < orig_size; x++)
 187   {
 188     prev = NULL;
 189     next_bucket = x + orig_size;
 190     for (entry = hash->nodes[x];
 191          entry;
 192          entry = prev ? prev->next : hash->nodes[x])
 193     {
 194       if ((entry->hashv & hash_mask) != x)
 195       {
 196         if (prev)
 197         {
 198           prev->next = entry->next;
 199         }
 200         else
 201         {
 202           hash->nodes[x] = entry->next;
 203         }
 204         entry->next = hash->nodes[next_bucket];
 205         hash->nodes[next_bucket] = entry;
 206       }
 207       else
 208       {
 209         prev = entry;
 210       }
 211     }
 212   }
 213
 214   return STATUS_OK;
 215 }