git.zerfleddert.de Git - proxmark3-svn/blob - client/jansson/hashtable.c

1 /*

3 *

4 * This library is free software; you can redistribute it and/or modify

5 * it under the terms of the MIT license. See LICENSE for details.

6 */

8 #if HAVE_CONFIG_H

9 #include <jansson_private_config.h>

10 #endif

12 #include <stdlib.h>

13 #include <string.h>

15 #if HAVE_STDINT_H

16 #include <stdint.h>

17 #endif

19 #include <jansson_config.h> /* for JSON_INLINE */

 #include "jansson_private.h"  /* for container_of() */

21 #include "hashtable.h"

23 #ifndef INITIAL_HASHTABLE_ORDER

24 #define INITIAL_HASHTABLE_ORDER 3

25 #endif

27 typedef struct hashtable_list list_t;

28 typedef struct hashtable_pair pair_t;

29 typedef struct hashtable_bucket bucket_t;

31 extern volatile uint32_t hashtable_seed;

33 /* Implementation of the hash function */

34 #include "lookup3.h"

36 #define list_to_pair(list_) container_of(list_, pair_t, list)

37 #define ordered_list_to_pair(list_) container_of(list_, pair_t, ordered_list)

38 #define hash_str(key) ((size_t)hashlittle((key), strlen(key), hashtable_seed))

 static JSON_INLINE void list_init(list_t *list)

41 {

42 list->next = list;

43 list->prev = list;

44 }

 static JSON_INLINE void list_insert(list_t *list, list_t *node)

47 {

48 node->next = list;

49 node->prev = list->prev;

50 list->prev->next = node;

51 list->prev = node;

52 }

 static JSON_INLINE void list_remove(list_t *list)

55 {

     list->prev->next = list->next;

     list->next->prev = list->prev;

58 }

 static JSON_INLINE int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)

61 {

     return bucket->first == &hashtable->list && bucket->first == bucket->last;

63 }

 static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket,

66 list_t *list)

67 {

     if(bucket_is_empty(hashtable, bucket))

69 {

         list_insert(&hashtable->list, list);

         bucket->first = bucket->last = list;

72 }

73 else

74 {

         list_insert(bucket->first, list);

76 bucket->first = list;

77 }

78 }

 static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,

                                    const char *key, size_t hash)

82 {

83 list_t *list;

84 pair_t *pair;

     if(bucket_is_empty(hashtable, bucket))

87 return NULL;

89 list = bucket->first;

90 while(1)

91 {

92 pair = list_to_pair(list);

         if(pair->hash == hash && strcmp(pair->key, key) == 0)

94 return pair;

         if(list == bucket->last)

97 break;

99 list = list->next;

100 }

101

102 return NULL;

103 }

104

105 /* returns 0 on success, -1 if key was not found */

 static int hashtable_do_del(hashtable_t *hashtable,

                             const char *key, size_t hash)

108 {

109 pair_t *pair;

110 bucket_t *bucket;

111 size_t index;

112

     index = hash & hashmask(hashtable->order);

114 bucket = &hashtable->buckets[index];

115

     pair = hashtable_find_pair(hashtable, bucket, key, hash);

117 if(!pair)

118 return -1;

119

     if(&pair->list == bucket->first && &pair->list == bucket->last)

         bucket->first = bucket->last = &hashtable->list;

122

     else if(&pair->list == bucket->first)

         bucket->first = pair->list.next;

125

     else if(&pair->list == bucket->last)

         bucket->last = pair->list.prev;

128

129 list_remove(&pair->list);

130 list_remove(&pair->ordered_list);

131 json_decref(pair->value);

132

133 jsonp_free(pair);

134 hashtable->size--;

135

136 return 0;

137 }

138

 static void hashtable_do_clear(hashtable_t *hashtable)

140 {

141 list_t *list, *next;

142 pair_t *pair;

143

     for(list = hashtable->list.next; list != &hashtable->list; list = next)

145 {

146 next = list->next;

147 pair = list_to_pair(list);

148 json_decref(pair->value);

149 jsonp_free(pair);

150 }

151 }

152

 static int hashtable_do_rehash(hashtable_t *hashtable)

154 {

155 list_t *list, *next;

156 pair_t *pair;

     size_t i, index, new_size, new_order;

158 struct hashtable_bucket *new_buckets;

159

     new_order = hashtable->order + 1;

161 new_size = hashsize(new_order);

162

     new_buckets = jsonp_malloc(new_size * sizeof(bucket_t));

164 if(!new_buckets)

165 return -1;

166

167 jsonp_free(hashtable->buckets);

168 hashtable->buckets = new_buckets;

169 hashtable->order = new_order;

170

     for(i = 0; i < hashsize(hashtable->order); i++)

172 {

         hashtable->buckets[i].first = hashtable->buckets[i].last =

174 &hashtable->list;

175 }

176

177 list = hashtable->list.next;

178 list_init(&hashtable->list);

179

     for(; list != &hashtable->list; list = next) {

181 next = list->next;

182 pair = list_to_pair(list);

183 index = pair->hash % new_size;

         insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);

185 }

186

187 return 0;

188 }

189

190

 int hashtable_init(hashtable_t *hashtable)

192 {

193 size_t i;

194

195 hashtable->size = 0;

196 hashtable->order = INITIAL_HASHTABLE_ORDER;

     hashtable->buckets = jsonp_malloc(hashsize(hashtable->order) * sizeof(bucket_t));

198 if(!hashtable->buckets)

199 return -1;

200

201 list_init(&hashtable->list);

202 list_init(&hashtable->ordered_list);

203

     for(i = 0; i < hashsize(hashtable->order); i++)

205 {

         hashtable->buckets[i].first = hashtable->buckets[i].last =

207 &hashtable->list;

208 }

209

210 return 0;

211 }

212

 void hashtable_close(hashtable_t *hashtable)

214 {

215 hashtable_do_clear(hashtable);

216 jsonp_free(hashtable->buckets);

217 }

218

 int hashtable_set(hashtable_t *hashtable, const char *key, json_t *value)

220 {

221 pair_t *pair;

222 bucket_t *bucket;

223 size_t hash, index;

224

225 /* rehash if the load ratio exceeds 1 */

     if(hashtable->size >= hashsize(hashtable->order))

         if(hashtable_do_rehash(hashtable))

228 return -1;

229

230 hash = hash_str(key);

     index = hash & hashmask(hashtable->order);

232 bucket = &hashtable->buckets[index];

     pair = hashtable_find_pair(hashtable, bucket, key, hash);

234

235 if(pair)

236 {

237 json_decref(pair->value);

238 pair->value = value;

239 }

240 else

241 {

242 /* offsetof(...) returns the size of pair_t without the last,

243 flexible member. This way, the correct amount is

244 allocated. */

245

         size_t len = strlen(key);

         if(len >= (size_t)-1 - offsetof(pair_t, key)) {

248 /* Avoid an overflow if the key is very long */

249 return -1;

250 }

251

         pair = jsonp_malloc(offsetof(pair_t, key) + len + 1);

253 if(!pair)

254 return -1;

255

256 pair->hash = hash;

         strncpy(pair->key, key, len + 1);

258 pair->value = value;

259 list_init(&pair->list);

260 list_init(&pair->ordered_list);

261

         insert_to_bucket(hashtable, bucket, &pair->list);

         list_insert(&hashtable->ordered_list, &pair->ordered_list);

264

265 hashtable->size++;

266 }

267 return 0;

268 }

269

 void *hashtable_get(hashtable_t *hashtable, const char *key)

271 {

272 pair_t *pair;

273 size_t hash;

274 bucket_t *bucket;

275

276 hash = hash_str(key);

     bucket = &hashtable->buckets[hash & hashmask(hashtable->order)];

278

     pair = hashtable_find_pair(hashtable, bucket, key, hash);

280 if(!pair)

281 return NULL;

282

283 return pair->value;

284 }

285

 int hashtable_del(hashtable_t *hashtable, const char *key)

287 {

     size_t hash = hash_str(key);

     return hashtable_do_del(hashtable, key, hash);

290 }

291

 void hashtable_clear(hashtable_t *hashtable)

293 {

294 size_t i;

295

296 hashtable_do_clear(hashtable);

297

     for(i = 0; i < hashsize(hashtable->order); i++)

299 {

         hashtable->buckets[i].first = hashtable->buckets[i].last =

301 &hashtable->list;

302 }

303

304 list_init(&hashtable->list);

305 list_init(&hashtable->ordered_list);

306 hashtable->size = 0;

307 }

308

 void *hashtable_iter(hashtable_t *hashtable)

310 {

     return hashtable_iter_next(hashtable, &hashtable->ordered_list);

312 }

313

 void *hashtable_iter_at(hashtable_t *hashtable, const char *key)

315 {

316 pair_t *pair;

317 size_t hash;

318 bucket_t *bucket;

319

320 hash = hash_str(key);

     bucket = &hashtable->buckets[hash & hashmask(hashtable->order)];

322

     pair = hashtable_find_pair(hashtable, bucket, key, hash);

324 if(!pair)

325 return NULL;

326

327 return &pair->ordered_list;

328 }

329

 void *hashtable_iter_next(hashtable_t *hashtable, void *iter)

331 {

332 list_t *list = (list_t *)iter;

     if(list->next == &hashtable->ordered_list)

334 return NULL;

335 return list->next;

336 }

337

 void *hashtable_iter_key(void *iter)

339 {

     pair_t *pair = ordered_list_to_pair((list_t *)iter);

341 return pair->key;

342 }

343

 void *hashtable_iter_value(void *iter)

345 {

     pair_t *pair = ordered_list_to_pair((list_t *)iter);

347 return pair->value;

348 }

349

 void hashtable_iter_set(void *iter, json_t *value)

351 {

     pair_t *pair = ordered_list_to_pair((list_t *)iter);

353

354 json_decref(pair->value);

355 pair->value = value;

356 }