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