chiark / gitweb /
Release 2.3.3.1.
[mLib] / struct / hash.c
1 /* -*-c-*-
2  *
3  * General hashtable infrastructure
4  *
5  * (c) 1999 Straylight/Edgeware
6  */
7
8 /*----- Licensing notice --------------------------------------------------*
9  *
10  * This file is part of the mLib utilities library.
11  *
12  * mLib is free software; you can redistribute it and/or modify
13  * it under the terms of the GNU Library General Public License as
14  * published by the Free Software Foundation; either version 2 of the
15  * License, or (at your option) any later version.
16  *
17  * mLib is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
20  * GNU Library General Public License for more details.
21  *
22  * You should have received a copy of the GNU Library General Public
23  * License along with mLib; if not, write to the Free
24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25  * MA 02111-1307, USA.
26  */
27
28 /*----- Header files ------------------------------------------------------*/
29
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <string.h>
33
34 #include "alloc.h"
35 #include "arena.h"
36 #include "bits.h"
37 #include "exc.h"
38 #include "hash.h"
39
40 /*----- Main code ---------------------------------------------------------*/
41
42 /* --- @hash_create@ --- *
43  *
44  * Arguments:   @hash_table *t@ = pointer to hashtable to initialize
45  *              @size_t n@ = number of bins to allocate (zero initially)
46  *
47  * Returns:     ---
48  *
49  * Use:         Initializes a hashtable with a given number of bins.  The
50  *              bins are initially empty.  The number of bins must be a power
51  *              of two.  This is not checked.
52  */
53
54 void hash_create(hash_table *t, size_t n)
55 {
56   hash_base **v;
57
58   t->a = arena_global;
59   t->v = x_alloc(t->a, n * sizeof(hash_base *));
60   t->mask = n - 1;
61   for (v = t->v; n; v++, n--)
62     *v = 0;
63 }
64
65 /* --- @hash_destroy@ --- *
66  *
67  * Arguments:   @hash_table *t@ = pointer to hashtable to destroy
68  *
69  * Returns:     ---
70  *
71  * Use:         Frees a hashtable.  The items are not freed: they are the
72  *              responsibility of the implementation.
73  */
74
75 void hash_destroy(hash_table *t) { x_free(t->a, t->v); }
76
77 /* --- @hash_bin@ --- *
78  *
79  * Arguments:   @hash_table *t@ = pointer to hashtable
80  *              @uint32 hash@ = hash value to look up
81  *
82  * Returns:     Pointer to the bin's list head.
83  *
84  * Use:         Given a hash value return the address of the appropriate list
85  *              head.  It is safe to remove the current entry from the table.
86  */
87
88 hash_base **hash_bin(hash_table *t, uint32 hash)
89   { return (HASH_BIN(t, hash)); }
90
91 /* --- @hash_extend@ --- *
92  *
93  * Arguments:   @hash_table *t@ = pointer to hashtable to extend
94  *
95  * Returns:     Nonzero if extension was successful.
96  *
97  * Use:         Extends a hashtable.  The number of bins is doubled and the
98  *              entries are redistributed.
99  */
100
101 int hash_extend(hash_table *t)
102 {
103   hash_base **v;
104   uint32 m = t->mask + 1;
105   size_t i;
106
107   /* --- Allocate a new hash bin vector --- */
108
109   if ((v = A_REALLOC(t->a, t->v,
110                      2 * m * sizeof(hash_base *),
111                      m * sizeof(hash_base *))) == 0) {
112     return (0);
113   }
114   t->v = v;
115   t->mask = (m * 2) - 1;
116
117   /* --- Wander through the table rehashing things --- */
118
119   for (i = 0; i < m; i++) {
120     hash_base **p = v + i;
121     hash_base **q = p + m;
122
123     while (*p) {
124       if (!((*p)->hash & m))
125         p = &(*p)->next;
126       else {
127         *q = *p;
128         q = &(*q)->next;
129         *p = (*p)->next;
130       }
131     }
132     *p = 0;
133     *q = 0;
134   }
135
136   return (1);
137 }
138
139 /* --- @hash_remove@ --- *
140  *
141  * Arguments:   @hash_table *t@ = pointer to hashtable
142  *              @hash_base *p@ = pointer to item to remove
143  *
144  * Returns:     ---
145  *
146  * Use:         Removes an item from a hashtable.  The item itself is not
147  *              freed, although it is removed from the data structure and is
148  *              safe to free.
149  */
150
151 void hash_remove(hash_table *t, hash_base *p)
152 {
153   hash_base **b = HASH_BIN(t, p->hash);
154   while (*b) {
155     if (*b == p) {
156       *b = p->next;
157       return;
158     }
159     b = &(*b)->next;
160   }
161   return;
162 }
163
164 /* --- @hash_mkiter@ --- *
165  *
166  * Arguments:   @hash_iter *i@ = pointer to iterator to create
167  *              @hash_table *t@ = pointer to hashtable to iterate
168  *
169  * Returns:     ---
170  *
171  * Use:         Initializes a hashtable iterator.
172  */
173
174 void hash_mkiter(hash_iter *i, hash_table *t) { HASH_MKITER(i, t); }
175
176 /* --- @hash_next@ --- *
177  *
178  * Arguments:   @hash_iter *i@ = pointer to iterator
179  *
180  * Returns:     Pointer to the next hashtable entry found, or null.
181  *
182  * Use:         Returns the next entry from the hashtable.
183  */
184
185 hash_base *hash_next(hash_iter *i)
186 {
187   hash_base *b;
188   HASH_NEXT(i, b);
189   return (b);
190 }
191
192 /*----- That's all, folks -------------------------------------------------*/