wtab.c

00001 #include <stdlib.h>
00002 #include "wtab.h"
00003 
00004 /*
00005  * wtab.c - a hash table implementation designed for use as node link storage
00006  * in cp_trie objects. performance benefits compared to cp_hashtable result 
00007  * from cutting the overhead of dereferencing generic hash and compare 
00008  * functions and saving on checks for collection mode.
00009  */
00010 
00011 /* an array of prime numbers for hash table sizes */
00012 static int sizes[] = {   1,   3,   5,   7,  11,  19,  29,  37,  47,  59,
00013                         71,  89, 107, 127, 151, 181, 211, 239, 257, 281 };
00014 
00015 static int sizes_len = 20;
00016 
00017 #define MIN_FILL_FACTOR 30
00018 #define MAX_FILL_FACTOR 100
00019 #define DOWNSIZE_RATIO   2
00020 
00021 static unsigned long mt_abs(long x) 
00022 {
00023     if (x < 0) return -x;
00024     return x;
00025 }
00026 
00027 /*
00028  * performs a binary search on the sizes array to choose the first entry larger
00029  * than the requested size. the sizes array is initialized with prime numbers.
00030  */
00031 static int choose_size(int size)
00032 {
00033     int new_size;
00034 
00035     if (sizes[sizes_len - 1] < size)
00036     {
00037         for (new_size = sizes[sizes_len - 1];
00038              new_size < size;
00039              new_size = new_size * 2 + 1);
00040     }
00041     else
00042     {
00043         int min = -1;
00044         int max = sizes_len - 1;
00045         int pos;
00046 
00047         while (max > min + 1)
00048         {
00049             pos = (max + min + 1) / 2;
00050             if (sizes[pos] < size)
00051                 min = pos;
00052             else
00053                 max = pos;
00054         }
00055 
00056         new_size = sizes[max];
00057     }
00058 
00059     return new_size;
00060 }
00061 
00062 static void resize_table(wtab *t, int size)
00063 {
00064     wtab_node **table = (wtab_node **) calloc(size, sizeof(wtab_node *));
00065 
00066     if (table)
00067     {
00068         int i;
00069         wtab_node *ni;
00070         wtab_node **nf;
00071         for (i = 0; i < t->size; i++)
00072         {
00073             ni = t->table[i];
00074             while (ni)
00075             {
00076                 nf = &table[ni->key % size];
00077                 while (*nf) nf = &(*nf)->next;
00078                 *nf = ni;
00079                 ni = ni->next;
00080                 (*nf)->next = NULL;
00081             }
00082         }
00083 
00084         free(t->table);
00085         t->table = table;
00086         t->size = size;
00087     }
00088 }
00089 
00090 wtab_node *wtab_node_new(wchar_t key, void *value, void *attr)
00091 {
00092     wtab_node *node = calloc(1, sizeof(wtab_node));
00093     if (node)
00094     {
00095         node->key = key;
00096         node->value = value;
00097         node->attr = attr;
00098     }
00099 
00100     return node;
00101 }
00102 
00103 
00104 wtab *wtab_new(int size)
00105 {
00106     wtab *t = calloc(1, sizeof(wtab));
00107     if (t)
00108     {
00109         t->size = choose_size(size);
00110         t->table = calloc(t->size, sizeof(wtab_node *));
00111         if (t->table == NULL)
00112         {
00113             free(t);
00114             t = NULL;
00115         }
00116     }
00117 
00118     return t;
00119 }
00120 
00121 /*
00122  * the 'owner' pointer is used by cp_trie deletion code to pass a pointer to the 
00123  * trie being deleted for access to mode settings etc.
00124  */
00125 void wtab_delete_custom(wtab *t, 
00126                         void *owner, 
00127                         wtab_dtr dtr)
00128 {
00129     while (t->size--)
00130     {
00131         wtab_node *curr = t->table[t->size];
00132         wtab_node *tmp;
00133         while (curr)
00134         {
00135             tmp = curr;
00136             curr = curr->next;
00137             (*dtr)(owner, tmp);
00138             free(tmp);
00139         }
00140     }
00141 
00142     free(t->table);
00143     free(t);
00144 }
00145 
00146 void wtab_delete(wtab *t)
00147 {
00148     while (t->size--)
00149     {
00150         wtab_node *curr = t->table[t->size];
00151         wtab_node *tmp;
00152         while (curr)
00153         {
00154             tmp = curr;
00155             curr = curr->next;
00156             free(tmp);
00157         }
00158     }
00159 
00160     free(t->table);
00161     free(t);
00162 }
00163 
00164 /*
00165  * wtab doesn't support collection modes. inserting a new value for an 
00166  * key already present silently replaces the existing value.
00167  */
00168 wtab_node *wtab_put(wtab *t, wchar_t key, void *value, void *attr)
00169 {
00170     wtab_node **loc;
00171         
00172     if ((t->items + 1) * 100 > t->size * MAX_FILL_FACTOR) 
00173         resize_table(t, choose_size(t->size + 1));
00174     
00175     loc = &t->table[key % t->size];
00176     while (*loc && (*loc)->key != key) loc = &(*loc)->next;
00177 
00178     if (*loc == NULL)
00179     {
00180         t->items++;
00181         *loc = wtab_node_new(key, value, attr);
00182     }
00183     else
00184     {
00185         (*loc)->value = value; /* replace */
00186         if ((*loc)->attr) free((*loc)->attr);
00187         (*loc)->attr = attr;
00188     }
00189 
00190     return *loc;
00191 }
00192 
00193 wtab_node *wtab_get(wtab *t, wchar_t key)
00194 {
00195     wtab_node *node = t->table[key % t->size];
00196 
00197     while (node && key != node->key)
00198         node = node->next;
00199 
00200     return node;
00201 }
00202 
00203 /*
00204  * wtab_remove performs a table resize if table density drops below the 'fill
00205  * ratio'. this is done to keep cp_trie memory usage low.
00206  */
00207 void *wtab_remove(wtab *t, wchar_t key)
00208 {
00209     wtab_node **node;
00210     void *res = NULL;
00211 
00212     node = &t->table[key % t->size];
00213 
00214     while ((*node) && key != (*node)->key)
00215         node = &(*node)->next;
00216 
00217     if (*node)
00218     {
00219         wtab_node *rm = *node;
00220         *node = rm->next; /* unlink */
00221         res = rm->value;
00222         if (rm->attr) free(rm->attr);
00223         free(rm);
00224 
00225         t->items--;
00226     }
00227 
00228     if (t->items > 0 && t->items * 100 < t->size * MIN_FILL_FACTOR)
00229         resize_table(t, choose_size(t->size / DOWNSIZE_RATIO));
00230 
00231     return res;
00232 }
00233 
00234 int wtab_count(wtab *t)
00235 {
00236     return t->items;
00237 }
00238 
00239 int wtab_callback(wtab *t, cp_callback_fn fn, void *prm)
00240 {
00241     int i;
00242     wtab_node *n;
00243     int count = 0;
00244     int res = 0;
00245 
00246     for (i = 0; i < t->size && count < t->items; i++)
00247     {
00248         n = t->table[i];
00249         while (n)
00250         {
00251             count++;
00252             if ((res = (*fn)(n, prm)) != 0) return res;
00253             n = n->next;
00254         }
00255     }
00256 
00257     return 0;
00258 }
00259 

Generated on Mon Dec 5 23:00:22 2011 for cprops by  doxygen 1.4.7