xref: /unit/src/test/nxt_lvlhsh_test.c (revision 840:500c3525e10e)
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #include <nxt_main.h>
8 #include "nxt_tests.h"
9 
10 
11 static nxt_int_t
12 nxt_lvlhsh_test_key_test(nxt_lvlhsh_query_t *lhq, void *data)
13 {
14     if (*(uintptr_t *) lhq->key.start == (uintptr_t) data) {
15         return NXT_OK;
16     }
17 
18     return NXT_DECLINED;
19 }
20 
21 
22 static void *
23 nxt_lvlhsh_test_pool_alloc(void *pool, size_t size)
24 {
25     return nxt_mp_align(pool, size, size);
26 }
27 
28 
29 static void
30 nxt_lvlhsh_test_pool_free(void *pool, void *p)
31 {
32     nxt_mp_free(pool, p);
33 }
34 
35 
36 static const nxt_lvlhsh_proto_t  malloc_proto  nxt_aligned(64) = {
37     //NXT_LVLHSH_LARGE_MEMALIGN,
38     NXT_LVLHSH_DEFAULT,
39     nxt_lvlhsh_test_key_test,
40     nxt_lvlhsh_alloc,
41     nxt_lvlhsh_free,
42 };
43 
44 static const nxt_lvlhsh_proto_t  pool_proto  nxt_aligned(64) = {
45     NXT_LVLHSH_LARGE_SLAB,
46     nxt_lvlhsh_test_key_test,
47     nxt_lvlhsh_test_pool_alloc,
48     nxt_lvlhsh_test_pool_free,
49 };
50 
51 
52 static nxt_int_t
53 nxt_lvlhsh_test_add(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
54     void *pool, uintptr_t key)
55 {
56     nxt_lvlhsh_query_t  lhq;
57 
58     lhq.key_hash = key;
59     lhq.replace = 0;
60     lhq.key.length = sizeof(uintptr_t);
61     lhq.key.start = (u_char *) &key;
62     lhq.value = (void *) key;
63     lhq.proto = proto;
64     lhq.pool = pool;
65 
66     switch (nxt_lvlhsh_insert(lh, &lhq)) {
67 
68     case NXT_OK:
69         return NXT_OK;
70 
71     case NXT_DECLINED:
72         nxt_thread_log_alert("lvlhsh test failed: "
73                              "key %p is already in hash", key);
74         /* Fall through. */
75     default:
76         return NXT_ERROR;
77     }
78 }
79 
80 
81 static nxt_int_t
82 nxt_lvlhsh_test_get(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
83     uintptr_t key)
84 {
85     nxt_lvlhsh_query_t  lhq;
86 
87     lhq.key_hash = key;
88     lhq.key.length = sizeof(uintptr_t);
89     lhq.key.start = (u_char *) &key;
90     lhq.proto = proto;
91 
92     if (nxt_lvlhsh_find(lh, &lhq) == NXT_OK) {
93 
94         if (key == (uintptr_t) lhq.value) {
95             return NXT_OK;
96         }
97     }
98 
99     nxt_thread_log_alert("lvlhsh test failed: "
100                          "key %p not found in hash", key);
101 
102     return NXT_ERROR;
103 }
104 
105 
106 static nxt_int_t
107 nxt_lvlhsh_test_delete(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
108     void *pool, uintptr_t key)
109 {
110     nxt_int_t           ret;
111     nxt_lvlhsh_query_t  lhq;
112 
113     lhq.key_hash = key;
114     lhq.key.length = sizeof(uintptr_t);
115     lhq.key.start = (u_char *) &key;
116     lhq.proto = proto;
117     lhq.pool = pool;
118 
119     ret = nxt_lvlhsh_delete(lh, &lhq);
120 
121     if (ret != NXT_OK) {
122         nxt_thread_log_alert("lvlhsh test failed: "
123                              "key %p not found in hash", key);
124     }
125 
126     return ret;
127 }
128 
129 
130 nxt_int_t
131 nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
132 {
133     void                      *value;
134     uint32_t                  key;
135     nxt_mp_t                  *mp;
136     nxt_nsec_t                start, end;
137     nxt_uint_t                i;
138     nxt_lvlhsh_t              lh;
139     nxt_lvlhsh_each_t         lhe;
140     const nxt_lvlhsh_proto_t  *proto;
141 
142     const size_t              min_chunk_size = 32;
143     const size_t              page_size = 1024;
144     const size_t              page_alignment = 128;
145     const size_t              cluster_size = 4096;
146 
147     nxt_thread_time_update(thr);
148     start = nxt_thread_monotonic_time(thr);
149 
150     if (use_pool) {
151         mp = nxt_mp_create(cluster_size, page_alignment, page_size,
152                            min_chunk_size);
153         if (mp == NULL) {
154             return NXT_ERROR;
155         }
156 
157         nxt_log_error(NXT_LOG_NOTICE, thr->log,
158                       "lvlhsh test started: %uD pool", n);
159         proto = &pool_proto;
160 
161     } else {
162         nxt_log_error(NXT_LOG_NOTICE, thr->log,
163                       "lvlhsh test started: %uD malloc", n);
164         proto = &malloc_proto;
165         mp = NULL;
166     }
167 
168     nxt_memzero(&lh, sizeof(nxt_lvlhsh_t));
169 
170     key = 0;
171     for (i = 0; i < n; i++) {
172         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
173 
174         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
175             nxt_log_error(NXT_LOG_NOTICE, thr->log,
176                           "lvlhsh add test failed at %ui", i);
177             return NXT_ERROR;
178         }
179     }
180 
181     key = 0;
182     for (i = 0; i < n; i++) {
183         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
184 
185         if (nxt_lvlhsh_test_get(&lh, proto, key) != NXT_OK) {
186             return NXT_ERROR;
187         }
188     }
189 
190     nxt_lvlhsh_each_init(&lhe, proto);
191 
192     for (i = 0; i < n + 1; i++) {
193         if (nxt_lvlhsh_each(&lh, &lhe) == NULL) {
194             break;
195         }
196     }
197 
198     if (i != n) {
199         nxt_log_error(NXT_LOG_NOTICE, thr->log,
200                       "lvlhsh each test failed at %ui of %ui", i, n);
201         return NXT_ERROR;
202     }
203 
204     for (i = 0; i < n; i++) {
205         value = nxt_lvlhsh_peek(&lh, proto);
206 
207         if (value == NULL) {
208             break;
209         }
210 
211         key = (uintptr_t) value;
212 
213         if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) {
214             return NXT_ERROR;
215         }
216     }
217 
218     if (i != n) {
219         nxt_log_error(NXT_LOG_NOTICE, thr->log,
220                       "lvlhsh peek test failed at %ui of %ui", i, n);
221         return NXT_ERROR;
222     }
223 
224     if (!nxt_lvlhsh_is_empty(&lh)) {
225         nxt_log_error(NXT_LOG_NOTICE, thr->log,
226                       "lvlhsh is not empty after deletion");
227         return NXT_ERROR;
228     }
229 
230     key = 0;
231     for (i = 0; i < n; i++) {
232         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
233 
234         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
235             nxt_log_error(NXT_LOG_NOTICE, thr->log,
236                           "lvlhsh add test failed at %ui", i);
237             return NXT_ERROR;
238         }
239     }
240 
241     for (i = 0; i < n; i++) {
242         value = nxt_lvlhsh_retrieve(&lh, proto, mp);
243 
244         if (value == NULL) {
245             break;
246         }
247     }
248 
249     if (i != n) {
250         nxt_log_error(NXT_LOG_NOTICE, thr->log,
251                       "lvlhsh retrieve test failed at %ui of %ui", i, n);
252         return NXT_ERROR;
253     }
254 
255     if (!nxt_lvlhsh_is_empty(&lh)) {
256         nxt_log_error(NXT_LOG_NOTICE, thr->log,
257                       "lvlhsh is not empty after retrieving");
258         return NXT_ERROR;
259     }
260 
261     if (mp != NULL) {
262         if (!nxt_mp_is_empty(mp)) {
263             nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty");
264             return NXT_ERROR;
265         }
266 
267         nxt_mp_destroy(mp);
268     }
269 
270     nxt_thread_time_update(thr);
271     end = nxt_thread_monotonic_time(thr);
272 
273     nxt_log_error(NXT_LOG_NOTICE, thr->log, "lvlhsh test passed: %0.3fs",
274                   (end - start) / 1000000000.0);
275 
276     return NXT_OK;
277 }
278