]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* Hash routine. |
2 | * Copyright (C) 1998 Kunihiro Ishiguro | |
3 | * | |
4 | * This file is part of GNU Zebra. | |
5 | * | |
6 | * GNU Zebra is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published | |
8 | * by the Free Software Foundation; either version 2, or (at your | |
9 | * option) any later version. | |
10 | * | |
11 | * GNU Zebra is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License | |
17 | * along with GNU Zebra; see the file COPYING. If not, write to the | |
18 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
19 | * Boston, MA 02111-1307, USA. | |
20 | */ | |
21 | ||
22 | #include <zebra.h> | |
23 | ||
24 | #include "hash.h" | |
25 | #include "memory.h" | |
26 | ||
27 | /* Allocate a new hash. */ | |
28 | struct hash * | |
29 | hash_create_size (unsigned int size, | |
30 | unsigned int (*hash_key) (), int (*hash_cmp) ()) | |
31 | { | |
32 | struct hash *hash; | |
33 | ||
34 | hash = XMALLOC (MTYPE_HASH, sizeof (struct hash)); | |
35 | hash->index = XMALLOC (MTYPE_HASH_INDEX, | |
36 | sizeof (struct hash_backet *) * size); | |
37 | memset (hash->index, 0, sizeof (struct hash_backet *) * size); | |
38 | hash->size = size; | |
39 | hash->hash_key = hash_key; | |
40 | hash->hash_cmp = hash_cmp; | |
41 | hash->count = 0; | |
42 | ||
43 | return hash; | |
44 | } | |
45 | ||
46 | /* Allocate a new hash with default hash size. */ | |
47 | struct hash * | |
48 | hash_create (unsigned int (*hash_key) (), int (*hash_cmp) ()) | |
49 | { | |
50 | return hash_create_size (HASHTABSIZE, hash_key, hash_cmp); | |
51 | } | |
52 | ||
53 | /* Utility function for hash_get(). When this function is specified | |
54 | as alloc_func, return arugment as it is. This function is used for | |
55 | intern already allocated value. */ | |
56 | void * | |
57 | hash_alloc_intern (void *arg) | |
58 | { | |
59 | return arg; | |
60 | } | |
61 | ||
62 | /* Lookup and return hash backet in hash. If there is no | |
63 | corresponding hash backet and alloc_func is specified, create new | |
64 | hash backet. */ | |
65 | void * | |
66 | hash_get (struct hash *hash, void *data, void * (*alloc_func) ()) | |
67 | { | |
68 | unsigned int key; | |
69 | unsigned int index; | |
70 | void *newdata; | |
71 | struct hash_backet *backet; | |
72 | ||
73 | key = (*hash->hash_key) (data); | |
74 | index = key % hash->size; | |
75 | ||
76 | for (backet = hash->index[index]; backet != NULL; backet = backet->next) | |
77 | if (backet->key == key && (*hash->hash_cmp) (backet->data, data)) | |
78 | return backet->data; | |
79 | ||
80 | if (alloc_func) | |
81 | { | |
82 | newdata = (*alloc_func) (data); | |
83 | if (newdata == NULL) | |
84 | return NULL; | |
85 | ||
86 | backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet)); | |
87 | backet->data = newdata; | |
88 | backet->key = key; | |
89 | backet->next = hash->index[index]; | |
90 | hash->index[index] = backet; | |
91 | hash->count++; | |
92 | return backet->data; | |
93 | } | |
94 | return NULL; | |
95 | } | |
96 | ||
97 | /* Hash lookup. */ | |
98 | void * | |
99 | hash_lookup (struct hash *hash, void *data) | |
100 | { | |
101 | return hash_get (hash, data, NULL); | |
102 | } | |
103 | ||
104 | /* This function release registered value from specified hash. When | |
105 | release is successfully finished, return the data pointer in the | |
106 | hash backet. */ | |
107 | void * | |
108 | hash_release (struct hash *hash, void *data) | |
109 | { | |
110 | void *ret; | |
111 | unsigned int key; | |
112 | unsigned int index; | |
113 | struct hash_backet *backet; | |
114 | struct hash_backet *pp; | |
115 | ||
116 | key = (*hash->hash_key) (data); | |
117 | index = key % hash->size; | |
118 | ||
119 | for (backet = pp = hash->index[index]; backet; backet = backet->next) | |
120 | { | |
121 | if (backet->key == key && (*hash->hash_cmp) (backet->data, data)) | |
122 | { | |
123 | if (backet == pp) | |
124 | hash->index[index] = backet->next; | |
125 | else | |
126 | pp->next = backet->next; | |
127 | ||
128 | ret = backet->data; | |
129 | XFREE (MTYPE_HASH_BACKET, backet); | |
130 | hash->count--; | |
131 | return ret; | |
132 | } | |
133 | pp = backet; | |
134 | } | |
135 | return NULL; | |
136 | } | |
137 | ||
138 | /* Iterator function for hash. */ | |
139 | void | |
140 | hash_iterate (struct hash *hash, | |
141 | void (*func) (struct hash_backet *, void *), void *arg) | |
142 | { | |
143 | int i; | |
144 | struct hash_backet *hb; | |
145 | ||
146 | for (i = 0; i < hash->size; i++) | |
147 | for (hb = hash->index[i]; hb; hb = hb->next) | |
148 | (*func) (hb, arg); | |
149 | } | |
150 | ||
151 | /* Clean up hash. */ | |
152 | void | |
153 | hash_clean (struct hash *hash, void (*free_func) (void *)) | |
154 | { | |
155 | int i; | |
156 | struct hash_backet *hb; | |
157 | struct hash_backet *next; | |
158 | ||
159 | for (i = 0; i < hash->size; i++) | |
160 | { | |
161 | for (hb = hash->index[i]; hb; hb = next) | |
162 | { | |
163 | next = hb->next; | |
164 | ||
165 | if (free_func) | |
166 | (*free_func) (hb->data); | |
167 | ||
168 | XFREE (MTYPE_HASH_BACKET, hb); | |
169 | hash->count--; | |
170 | } | |
171 | hash->index[i] = NULL; | |
172 | } | |
173 | } | |
174 | ||
175 | /* Free hash memory. You may call hash_clean before call this | |
176 | function. */ | |
177 | void | |
178 | hash_free (struct hash *hash) | |
179 | { | |
180 | XFREE (MTYPE_HASH_INDEX, hash->index); | |
181 | XFREE (MTYPE_HASH, hash); | |
182 | } |