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