Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2017 Amlogic Corporation. |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | /*-------------------------------------------------------------------------*/ |
| 18 | /** |
| 19 | @file dictionary.c |
| 20 | @author N. Devillard |
| 21 | @brief Implements a dictionary for string variables. |
| 22 | |
| 23 | This module implements a simple dictionary object, i.e. a list |
| 24 | of string/string associations. This object is useful to store e.g. |
| 25 | informations retrieved from a configuration file (ini files). |
| 26 | */ |
| 27 | /*--------------------------------------------------------------------------*/ |
| 28 | |
| 29 | /*--------------------------------------------------------------------------- |
| 30 | Includes |
| 31 | ---------------------------------------------------------------------------*/ |
| 32 | #include "dictionary.h" |
| 33 | |
| 34 | #include <stdio.h> |
| 35 | #include <stdlib.h> |
| 36 | #include <string.h> |
| 37 | #include <unistd.h> |
| 38 | |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 39 | #include "aml_malloc_debug.h" |
| 40 | |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 41 | /** Maximum value size for integers and doubles. */ |
| 42 | #define MAXVALSZ 1024 |
| 43 | |
| 44 | /** Minimal allocated number of entries in a dictionary */ |
| 45 | #define DICTMINSZ 128 |
| 46 | |
| 47 | /** Invalid key token */ |
| 48 | #define DICT_INVALID_KEY ((char*)-1) |
| 49 | |
| 50 | /*--------------------------------------------------------------------------- |
| 51 | Private functions |
| 52 | ---------------------------------------------------------------------------*/ |
| 53 | |
| 54 | /*-------------------------------------------------------------------------*/ |
| 55 | /** |
| 56 | @brief Duplicate a string |
| 57 | @param s String to duplicate |
| 58 | @return Pointer to a newly allocated string, to be freed with free() |
| 59 | |
| 60 | This is a replacement for strdup(). This implementation is provided |
| 61 | for systems that do not have it. |
| 62 | */ |
| 63 | /*--------------------------------------------------------------------------*/ |
| 64 | static char *xstrdup(const char *s) |
| 65 | { |
| 66 | char *t; |
| 67 | size_t len; |
| 68 | |
| 69 | if (!s) |
| 70 | return NULL; |
| 71 | |
| 72 | len = strlen(s) + 1; |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 73 | t = (char*)aml_audio_malloc(len); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 74 | |
| 75 | if (t) { |
| 76 | memcpy(t, s, len); |
| 77 | } |
| 78 | |
| 79 | return t; |
| 80 | } |
| 81 | |
| 82 | /*-------------------------------------------------------------------------*/ |
| 83 | /** |
| 84 | @brief Double the size of the dictionary |
| 85 | @param d Dictionary to grow |
| 86 | @return This function returns non-zero in case of failure |
| 87 | */ |
| 88 | /*--------------------------------------------------------------------------*/ |
| 89 | static int dictionary_grow(dictionary *d) |
| 90 | { |
| 91 | char **new_val; |
| 92 | char **new_key; |
| 93 | unsigned *new_hash; |
| 94 | |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 95 | new_val = (char**)aml_audio_calloc(d->size * 2, sizeof *d->val); |
| 96 | new_key = (char**)aml_audio_calloc(d->size * 2, sizeof *d->key); |
| 97 | new_hash = (unsigned*)aml_audio_calloc(d->size * 2, sizeof *d->hash); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 98 | |
| 99 | if (!new_val || !new_key || !new_hash) { |
| 100 | /* An allocation failed, leave the dictionary unchanged */ |
| 101 | if (new_val) |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 102 | aml_audio_free(new_val); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 103 | if (new_key) |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 104 | aml_audio_free(new_key); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 105 | if (new_hash) |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 106 | aml_audio_free(new_hash); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 107 | return -1; |
| 108 | } |
| 109 | |
| 110 | /* Initialize the newly allocated space */ |
| 111 | memcpy(new_val, d->val, d->size * sizeof(char *)); |
| 112 | memcpy(new_key, d->key, d->size * sizeof(char *)); |
| 113 | memcpy(new_hash, d->hash, d->size * sizeof(unsigned)); |
| 114 | |
| 115 | /* Delete previous data */ |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 116 | aml_audio_free(d->val); |
| 117 | aml_audio_free(d->key); |
| 118 | aml_audio_free(d->hash); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 119 | |
| 120 | /* Actually update the dictionary */ |
| 121 | d->size *= 2; |
| 122 | d->val = new_val; |
| 123 | d->key = new_key; |
| 124 | d->hash = new_hash; |
| 125 | |
| 126 | return 0; |
| 127 | } |
| 128 | |
| 129 | /*--------------------------------------------------------------------------- |
| 130 | Function codes |
| 131 | ---------------------------------------------------------------------------*/ |
| 132 | /*-------------------------------------------------------------------------*/ |
| 133 | /** |
| 134 | @brief Compute the hash key for a string. |
| 135 | @param key Character string to use for key. |
| 136 | @return 1 unsigned int on at least 32 bits. |
| 137 | |
| 138 | This hash function has been taken from an Article in Dr Dobbs Journal. |
| 139 | This is normally a collision-free function, distributing keys evenly. |
| 140 | The key is stored anyway in the struct so that collision can be avoided |
| 141 | by comparing the key itself in last resort. |
| 142 | */ |
| 143 | /*--------------------------------------------------------------------------*/ |
| 144 | unsigned dictionary_hash(const char *key) |
| 145 | { |
| 146 | size_t len; |
| 147 | unsigned hash; |
| 148 | size_t i; |
| 149 | |
| 150 | if (!key) |
| 151 | return 0; |
| 152 | |
| 153 | len = strlen(key); |
| 154 | for (hash = 0, i = 0; i < len; i++) { |
| 155 | hash += (unsigned)key[i]; |
| 156 | hash += (hash << 10); |
| 157 | hash ^= (hash >> 6); |
| 158 | } |
| 159 | |
| 160 | hash += (hash << 3); |
| 161 | hash ^= (hash >> 11); |
| 162 | hash += (hash << 15); |
| 163 | |
| 164 | return hash; |
| 165 | } |
| 166 | |
| 167 | /*-------------------------------------------------------------------------*/ |
| 168 | /** |
| 169 | @brief Create a new dictionary object. |
| 170 | @param size Optional initial size of the dictionary. |
| 171 | @return 1 newly allocated dictionary objet. |
| 172 | |
| 173 | This function allocates a new dictionary object of given size and returns |
| 174 | it. If you do not know in advance (roughly) the number of entries in the |
| 175 | dictionary, give size=0. |
| 176 | */ |
| 177 | /*-------------------------------------------------------------------------*/ |
| 178 | dictionary *dictionary_new(size_t size) |
| 179 | { |
| 180 | dictionary *d; |
| 181 | |
| 182 | /* If no size was specified, allocate space for DICTMINSZ */ |
| 183 | if (size < DICTMINSZ) |
| 184 | size = DICTMINSZ; |
| 185 | |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 186 | d = (dictionary*)aml_audio_calloc(1, sizeof *d); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 187 | |
| 188 | if (d) { |
| 189 | d->size = size; |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 190 | d->val = (char**)aml_audio_calloc(size, sizeof *d->val); |
| 191 | d->key = (char**)aml_audio_calloc(size, sizeof *d->key); |
| 192 | d->hash = (unsigned*)aml_audio_calloc(size, sizeof *d->hash); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 193 | } |
| 194 | return d; |
| 195 | } |
| 196 | |
| 197 | /*-------------------------------------------------------------------------*/ |
| 198 | /** |
| 199 | @brief Delete a dictionary object |
| 200 | @param d dictionary object to deallocate. |
| 201 | @return void |
| 202 | |
| 203 | Deallocate a dictionary object and all memory associated to it. |
| 204 | */ |
| 205 | /*--------------------------------------------------------------------------*/ |
| 206 | void dictionary_del(dictionary *d) |
| 207 | { |
| 208 | ssize_t i; |
| 209 | |
| 210 | if (d == NULL) |
| 211 | return; |
| 212 | |
| 213 | for (i = 0; i < d->size; i++) { |
| 214 | if (d->key[i] != NULL) |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 215 | aml_audio_free(d->key[i]); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 216 | if (d->val[i] != NULL) |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 217 | aml_audio_free(d->val[i]); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 218 | } |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 219 | aml_audio_free(d->val); |
| 220 | aml_audio_free(d->key); |
| 221 | aml_audio_free(d->hash); |
| 222 | aml_audio_free(d); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 223 | return; |
| 224 | } |
| 225 | |
| 226 | /*-------------------------------------------------------------------------*/ |
| 227 | /** |
| 228 | @brief Get a value from a dictionary. |
| 229 | @param d dictionary object to search. |
| 230 | @param key Key to look for in the dictionary. |
| 231 | @param def Default value to return if key not found. |
| 232 | @return 1 pointer to internally allocated character string. |
| 233 | |
| 234 | This function locates a key in a dictionary and returns a pointer to its |
| 235 | value, or the passed 'def' pointer if no such key can be found in |
| 236 | dictionary. The returned character pointer points to data internal to the |
| 237 | dictionary object, you should not try to free it or modify it. |
| 238 | */ |
| 239 | /*--------------------------------------------------------------------------*/ |
| 240 | const char * dictionary_get(const dictionary *d, const char *key, const char *def) |
| 241 | { |
| 242 | unsigned hash; |
| 243 | ssize_t i; |
| 244 | |
| 245 | hash = dictionary_hash(key); |
| 246 | |
| 247 | for (i = 0; i < d->size; i++) { |
| 248 | if (d->key[i] == NULL) |
| 249 | continue; |
| 250 | |
| 251 | /* Compare hash */ |
| 252 | if (hash == d->hash[i]) { |
| 253 | /* Compare string, to avoid hash collisions */ |
| 254 | if (!strcmp(key, d->key[i])) { |
| 255 | return d->val[i]; |
| 256 | } |
| 257 | } |
| 258 | } |
| 259 | return def; |
| 260 | } |
| 261 | |
| 262 | /*-------------------------------------------------------------------------*/ |
| 263 | /** |
| 264 | @brief Set a value in a dictionary. |
| 265 | @param d dictionary object to modify. |
| 266 | @param key Key to modify or add. |
| 267 | @param val Value to add. |
| 268 | @return int 0 if Ok, anything else otherwise |
| 269 | |
| 270 | If the given key is found in the dictionary, the associated value is |
| 271 | replaced by the provided one. If the key cannot be found in the |
| 272 | dictionary, it is added to it. |
| 273 | |
| 274 | It is Ok to provide a NULL value for val, but NULL values for the dictionary |
| 275 | or the key are considered as errors: the function will return immediately |
| 276 | in such a case. |
| 277 | |
| 278 | Notice that if you dictionary_set a variable to NULL, a call to |
| 279 | dictionary_get will return a NULL value: the variable will be found, and |
| 280 | its value (NULL) is returned. In other words, setting the variable |
| 281 | content to NULL is equivalent to deleting the variable from the |
| 282 | dictionary. It is not possible (in this implementation) to have a key in |
| 283 | the dictionary without value. |
| 284 | |
| 285 | This function returns non-zero in case of failure. |
| 286 | */ |
| 287 | /*--------------------------------------------------------------------------*/ |
| 288 | int dictionary_set(dictionary *d, const char *key, const char *val) |
| 289 | { |
| 290 | ssize_t i; |
| 291 | unsigned hash; |
| 292 | |
| 293 | if (d == NULL || key == NULL) |
| 294 | return -1; |
| 295 | |
| 296 | /* Compute hash for this key */ |
| 297 | hash = dictionary_hash(key); |
| 298 | /* Find if value is already in dictionary */ |
| 299 | if (d->n > 0) { |
| 300 | for (i = 0; i < d->size; i++) { |
| 301 | if (d->key[i] == NULL) |
| 302 | continue; |
| 303 | if (hash == d->hash[i]) { /* Same hash value */ |
| 304 | if (!strcmp(key, d->key[i])) { /* Same key */ |
| 305 | /* Found a value: modify and return */ |
| 306 | if (d->val[i] != NULL) |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 307 | aml_audio_free(d->val[i]); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 308 | d->val[i] = (val ? xstrdup(val) : NULL); |
| 309 | /* Value has been modified: return */ |
| 310 | return 0; |
| 311 | } |
| 312 | } |
| 313 | } |
| 314 | } |
| 315 | /* Add a new value */ |
| 316 | /* See if dictionary needs to grow */ |
| 317 | if (d->n == d->size) { |
| 318 | /* Reached maximum size: reallocate dictionary */ |
| 319 | if (dictionary_grow(d) != 0) |
| 320 | return -1; |
| 321 | } |
| 322 | |
| 323 | /* Insert key in the first empty slot. Start at d->n and wrap at |
| 324 | d->size. Because d->n < d->size this will necessarily |
| 325 | terminate. */ |
| 326 | for (i = d->n; d->key[i]; ) { |
| 327 | if (++i == d->size) |
| 328 | i = 0; |
| 329 | } |
| 330 | /* Copy key */ |
| 331 | d->key[i] = xstrdup(key); |
| 332 | d->val[i] = (val ? xstrdup(val) : NULL); |
| 333 | d->hash[i] = hash; |
| 334 | d->n++; |
| 335 | return 0; |
| 336 | } |
| 337 | |
| 338 | /*-------------------------------------------------------------------------*/ |
| 339 | /** |
| 340 | @brief Delete a key in a dictionary |
| 341 | @param d dictionary object to modify. |
| 342 | @param key Key to remove. |
| 343 | @return void |
| 344 | |
| 345 | This function deletes a key in a dictionary. Nothing is done if the |
| 346 | key cannot be found. |
| 347 | */ |
| 348 | /*--------------------------------------------------------------------------*/ |
| 349 | void dictionary_unset(dictionary *d, const char *key) |
| 350 | { |
| 351 | unsigned hash; |
| 352 | ssize_t i; |
| 353 | |
| 354 | if (key == NULL || d == NULL) |
| 355 | return; |
| 356 | |
| 357 | hash = dictionary_hash(key); |
| 358 | for (i = 0; i < d->size; i++) { |
| 359 | if (d->key[i] == NULL) |
| 360 | continue; |
| 361 | /* Compare hash */ |
| 362 | if (hash == d->hash[i]) { |
| 363 | /* Compare string, to avoid hash collisions */ |
| 364 | if (!strcmp(key, d->key[i])) { |
| 365 | /* Found key */ |
| 366 | break; |
| 367 | } |
| 368 | } |
| 369 | } |
| 370 | if (i >= d->size) |
| 371 | /* Key not found */ |
| 372 | return; |
| 373 | |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 374 | aml_audio_free(d->key[i]); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 375 | d->key[i] = NULL; |
| 376 | if (d->val[i] != NULL) { |
haiyang.ren | 004fee8 | 2024-06-26 03:21:54 +0000 | [diff] [blame] | 377 | aml_audio_free(d->val[i]); |
Zhe Wang | 8ae3b11 | 2019-06-18 13:23:54 +0800 | [diff] [blame] | 378 | d->val[i] = NULL; |
| 379 | } |
| 380 | d->hash[i] = 0; |
| 381 | d->n--; |
| 382 | return; |
| 383 | } |
| 384 | |
| 385 | /*-------------------------------------------------------------------------*/ |
| 386 | /** |
| 387 | @brief Dump a dictionary to an opened file pointer. |
| 388 | @param d Dictionary to dump |
| 389 | @param f Opened file pointer. |
| 390 | @return void |
| 391 | |
| 392 | Dumps a dictionary onto an opened file pointer. Key pairs are printed out |
| 393 | as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as |
| 394 | output file pointers. |
| 395 | */ |
| 396 | /*--------------------------------------------------------------------------*/ |
| 397 | void dictionary_dump(const dictionary *d, FILE *out) |
| 398 | { |
| 399 | ssize_t i; |
| 400 | |
| 401 | if (d == NULL || out == NULL) |
| 402 | return; |
| 403 | |
| 404 | if (d->n < 1) { |
| 405 | fprintf(out, "empty dictionary\n"); |
| 406 | return; |
| 407 | } |
| 408 | |
| 409 | for (i = 0; i < d->size; i++) { |
| 410 | if (d->key[i]) { |
| 411 | fprintf(out, "%20s\t[%s]\n", |
| 412 | d->key[i], |
| 413 | d->val[i] ? d->val[i] : "UNDEF"); |
| 414 | } |
| 415 | } |
| 416 | |
| 417 | return; |
| 418 | } |