Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 : : /*
3 : : * Hash Table
4 : : * (C) 2013 Jung-Sang Ahn <jungsang.ahn@gmail.com>
5 : : */
6 : :
7 : : #include <stdio.h>
8 : : #include <stdlib.h>
9 : : #include "hash.h"
10 : : #include "memleak.h"
11 : :
12 : : #ifdef _HASH_LOCK
13 : : #define IFDEF_LOCK(...) __VA_ARGS__
14 : : #else
15 : : #define IFDEF_LOCK(...)
16 : : #endif
17 : :
18 : : #ifdef _HASH_TREE
19 : 86124161 : int _hash_cmp_wrap(struct avl_node *a, struct avl_node *b, void *aux)
20 : : {
21 : : return ((struct hash *)aux)->cmp(
22 : : _get_entry(a, struct hash_elem, avl),
23 : 86124161 : _get_entry(b, struct hash_elem, avl));
24 : : }
25 : : #endif
26 : :
27 : 804 : void hash_init(struct hash *hash, int nbuckets, hash_hash_func *hash_func, hash_cmp_func *cmp_func)
28 : : {
29 : : int i;
30 : 804 : hash->nbuckets = nbuckets;
31 : : #ifdef _HASH_TREE
32 : 804 : hash->buckets = (struct avl_tree *)malloc(sizeof(struct avl_tree) * hash->nbuckets);
33 : : #else
34 : : hash->buckets = (struct list *)malloc(sizeof(struct list) * hash->nbuckets);
35 : : #endif
36 : :
37 : : IFDEF_LOCK( hash->locks = (spin_t*)malloc(sizeof(spin_t) * hash->nbuckets) );
38 : :
39 [ + + ]: 2894628 : for (i=0;i<hash->nbuckets;++i){
40 : : #ifdef _HASH_TREE
41 : 2893824 : avl_init(hash->buckets + i, (void *)hash);
42 : : #else
43 : : list_init(hash->buckets + i);
44 : : #endif
45 : :
46 : : IFDEF_LOCK( spin_init(hash->locks + i); );
47 : : }
48 : :
49 : 804 : hash->hash_func = hash_func;
50 : 804 : hash->cmp = cmp_func;
51 : 804 : }
52 : :
53 : 10454444 : void hash_insert(struct hash *hash, struct hash_elem *e)
54 : : {
55 : 10454444 : int bucket = hash->hash_func(hash, e);
56 : :
57 : : IFDEF_LOCK( spin_lock(hash->locks + bucket) );
58 : :
59 : : #ifdef _HASH_TREE
60 : 10454424 : avl_insert(hash->buckets + bucket, &e->avl, _hash_cmp_wrap);
61 : : #else
62 : : list_push_back(hash->buckets + bucket, &e->list_elem);
63 : : #endif
64 : :
65 : : IFDEF_LOCK( spin_unlock(hash->locks + bucket) );
66 : 10454334 : }
67 : :
68 : 39935235 : struct hash_elem * hash_find(struct hash *ht, struct hash_elem *e)
69 : : {
70 : 39935235 : int bucket = ht->hash_func(ht, e);
71 : 39933515 : struct hash_elem *elem = NULL;
72 : :
73 : : IFDEF_LOCK( spin_lock(ht->locks + bucket) );
74 : :
75 : : #ifdef _HASH_TREE
76 : : struct avl_node *node;
77 : 39933515 : node = avl_search(ht->buckets + bucket, &e->avl, _hash_cmp_wrap);
78 [ + + ]: 39937960 : if (node) {
79 : : IFDEF_LOCK( spin_unlock(ht->locks + bucket) );
80 : 29150368 : elem = _get_entry(node, struct hash_elem, avl);
81 : 29150368 : return elem;
82 : : }
83 : : #else
84 : : struct list_elem *le = list_begin(ht->buckets + bucket);
85 : : while(le) {
86 : : elem = _get_entry(le, struct hash_elem, list_elem);
87 : : if (!ht->cmp(e, elem)) {
88 : : IFDEF_LOCK( spin_unlock(ht->locks + bucket) );
89 : : return elem;
90 : : }
91 : : le = list_next(le);
92 : : }
93 : : #endif
94 : :
95 : : IFDEF_LOCK( spin_unlock(ht->locks + bucket) );
96 : 39937960 : return NULL;
97 : : }
98 : :
99 : 10452696 : struct hash_elem * hash_remove(struct hash *hash, struct hash_elem *e)
100 : : {
101 : 10452696 : int bucket = hash->hash_func(hash, e);
102 : : struct hash_elem *hash_elem;
103 : :
104 : : IFDEF_LOCK( spin_lock(hash->locks + bucket) );
105 : :
106 : : #ifdef _HASH_TREE
107 : : struct avl_node *node;
108 : 10453258 : node = avl_search(hash->buckets + bucket, &e->avl, _hash_cmp_wrap);
109 [ + + ]: 10453507 : if (node) {
110 : 10453489 : avl_remove(hash->buckets + bucket, node);
111 : : IFDEF_LOCK( spin_unlock(hash->locks + bucket) );
112 : 10453130 : hash_elem = _get_entry(node, struct hash_elem, avl);
113 : 10453130 : return hash_elem;
114 : : }
115 : :
116 : : #else
117 : : struct list_elem *le;
118 : : le = list_begin(hash->buckets + bucket);
119 : : while(le) {
120 : : hash_elem = _get_entry(le, struct hash_elem, list_elem);
121 : : if (!hash->cmp(e, hash_elem)) {
122 : : list_remove(hash->buckets + bucket, le);
123 : :
124 : : IFDEF_LOCK( spin_unlock(hash->locks + bucket) );
125 : :
126 : : return hash_elem;
127 : : }
128 : : le = list_next(le);
129 : : }
130 : : #endif
131 : :
132 : : IFDEF_LOCK( spin_unlock(hash->locks + bucket) );
133 : :
134 : 10453148 : return NULL;
135 : : }
136 : :
137 : 798 : void hash_free(struct hash *hash)
138 : : {
139 : 798 : free(hash->buckets);
140 : : IFDEF_LOCK( free((void *)hash->locks) );
141 : 798 : }
142 : :
143 : 179 : void hash_free_active(struct hash *hash, hash_free_func *free_func)
144 : : {
145 : : int i;
146 : :
147 : : #ifdef _HASH_TREE
148 : : struct avl_node *node;
149 : : #else
150 : : struct list_elem *e, *e_next;
151 : : #endif
152 : :
153 : : struct hash_elem *h;
154 : :
155 [ + + ]: 355507 : for (i=0;i<hash->nbuckets;++i){
156 : : #ifdef _HASH_TREE
157 : 355328 : node = avl_first(hash->buckets + i);
158 [ + + ]: 355329 : while(node){
159 : 1 : h = _get_entry(node, struct hash_elem, avl);
160 : 1 : node = avl_next(node);
161 : 1 : avl_remove(hash->buckets + i, &h->avl);
162 : 1 : free_func(h);
163 : : }
164 : :
165 : : #else
166 : : e = list_begin(hash->buckets + i);
167 : : while(e) {
168 : : e_next = list_remove(hash->buckets + i, e);
169 : : h = _get_entry(e, struct hash_elem, list_elem);
170 : : free_func(h);
171 : : e = e_next;
172 : : }
173 : :
174 : : #endif
175 : : }
176 : :
177 : 179 : hash_free(hash);
178 : 179 : }
179 : :
|
