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 #include "curlx.h"
27
28 #include "hash.h"
29
30 #include "memdebug.h" /* LAST include file */
31
32 static struct Curl_hash hash_static;
33 static const size_t slots = 3;
34
mydtor(void * p)35 static void mydtor(void *p)
36 {
37 /* Data are statically allocated */
38 (void)p; /* unused */
39 }
40
41 static size_t elem_dtor_calls;
42
my_elem_dtor(void * key,size_t key_len,void * p)43 static void my_elem_dtor(void *key, size_t key_len, void *p)
44 {
45 (void)p; /* unused */
46 (void)key; /* unused */
47 (void)key_len; /* unused */
48 ++elem_dtor_calls;
49 }
50
unit_setup(void)51 static CURLcode unit_setup(void)
52 {
53 Curl_hash_init(&hash_static, slots, Curl_hash_str,
54 Curl_str_key_compare, mydtor);
55 return CURLE_OK;
56 }
57
unit_stop(void)58 static void unit_stop(void)
59 {
60 Curl_hash_destroy(&hash_static);
61 }
62
63 UNITTEST_START
64 char key1[] = "key1";
65 char key2[] = "key2b";
66 char key3[] = "key3";
67 char key4[] = "key4";
68 char notakey[] = "notakey";
69 char *nodep;
70 int rc;
71
72 /* Ensure the key hashes are as expected in order to test both hash
73 collisions and a full table. Unfortunately, the hashes can vary
74 between architectures. */
75 if(Curl_hash_str(key1, strlen(key1), slots) != 1 ||
76 Curl_hash_str(key2, strlen(key2), slots) != 0 ||
77 Curl_hash_str(key3, strlen(key3), slots) != 2 ||
78 Curl_hash_str(key4, strlen(key4), slots) != 1)
79 fprintf(stderr, "Warning: hashes are not computed as expected on this "
80 "architecture; test coverage will be less comprehensive\n");
81
82 nodep = Curl_hash_add(&hash_static, &key1, strlen(key1), &key1);
83 fail_unless(nodep, "insertion into hash failed");
84 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
85 fail_unless(nodep == key1, "hash retrieval failed");
86
87 nodep = Curl_hash_add(&hash_static, &key2, strlen(key2), &key2);
88 fail_unless(nodep, "insertion into hash failed");
89 nodep = Curl_hash_pick(&hash_static, &key2, strlen(key2));
90 fail_unless(nodep == key2, "hash retrieval failed");
91
92 nodep = Curl_hash_add(&hash_static, &key3, strlen(key3), &key3);
93 fail_unless(nodep, "insertion into hash failed");
94 nodep = Curl_hash_pick(&hash_static, &key3, strlen(key3));
95 fail_unless(nodep == key3, "hash retrieval failed");
96
97 /* The fourth element exceeds the number of slots & collides */
98 nodep = Curl_hash_add(&hash_static, &key4, strlen(key4), &key4);
99 fail_unless(nodep, "insertion into hash failed");
100 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
101 fail_unless(nodep == key4, "hash retrieval failed");
102
103 /* Make sure all elements are still accessible */
104 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
105 fail_unless(nodep == key1, "hash retrieval failed");
106 nodep = Curl_hash_pick(&hash_static, &key2, strlen(key2));
107 fail_unless(nodep == key2, "hash retrieval failed");
108 nodep = Curl_hash_pick(&hash_static, &key3, strlen(key3));
109 fail_unless(nodep == key3, "hash retrieval failed");
110 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
111 fail_unless(nodep == key4, "hash retrieval failed");
112
113 /* Delete the second of two entries in a bucket */
114 rc = Curl_hash_delete(&hash_static, &key4, strlen(key4));
115 fail_unless(rc == 0, "hash delete failed");
116 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
117 fail_unless(nodep == key1, "hash retrieval failed");
118 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
119 fail_unless(!nodep, "hash retrieval should have failed");
120
121 /* Insert that deleted node again */
122 nodep = Curl_hash_add(&hash_static, &key4, strlen(key4), &key4);
123 fail_unless(nodep, "insertion into hash failed");
124 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
125 fail_unless(nodep == key4, "hash retrieval failed");
126
127 /* Delete the first of two entries in a bucket */
128 rc = Curl_hash_delete(&hash_static, &key1, strlen(key1));
129 fail_unless(rc == 0, "hash delete failed");
130 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
131 fail_unless(!nodep, "hash retrieval should have failed");
132 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
133 fail_unless(nodep == key4, "hash retrieval failed");
134
135 /* Delete the remaining one of two entries in a bucket */
136 rc = Curl_hash_delete(&hash_static, &key4, strlen(key4));
137 fail_unless(rc == 0, "hash delete failed");
138 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
139 fail_unless(!nodep, "hash retrieval should have failed");
140 nodep = Curl_hash_pick(&hash_static, &key4, strlen(key4));
141 fail_unless(!nodep, "hash retrieval should have failed");
142
143 /* Delete an already deleted node */
144 rc = Curl_hash_delete(&hash_static, &key4, strlen(key4));
145 fail_unless(rc, "hash delete should have failed");
146
147 /* Replace an existing node */
148 nodep = Curl_hash_add(&hash_static, &key1, strlen(key1), ¬akey);
149 fail_unless(nodep, "insertion into hash failed");
150 nodep = Curl_hash_pick(&hash_static, &key1, strlen(key1));
151 fail_unless(nodep == notakey, "hash retrieval failed");
152
153 /* Make sure all remaining elements are still accessible */
154 nodep = Curl_hash_pick(&hash_static, &key2, strlen(key2));
155 fail_unless(nodep == key2, "hash retrieval failed");
156 nodep = Curl_hash_pick(&hash_static, &key3, strlen(key3));
157 fail_unless(nodep == key3, "hash retrieval failed");
158
159 /* Add element with own destructor */
160 nodep = Curl_hash_add2(&hash_static, &key1, strlen(key1), &key1,
161 my_elem_dtor);
162 fail_unless(nodep, "add2 insertion into hash failed");
163 fail_unless(elem_dtor_calls == 0, "element destructor count should be 0");
164 /* Add it again, should invoke destructor on first */
165 nodep = Curl_hash_add2(&hash_static, &key1, strlen(key1), &key1,
166 my_elem_dtor);
167 fail_unless(nodep, "add2 again, insertion into hash failed");
168 fail_unless(elem_dtor_calls == 1, "element destructor count should be 1");
169 /* remove, should invoke destructor */
170 rc = Curl_hash_delete(&hash_static, &key1, strlen(key1));
171 fail_unless(rc == 0, "hash delete failed");
172 fail_unless(elem_dtor_calls == 2, "element destructor count should be 1");
173
174
175 /* Clean up */
176 Curl_hash_clean(&hash_static);
177
178 UNITTEST_STOP
179
