blob: bdaafb86b814cd29ef94932830ca4f97070de6d6 [file] [log] [blame]
Zhe Wang8ae3b112019-06-18 13:23:54 +08001/*
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.ren004fee82024-06-26 03:21:54 +000039#include "aml_malloc_debug.h"
40
Zhe Wang8ae3b112019-06-18 13:23:54 +080041/** 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/*--------------------------------------------------------------------------*/
64static 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.ren004fee82024-06-26 03:21:54 +000073 t = (char*)aml_audio_malloc(len);
Zhe Wang8ae3b112019-06-18 13:23:54 +080074
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/*--------------------------------------------------------------------------*/
89static int dictionary_grow(dictionary *d)
90{
91 char **new_val;
92 char **new_key;
93 unsigned *new_hash;
94
haiyang.ren004fee82024-06-26 03:21:54 +000095 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 Wang8ae3b112019-06-18 13:23:54 +080098
99 if (!new_val || !new_key || !new_hash) {
100 /* An allocation failed, leave the dictionary unchanged */
101 if (new_val)
haiyang.ren004fee82024-06-26 03:21:54 +0000102 aml_audio_free(new_val);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800103 if (new_key)
haiyang.ren004fee82024-06-26 03:21:54 +0000104 aml_audio_free(new_key);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800105 if (new_hash)
haiyang.ren004fee82024-06-26 03:21:54 +0000106 aml_audio_free(new_hash);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800107 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.ren004fee82024-06-26 03:21:54 +0000116 aml_audio_free(d->val);
117 aml_audio_free(d->key);
118 aml_audio_free(d->hash);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800119
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/*--------------------------------------------------------------------------*/
144unsigned 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/*-------------------------------------------------------------------------*/
178dictionary *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.ren004fee82024-06-26 03:21:54 +0000186 d = (dictionary*)aml_audio_calloc(1, sizeof *d);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800187
188 if (d) {
189 d->size = size;
haiyang.ren004fee82024-06-26 03:21:54 +0000190 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 Wang8ae3b112019-06-18 13:23:54 +0800193 }
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/*--------------------------------------------------------------------------*/
206void 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.ren004fee82024-06-26 03:21:54 +0000215 aml_audio_free(d->key[i]);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800216 if (d->val[i] != NULL)
haiyang.ren004fee82024-06-26 03:21:54 +0000217 aml_audio_free(d->val[i]);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800218 }
haiyang.ren004fee82024-06-26 03:21:54 +0000219 aml_audio_free(d->val);
220 aml_audio_free(d->key);
221 aml_audio_free(d->hash);
222 aml_audio_free(d);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800223 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/*--------------------------------------------------------------------------*/
240const 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/*--------------------------------------------------------------------------*/
288int 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.ren004fee82024-06-26 03:21:54 +0000307 aml_audio_free(d->val[i]);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800308 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/*--------------------------------------------------------------------------*/
349void 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.ren004fee82024-06-26 03:21:54 +0000374 aml_audio_free(d->key[i]);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800375 d->key[i] = NULL;
376 if (d->val[i] != NULL) {
haiyang.ren004fee82024-06-26 03:21:54 +0000377 aml_audio_free(d->val[i]);
Zhe Wang8ae3b112019-06-18 13:23:54 +0800378 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/*--------------------------------------------------------------------------*/
397void 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}