1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
|
static const char rcsid[] = "$Id: hsearch.c,v 1.12 2004/04/30 17:00:58 will Exp $";
/**
* hsearch.c --- PD simple implementation of System V hsearch(3c) routine
* It is by Arnold Robbins (arnold@skeeve.atl.ga.us) -- thanks!
**/
#include "localsys.h"
#include "stdio.h"
#include "hsearch.h"
static ELEMENT **Table = NULL; /* pointer to dynamicly allocated table */
static int Num_elem = -1; /* number of elements */
static int hashit();
/*
* table of primes just below 2^n, n=2..31 for use in finding the right prime
* number to be the table size. this table may be generally useful...
*/
static unsigned int primetab[] = {
/*
* comment these out, so that table will always have a minimal size...
3, 7, 13, 31, 61,
*/
127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071,
262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393,
67108859, 134217689, 268435399, 536870909, 1073741789, 2147483647
};
/* hcreate --- create a hash table at least how_many big */
int hcreate (how_many)
register unsigned int how_many;
{
register int i, j;
/*
* find first prime number >= how_many, and use it for table size
*/
if (Num_elem != -1) /* already a table out there */
hdestroy(); /* remove it */
j = sizeof (primetab) / sizeof (primetab[0]);
for (i = 0; i < j; i++)
if (primetab[i] >= how_many)
break;
if (i >= j) /* how_many bigger than any prime we have, use it */
Num_elem = how_many;
else
Num_elem = primetab[i];
if ((Table = (ELEMENT **) calloc ((unsigned) Num_elem, sizeof (ELEMENT *))) == NULL)
return (0);
else
return (1);
}
/* idestroy --- destroy a single element on a chain */
static void idestroy (elem)
ELEMENT *elem;
{
if (elem != NULL)
{
idestroy (elem->next);
free ((char *) elem);
}
}
/* hdestroy --- nuke the existing hash table */
void hdestroy()
{
register unsigned int i;
if (Table != NULL)
{
/* free all the chains */
for (i = 0; i < Num_elem; i++)
idestroy (Table[i]);
/* now the table itself */
free ((char *) Table);
Num_elem = -1;
Table = NULL;
}
}
/* hsearch --- lookup or enter an item in the hash table */
ENTRY *hsearch (entry, action)
ENTRY entry;
ACTION action;
{
ELEMENT e;
ELEMENT *ep = NULL;
ELEMENT *ep2 = NULL;
int hindex;
if (Table == NULL)
return (NULL);
hindex = hashit (entry.key);
if (Table[hindex] == NULL) /* nothing there */
{
if (action == FIND)
return (NULL);
else
{
/* add it to the table */
e.item = entry;
e.next = NULL;
if ((Table[hindex] = (ELEMENT *) calloc (1, sizeof (ELEMENT))) == NULL)
return (NULL);
*Table[hindex] = e;
return (& Table[hindex]->item);
}
}
else
{
/* something in bucket, see if already on chain */
for (ep = Table[hindex]; ep != NULL; ep = ep->next)
{
if (strcmp (ep->item.key, entry.key) == 0)
{
if (action == ENTER)
ep->item.data = entry.data;
/* already there, just change data */
/* or action was just find it */
return (& ep->item);
}
else
ep2 = ep;
}
/* at this point, item was not in table */
/* ep2 points at last element on the list */
if (action == ENTER)
{
if ((ep2->next = (ELEMENT *) calloc (1, sizeof (ELEMENT))) == NULL)
return (NULL);
ep2->next->item = entry;
ep2->next->next = NULL;
return (& ep2->next->item);
}
else
return (NULL);
}
/*NOTREACHED*/
}
/* hashit --- do the hashing algorithm */
/*
* algorithm is sum of string elements, plus string length
* mod table size.
*/
static int hashit (text)
register char *text;
{
register long int sum = 0;
register int i;
for (i = 0; text[i] != '\0'; i++)
sum += text[i];
sum += i;
return (sum % Num_elem);
}
/*
* Prints all elements of the table, in no particular order.
*/
void
hprint(f)
void (*f)(); /* (*f) is a function that will be called by hprint, is passed
* (hashIndex, ptrToKey, ptrToData), and should print these.
*/
{
ELEMENT *p;
int i;
for (i=0; i<Num_elem; i++) {
for (p = Table[i]; p; p = p->next)
(*f)(i, p->item.key, p->item.data);
}
}
/*
* A function suitable for passing to hprint, if both key and data are text
* suitable for passing to printf. You can use this one or supply your
* own.
*/
void
htext(indx, key, data)
int indx;
char *key;
char *data;
{
printf("(%d)\t%s :\t%s\n", indx, key, data);
}
|