Coverage Report

Created: 2026-06-10 07:30

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/libyang/src/dict.c
Line
Count
Source
1
/**
2
 * @file dict.c
3
 * @author Radek Krejci <rkrejci@cesnet.cz>
4
 * @author Michal Vasko <mvasko@cesnet.cz>
5
 * @brief libyang dictionary for storing strings
6
 *
7
 * Copyright (c) 2015 - 2023 CESNET, z.s.p.o.
8
 *
9
 * This source code is licensed under BSD 3-Clause License (the "License").
10
 * You may not use this file except in compliance with the License.
11
 * You may obtain a copy of the License at
12
 *
13
 *     https://opensource.org/licenses/BSD-3-Clause
14
 */
15
16
#include "dict.h"
17
18
#include <assert.h>
19
#include <pthread.h>
20
#include <stdint.h>
21
#include <stdlib.h>
22
#include <string.h>
23
24
#include "compat.h"
25
#include "log.h"
26
#include "ly_common.h"
27
28
/* starting size of the dictionary */
29
0
#define LYDICT_MIN_SIZE 1024
30
31
/**
32
 * @brief Comparison callback for dictionary's hash table
33
 *
34
 * Implementation of ::lyht_value_equal_cb.
35
 */
36
static ly_bool
37
lydict_val_eq(void *val1_p, void *val2_p, ly_bool UNUSED(mod), void *cb_data)
38
0
{
39
0
    const char *str1, *str2;
40
0
    size_t *len1;
41
42
0
    str1 = ((struct ly_dict_rec *)val1_p)->value;
43
0
    str2 = ((struct ly_dict_rec *)val2_p)->value;
44
0
    len1 = cb_data;
45
46
0
    if (!strncmp(str1, str2, *len1) && !str2[*len1]) {
47
0
        return 1;
48
0
    }
49
50
0
    return 0;
51
0
}
52
53
void
54
lydict_init(struct ly_dict *dict)
55
0
{
56
0
    LY_CHECK_ARG_RET(NULL, dict, );
57
58
0
    dict->hash_tab = lyht_new(LYDICT_MIN_SIZE, sizeof(struct ly_dict_rec), lydict_val_eq, NULL, 1);
59
0
    LY_CHECK_ERR_RET(!dict->hash_tab, LOGINT(NULL), );
60
0
    pthread_mutex_init(&dict->lock, NULL);
61
0
}
62
63
void
64
lydict_clean(struct ly_dict *dict)
65
0
{
66
0
    struct ly_dict_rec *dict_rec = NULL;
67
0
    struct ly_ht_rec *rec = NULL;
68
0
    uint32_t hlist_idx;
69
0
    uint32_t rec_idx;
70
71
0
    if (!dict) {
72
0
        return;
73
0
    }
74
75
0
    LYHT_ITER_ALL_RECS(dict->hash_tab, hlist_idx, rec_idx, rec) {
76
        /*
77
         * this should not happen, all records inserted into
78
         * dictionary are supposed to be removed using lydict_remove()
79
         * before calling lydict_clean()
80
         */
81
0
        dict_rec = (struct ly_dict_rec *)rec->val;
82
0
        LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %" PRIu32 ".", dict_rec->value, dict_rec->refcount);
83
        /* if record wasn't removed before free string allocated for that record */
84
#ifdef NDEBUG
85
        free(dict_rec->value);
86
#endif
87
0
    }
88
89
    /* free table and destroy mutex */
90
0
    lyht_free(dict->hash_tab, NULL);
91
0
    pthread_mutex_destroy(&dict->lock);
92
0
}
93
94
static ly_bool
95
lydict_resize_val_eq(void *val1_p, void *val2_p, ly_bool mod, void *UNUSED(cb_data))
96
0
{
97
0
    const char *str1, *str2;
98
99
0
    LY_CHECK_ARG_RET(NULL, val1_p, val2_p, 0);
100
101
0
    str1 = ((struct ly_dict_rec *)val1_p)->value;
102
0
    str2 = ((struct ly_dict_rec *)val2_p)->value;
103
104
0
    if (mod) {
105
        /* used when inserting new values */
106
0
        if (strcmp(str1, str2) == 0) {
107
0
            return 1;
108
0
        }
109
0
    } else {
110
        /* used when finding the original value again in the resized table */
111
0
        if (str1 == str2) {
112
0
            return 1;
113
0
        }
114
0
    }
115
116
0
    return 0;
117
0
}
118
119
/**
120
 * @brief Remove a string from the dictionary.
121
 *
122
 * @param[in] ctx Context to use.
123
 * @param[in] dict Dictionary to remove from.
124
 * @param[in] value Value to remove.
125
 * @return LY_SUCCESS on success, LY_ERR value on error.
126
 */
127
static LY_ERR
128
_lydict_remove(const struct ly_ctx *ctx, struct ly_dict *dict, const char *value)
129
0
{
130
0
    LY_ERR ret = LY_SUCCESS;
131
0
    size_t len;
132
0
    uint32_t hash;
133
0
    struct ly_dict_rec rec, *match = NULL;
134
0
    char *val_p;
135
136
0
    LOGDBG(LY_LDGDICT, "removing \"%s\"", value);
137
138
0
    len = strlen(value);
139
0
    hash = lyht_hash(value, len);
140
141
    /* create record for lyht_find call */
142
0
    rec.value = (char *)value;
143
0
    rec.refcount = 0;
144
145
    /* set len as data for compare callback */
146
0
    lyht_set_cb_data(dict->hash_tab, (void *)&len);
147
    /* check if value is already inserted */
148
0
    ret = lyht_find(dict->hash_tab, &rec, hash, (void **)&match);
149
150
0
    if (ret == LY_SUCCESS) {
151
0
        LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), cleanup);
152
153
        /* if value is already in dictionary, decrement reference counter */
154
0
        match->refcount--;
155
0
        if (match->refcount == 0) {
156
            /*
157
             * remove record
158
             * save pointer to stored string before lyht_remove to
159
             * free it after it is removed from hash table
160
             */
161
0
            val_p = match->value;
162
0
            ret = lyht_remove_with_resize_cb(dict->hash_tab, &rec, hash, lydict_resize_val_eq);
163
0
            free(val_p);
164
0
            LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), cleanup);
165
0
        }
166
0
    } else if (ret == LY_ENOTFOUND) {
167
0
        LOGERR(ctx, LY_ENOTFOUND, "Value \"%s\" was not found in the dictionary.", value);
168
0
    } else {
169
0
        LOGINT(ctx);
170
0
    }
171
172
0
cleanup:
173
0
    return ret;
174
0
}
175
176
LY_ERR
177
lysdict_remove(const struct ly_ctx *ctx, const char *value)
178
0
{
179
0
    if (!ctx || !value) {
180
0
        return LY_SUCCESS;
181
0
    }
182
183
0
    return _lydict_remove(ctx, (struct ly_dict *)&ctx->dict, value);
184
0
}
185
186
LIBYANG_API_DEF LY_ERR
187
lydict_remove(const struct ly_ctx *ctx, const char *value)
188
0
{
189
0
    LY_ERR ret;
190
0
    struct ly_dict *dict;
191
192
0
    if (!ctx || !value) {
193
0
        return LY_SUCCESS;
194
0
    }
195
196
0
    dict = ly_ctx_data_dict_get(ctx);
197
198
0
    pthread_mutex_lock(&dict->lock);
199
0
    ret = _lydict_remove(ctx, dict, value);
200
0
    pthread_mutex_unlock(&dict->lock);
201
202
0
    return ret;
203
0
}
204
205
/**
206
 * @brief Insert a new string into the dictionary.
207
 *
208
 * @param[in] dict Dictionary to insert into.
209
 * @param[in] value Value to insert.
210
 * @param[in] len Length of @p value.
211
 * @param[in] zerocopy Whether to use the value directly or make a copy.
212
 * @param[out] str_p Optional pointer to the inserted string.
213
 * @return LY_SUCCESS on success, LY_ERR value on error.
214
 */
215
static LY_ERR
216
dict_insert(struct ly_dict *dict, char *value, size_t len, ly_bool zerocopy, const char **str_p)
217
0
{
218
0
    LY_ERR ret = LY_SUCCESS;
219
0
    struct ly_dict_rec *match = NULL, rec;
220
0
    uint32_t hash;
221
222
0
    LOGDBG(LY_LDGDICT, "inserting \"%.*s\"", (int)len, value);
223
224
0
    hash = lyht_hash(value, len);
225
    /* set len as data for compare callback */
226
0
    lyht_set_cb_data(dict->hash_tab, (void *)&len);
227
    /* create record for lyht_insert */
228
0
    rec.value = value;
229
0
    rec.refcount = 1;
230
231
0
    ret = lyht_insert_with_resize_cb(dict->hash_tab, (void *)&rec, hash, lydict_resize_val_eq, (void **)&match);
232
0
    if (ret == LY_EEXIST) {
233
0
        match->refcount++;
234
0
        if (zerocopy) {
235
0
            free(value);
236
0
        }
237
0
        ret = LY_SUCCESS;
238
0
    } else if (ret == LY_SUCCESS) {
239
0
        if (!zerocopy) {
240
            /*
241
             * allocate string for new record
242
             * record is already inserted in hash table
243
             */
244
0
            match->value = malloc(sizeof *match->value * (len + 1));
245
0
            LY_CHECK_ERR_RET(!match->value, LOGMEM(NULL), LY_EMEM);
246
0
            if (len) {
247
0
                memcpy(match->value, value, len);
248
0
            }
249
0
            match->value[len] = '\0';
250
0
        }
251
0
    } else {
252
        /* lyht_insert returned error */
253
0
        if (zerocopy) {
254
0
            free(value);
255
0
        }
256
0
        return ret;
257
0
    }
258
259
0
    *str_p = match->value;
260
261
0
    return ret;
262
0
}
263
264
LY_ERR
265
lysdict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
266
0
{
267
0
    if (!value) {
268
0
        *str_p = NULL;
269
0
        return LY_SUCCESS;
270
0
    }
271
272
0
    if (!len) {
273
0
        len = strlen(value);
274
0
    }
275
276
    /* no need to lock dict lock, because we are inserting into a schema dict,
277
     * which is thread safe unlike data parsing */
278
0
    return dict_insert((struct ly_dict *)&ctx->dict, (char *)value, len, 0, str_p);
279
0
}
280
281
LIBYANG_API_DEF LY_ERR
282
lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
283
0
{
284
0
    LY_ERR rc;
285
0
    struct ly_dict *dict;
286
287
0
    LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
288
289
0
    if (!value) {
290
0
        *str_p = NULL;
291
0
        return LY_SUCCESS;
292
0
    }
293
294
0
    if (!len) {
295
0
        len = strlen(value);
296
0
    }
297
298
0
    dict = ly_ctx_data_dict_get(ctx);
299
300
0
    pthread_mutex_lock(&dict->lock);
301
0
    rc = dict_insert(dict, (char *)value, len, 0, str_p);
302
0
    pthread_mutex_unlock(&dict->lock);
303
304
0
    return rc;
305
0
}
306
307
LY_ERR
308
lysdict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
309
0
{
310
0
    if (!value) {
311
0
        *str_p = NULL;
312
0
        return LY_SUCCESS;
313
0
    }
314
315
0
    return dict_insert((struct ly_dict *)&ctx->dict, value, strlen(value), 1, str_p);
316
0
}
317
318
LIBYANG_API_DEF LY_ERR
319
lydict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
320
0
{
321
0
    LY_ERR rc;
322
0
    struct ly_dict *dict;
323
324
0
    LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
325
326
0
    if (!value) {
327
0
        *str_p = NULL;
328
0
        return LY_SUCCESS;
329
0
    }
330
331
0
    dict = ly_ctx_data_dict_get(ctx);
332
333
0
    pthread_mutex_lock(&dict->lock);
334
0
    rc = dict_insert(dict, value, strlen(value), 1, str_p);
335
0
    pthread_mutex_unlock(&dict->lock);
336
337
0
    return rc;
338
0
}
339
340
static LY_ERR
341
dict_dup(struct ly_dict *dict, char *value, const char **str_p)
342
0
{
343
0
    LY_ERR ret = LY_SUCCESS;
344
0
    struct ly_dict_rec *match = NULL, rec;
345
0
    uint32_t hash;
346
347
    /* set new callback to only compare memory addresses */
348
0
    lyht_value_equal_cb prev = lyht_set_cb(dict->hash_tab, lydict_resize_val_eq);
349
350
0
    LOGDBG(LY_LDGDICT, "duplicating %s", value);
351
0
    hash = lyht_hash(value, strlen(value));
352
0
    rec.value = value;
353
354
0
    ret = lyht_find(dict->hash_tab, (void *)&rec, hash, (void **)&match);
355
0
    if (ret == LY_SUCCESS) {
356
        /* record found, increase refcount */
357
0
        match->refcount++;
358
0
        *str_p = match->value;
359
0
    }
360
361
    /* restore callback */
362
0
    lyht_set_cb(dict->hash_tab, prev);
363
364
0
    return ret;
365
0
}
366
367
LY_ERR
368
lysdict_dup(const struct ly_ctx *ctx, const char *value, const char **str_p)
369
0
{
370
0
    if (!value) {
371
0
        *str_p = NULL;
372
0
        return LY_SUCCESS;
373
0
    }
374
375
0
    return dict_dup((struct ly_dict *)&ctx->dict, (char *)value, str_p);
376
0
}
377
378
LIBYANG_API_DEF LY_ERR
379
lydict_dup(const struct ly_ctx *ctx, const char *value, const char **str_p)
380
0
{
381
0
    LY_ERR rc;
382
0
    struct ly_dict *dict;
383
384
0
    LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
385
386
0
    if (!value) {
387
0
        *str_p = NULL;
388
0
        return LY_SUCCESS;
389
0
    }
390
391
0
    dict = ly_ctx_data_dict_get(ctx);
392
393
0
    pthread_mutex_lock(&dict->lock);
394
0
    rc = dict_dup(dict, (char *)value, str_p);
395
0
    pthread_mutex_unlock(&dict->lock);
396
397
0
    return rc;
398
0
}