uint-hash.c (6018B)
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 25 #include "curl_setup.h" 26 27 #include <curl/curl.h> 28 29 #include "uint-hash.h" 30 #include "curl_memory.h" 31 32 /* The last #include file should be: */ 33 #include "memdebug.h" 34 35 /* random patterns for API verification */ 36 #ifdef DEBUGBUILD 37 #define CURL_UINTHASHINIT 0x7117e779 38 #endif 39 40 static unsigned int uint_hash_hash(unsigned int id, unsigned int slots) 41 { 42 return (id % slots); 43 } 44 45 46 struct uint_hash_entry { 47 struct uint_hash_entry *next; 48 void *value; 49 unsigned int id; 50 }; 51 52 void Curl_uint_hash_init(struct uint_hash *h, 53 unsigned int slots, 54 Curl_uint_hash_dtor *dtor) 55 { 56 DEBUGASSERT(h); 57 DEBUGASSERT(slots); 58 59 h->table = NULL; 60 h->dtor = dtor; 61 h->size = 0; 62 h->slots = slots; 63 #ifdef DEBUGBUILD 64 h->init = CURL_UINTHASHINIT; 65 #endif 66 } 67 68 static struct uint_hash_entry *uint_hash_mk_entry(unsigned int id, void *value) 69 { 70 struct uint_hash_entry *e; 71 72 /* allocate the struct for the hash entry */ 73 e = malloc(sizeof(*e)); 74 if(e) { 75 e->id = id; 76 e->next = NULL; 77 e->value = value; 78 } 79 return e; 80 } 81 82 static void uint_hash_entry_clear(struct uint_hash *h, 83 struct uint_hash_entry *e) 84 { 85 DEBUGASSERT(h); 86 DEBUGASSERT(e); 87 if(e->value) { 88 if(h->dtor) 89 h->dtor(e->id, e->value); 90 e->value = NULL; 91 } 92 } 93 94 static void uint_hash_entry_destroy(struct uint_hash *h, 95 struct uint_hash_entry *e) 96 { 97 uint_hash_entry_clear(h, e); 98 free(e); 99 } 100 101 static void uint_hash_entry_unlink(struct uint_hash *h, 102 struct uint_hash_entry **he_anchor, 103 struct uint_hash_entry *he) 104 { 105 *he_anchor = he->next; 106 --h->size; 107 } 108 109 static void uint_hash_elem_link(struct uint_hash *h, 110 struct uint_hash_entry **he_anchor, 111 struct uint_hash_entry *he) 112 { 113 he->next = *he_anchor; 114 *he_anchor = he; 115 ++h->size; 116 } 117 118 #define CURL_UINT_HASH_SLOT(h,id) h->table[uint_hash_hash(id, h->slots)] 119 #define CURL_UINT_HASH_SLOT_ADDR(h,id) &CURL_UINT_HASH_SLOT(h,id) 120 121 bool Curl_uint_hash_set(struct uint_hash *h, unsigned int id, void *value) 122 { 123 struct uint_hash_entry *he, **slot; 124 125 DEBUGASSERT(h); 126 DEBUGASSERT(h->slots); 127 DEBUGASSERT(h->init == CURL_UINTHASHINIT); 128 if(!h->table) { 129 h->table = calloc(h->slots, sizeof(*he)); 130 if(!h->table) 131 return FALSE; /* OOM */ 132 } 133 134 slot = CURL_UINT_HASH_SLOT_ADDR(h, id); 135 for(he = *slot; he; he = he->next) { 136 if(he->id == id) { 137 /* existing key entry, overwrite by clearing old pointer */ 138 uint_hash_entry_clear(h, he); 139 he->value = value; 140 return TRUE; 141 } 142 } 143 144 he = uint_hash_mk_entry(id, value); 145 if(!he) 146 return FALSE; /* OOM */ 147 148 uint_hash_elem_link(h, slot, he); 149 return TRUE; 150 } 151 152 bool Curl_uint_hash_remove(struct uint_hash *h, unsigned int id) 153 { 154 DEBUGASSERT(h); 155 DEBUGASSERT(h->slots); 156 DEBUGASSERT(h->init == CURL_UINTHASHINIT); 157 if(h->table) { 158 struct uint_hash_entry *he, **he_anchor; 159 160 he_anchor = CURL_UINT_HASH_SLOT_ADDR(h, id); 161 while(*he_anchor) { 162 he = *he_anchor; 163 if(id == he->id) { 164 uint_hash_entry_unlink(h, he_anchor, he); 165 uint_hash_entry_destroy(h, he); 166 return TRUE; 167 } 168 he_anchor = &he->next; 169 } 170 } 171 return FALSE; 172 } 173 174 void *Curl_uint_hash_get(struct uint_hash *h, unsigned int id) 175 { 176 DEBUGASSERT(h); 177 DEBUGASSERT(h->init == CURL_UINTHASHINIT); 178 if(h->table) { 179 struct uint_hash_entry *he; 180 DEBUGASSERT(h->slots); 181 he = CURL_UINT_HASH_SLOT(h, id); 182 while(he) { 183 if(id == he->id) { 184 return he->value; 185 } 186 he = he->next; 187 } 188 } 189 return NULL; 190 } 191 192 static void uint_hash_clear(struct uint_hash *h) 193 { 194 if(h && h->table) { 195 struct uint_hash_entry *he, **he_anchor; 196 size_t i; 197 DEBUGASSERT(h->init == CURL_UINTHASHINIT); 198 for(i = 0; i < h->slots; ++i) { 199 he_anchor = &h->table[i]; 200 while(*he_anchor) { 201 he = *he_anchor; 202 uint_hash_entry_unlink(h, he_anchor, he); 203 uint_hash_entry_destroy(h, he); 204 } 205 } 206 } 207 } 208 209 #ifdef UNITTESTS 210 UNITTEST void Curl_uint_hash_clear(struct uint_hash *h) 211 { 212 uint_hash_clear(h); 213 } 214 #endif 215 216 void Curl_uint_hash_destroy(struct uint_hash *h) 217 { 218 DEBUGASSERT(h->init == CURL_UINTHASHINIT); 219 if(h->table) { 220 uint_hash_clear(h); 221 Curl_safefree(h->table); 222 } 223 DEBUGASSERT(h->size == 0); 224 h->slots = 0; 225 } 226 227 unsigned int Curl_uint_hash_count(struct uint_hash *h) 228 { 229 DEBUGASSERT(h->init == CURL_UINTHASHINIT); 230 return h->size; 231 } 232 233 void Curl_uint_hash_visit(struct uint_hash *h, 234 Curl_uint_hash_visit_cb *cb, 235 void *user_data) 236 { 237 if(h && h->table && cb) { 238 struct uint_hash_entry *he; 239 size_t i; 240 DEBUGASSERT(h->init == CURL_UINTHASHINIT); 241 for(i = 0; i < h->slots; ++i) { 242 for(he = h->table[i]; he; he = he->next) { 243 if(!cb(he->id, he->value, user_data)) 244 return; 245 } 246 } 247 } 248 }