1 /***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
9 *
10 * This software is licensed as described in the file COPYING, which
11 * you should have received as part of this distribution. The terms
12 * are also available at https://curl.se/docs/copyright.html.
13 *
14 * You may opt to use, copy, modify, merge, publish, distribute and/or sell
15 * copies of the Software, and permit persons to whom the Software is
16 * furnished to do so, under the terms of the COPYING file.
17 *
18 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19 * KIND, either express or implied.
20 *
21 * SPDX-License-Identifier: curl
22 *
23 ***************************************************************************/
24 #include "curlcheck.h"
25
26 #define ENABLE_CURLX_PRINTF
27 #include "curlx.h"
28
29 #include "hash.h"
30
31 #include "memdebug.h" /* LAST include file */
32
33 static struct Curl_hash hash_static;
34 static const size_t slots = 3;
35
mydtor(void * p)36 static void mydtor(void *p)
37 {
38 /* Data are statically allocated */
39 (void)p; /* unused */
40 }
41
42 static size_t elem_dtor_calls;
43
my_elem_dtor(void * key,size_t key_len,void * p)44 static void my_elem_dtor(void *key, size_t key_len, void *p)
45 {
46 (void)p; /* unused */
47 (void)key; /* unused */
48 (void)key_len; /* unused */
49 ++elem_dtor_calls;
50 }
51
unit_setup(void)52 static CURLcode unit_setup(void)
53 {
54 Curl_hash_init(&hash_static, slots, Curl_hash_str,
55 Curl_str_key_compare, mydtor);
56 return CURLE_OK;
57 }
58
unit_stop(void)59 static void unit_stop(void)
60 {
61 Curl_hash_destroy(&hash_static);
62 }
63
64 UNITTEST_START
65 char key1[] = "key1";
66 char key2[] = "key2b";
67 char key3[] = "key3";
68 char key4[] = "key4";
69 char notakey[] = "notakey";
70 char *nodep;
71 int rc;
72
73 /* Ensure the key hashes are as expected in order to test both hash
74 collisions and a full table. Unfortunately, the hashes can vary
75 between architectures. */
76 if(Curl_hash_str(key1, strlen(key1), slots) != 1 ||
77 Curl_hash_str(key2, strlen(key2), slots) != 0 ||
78 Curl_hash_str(key3, strlen(key3), slots) != 2 ||
79 Curl_hash_str(key4, strlen(key4), slots) != 1)
80 fprintf(stderr, "Warning: hashes are not computed as expected on this "
81 "architecture; test coverage will be less comprehensive\n");
82
83 nodep = Curl_hash_add(&hash_static, &key1, strlen(key1), &key1);
84 fail_unless(nodep, "insertion into hash failed");
85 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
86 fail_unless(nodep == key1, "hash retrieval failed");
87
88 nodep = Curl_hash_add(&hash_static, &key2, strlen(key2), &key2);
89 fail_unless(nodep, "insertion into hash failed");
90 nodep = Curl_hash_pick(&hash_static, &key2, strlen(key2));
91 fail_unless(nodep == key2, "hash retrieval failed");
92
93 nodep = Curl_hash_add(&hash_static, &key3, strlen(key3), &key3);
94 fail_unless(nodep, "insertion into hash failed");
95 nodep = Curl_hash_pick(&hash_static, &key3, strlen(key3));
96 fail_unless(nodep == key3, "hash retrieval failed");
97
98 /* The fourth element exceeds the number of slots & collides */
99 nodep = Curl_hash_add(&hash_static, &key4, strlen(key4), &key4);
100 fail_unless(nodep, "insertion into hash failed");
101 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
102 fail_unless(nodep == key4, "hash retrieval failed");
103
104 /* Make sure all elements are still accessible */
105 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
106 fail_unless(nodep == key1, "hash retrieval failed");
107 nodep = Curl_hash_pick(&hash_static, &key2, strlen(key2));
108 fail_unless(nodep == key2, "hash retrieval failed");
109 nodep = Curl_hash_pick(&hash_static, &key3, strlen(key3));
110 fail_unless(nodep == key3, "hash retrieval failed");
111 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
112 fail_unless(nodep == key4, "hash retrieval failed");
113
114 /* Delete the second of two entries in a bucket */
115 rc = Curl_hash_delete(&hash_static, &key4, strlen(key4));
116 fail_unless(rc == 0, "hash delete failed");
117 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
118 fail_unless(nodep == key1, "hash retrieval failed");
119 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
120 fail_unless(!nodep, "hash retrieval should have failed");
121
122 /* Insert that deleted node again */
123 nodep = Curl_hash_add(&hash_static, &key4, strlen(key4), &key4);
124 fail_unless(nodep, "insertion into hash failed");
125 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
126 fail_unless(nodep == key4, "hash retrieval failed");
127
128 /* Delete the first of two entries in a bucket */
129 rc = Curl_hash_delete(&hash_static, &key1, strlen(key1));
130 fail_unless(rc == 0, "hash delete failed");
131 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
132 fail_unless(!nodep, "hash retrieval should have failed");
133 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
134 fail_unless(nodep == key4, "hash retrieval failed");
135
136 /* Delete the remaining one of two entries in a bucket */
137 rc = Curl_hash_delete(&hash_static, &key4, strlen(key4));
138 fail_unless(rc == 0, "hash delete failed");
139 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
140 fail_unless(!nodep, "hash retrieval should have failed");
141 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
142 fail_unless(!nodep, "hash retrieval should have failed");
143
144 /* Delete an already deleted node */
145 rc = Curl_hash_delete(&hash_static, &key4, strlen(key4));
146 fail_unless(rc, "hash delete should have failed");
147
148 /* Replace an existing node */
149 nodep = Curl_hash_add(&hash_static, &key1, strlen(key1), ¬akey);
150 fail_unless(nodep, "insertion into hash failed");
151 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
152 fail_unless(nodep == notakey, "hash retrieval failed");
153
154 /* Make sure all remaining elements are still accessible */
155 nodep = Curl_hash_pick(&hash_static, &key2, strlen(key2));
156 fail_unless(nodep == key2, "hash retrieval failed");
157 nodep = Curl_hash_pick(&hash_static, &key3, strlen(key3));
158 fail_unless(nodep == key3, "hash retrieval failed");
159
160 /* Add element with own destructor */
161 nodep = Curl_hash_add2(&hash_static, &key1, strlen(key1), &key1,
162 my_elem_dtor);
163 fail_unless(nodep, "add2 insertion into hash failed");
164 fail_unless(elem_dtor_calls == 0, "element destructor count should be 0");
165 /* Add it again, should invoke destructor on first */
166 nodep = Curl_hash_add2(&hash_static, &key1, strlen(key1), &key1,
167 my_elem_dtor);
168 fail_unless(nodep, "add2 again, insertion into hash failed");
169 fail_unless(elem_dtor_calls == 1, "element destructor count should be 1");
170 /* remove, should invoke destructor */
171 rc = Curl_hash_delete(&hash_static, &key1, strlen(key1));
172 fail_unless(rc == 0, "hash delete failed");
173 fail_unless(elem_dtor_calls == 2, "element destructor count should be 1");
174
175
176 /* Clean up */
177 Curl_hash_clean(&hash_static);
178
179 UNITTEST_STOP
180
