openblt

a hobby OS from the late 90s
git clone http://frotz.net/git/openblt.git
Log | Files | Refs | LICENSE

hash.c (5983B)

      1 /* $Id: //depot/blt/lib/libblt/hash.c#3 $
      2 **
      3 ** Copyright 1999 Sidney Cammeresi.
      4 ** All rights reserved.
      5 ** 
      6 ** Redistribution and use in source and binary forms, with or without
      7 ** modification, are permitted provided that the following conditions
      8 ** are met:
      9 ** 
     10 ** 1. Redistributions of source code must retain the above copyright notice,
     11 **    this list of conditions and the following disclaimer.
     12 ** 
     13 ** 2. Redistributions in binary form must reproduce the above copyright
     14 **    notice, this list of conditions and the following disclaimer in the
     15 **    documentation and/or other materials provided with the distribution.
     16 ** 
     17 ** 3. The name of the author may not be used to endorse or promote products
     18 **    derived from this software without specific prior written permission.
     19 ** 
     20 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS' AND ANY EXPRESS OR IMPLIED
     21 ** WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
     22 ** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
     23 ** NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     24 ** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
     25 ** TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     26 ** PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
     27 ** LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     28 ** NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     29 ** SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     30 */
     31 
     32 /*
     33  * these algorithms are based on knuth's algorithm 6.4d, as described in
     34  * vol. 3, p. 529 of taocp.
     35  *
     36  * XXX - keys must be unique!
     37  */
     38 
     39 /*
     40 
     41 the primes were computed by using the following program:
     42 
     43 int main (void)
     44 {
     45     unsigned int i, j, good, last;
     46 
     47     for (i = 17, last = 0; i < 65536 * 16384 - 1; i++)
     48         {   
     49             for (j = 2, good = 1; (j <= floor (sqrt ((double) i))) && good; j++)
     50                 if (!(i % j))
     51                     good = 0;
     52             if (good)
     53                 {
     54                     if (last == i - 2)
     55                         {
     56                             printf ("%d %d\n", last, i);
     57                             i *= 2;
     58                         }
     59                     last = i;
     60                 }
     61         }
     62 
     63     return 0;
     64 }
     65 
     66 */
     67 
     68 #include <stddef.h>
     69 #include <stdlib.h>
     70 #include <blt/hash.h>
     71 
     72 static unsigned int table_size[] = { 7, 19, 43, 103, 229, 463, 1021, 2083, 4219,
     73 	8539, 17191, 34471, 69031, 138079, 276373, 552751, 1105549, 2211259,
     74 	4422619, 8845453, 17691043, 35382091, 70764259, 141528559, 283057213,
     75 	566115259 };
     76 
     77 static int hash (int key, int size);
     78 static int rehash (int key, int size);
     79 static void hashtable_rebuild (hashtable_t *t, int dir);
     80 
     81 static int hash (int key, int size)
     82 {
     83 	return key % table_size[size];
     84 }
     85 
     86 static int rehash (int key, int size)
     87 {
     88 	return 1 + (key % (table_size[size] - 2));
     89 }
     90 
     91 hashtable_t *hashtable_new (float max_load)
     92 {
     93 	int i;
     94 	hashtable_t *t;
     95 
     96 	t = (hashtable_t *) malloc (sizeof (hashtable_t));
     97 	t->size_index = 0;
     98 	t->used = t->dirty = 0;
     99 	t->max_load = max_load;
    100 	t->table = (hashnode_t *) malloc (sizeof (hashnode_t) * *table_size);
    101 	for (i = 0; i < table_size[t->size_index]; i++)
    102 		t->table[i].valid = t->table[i].dirty = 0;
    103 	return t;
    104 }
    105 
    106 void hashtable_del (hashtable_t *t)
    107 {
    108 	free (t->table);
    109 }
    110 
    111 void hashtable_insert (hashtable_t *t, int key, void *data, int dsize)
    112 {
    113 	int i, c;
    114 
    115 	if (t->used > (t->max_load * table_size[t->size_index]))
    116 		hashtable_rebuild (t, 1);
    117 
    118 	i = hash (key, t->size_index);
    119 	if (t->table[i].valid)
    120 		do
    121 			{
    122 				c = rehash (key, t->size_index);
    123 				i -= c;
    124 				if (i < 0)
    125 					i += table_size[t->size_index];
    126 			}
    127 		while (t->table[i].valid && !t->table[i].dirty);
    128 	if (!t->table[i].dirty)
    129 		t->used++;
    130 	t->table[i].valid = 1;
    131 	t->table[i].dirty = 0;
    132 	t->table[i].key = key;
    133 	t->table[i].dsize = dsize;
    134 	t->table[i].data = data;
    135 }
    136 
    137 static void hashtable_rebuild (hashtable_t *t, int dir)
    138 {
    139 	int i, old_index;
    140 	hashnode_t *old;
    141 
    142 	old = t->table;
    143 	old_index = t->size_index;
    144 	switch (dir)
    145 		{
    146 			case -1:
    147 				t->size_index = t->size_index ? t->size_index - 1 : 0;
    148 				break;
    149 			case 0:
    150 				break;
    151 			case 1:
    152 				t->size_index++;
    153 				break;
    154 			default:
    155 				return;
    156 		}
    157 
    158 	t->used = t->dirty = 0;
    159 	t->table = (hashnode_t *) malloc (sizeof (hashnode_t) *
    160 		table_size[t->size_index]);
    161 	for (i = 0; i < table_size[t->size_index]; i++)
    162 		t->table[i].valid = t->table[i].dirty = 0;
    163 	for (i = 0; i < table_size[old_index]; i++)
    164 		if (old[i].valid && !old[i].dirty)
    165 			hashtable_insert (t, old[i].key, old[i].data, old[i].dsize);
    166 	free (old);
    167 }
    168 
    169 void *hashtable_lookup (hashtable_t *t, int key, int *dsize)
    170 {
    171 	int i, c;
    172 
    173 	i = hash (key, t->size_index);
    174 	while (t->table[i].valid)
    175 		{
    176 			if ((t->table[i].key == key) && !t->table[i].dirty)
    177 				{
    178 					if (dsize != NULL)
    179 						*dsize = t->table[i].dsize;
    180 					return t->table[i].data;
    181 				}
    182 			c = rehash (key, t->size_index);
    183 			i -= c;
    184 			if (i < 0)
    185 				i += table_size[t->size_index];
    186 		}
    187 	if (dsize != NULL)
    188 		*dsize = 0;
    189 	return NULL;
    190 }
    191 
    192 void *hashtable_remove (hashtable_t *t, int key, int *dsize)
    193 {
    194 	int i, c;
    195 	void *temp;
    196 
    197 	i = hash (key, t->size_index);
    198 	while (t->table[i].valid)
    199 		{
    200 			if ((t->table[i].key == key) && !t->table[i].dirty)
    201 				{
    202 					if (dsize != NULL)
    203 						*dsize = t->table[i].dsize;
    204 					temp = t->table[i].data;
    205 					t->table[i].dirty = 1;
    206 					t->dirty++;
    207 					if ((t->dirty > ((1 - t->max_load) *
    208 							table_size[t->size_index])) && t->size_index)
    209 						hashtable_rebuild (t, -1);
    210 					return temp;
    211 				}
    212 			c = rehash (key, t->size_index);
    213 			i -= c;
    214 			if (i < 0)
    215 				i += table_size[t->size_index];
    216 		}
    217 	if (dsize != NULL)
    218 		*dsize = 0;
    219 	return NULL;
    220 }
    221 
    222 /*
    223 void hashtable_print (hashtable_t *t)
    224 {
    225 	int i;
    226 
    227 	printf ("used:  %d\ndirty: %d\n\n", t->used, t->dirty);
    228 	for (i = 0; i < table_size[t->size_index]; i++)
    229 		printf ("%3d: %d %d %3d %3d %3d\n", i, t->table[i].valid,
    230 			t->table[i].dirty, t->table[i].key,
    231 			t->table[i].data, t->table[i].dsize);
    232 }
    233 */
    234