blob: bf495611fe31d738ba6887fc5494bbe8a8da9147 [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;
85 LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
86 /* 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
107 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
108 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
109
110 if (mod) {
111 /* used when inserting new values */
112 if (strcmp(str1, str2) == 0) {
113 return 1;
114 }
115 } else {
116 /* used when finding the original value again in the resized table */
Michal Vaskoc6a1fe62023-09-29 14:10:33 +0200117 if (str1 == str2) {
118 return 1;
119 }
Michal Vaskoae130f52023-04-20 14:25:16 +0200120 }
121
122 return 0;
123}
124
125LIBYANG_API_DEF LY_ERR
126lydict_remove(const struct ly_ctx *ctx, const char *value)
127{
128 LY_ERR ret = LY_SUCCESS;
129 size_t len;
130 uint32_t hash;
131 struct ly_dict_rec rec, *match = NULL;
132 char *val_p;
133
134 if (!ctx || !value) {
135 return LY_SUCCESS;
136 }
137
138 LOGDBG(LY_LDGDICT, "removing \"%s\"", value);
139
140 len = strlen(value);
141 hash = lyht_hash(value, len);
142
143 /* create record for lyht_find call */
144 rec.value = (char *)value;
145 rec.refcount = 0;
146
147 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
148 /* set len as data for compare callback */
149 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
150 /* check if value is already inserted */
151 ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
152
153 if (ret == LY_SUCCESS) {
154 LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
155
156 /* if value is already in dictionary, decrement reference counter */
157 match->refcount--;
158 if (match->refcount == 0) {
159 /*
160 * remove record
161 * save pointer to stored string before lyht_remove to
162 * free it after it is removed from hash table
163 */
164 val_p = match->value;
165 ret = lyht_remove_with_resize_cb(ctx->dict.hash_tab, &rec, hash, lydict_resize_val_eq);
166 free(val_p);
167 LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
168 }
169 } else if (ret == LY_ENOTFOUND) {
170 LOGERR(ctx, LY_ENOTFOUND, "Value \"%s\" was not found in the dictionary.", value);
171 } else {
172 LOGINT(ctx);
173 }
174
175finish:
176 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
177 return ret;
178}
179
180LY_ERR
181dict_insert(const struct ly_ctx *ctx, char *value, size_t len, ly_bool zerocopy, const char **str_p)
182{
183 LY_ERR ret = LY_SUCCESS;
184 struct ly_dict_rec *match = NULL, rec;
185 uint32_t hash;
186
187 LOGDBG(LY_LDGDICT, "inserting \"%.*s\"", (int)len, value);
188
189 hash = lyht_hash(value, len);
190 /* set len as data for compare callback */
191 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
192 /* create record for lyht_insert */
193 rec.value = value;
194 rec.refcount = 1;
195
196 ret = lyht_insert_with_resize_cb(ctx->dict.hash_tab, (void *)&rec, hash, lydict_resize_val_eq, (void **)&match);
197 if (ret == LY_EEXIST) {
198 match->refcount++;
199 if (zerocopy) {
200 free(value);
201 }
202 ret = LY_SUCCESS;
203 } else if (ret == LY_SUCCESS) {
204 if (!zerocopy) {
205 /*
206 * allocate string for new record
207 * record is already inserted in hash table
208 */
209 match->value = malloc(sizeof *match->value * (len + 1));
210 LY_CHECK_ERR_RET(!match->value, LOGMEM(ctx), LY_EMEM);
211 if (len) {
212 memcpy(match->value, value, len);
213 }
214 match->value[len] = '\0';
215 }
216 } else {
217 /* lyht_insert returned error */
218 if (zerocopy) {
219 free(value);
220 }
221 return ret;
222 }
223
224 if (str_p) {
225 *str_p = match->value;
226 }
227
228 return ret;
229}
230
231LIBYANG_API_DEF LY_ERR
232lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
233{
234 LY_ERR result;
235
236 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
237
238 if (!value) {
239 *str_p = NULL;
240 return LY_SUCCESS;
241 }
242
243 if (!len) {
244 len = strlen(value);
245 }
246
247 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
248 result = dict_insert(ctx, (char *)value, len, 0, str_p);
249 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
250
251 return result;
252}
253
254LIBYANG_API_DEF LY_ERR
255lydict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
256{
257 LY_ERR result;
258
259 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
260
261 if (!value) {
262 *str_p = NULL;
263 return LY_SUCCESS;
264 }
265
266 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
267 result = dict_insert(ctx, value, strlen(value), 1, str_p);
268 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
269
270 return result;
271}