## gdp / ep / ep_hash.c @ master

History | View | Annotate | Download (5.87 KB)

1 | a901db09 | Eric Allman | ```
/* vim: set ai sw=8 sts=8 ts=8 :*/
``` |
---|---|---|---|

2 | 47c6ea64 | Eric Allman | |

3 | ```
/***********************************************************************
``` |
||

4 | 055d3009 | Eric Allman | ```
** ----- BEGIN LICENSE BLOCK -----
``` |

5 | ```
** LIBEP: Enhanced Portability Library (Reduced Edition)
``` |
||

6 | ```
**
``` |
||

7 | c87dd166 | Eric Allman | ```
** Copyright (c) 2008-2019, Eric P. Allman. All rights reserved.
``` |

8 | ```
** Copyright (c) 2015-2019, Regents of the University of California.
``` |
||

9 | 6bd5476b | Eric Allman | ```
** All rights reserved.
``` |

10 | 055d3009 | Eric Allman | ```
**
``` |

11 | 6bd5476b | Eric Allman | ```
** Permission is hereby granted, without written agreement and without
``` |

12 | ```
** license or royalty fees, to use, copy, modify, and distribute this
``` |
||

13 | ```
** software and its documentation for any purpose, provided that the above
``` |
||

14 | ```
** copyright notice and the following two paragraphs appear in all copies
``` |
||

15 | ```
** of this software.
``` |
||

16 | 055d3009 | Eric Allman | ```
**
``` |

17 | 6bd5476b | Eric Allman | ```
** IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT,
``` |

18 | ```
** SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST
``` |
||

19 | ```
** PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION,
``` |
||

20 | ```
** EVEN IF REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
``` |
||

21 | 055d3009 | Eric Allman | ```
**
``` |

22 | 6bd5476b | Eric Allman | ```
** REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
``` |

23 | 055d3009 | Eric Allman | ```
** LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
``` |

24 | 6bd5476b | Eric Allman | ```
** FOR A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION,
``` |

25 | ```
** IF ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO
``` |
||

26 | ```
** OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS,
``` |
||

27 | ```
** OR MODIFICATIONS.
``` |
||

28 | 055d3009 | Eric Allman | ```
** ----- END LICENSE BLOCK -----
``` |

29 | 47c6ea64 | Eric Allman | ```
***********************************************************************/
``` |

30 | |||

31 | #include <ep.h> |
||

32 | #include <ep_rpool.h> |
||

33 | #include <ep_stat.h> |
||

34 | #include <ep_assert.h> |
||

35 | #include <ep_hash.h> |
||

36 | #include <ep_string.h> |
||

37 | 49c87bd9 | Eric Allman | #include <ep_thr.h> |

38 | 47c6ea64 | Eric Allman | |

39 | |||

40 | |||

41 | ```
/***********************************************************************
``` |
||

42 | ```
**
``` |
||

43 | ```
** HASH HANDLING
``` |
||

44 | ```
*/
``` |
||

45 | |||

46 | ```
/************************** BEGIN PRIVATE **************************/
``` |
||

47 | |||

48 | ```
struct node
``` |
||

49 | { |
||

50 | 80662ee3 | Eric Allman | ```
size_t keylen; // length of key
``` |

51 | 58292089 | Eric Allman | const void *key; // actual key |

52 | const void *val; // value |
||

53 | 47c6ea64 | Eric Allman | struct node *next; // next in chain |

54 | }; |
||

55 | |||

56 | ```
struct EP_HASH
``` |
||

57 | { |
||

58 | ```
EP_RPOOL *rpool; // resource pool
``` |
||

59 | ```
uint32_t flags; // flags -- see below
``` |
||

60 | 49c87bd9 | Eric Allman | ```
EP_THR_MUTEX mutex; // lock on this object
``` |

61 | 47c6ea64 | Eric Allman | ```
EP_HASH_HASH_FUNCP hfunc; // hashing function
``` |

62 | int tabsize; // size of hash tab |
||

63 | struct node *tab[0]; // actually longer |
||

64 | }; |
||

65 | |||

66 | ```
// no flags at this time
``` |
||

67 | |||

68 | |||

69 | ```
int
``` |
||

70 | def_hfunc( |
||

71 | const EP_HASH *const hp, |
||

72 | 80662ee3 | Eric Allman | ```
const size_t keysize,
``` |

73 | fc0cbc23 | Eric Allman | const void *_key) |

74 | 47c6ea64 | Eric Allman | { |

75 | fc0cbc23 | Eric Allman | uint8_t *key = (uint8_t *) _key; |

76 | 47c6ea64 | Eric Allman | int hfunc = 0; |

77 | 80662ee3 | Eric Allman | size_t i; |

78 | 47c6ea64 | Eric Allman | |

79 | for (i = 0; i < keysize; i++) |
||

80 | { |
||

81 | hfunc = ((hfunc << 1) ^ (*(uint8_t*)key++ & 0xff)) % hp->tabsize; |
||

82 | } |
||

83 | ```
return hfunc;
``` |
||

84 | } |
||

85 | |||

86 | ```
/*************************** END PRIVATE ***************************/
``` |
||

87 | |||

88 | EP_HASH * |
||

89 | ep_hash_new( |
||

90 | const char *name, |
||

91 | EP_HASH_HASH_FUNCP hfunc, |
||

92 | ```
int tabsize)
``` |
||

93 | { |
||

94 | ```
uint32_t flags = 0;
``` |
||

95 | EP_HASH *hash; |
||

96 | EP_RPOOL *rp; |
||

97 | 80662ee3 | Eric Allman | size_t xtra; |

98 | 47c6ea64 | Eric Allman | |

99 | if (tabsize == 0) |
||

100 | tabsize = ep_adm_getintparam("libep.hash.tabsize", 2003); |
||

101 | 9e55d093 | Eric Allman | if (name == NULL) |

102 | 47c6ea64 | Eric Allman | ```
name = "<hash>";
``` |

103 | 9e55d093 | Eric Allman | if (hfunc == NULL) |

104 | 47c6ea64 | Eric Allman | hfunc = def_hfunc; |

105 | |||

106 | ```
EP_ASSERT(tabsize >= 2);
``` |
||

107 | |||

108 | ```
rp = ep_rpool_new(name, (size_t) 0);
``` |
||

109 | |||

110 | ```
// figure how much extra space we need to allocate for table
``` |
||

111 | xtra = tabsize * sizeof hash->tab[0]; |
||

112 | |||

113 | fc0cbc23 | Eric Allman | ```
hash = (EP_HASH *) ep_rpool_zalloc(rp, sizeof *hash + xtra);
``` |

114 | 47c6ea64 | Eric Allman | hash->rpool = rp; |

115 | hash->hfunc = hfunc; |
||

116 | hash->flags = flags; |
||

117 | hash->tabsize = tabsize; |
||

118 | 51775f02 | Eric Allman | ep_thr_mutex_init(&hash->mutex, EP_THR_MUTEX_DEFAULT); |

119 | 47c6ea64 | Eric Allman | |

120 | ```
return hash;
``` |
||

121 | } |
||

122 | |||

123 | |||

124 | ```
void
``` |
||

125 | ep_hash_free(EP_HASH *hash) |
||

126 | { |
||

127 | EP_ASSERT_POINTER_VALID(hash); |
||

128 | 49c87bd9 | Eric Allman | ep_thr_mutex_destroy(&hash->mutex); |

129 | 47c6ea64 | Eric Allman | ```
ep_rpool_free(hash->rpool); // also frees hash
``` |

130 | } |
||

131 | |||

132 | |||

133 | 0c663d10 | Eric Allman | ```
struct node **
``` |

134 | find_node_ptr(EP_HASH *hp, |
||

135 | 80662ee3 | Eric Allman | size_t keylen, |

136 | 47c6ea64 | Eric Allman | const void *key) |

137 | { |
||

138 | ```
int indx;
``` |
||

139 | 0c663d10 | Eric Allman | ```
struct node **npp;
``` |

140 | 47c6ea64 | Eric Allman | ```
struct node *n;
``` |

141 | |||

142 | indx = hp->hfunc(hp, keylen, key); |
||

143 | 0c663d10 | Eric Allman | npp = &hp->tab[indx]; |

144 | 47c6ea64 | Eric Allman | |

145 | 0c663d10 | Eric Allman | for (n = *npp; n != NULL; npp = &n->next, n = *npp) |

146 | 47c6ea64 | Eric Allman | { |

147 | ```
if (keylen == n->keylen &&
``` |
||

148 | ```
memcmp(key, n->key, keylen) == 0)
``` |
||

149 | { |
||

150 | ```
// match
``` |
||

151 | 0c663d10 | Eric Allman | ```
break;
``` |

152 | 47c6ea64 | Eric Allman | } |

153 | } |
||

154 | 0c663d10 | Eric Allman | |

155 | ```
return npp;
``` |
||

156 | } |
||

157 | |||

158 | |||

159 | 58292089 | Eric Allman | const void * |

160 | 0c663d10 | Eric Allman | ep_hash_search( |

161 | EP_HASH *hp, |
||

162 | 80662ee3 | Eric Allman | size_t keylen, |

163 | 0c663d10 | Eric Allman | const void *key) |

164 | { |
||

165 | ```
struct node **npp;
``` |
||

166 | 58292089 | Eric Allman | const void *val; |

167 | 0c663d10 | Eric Allman | |

168 | EP_ASSERT_POINTER_VALID(hp); |
||

169 | |||

170 | 0314a7a7 | Eric Allman | ep_thr_mutex_lock(&hp->mutex); |

171 | 0c663d10 | Eric Allman | npp = find_node_ptr(hp, keylen, key); |

172 | if (*npp == NULL) |
||

173 | 0314a7a7 | Eric Allman | ```
val = NULL;
``` |

174 | 0c663d10 | Eric Allman | ```
else
``` |

175 | 0314a7a7 | Eric Allman | val = (*npp)->val; |

176 | ep_thr_mutex_unlock(&hp->mutex); |
||

177 | ```
return val;
``` |
||

178 | 47c6ea64 | Eric Allman | } |

179 | |||

180 | |||

181 | 58292089 | Eric Allman | const void * |

182 | 47c6ea64 | Eric Allman | ep_hash_insert( |

183 | EP_HASH *hp, |
||

184 | 80662ee3 | Eric Allman | size_t keylen, |

185 | 47c6ea64 | Eric Allman | const void *key, |

186 | 58292089 | Eric Allman | const void *val) |

187 | 47c6ea64 | Eric Allman | { |

188 | 0c663d10 | Eric Allman | ```
struct node **npp;
``` |

189 | 47c6ea64 | Eric Allman | ```
struct node *n;
``` |

190 | ```
void *kp;
``` |
||

191 | |||

192 | EP_ASSERT_POINTER_VALID(hp); |
||

193 | |||

194 | 0314a7a7 | Eric Allman | ep_thr_mutex_lock(&hp->mutex); |

195 | 0c663d10 | Eric Allman | npp = find_node_ptr(hp, keylen, key); |

196 | if (*npp != NULL) |
||

197 | 47c6ea64 | Eric Allman | { |

198 | 0c663d10 | Eric Allman | ```
// there is an existing value; replace it
``` |

199 | 58292089 | Eric Allman | const void *oldval; |

200 | 47c6ea64 | Eric Allman | |

201 | 0c663d10 | Eric Allman | n = *npp; |

202 | oldval = n->val; |
||

203 | n->val = val; |
||

204 | 0314a7a7 | Eric Allman | ep_thr_mutex_unlock(&hp->mutex); |

205 | 0c663d10 | Eric Allman | ```
return oldval;
``` |

206 | 47c6ea64 | Eric Allman | } |

207 | |||

208 | ```
// not found -- insert it
``` |
||

209 | fc0cbc23 | Eric Allman | n = (struct node *) ep_rpool_malloc(hp->rpool, sizeof *n); |

210 | 47c6ea64 | Eric Allman | n->keylen = keylen; |

211 | kp = ep_rpool_malloc(hp->rpool, keylen); |
||

212 | memcpy(kp, key, keylen); |
||

213 | n->key = kp; |
||

214 | n->val = val; |
||

215 | 0c663d10 | Eric Allman | ```
n->next = NULL;
``` |

216 | *npp = n; |
||

217 | 0314a7a7 | Eric Allman | ep_thr_mutex_unlock(&hp->mutex); |

218 | 9e55d093 | Eric Allman | return NULL; |

219 | 47c6ea64 | Eric Allman | } |

220 | |||

221 | |||

222 | 58292089 | Eric Allman | const void * |

223 | 0c663d10 | Eric Allman | ep_hash_delete( |

224 | EP_HASH *hp, |
||

225 | 80662ee3 | Eric Allman | size_t keylen, |

226 | 0c663d10 | Eric Allman | const void *key) |

227 | { |
||

228 | ```
struct node **npp;
``` |
||

229 | ```
struct node *n;
``` |
||

230 | 58292089 | Eric Allman | const void *v; |

231 | 0c663d10 | Eric Allman | |

232 | EP_ASSERT_POINTER_VALID(hp); |
||

233 | |||

234 | 0314a7a7 | Eric Allman | ep_thr_mutex_lock(&hp->mutex); |

235 | 0c663d10 | Eric Allman | npp = find_node_ptr(hp, keylen, key); |

236 | if (*npp == NULL) |
||

237 | { |
||

238 | ```
// entry does not exist
``` |
||

239 | 0314a7a7 | Eric Allman | ep_thr_mutex_unlock(&hp->mutex); |

240 | 0c663d10 | Eric Allman | return NULL; |

241 | } |
||

242 | |||

243 | n = *npp; |
||

244 | v = n->val; |
||

245 | 58283344 | Eric Allman | ```
n->val = NULL;
``` |

246 | |||

247 | ```
// since ep_rpool_mfree doesn't free yet, leave this node in
``` |
||

248 | ```
// the list to allow re-use of the key without losing more memory
``` |
||

249 | ```
//*npp = n->next;
``` |
||

250 | ```
//ep_rpool_mfree(hp->rpool, n->key);
``` |
||

251 | ```
//ep_rpool_mfree(hp->rpool, n);
``` |
||

252 | |||

253 | 0314a7a7 | Eric Allman | ep_thr_mutex_unlock(&hp->mutex); |

254 | 0c663d10 | Eric Allman | ```
return v;
``` |

255 | } |
||

256 | |||

257 | |||

258 | 47c6ea64 | Eric Allman | ```
/*
``` |

259 | ```
** EP_HASH_FORALL -- apply a function to all nodes
``` |
||

260 | ```
*/
``` |
||

261 | |||

262 | ```
void
``` |
||

263 | ep_hash_forall( |
||

264 | EP_HASH *hp, |
||

265 | EP_HASH_FORALL_FUNCP func, |
||

266 | ...) |
||

267 | { |
||

268 | va_list av; |
||

269 | ```
struct node *n;
``` |
||

270 | ```
int i;
``` |
||

271 | |||

272 | va_start(av, func); |
||

273 | |||

274 | EP_ASSERT_POINTER_VALID(hp); |
||

275 | |||

276 | 0314a7a7 | Eric Allman | ep_thr_mutex_lock(&hp->mutex); |

277 | 47c6ea64 | Eric Allman | for (i = 0; i < hp->tabsize; i++) |

278 | { |
||

279 | 458b37ea | Eric Allman | ```
struct node *next;
``` |

280 | for (n = hp->tab[i]; n != NULL; n = next) |
||

281 | 47c6ea64 | Eric Allman | { |

282 | va_list lav; |
||

283 | 458b37ea | Eric Allman | next = n->next; |

284 | 47c6ea64 | Eric Allman | |

285 | va_copy(lav, av); |
||

286 | (*func)(n->keylen, n->key, n->val, lav); |
||

287 | } |
||

288 | } |
||

289 | |||

290 | va_end(av); |
||

291 | 0314a7a7 | Eric Allman | ep_thr_mutex_unlock(&hp->mutex); |

292 | 47c6ea64 | Eric Allman | } |