source: trunk/third/moira/lib/hash.c @ 24319

Revision 24319, 3.3 KB checked in by broder, 14 years ago (diff)
New Moira snapshot from SVN.
RevLine 
[24319]1/* $Id: hash.c 3956 2010-01-05 20:56:56Z zacheiss $
[23095]2 *
3 * Generic hash table routines.  Uses integer keys to store char * values.
4 *
5 * Copyright (C) 1988-1998 by the Massachusetts Institute of Technology.
6 * For copying and distribution information, please see the file
7 * <mit-copyright.h>.
8 */
9
10#include <mit-copyright.h>
11#include <moira.h>
12
13#include <stdlib.h>
14#include <string.h>
15
[24319]16RCSID("$HeadURL: svn+ssh://svn.mit.edu/moira/trunk/moira/lib/hash.c $ $Id: hash.c 3956 2010-01-05 20:56:56Z zacheiss $");
[23095]17
18#define hash_func(h, key) (key >= 0 ? (key % h->size) : (-key % h->size))
19
20/* Create a hash table.  The size is just a hint, not a maximum. */
21
22struct hash *create_hash(int size)
23{
24  struct hash *h;
25
26  h = malloc(sizeof(struct hash));
27  if (!h)
28    return NULL;
29  h->size = size;
30  h->data = malloc(size * sizeof(void *));
31  if (!h->data)
32    {
33      free(h);
34      return NULL;
35    }
36  memset(h->data, 0, size * sizeof(void *));
37  return h;
38}
39
40/* Lookup an object in the hash table.  Returns the value associated with
41 * the key, or NULL (thus NULL is not a very good value to store...)
42 */
43
44void *hash_lookup(struct hash *h, int key)
45{
46  struct bucket *b;
47
48  b = h->data[hash_func(h, key)];
49  while (b && b->key != key)
50    b = b->next;
51  if (b && b->key == key)
52    return b->data;
53  else
54    return NULL;
55}
56
57
58/* Update an existing object in the hash table.  Returns 1 if the object
59 * existed, or 0 if not.
60 */
61
62int hash_update(struct hash *h, int key, void *value)
63{
64  struct bucket *b;
65
66  b = h->data[hash_func(h, key)];
67  while (b && b->key != key)
68    b = b->next;
69  if (b && b->key == key)
70    {
71      b->data = value;
72      return 1;
73    }
74  else
75    return 0;
76}
77
78
79/* Store an item in the hash table.  Returns 0 if the key was not previously
80 * there, 1 if it was, or -1 if we ran out of memory.
81 */
82
83int hash_store(struct hash *h, int key, void *value)
84{
85  struct bucket *b, **p;
86
87  p = &(h->data[hash_func(h, key)]);
88  if (!*p)
89    {
90      b = *p = malloc(sizeof(struct bucket));
91      if (!b)
92        return -1;
93      b->next = NULL;
94      b->key = key;
95      b->data = value;
96      return 0;
97    }
98
99  for (b = *p; b && b->key != key; b = *p)
100    p = (struct bucket **) *p;
101  if (b && b->key == key)
102    {
103      b->data = value;
104      return 1;
105    }
106  b = *p = malloc(sizeof(struct bucket));
107  if (!b)
108    return -1;
109  b->next = NULL;
110  b->key = key;
111  b->data = value;
112  return 0;
113}
114
115
116/* Search through the hash table for a given value.  For each piece of
117 * data with that value, call the callback proc with the corresponding key.
118 */
119
120void hash_search(struct hash *h, void *value, void (*callback)(int))
121{
122  struct bucket *b, **p;
123
124  for (p = &(h->data[h->size - 1]); p >= h->data; p--)
125    {
126      for (b = *p; b; b = b->next)
127        {
128          if (b->data == value)
129            (*callback)(b->key);
130        }
131    }
132}
133
134
135/* Step through the hash table, calling the callback proc with each key.
136 */
137
138void hash_step(struct hash *h, void (*callback)(int, void *, void *),
139               void *hint)
140{
141  struct bucket *b, **p;
142
143  for (p = &(h->data[h->size - 1]); p >= h->data; p--)
144    {
145      for (b = *p; b; b = b->next)
146        (*callback)(b->key, b->data, hint);
147    }
148}
149
150
151/* Deallocate all of the memory associated with a table */
152
153void hash_destroy(struct hash *h)
154{
155  struct bucket *b, **p, *b1;
156
157  for (p = &(h->data[h->size - 1]); p >= h->data; p--)
158    {
159      for (b = *p; b; b = b1)
160        {
161          b1 = b->next;
162          free(b);
163        }
164    }
165}
Note: See TracBrowser for help on using the repository browser.