File: hsearch.c

package info (click to toggle)
super 3.26.0-2
  • links: PTS
  • area: main
  • in suites: sarge
  • size: 1,036 kB
  • ctags: 732
  • sloc: ansic: 9,840; sh: 276; makefile: 196
file content (204 lines) | stat: -rw-r--r-- 4,474 bytes parent folder | download
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);
}