1 /* $OpenBSD: ohash_do.c,v 1.4 2004/06/22 20:00:16 espie Exp $ */
2 /* ex:ts=8 sw=4:
3  */
4 
5 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
6  *
7  * Permission to use, copy, modify, and distribute this software for any
8  * purpose with or without fee is hereby granted, provided that the above
9  * copyright notice and this permission notice appear in all copies.
10  *
11  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18  */
19 
20 #include "ohash_int.h"
21 
22 static void ohash_resize(struct ohash *);
23 
24 static void
ohash_resize(struct ohash * h)25 ohash_resize(struct ohash *h)
26 {
27           struct _ohash_record *n;
28           unsigned int        ns, j;
29           unsigned int        i, incr;
30 
31           if (4 * h->deleted < h->total)
32                     ns = h->size << 1;
33           else if (3 * h->deleted > 2 * h->total)
34                     ns = h->size >> 1;
35           else
36                     ns = h->size;
37           if (ns < MINSIZE)
38                     ns = MINSIZE;
39 #ifdef STATS_HASH
40           STAT_HASH_EXPAND++;
41           STAT_HASH_SIZE += ns - h->size;
42 #endif
43           n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data);
44           if (!n)
45                     return;
46 
47           for (j = 0; j < h->size; j++) {
48                     if (h->t[j].p != NULL && h->t[j].p != DELETED) {
49                               i = h->t[j].hv % ns;
50                               incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
51                               while (n[i].p != NULL) {
52                                         i += incr;
53                                         if (i >= ns)
54                                                   i -= ns;
55                               }
56                               n[i].hv = h->t[j].hv;
57                               n[i].p = h->t[j].p;
58                     }
59           }
60           (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size,
61                     h->info.data);
62           h->t = n;
63           h->size = ns;
64           h->total -= h->deleted;
65           h->deleted = 0;
66 }
67 
68 void *
ohash_remove(struct ohash * h,unsigned int i)69 ohash_remove(struct ohash *h, unsigned int i)
70 {
71           void                *result = __UNCONST(h->t[i].p);
72 
73           if (result == NULL || result == DELETED)
74                     return NULL;
75 
76 #ifdef STATS_HASH
77           STAT_HASH_ENTRIES--;
78 #endif
79           h->t[i].p = DELETED;
80           h->deleted++;
81           if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
82                     ohash_resize(h);
83           return result;
84 }
85 
86 void *
ohash_find(struct ohash * h,unsigned int i)87 ohash_find(struct ohash *h, unsigned int i)
88 {
89           if (h->t[i].p == DELETED)
90                     return NULL;
91           else
92                     return __UNCONST(h->t[i].p);
93 }
94 
95 void *
ohash_insert(struct ohash * h,unsigned int i,void * p)96 ohash_insert(struct ohash *h, unsigned int i, void *p)
97 {
98 #ifdef STATS_HASH
99           STAT_HASH_ENTRIES++;
100 #endif
101           if (h->t[i].p == DELETED) {
102                     h->deleted--;
103                     h->t[i].p = p;
104           } else {
105                     h->t[i].p = p;
106           /* Arbitrary resize boundary.  Tweak if not efficient enough.  */
107                     if (++h->total * 4 > h->size * 3)
108                               ohash_resize(h);
109           }
110           return p;
111 }
112