← Back to branch summary

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

« back to all changes in this revision

Viewing changes to ypserv-2.18/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.18/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
}