1 /*-
2 * Copyright (c) 2013 Larisa Grigore<larisagrigore@gmail.com>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27 #include <stdlib.h>
28 #include <stdio.h>
29 #include <errno.h>
30
31 #include "sysvipc_hash.h"
32
33 struct hashtable *
_hash_init(int nr_elems)34 _hash_init(int nr_elems)
35 {
36 long hashsize;
37 struct hashtable *hashtable;
38 int i;
39
40 if (nr_elems <= 0)
41 return NULL;
42 for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1)
43 continue;
44
45 hashtable = malloc(sizeof(struct hashtable));
46 if (!hashtable) {
47 return NULL;
48 }
49
50 hashtable->entries = malloc(hashsize * sizeof(struct entries_list));
51 if (!hashtable->entries) {
52 free(hashtable);
53 hashtable = NULL;
54 goto out;
55 }
56
57 hashtable->nr_elems = hashsize;
58
59 for (i = 0; i < hashsize; i++)
60 LIST_INIT(&hashtable->entries[i]);
61
62 out:
63 return hashtable;
64 }
65
66 int
_hash_destroy(struct hashtable * hashtable)67 _hash_destroy(struct hashtable *hashtable)
68 {
69 struct entries_list *tmp;
70 u_long hashmask = hashtable->nr_elems -1;
71
72 for (tmp = &hashtable->entries[0]; tmp <= &hashtable->entries[hashmask]; tmp++) {
73 if (!LIST_EMPTY(tmp))
74 return -1;
75 }
76 free(hashtable->entries);
77 free(hashtable);
78 hashtable = NULL;
79 return 0;
80 }
81
82 void
_hash_insert(struct hashtable * hashtable,u_long key,void * value)83 _hash_insert(struct hashtable *hashtable, u_long key, void *value)
84 {
85
86 u_long hashmask = hashtable->nr_elems -1;
87 struct entries_list *list =
88 &hashtable->entries[key & hashmask];
89 struct hashentry *new_entry = malloc(sizeof(struct hashentry));
90 new_entry->value = value;
91 new_entry->key = key;
92 LIST_INSERT_HEAD(list, new_entry, entry_link);
93 }
94
95 void *
_hash_lookup(struct hashtable * hashtable,u_long key)96 _hash_lookup(struct hashtable *hashtable, u_long key)
97 {
98
99 u_long hashmask = hashtable->nr_elems -1;
100 struct entries_list *list =
101 &hashtable->entries[key & hashmask];
102 struct hashentry *tmp;
103
104 LIST_FOREACH(tmp, list, entry_link) {
105 if (tmp->key == key) {
106 return tmp->value;
107 }
108 }
109
110 return NULL;
111 }
112
113 void *
_hash_remove(struct hashtable * hashtable,u_long key)114 _hash_remove(struct hashtable *hashtable, u_long key)
115 {
116
117 void *value;
118 u_long hashmask = hashtable->nr_elems -1;
119 struct entries_list *list =
120 &hashtable->entries[key & hashmask];
121 struct hashentry *tmp;
122
123 LIST_FOREACH(tmp, list, entry_link) {
124 if (tmp->key == key)
125 goto done;
126 }
127
128 return NULL;
129
130 done:
131 LIST_REMOVE(tmp, entry_link);
132 value = tmp->value;
133 free(tmp);
134 return value;
135 }
136
137 int
get_hash_size(int nr_elems)138 get_hash_size(int nr_elems)
139 {
140 long hashsize = 0;
141
142 for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1)
143 continue;
144
145 return hashsize;
146 }
147