blob: a8806962cfa18016c47bc72b4de03081ac48fa23 [file] [log] [blame]
Michal Vaskoae130f52023-04-20 14:25:16 +02001/**
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
Michal Vaskoae130f52023-04-20 14:25:16 +020024#include "compat.h"
25#include "log.h"
Michal Vasko8f702ee2024-02-20 15:44:24 +010026#include "ly_common.h"
Michal Vaskoae130f52023-04-20 14:25:16 +020027
28/* starting size of the dictionary */
29#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 */
36static ly_bool
37lydict_val_eq(void *val1_p, void *val2_p, ly_bool UNUSED(mod), void *cb_data)
38{
Michal Vaskode17be12023-09-29 14:09:53 +020039 const char *str1, *str2;
40 size_t *len1;
41
Michal Vaskoae130f52023-04-20 14:25:16 +020042 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, cb_data, 0);
43
Michal Vaskode17be12023-09-29 14:09:53 +020044 str1 = ((struct ly_dict_rec *)val1_p)->value;
45 str2 = ((struct ly_dict_rec *)val2_p)->value;
46 len1 = cb_data;
Michal Vaskoae130f52023-04-20 14:25:16 +020047
48 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
49 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
50
Michal Vaskode17be12023-09-29 14:09:53 +020051 if (!strncmp(str1, str2, *len1) && !str2[*len1]) {
Michal Vaskoae130f52023-04-20 14:25:16 +020052 return 1;
53 }
54
55 return 0;
56}
57
58void
59lydict_init(struct ly_dict *dict)
60{
61 LY_CHECK_ARG_RET(NULL, dict, );
62
63 dict->hash_tab = lyht_new(LYDICT_MIN_SIZE, sizeof(struct ly_dict_rec), lydict_val_eq, NULL, 1);
64 LY_CHECK_ERR_RET(!dict->hash_tab, LOGINT(NULL), );
65 pthread_mutex_init(&dict->lock, NULL);
66}
67
68void
69lydict_clean(struct ly_dict *dict)
70{
71 struct ly_dict_rec *dict_rec = NULL;
72 struct ly_ht_rec *rec = NULL;
Olivier Matz75c00192023-09-21 14:35:12 +020073 uint32_t hlist_idx;
74 uint32_t rec_idx;
Michal Vaskoae130f52023-04-20 14:25:16 +020075
76 LY_CHECK_ARG_RET(NULL, dict, );
77
Olivier Matz75c00192023-09-21 14:35:12 +020078 LYHT_ITER_ALL_RECS(dict->hash_tab, hlist_idx, rec_idx, rec) {
79 /*
80 * this should not happen, all records inserted into
81 * dictionary are supposed to be removed using lydict_remove()
82 * before calling lydict_clean()
83 */
84 dict_rec = (struct ly_dict_rec *)rec->val;
Michal Vasko21eaa392024-02-20 15:48:42 +010085 LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %" PRIu32 ".", dict_rec->value, dict_rec->refcount);
Olivier Matz75c00192023-09-21 14:35:12 +020086 /* if record wasn't removed before free string allocated for that record */
Michal Vaskoae130f52023-04-20 14:25:16 +020087#ifdef NDEBUG
Olivier Matz75c00192023-09-21 14:35:12 +020088 free(dict_rec->value);
Michal Vaskoae130f52023-04-20 14:25:16 +020089#endif
Michal Vaskoae130f52023-04-20 14:25:16 +020090 }
91
92 /* free table and destroy mutex */
93 lyht_free(dict->hash_tab, NULL);
94 pthread_mutex_destroy(&dict->lock);
95}
96
97static ly_bool
Michal Vaskoc6a1fe62023-09-29 14:10:33 +020098lydict_resize_val_eq(void *val1_p, void *val2_p, ly_bool mod, void *UNUSED(cb_data))
Michal Vaskoae130f52023-04-20 14:25:16 +020099{
Michal Vaskoc6a1fe62023-09-29 14:10:33 +0200100 const char *str1, *str2;
101
Michal Vaskoae130f52023-04-20 14:25:16 +0200102 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, 0);
103
Michal Vaskoc6a1fe62023-09-29 14:10:33 +0200104 str1 = ((struct ly_dict_rec *)val1_p)->value;
105 str2 = ((struct ly_dict_rec *)val2_p)->value;
Michal Vaskoae130f52023-04-20 14:25:16 +0200106
Michal Vaskoae130f52023-04-20 14:25:16 +0200107 if (mod) {
108 /* used when inserting new values */
109 if (strcmp(str1, str2) == 0) {
110 return 1;
111 }
112 } else {
113 /* used when finding the original value again in the resized table */
Michal Vaskoc6a1fe62023-09-29 14:10:33 +0200114 if (str1 == str2) {
115 return 1;
116 }
Michal Vaskoae130f52023-04-20 14:25:16 +0200117 }
118
119 return 0;
120}
121
122LIBYANG_API_DEF LY_ERR
123lydict_remove(const struct ly_ctx *ctx, const char *value)
124{
125 LY_ERR ret = LY_SUCCESS;
126 size_t len;
127 uint32_t hash;
128 struct ly_dict_rec rec, *match = NULL;
129 char *val_p;
130
131 if (!ctx || !value) {
132 return LY_SUCCESS;
133 }
134
135 LOGDBG(LY_LDGDICT, "removing \"%s\"", value);
136
137 len = strlen(value);
138 hash = lyht_hash(value, len);
139
140 /* create record for lyht_find call */
141 rec.value = (char *)value;
142 rec.refcount = 0;
143
144 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
145 /* set len as data for compare callback */
146 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
147 /* check if value is already inserted */
148 ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
149
150 if (ret == LY_SUCCESS) {
151 LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
152
153 /* if value is already in dictionary, decrement reference counter */
154 match->refcount--;
155 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 val_p = match->value;
162 ret = lyht_remove_with_resize_cb(ctx->dict.hash_tab, &rec, hash, lydict_resize_val_eq);
163 free(val_p);
164 LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
165 }
166 } else if (ret == LY_ENOTFOUND) {
167 LOGERR(ctx, LY_ENOTFOUND, "Value \"%s\" was not found in the dictionary.", value);
168 } else {
169 LOGINT(ctx);
170 }
171
172finish:
173 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
174 return ret;
175}
176
Michal Vaskoa26f9ae2024-09-09 15:16:44 +0200177static LY_ERR
Michal Vaskoae130f52023-04-20 14:25:16 +0200178dict_insert(const struct ly_ctx *ctx, char *value, size_t len, ly_bool zerocopy, const char **str_p)
179{
180 LY_ERR ret = LY_SUCCESS;
181 struct ly_dict_rec *match = NULL, rec;
182 uint32_t hash;
183
184 LOGDBG(LY_LDGDICT, "inserting \"%.*s\"", (int)len, value);
185
186 hash = lyht_hash(value, len);
187 /* set len as data for compare callback */
188 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
189 /* create record for lyht_insert */
190 rec.value = value;
191 rec.refcount = 1;
192
193 ret = lyht_insert_with_resize_cb(ctx->dict.hash_tab, (void *)&rec, hash, lydict_resize_val_eq, (void **)&match);
194 if (ret == LY_EEXIST) {
195 match->refcount++;
196 if (zerocopy) {
197 free(value);
198 }
199 ret = LY_SUCCESS;
200 } else if (ret == LY_SUCCESS) {
201 if (!zerocopy) {
202 /*
203 * allocate string for new record
204 * record is already inserted in hash table
205 */
206 match->value = malloc(sizeof *match->value * (len + 1));
207 LY_CHECK_ERR_RET(!match->value, LOGMEM(ctx), LY_EMEM);
208 if (len) {
209 memcpy(match->value, value, len);
210 }
211 match->value[len] = '\0';
212 }
213 } else {
214 /* lyht_insert returned error */
215 if (zerocopy) {
216 free(value);
217 }
218 return ret;
219 }
220
Michal Vaskoa26f9ae2024-09-09 15:16:44 +0200221 *str_p = match->value;
Michal Vaskoae130f52023-04-20 14:25:16 +0200222
223 return ret;
224}
225
226LIBYANG_API_DEF LY_ERR
227lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
228{
229 LY_ERR result;
230
231 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
232
233 if (!value) {
234 *str_p = NULL;
235 return LY_SUCCESS;
236 }
237
238 if (!len) {
239 len = strlen(value);
240 }
241
242 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
243 result = dict_insert(ctx, (char *)value, len, 0, str_p);
244 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
245
246 return result;
247}
248
249LIBYANG_API_DEF LY_ERR
250lydict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
251{
252 LY_ERR result;
253
254 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
255
256 if (!value) {
257 *str_p = NULL;
258 return LY_SUCCESS;
259 }
260
261 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
262 result = dict_insert(ctx, value, strlen(value), 1, str_p);
263 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
264
265 return result;
266}