From f449f278dd3c70e479a035f50a9bb817a9b433ba Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:24:08 +0200 Subject: Adding upstream version 3.2.6. Signed-off-by: Daniel Baumann --- src/utils/common/lookup.c | 295 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 295 insertions(+) create mode 100644 src/utils/common/lookup.c (limited to 'src/utils/common/lookup.c') diff --git a/src/utils/common/lookup.c b/src/utils/common/lookup.c new file mode 100644 index 0000000..e7f6084 --- /dev/null +++ b/src/utils/common/lookup.c @@ -0,0 +1,295 @@ +/* Copyright (C) 2022 CZ.NIC, z.s.p.o. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . + */ + +#include + +#include "utils/common/lookup.h" +#include "contrib/mempattern.h" +#include "contrib/ucw/mempool.h" +#include "libknot/error.h" + +int lookup_init(lookup_t *lookup) +{ + if (lookup == NULL) { + return KNOT_EINVAL; + } + memset(lookup, 0, sizeof(*lookup)); + + mm_ctx_mempool(&lookup->mm, MM_DEFAULT_BLKSIZE); + lookup->trie = trie_create(&lookup->mm); + if (lookup->trie == NULL) { + mp_delete(lookup->mm.ctx); + return KNOT_ENOMEM; + } + + return KNOT_EOK; +} + +static void reset_output(lookup_t *lookup) +{ + if (lookup == NULL) { + return; + } + + mm_free(&lookup->mm, lookup->found.key); + lookup->found.key = NULL; + lookup->found.data = NULL; + + lookup->iter.count = 0; + + mm_free(&lookup->mm, lookup->iter.first_key); + lookup->iter.first_key = NULL; + + trie_it_free(lookup->iter.it); + lookup->iter.it = NULL; +} + +void lookup_deinit(lookup_t *lookup) +{ + if (lookup == NULL) { + return; + } + + reset_output(lookup); + + trie_free(lookup->trie); + mp_delete(lookup->mm.ctx); +} + +int lookup_insert(lookup_t *lookup, const char *str, void *data) +{ + if (lookup == NULL || str == NULL) { + return KNOT_EINVAL; + } + + size_t str_len = strlen(str); + if (str_len == 0) { + return KNOT_EINVAL; + } + + trie_val_t *val = trie_get_ins(lookup->trie, (const trie_key_t *)str, str_len); + if (val == NULL) { + return KNOT_ENOMEM; + } + *val = data; + + return KNOT_EOK; +} + +int lookup_remove(lookup_t *lookup, const char *str) +{ + if (lookup == NULL || str == NULL) { + return KNOT_EINVAL; + } + + size_t str_len = strlen(str); + if (str_len > 0) { + (void)trie_del(lookup->trie, (const trie_key_t *)str, str_len, NULL); + } + + return KNOT_EOK; +} + +static int set_key(lookup_t *lookup, char **dst, const char *key, size_t key_len) +{ + if (*dst != NULL) { + mm_free(&lookup->mm, *dst); + } + *dst = mm_alloc(&lookup->mm, key_len + 1); + if (*dst == NULL) { + return KNOT_ENOMEM; + } + memcpy(*dst, key, key_len); + (*dst)[key_len] = '\0'; + + return KNOT_EOK; +} + +int lookup_search(lookup_t *lookup, const char *str, size_t str_len) +{ + if (lookup == NULL) { + return KNOT_EINVAL; + } + + // Change NULL string to the empty one. + if (str == NULL) { + str = ""; + } + + reset_output(lookup); + + size_t new_len = 0; + trie_it_t *it = trie_it_begin(lookup->trie); + for (; !trie_it_finished(it); trie_it_next(it)) { + size_t len; + const char *key = (const char *)trie_it_key(it, &len); + + // Compare with a shorter key. + if (len < str_len) { + int ret = memcmp(str, key, len); + if (ret >= 0) { + continue; + } else { + break; + } + } + + // Compare with an equal length or longer key. + int ret = memcmp(str, key, str_len); + if (ret == 0) { + lookup->iter.count++; + + // First candidate. + if (lookup->iter.count == 1) { + ret = set_key(lookup, &lookup->found.key, key, len); + if (ret != KNOT_EOK) { + break; + } + lookup->found.data = *trie_it_val(it); + new_len = len; + // Another candidate. + } else if (new_len > str_len) { + if (new_len > len) { + new_len = len; + } + while (memcmp(lookup->found.key, key, new_len) != 0) { + new_len--; + } + } + // Stop if greater than the key, and also than all the following keys. + } else if (ret < 0) { + break; + } + } + trie_it_free(it); + + switch (lookup->iter.count) { + case 0: + return KNOT_ENOENT; + case 1: + return KNOT_EOK; + default: + // Store full name of the first candidate. + if (set_key(lookup, &lookup->iter.first_key, lookup->found.key, + strlen(lookup->found.key)) != KNOT_EOK) { + return KNOT_ENOMEM; + } + lookup->found.key[new_len] = '\0'; + lookup->found.data = NULL; + + return KNOT_EFEWDATA; + } +} + +void lookup_list(lookup_t *lookup) +{ + if (lookup == NULL || lookup->iter.first_key == NULL) { + return; + } + + if (lookup->iter.it != NULL) { + if (trie_it_finished(lookup->iter.it)) { + trie_it_free(lookup->iter.it); + lookup->iter.it = NULL; + return; + } + + trie_it_next(lookup->iter.it); + + size_t len; + const char *key = (const char *)trie_it_key(lookup->iter.it, &len); + + int ret = set_key(lookup, &lookup->found.key, key, len); + if (ret == KNOT_EOK) { + lookup->found.data = *trie_it_val(lookup->iter.it); + } + return; + } + + lookup->iter.it = trie_it_begin(lookup->trie); + while (!trie_it_finished(lookup->iter.it)) { + size_t len; + const char *key = (const char *)trie_it_key(lookup->iter.it, &len); + + if (strncmp(key, lookup->iter.first_key, len) == 0) { + int ret = set_key(lookup, &lookup->found.key, key, len); + if (ret == KNOT_EOK) { + lookup->found.data = *trie_it_val(lookup->iter.it); + } + break; + } + trie_it_next(lookup->iter.it); + } +} + +static void print_options(lookup_t *lookup, EditLine *el) +{ + // Get terminal lines. + unsigned lines = 0; + if (el_get(el, EL_GETTC, "li", &lines) != 0 || lines < 3) { + return; + } + + for (size_t i = 1; i <= lookup->iter.count; i++) { + lookup_list(lookup); + printf("\n%s", lookup->found.key); + + if (i > 1 && i % (lines - 1) == 0 && i < lookup->iter.count) { + printf("\n Display next from %zu possibilities? (y or n)", + lookup->iter.count); + char next; + el_getc(el, &next); + if (next != 'y') { + break; + } + } + } + + printf("\n"); + fflush(stdout); +} + +int lookup_complete(lookup_t *lookup, const char *str, size_t str_len, + EditLine *el, bool add_space) +{ + if (lookup == NULL || el == NULL) { + return KNOT_EINVAL; + } + + // Try to complete the command name. + int ret = lookup_search(lookup, str, str_len); + switch (ret) { + case KNOT_EOK: + el_deletestr(el, str_len); + el_insertstr(el, lookup->found.key); + if (add_space) { + el_insertstr(el, " "); + } + break; + case KNOT_EFEWDATA: + if (strlen(lookup->found.key) > str_len) { + el_deletestr(el, str_len); + el_insertstr(el, lookup->found.key); + } else { + print_options(lookup, el); + } + break; + default: + break; + } + + return ret; +} -- cgit v1.2.3