← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/nis/oneiric-proposed

« back to all changes in this revision

Viewing changes to ypserv-2.17/revnetgroup/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Scott James Remnant
  • Date: 2005-11-16 23:42:06 UTC
  • mfrom: (1.1.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20051116234206-p00omaw5ji5q0qhr
Tags: 3.15-3ubuntu1
Resynchronise with Debian.  (me)

Show diffs side-by-side

added added

removed removed

Lines of Context:
ypserv-2.17/revnetgroup/hash.c
1
 
/*
2
 
** hash.c - functions for a hash table.
3
 
**
4
 
** Copyright (c) 1996, 1997, 1999 Thorsten Kukuk
5
 
**
6
 
** This file is part of the NYS YP Server.
7
 
**
8
 
** The YP Server is free software; you can redistribute it and/or
9
 
** modify it under the terms of the GNU General Public License
10
 
** version 2 as published by the Free Software Foundation.
11
 
**
12
 
** The NYS YP Server is distributed in the hope that it will be useful,
13
 
** but WITHOUT ANY WARRANTY; without even the implied warranty of
14
 
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15
 
** General Public License for more details.
16
 
**
17
 
** You should have received a copy of the GNU General Public
18
 
** License along with the NYS YP Server; see the file COPYING.  If
19
 
** not, write to the Free Software Foundation, Inc., 675 Mass Ave,
20
 
** Cambridge, MA 02139, USA.
21
 
**
22
 
** Author: Thorsten Kukuk <kukuk@suse.de>
23
 
*/
24
 
 
25
 
 
26
 
#ifdef HAVE_CONFIG_H
27
 
#include "config.h"
28
 
#endif
29
 
#include <stdio.h>
30
 
#include <stdlib.h>
31
 
#include <string.h>
32
 
#include "hash.h"
33
 
#include <assert.h>
34
 
#include "compat.h"
35
 
 
36
 
#define TABLESIZE 997           /*Should be a prime */
37
 
 
38
 
/*
39
 
 * hash_malloc(void)
40
 
 *
41
 
 *   Initialize a new hash table.
42
 
 */
43
 
hash_t **
44
 
hash_malloc (void)
45
 
{
46
 
  hash_t **work = NULL;
47
 
  int i = 0;
48
 
 
49
 
  work = malloc (sizeof (hash_t *) * TABLESIZE);
50
 
  if (work == NULL)
51
 
    {
52
 
      fprintf (stderr, "Out of memory.\n");
53
 
      exit (1);
54
 
    }
55
 
 
56
 
  for (i = 0; i < TABLESIZE; i++)
57
 
    work[i] = NULL;
58
 
 
59
 
  return work;
60
 
}
61
 
 
62
 
/*
63
 
 * hash_calc_key(const char* key)
64
 
 *
65
 
 *   Calculates the key, returns it.
66
 
 */
67
 
static inline long
68
 
hash_calc_key (const char *key)
69
 
{
70
 
  long hkey = 0;
71
 
  int length = strlen (key);
72
 
  int i = -1;
73
 
 
74
 
  for (i = 0; i < length; i++)
75
 
    hkey = (256 * hkey + key[i]) % TABLESIZE;
76
 
 
77
 
  assert (hkey < TABLESIZE);
78
 
  return hkey;
79
 
}
80
 
 
81
 
 
82
 
/*
83
 
 * hash_insert(hash_t **table, const char*, const char*)
84
 
 *
85
 
 *   Complete re-write, to insert item into head of list
86
 
 *   at it's entry in the table.
87
 
 */
88
 
int
89
 
hash_insert (hash_t **table, const char *key, const char *val)
90
 
{
91
 
  long hkey = -1;
92
 
  hash_t *work = NULL;
93
 
 
94
 
  assert (table != NULL);
95
 
  assert (key != NULL);
96
 
  assert (val != NULL);
97
 
 
98
 
  hkey = hash_calc_key (key);
99
 
 
100
 
  /* look for the item */
101
 
  work = table[hkey];
102
 
  while (work != NULL)
103
 
    {
104
 
      if (strcmp (work->key, key) == 0)
105
 
        {
106
 
          return -1;
107
 
        }
108
 
      work = work->next;
109
 
    }
110
 
 
111
 
  /* insert into head of list */
112
 
  work = malloc (sizeof (hash_t));
113
 
  if (work == NULL)
114
 
    {
115
 
      fprintf (stderr, "Out of Memory.\n");
116
 
      exit (1);
117
 
    }
118
 
 
119
 
  /* setup the new node */
120
 
  work->key = strdup (key);
121
 
  work->val = strdup (val);
122
 
  work->next = NULL;
123
 
 
124
 
  if (table[hkey] != NULL)
125
 
    {
126
 
      work->next = table[hkey];
127
 
    }
128
 
 
129
 
  table[hkey] = work;
130
 
 
131
 
  return 0;
132
 
}
133
 
 
134
 
 
135
 
/*
136
 
 * hash_free(hash_t**)
137
 
 *
138
 
 *   Deallocates all the structures.
139
 
 *
140
 
 */
141
 
int
142
 
hash_free (hash_t **table UNUSED)
143
 
{
144
 
  /* XXX Not implementet yet! */
145
 
 
146
 
  return 0;
147
 
}
148
 
 
149
 
 
150
 
/*
151
 
 * hash_search(hash_t**, const char*)
152
 
 *
153
 
 *   Looks for specified key, returns value if found,
154
 
 *   and NULL if not.
155
 
 *
156
 
 */
157
 
char *
158
 
hash_search (hash_t **table, const char *key)
159
 
{
160
 
  hash_t *work = NULL;
161
 
  long hkey = -1;
162
 
 
163
 
  assert (table != NULL);
164
 
  assert (key != NULL);
165
 
 
166
 
  hkey = hash_calc_key (key);
167
 
 
168
 
  /* look for the key in the list */
169
 
  work = table[hkey];
170
 
  while (work != NULL)
171
 
    {
172
 
      if (strcmp (work->key, key) == 0)
173
 
        return work->val;
174
 
 
175
 
      work = work->next;
176
 
    }
177
 
 
178
 
  return NULL;
179
 
}
180
 
 
181
 
 
182
 
/*
183
 
 * hash_delkey(hash_t**, const char* )
184
 
 *
185
 
 *   Delete the item from the table.
186
 
 */
187
 
int
188
 
hash_delkey (hash_t **table, const char *key)
189
 
{
190
 
  hash_t *work = NULL;
191
 
  hash_t *prev = NULL;
192
 
  long hkey = -1;
193
 
 
194
 
  assert (table != NULL);
195
 
  assert (key != NULL);
196
 
 
197
 
  hkey = hash_calc_key (key);
198
 
 
199
 
  work = table[hkey];
200
 
  prev = table[hkey];
201
 
 
202
 
  while (work != NULL)
203
 
    {
204
 
      if (strcmp (work->key, key) == 0)
205
 
        {
206
 
 
207
 
          /* delete this node, and return? */
208
 
          if (work == table[hkey])
209
 
            table[hkey] = work->next;
210
 
          else
211
 
            prev->next = work->next;
212
 
 
213
 
          free (work->key);
214
 
          free (work->val);
215
 
          free (work);
216
 
          break;
217
 
        }
218
 
 
219
 
      prev = work;
220
 
      work = work->next;
221
 
    }
222
 
 
223
 
  return 0;
224
 
}
225
 
 
226
 
 
227
 
/*
228
 
 * hash_first(hash_t**)
229
 
 *
230
 
 *   Returns the first item in the hash table.
231
 
 */
232
 
hash_t *
233
 
hash_first (hash_t **table)
234
 
{
235
 
  unsigned long i = 0;
236
 
 
237
 
  for (i = 0; i < TABLESIZE; i++)
238
 
    {
239
 
      if (table[i] != NULL)
240
 
        return table[i];
241
 
    }
242
 
 
243
 
  return NULL;
244
 
}
245
 
 
246
 
/*
247
 
 * hash_next(hash_t**, const char*)
248
 
 *
249
 
 *   Returns the next item in the cache.
250
 
 */
251
 
hash_t *
252
 
hash_next (hash_t **table, const char *key)
253
 
{
254
 
  hash_t *work = NULL;
255
 
  long hkey = -1;
256
 
 
257
 
  assert (table != NULL);
258
 
  assert (key != NULL);
259
 
 
260
 
  hkey = hash_calc_key (key);
261
 
 
262
 
  /* look for the item */
263
 
  work = table[hkey];
264
 
  while (work != NULL)
265
 
    {
266
 
      if (strcmp (work->key, key) == 0)
267
 
        {
268
 
          work = work->next;
269
 
          break;
270
 
        }
271
 
      work = work->next;
272
 
    }
273
 
 
274
 
  /* at this point, we have seen the key:
275
 
   * starting from here, return the first
276
 
   * valid pointer we find
277
 
   */
278
 
  if (work != NULL)
279
 
    return work;
280
 
 
281
 
  /* work is NULL, increment to next list. */
282
 
  hkey++;
283
 
  while (hkey < TABLESIZE)
284
 
    {
285
 
      if (table[hkey] != NULL)
286
 
        return table[hkey];
287
 
 
288
 
      hkey++;
289
 
    }
290
 
 
291
 
  return NULL;
292
 
}