1 files changed, 271 insertions, 0 deletions
diff --git a/src/dict.c b/src/dict.c
new file mode 100644
index 0000000..9f741a2
--- /dev/null
+++ b/src/dict.c
@@ -0,0 +1,271 @@
+/**
+ * @file dict.c
+ * @author Radek Krejci <rkrejci@cesnet.cz>
+ * @author Michal Vasko <mvasko@cesnet.cz>
+ * @brief libyang dictionary for storing strings
+ *
+ * Copyright (c) 2015 - 2023 CESNET, z.s.p.o.
+ *
+ * This source code is licensed under BSD 3-Clause License (the "License").
+ * You may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://opensource.org/licenses/BSD-3-Clause
+ */
+
+#include "dict.h"
+
+#include <assert.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "compat.h"
+#include "log.h"
+#include "ly_common.h"
+
+/* starting size of the dictionary */
+#define LYDICT_MIN_SIZE 1024
+
+/**
+ * @brief Comparison callback for dictionary's hash table
+ *
+ * Implementation of ::lyht_value_equal_cb.
+ */
+static ly_bool
+lydict_val_eq(void *val1_p, void *val2_p, ly_bool UNUSED(mod), void *cb_data)
+{
+    const char *str1, *str2;
+    size_t *len1;
+
+    LY_CHECK_ARG_RET(NULL, val1_p, val2_p, cb_data, 0);
+
+    str1 = ((struct ly_dict_rec *)val1_p)->value;
+    str2 = ((struct ly_dict_rec *)val2_p)->value;
+    len1 = cb_data;
+
+    LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
+    LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
+
+    if (!strncmp(str1, str2, *len1) && !str2[*len1]) {
+        return 1;
+    }
+
+    return 0;
+}
+
+void
+lydict_init(struct ly_dict *dict)
+{
+    LY_CHECK_ARG_RET(NULL, dict, );
+
+    dict->hash_tab = lyht_new(LYDICT_MIN_SIZE, sizeof(struct ly_dict_rec), lydict_val_eq, NULL, 1);
+    LY_CHECK_ERR_RET(!dict->hash_tab, LOGINT(NULL), );
+    pthread_mutex_init(&dict->lock, NULL);
+}
+
+void
+lydict_clean(struct ly_dict *dict)
+{
+    struct ly_dict_rec *dict_rec = NULL;
+    struct ly_ht_rec *rec = NULL;
+    uint32_t hlist_idx;
+    uint32_t rec_idx;
+
+    LY_CHECK_ARG_RET(NULL, dict, );
+
+    LYHT_ITER_ALL_RECS(dict->hash_tab, hlist_idx, rec_idx, rec) {
+        /*
+         * this should not happen, all records inserted into
+         * dictionary are supposed to be removed using lydict_remove()
+         * before calling lydict_clean()
+         */
+        dict_rec = (struct ly_dict_rec *)rec->val;
+        LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %" PRIu32 ".", dict_rec->value, dict_rec->refcount);
+        /* if record wasn't removed before free string allocated for that record */
+#ifdef NDEBUG
+        free(dict_rec->value);
+#endif
+    }
+
+    /* free table and destroy mutex */
+    lyht_free(dict->hash_tab, NULL);
+    pthread_mutex_destroy(&dict->lock);
+}
+
+static ly_bool
+lydict_resize_val_eq(void *val1_p, void *val2_p, ly_bool mod, void *UNUSED(cb_data))
+{
+    const char *str1, *str2;
+
+    LY_CHECK_ARG_RET(NULL, val1_p, val2_p, 0);
+
+    str1 = ((struct ly_dict_rec *)val1_p)->value;
+    str2 = ((struct ly_dict_rec *)val2_p)->value;
+
+    LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
+    LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
+
+    if (mod) {
+        /* used when inserting new values */
+        if (strcmp(str1, str2) == 0) {
+            return 1;
+        }
+    } else {
+        /* used when finding the original value again in the resized table */
+        if (str1 == str2) {
+            return 1;
+        }
+    }
+
+    return 0;
+}
+
+LIBYANG_API_DEF LY_ERR
+lydict_remove(const struct ly_ctx *ctx, const char *value)
+{
+    LY_ERR ret = LY_SUCCESS;
+    size_t len;
+    uint32_t hash;
+    struct ly_dict_rec rec, *match = NULL;
+    char *val_p;
+
+    if (!ctx || !value) {
+        return LY_SUCCESS;
+    }
+
+    LOGDBG(LY_LDGDICT, "removing \"%s\"", value);
+
+    len = strlen(value);
+    hash = lyht_hash(value, len);
+
+    /* create record for lyht_find call */
+    rec.value = (char *)value;
+    rec.refcount = 0;
+
+    pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
+    /* set len as data for compare callback */
+    lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
+    /* check if value is already inserted */
+    ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
+
+    if (ret == LY_SUCCESS) {
+        LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
+
+        /* if value is already in dictionary, decrement reference counter */
+        match->refcount--;
+        if (match->refcount == 0) {
+            /*
+             * remove record
+             * save pointer to stored string before lyht_remove to
+             * free it after it is removed from hash table
+             */
+            val_p = match->value;
+            ret = lyht_remove_with_resize_cb(ctx->dict.hash_tab, &rec, hash, lydict_resize_val_eq);
+            free(val_p);
+            LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
+        }
+    } else if (ret == LY_ENOTFOUND) {
+        LOGERR(ctx, LY_ENOTFOUND, "Value \"%s\" was not found in the dictionary.", value);
+    } else {
+        LOGINT(ctx);
+    }
+
+finish:
+    pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
+    return ret;
+}
+
+LY_ERR
+dict_insert(const struct ly_ctx *ctx, char *value, size_t len, ly_bool zerocopy, const char **str_p)
+{
+    LY_ERR ret = LY_SUCCESS;
+    struct ly_dict_rec *match = NULL, rec;
+    uint32_t hash;
+
+    LOGDBG(LY_LDGDICT, "inserting \"%.*s\"", (int)len, value);
+
+    hash = lyht_hash(value, len);
+    /* set len as data for compare callback */
+    lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
+    /* create record for lyht_insert */
+    rec.value = value;
+    rec.refcount = 1;
+
+    ret = lyht_insert_with_resize_cb(ctx->dict.hash_tab, (void *)&rec, hash, lydict_resize_val_eq, (void **)&match);
+    if (ret == LY_EEXIST) {
+        match->refcount++;
+        if (zerocopy) {
+            free(value);
+        }
+        ret = LY_SUCCESS;
+    } else if (ret == LY_SUCCESS) {
+        if (!zerocopy) {
+            /*
+             * allocate string for new record
+             * record is already inserted in hash table
+             */
+            match->value = malloc(sizeof *match->value * (len + 1));
+            LY_CHECK_ERR_RET(!match->value, LOGMEM(ctx), LY_EMEM);
+            if (len) {
+                memcpy(match->value, value, len);
+            }
+            match->value[len] = '\0';
+        }
+    } else {
+        /* lyht_insert returned error */
+        if (zerocopy) {
+            free(value);
+        }
+        return ret;
+    }
+
+    if (str_p) {
+        *str_p = match->value;
+    }
+
+    return ret;
+}
+
+LIBYANG_API_DEF LY_ERR
+lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
+{
+    LY_ERR result;
+
+    LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
+
+    if (!value) {
+        *str_p = NULL;
+        return LY_SUCCESS;
+    }
+
+    if (!len) {
+        len = strlen(value);
+    }
+
+    pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
+    result = dict_insert(ctx, (char *)value, len, 0, str_p);
+    pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
+
+    return result;
+}
+
+LIBYANG_API_DEF LY_ERR
+lydict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
+{
+    LY_ERR result;
+
+    LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
+
+    if (!value) {
+        *str_p = NULL;
+        return LY_SUCCESS;
+    }
+
+    pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
+    result = dict_insert(ctx, value, strlen(value), 1, str_p);
+    pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
+
+    return result;
+}