xref: /unit/src/test/nxt_lvlhsh_test.c (revision 595:686246c79c5a)
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     uintptr_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_memzero(&lhe, sizeof(nxt_lvlhsh_each_t));
191     lhe.proto = proto;
192 
193     for (i = 0; i < n + 1; i++) {
194         if (nxt_lvlhsh_each(&lh, &lhe) == NULL) {
195             break;
196         }
197     }
198 
199     if (i != n) {
200         nxt_log_error(NXT_LOG_NOTICE, thr->log,
201                       "lvlhsh each test failed at %ui of %ui", i, n);
202         return NXT_ERROR;
203     }
204 
205     for (i = 0; i < n; i++) {
206         value = nxt_lvlhsh_peek(&lh, proto);
207 
208         if (value == NULL) {
209             break;
210         }
211 
212         key = (uintptr_t) value;
213 
214         if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) {
215             return NXT_ERROR;
216         }
217     }
218 
219     if (i != n) {
220         nxt_log_error(NXT_LOG_NOTICE, thr->log,
221                       "lvlhsh peek test failed at %ui of %ui", i, n);
222         return NXT_ERROR;
223     }
224 
225     if (!nxt_lvlhsh_is_empty(&lh)) {
226         nxt_log_error(NXT_LOG_NOTICE, thr->log,
227                       "lvlhsh is not empty after deletion");
228         return NXT_ERROR;
229     }
230 
231     key = 0;
232     for (i = 0; i < n; i++) {
233         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
234 
235         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
236             nxt_log_error(NXT_LOG_NOTICE, thr->log,
237                           "lvlhsh add test failed at %ui", i);
238             return NXT_ERROR;
239         }
240     }
241 
242     for (i = 0; i < n; i++) {
243         value = nxt_lvlhsh_retrieve(&lh, proto, mp);
244 
245         if (value == NULL) {
246             break;
247         }
248     }
249 
250     if (i != n) {
251         nxt_log_error(NXT_LOG_NOTICE, thr->log,
252                       "lvlhsh retrieve test failed at %ui of %ui", i, n);
253         return NXT_ERROR;
254     }
255 
256     if (!nxt_lvlhsh_is_empty(&lh)) {
257         nxt_log_error(NXT_LOG_NOTICE, thr->log,
258                       "lvlhsh is not empty after retrieving");
259         return NXT_ERROR;
260     }
261 
262     if (mp != NULL) {
263         if (!nxt_mp_is_empty(mp)) {
264             nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty");
265             return NXT_ERROR;
266         }
267 
268         nxt_mp_destroy(mp);
269     }
270 
271     nxt_thread_time_update(thr);
272     end = nxt_thread_monotonic_time(thr);
273 
274     nxt_log_error(NXT_LOG_NOTICE, thr->log, "lvlhsh test passed: %0.3fs",
275                   (end - start) / 1000000000.0);
276 
277     return NXT_OK;
278 }
279