X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=lib%2Fhashtable.c;h=f08847758a091da8d9960ff94ec830fbcfa502ce;hb=3fea95369850987de15a2a0ac009d05e13b90246;hp=f4d57950591366128b5c06c339bdec076970b61d;hpb=3d3b52f2586a8bf1c53496547062594fd4386454;p=u-boot diff --git a/lib/hashtable.c b/lib/hashtable.c index f4d5795059..f08847758a 100644 --- a/lib/hashtable.c +++ b/lib/hashtable.c @@ -2,7 +2,7 @@ * This implementation is based on code from uClibc-0.9.30.3 but was * modified and extended for use within U-Boot. * - * Copyright (C) 2010 Wolfgang Denk + * Copyright (C) 2010-2013 Wolfgang Denk * * Original license header: * @@ -10,20 +10,7 @@ * This file is part of the GNU C Library. * Contributed by Ulrich Drepper , 1993. * - * The GNU C Library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * The GNU C Library 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with the GNU C Library; if not, write to the Free - * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA - * 02111-1307 USA. + * SPDX-License-Identifier: LGPL-2.1+ */ #include @@ -54,7 +41,10 @@ #define CONFIG_ENV_MAX_ENTRIES 512 #endif -#include "search.h" +#include +#include +#include +#include /* * [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986 @@ -66,12 +56,16 @@ * Instead the interface of all functions is extended to take an argument * which describes the current status. */ + typedef struct _ENTRY { int used; ENTRY entry; } _ENTRY; +static void _hdelete(const char *key, struct hsearch_data *htab, ENTRY *ep, + int idx); + /* * hcreate() */ @@ -204,29 +198,6 @@ void hdestroy_r(struct hsearch_data *htab) * example for functions like hdelete(). */ -/* - * hstrstr_r - return index to entry whose key and/or data contains match - */ -int hstrstr_r(const char *match, int last_idx, ENTRY ** retval, - struct hsearch_data *htab) -{ - unsigned int idx; - - for (idx = last_idx + 1; idx < htab->size; ++idx) { - if (htab->table[idx].used <= 0) - continue; - if (strstr(htab->table[idx].entry.key, match) || - strstr(htab->table[idx].entry.data, match)) { - *retval = &htab->table[idx].entry; - return idx; - } - } - - __set_errno(ESRCH); - *retval = NULL; - return 0; -} - int hmatch_r(const char *match, int last_idx, ENTRY ** retval, struct hsearch_data *htab) { @@ -259,6 +230,28 @@ static inline int _compare_and_overwrite_entry(ENTRY item, ACTION action, && strcmp(item.key, htab->table[idx].entry.key) == 0) { /* Overwrite existing value? */ if ((action == ENTER) && (item.data != NULL)) { + /* check for permission */ + if (htab->change_ok != NULL && htab->change_ok( + &htab->table[idx].entry, item.data, + env_op_overwrite, flag)) { + debug("change_ok() rejected setting variable " + "%s, skipping it!\n", item.key); + __set_errno(EPERM); + *retval = NULL; + return 0; + } + + /* If there is a callback, call it */ + if (htab->table[idx].entry.callback && + htab->table[idx].entry.callback(item.key, + item.data, env_op_overwrite, flag)) { + debug("callback() rejected setting variable " + "%s, skipping it!\n", item.key); + __set_errno(EINVAL); + *retval = NULL; + return 0; + } + free(htab->table[idx].entry.data); htab->table[idx].entry.data = strdup(item.data); if (!htab->table[idx].entry.data) { @@ -383,6 +376,34 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, ++htab->filled; + /* This is a new entry, so look up a possible callback */ + env_callback_init(&htab->table[idx].entry); + /* Also look for flags */ + env_flags_init(&htab->table[idx].entry); + + /* check for permission */ + if (htab->change_ok != NULL && htab->change_ok( + &htab->table[idx].entry, item.data, env_op_create, flag)) { + debug("change_ok() rejected setting variable " + "%s, skipping it!\n", item.key); + _hdelete(item.key, htab, &htab->table[idx].entry, idx); + __set_errno(EPERM); + *retval = NULL; + return 0; + } + + /* If there is a callback, call it */ + if (htab->table[idx].entry.callback && + htab->table[idx].entry.callback(item.key, item.data, + env_op_create, flag)) { + debug("callback() rejected setting variable " + "%s, skipping it!\n", item.key); + _hdelete(item.key, htab, &htab->table[idx].entry, idx); + __set_errno(EINVAL); + *retval = NULL; + return 0; + } + /* return new entry */ *retval = &htab->table[idx].entry; return 1; @@ -404,6 +425,20 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, * do that. */ +static void _hdelete(const char *key, struct hsearch_data *htab, ENTRY *ep, + int idx) +{ + /* free used ENTRY */ + debug("hdelete: DELETING key \"%s\"\n", key); + free((void *)ep->key); + free(ep->data); + ep->callback = NULL; + ep->flags = 0; + htab->table[idx].used = -1; + + --htab->filled; +} + int hdelete_r(const char *key, struct hsearch_data *htab, int flag) { ENTRY e, *ep; @@ -420,28 +455,33 @@ int hdelete_r(const char *key, struct hsearch_data *htab, int flag) } /* Check for permission */ - if (htab->apply != NULL && - htab->apply(ep->key, ep->data, NULL, flag)) { + if (htab->change_ok != NULL && + htab->change_ok(ep, NULL, env_op_delete, flag)) { + debug("change_ok() rejected deleting variable " + "%s, skipping it!\n", key); __set_errno(EPERM); return 0; } - /* free used ENTRY */ - debug("hdelete: DELETING key \"%s\"\n", key); - free((void *)ep->key); - free(ep->data); - htab->table[idx].used = -1; + /* If there is a callback, call it */ + if (htab->table[idx].entry.callback && + htab->table[idx].entry.callback(key, NULL, env_op_delete, flag)) { + debug("callback() rejected deleting variable " + "%s, skipping it!\n", key); + __set_errno(EINVAL); + return 0; + } - --htab->filled; + _hdelete(key, htab, ep, idx); return 1; } +#if !(defined(CONFIG_SPL_BUILD) && !defined(CONFIG_SPL_SAVEENV)) /* * hexport() */ -#ifndef CONFIG_SPL_BUILD /* * Export the data stored in the hash table in linearized form. * @@ -459,7 +499,7 @@ int hdelete_r(const char *key, struct hsearch_data *htab, int flag) * * If the separator character is different from NUL, then any * separator characters and backslash characters in the values will - * be escaped by a preceeding backslash in output. This is needed for + * be escaped by a preceding backslash in output. This is needed for * example to enable multi-line values, especially when the output * shall later be parsed (for example, for re-import). * @@ -488,7 +528,66 @@ static int cmpkey(const void *p1, const void *p2) return (strcmp(e1->key, e2->key)); } -ssize_t hexport_r(struct hsearch_data *htab, const char sep, +static int match_string(int flag, const char *str, const char *pat, void *priv) +{ + switch (flag & H_MATCH_METHOD) { + case H_MATCH_IDENT: + if (strcmp(str, pat) == 0) + return 1; + break; + case H_MATCH_SUBSTR: + if (strstr(str, pat)) + return 1; + break; +#ifdef CONFIG_REGEX + case H_MATCH_REGEX: + { + struct slre *slrep = (struct slre *)priv; + struct cap caps[slrep->num_caps + 2]; + + if (slre_match(slrep, str, strlen(str), caps)) + return 1; + } + break; +#endif + default: + printf("## ERROR: unsupported match method: 0x%02x\n", + flag & H_MATCH_METHOD); + break; + } + return 0; +} + +static int match_entry(ENTRY *ep, int flag, + int argc, char * const argv[]) +{ + int arg; + void *priv = NULL; + + for (arg = 0; arg < argc; ++arg) { +#ifdef CONFIG_REGEX + struct slre slre; + + if (slre_compile(&slre, argv[arg]) == 0) { + printf("Error compiling regex: %s\n", slre.err_str); + return 0; + } + + priv = (void *)&slre; +#endif + if (flag & H_MATCH_KEY) { + if (match_string(flag, ep->key, argv[arg], priv)) + return 1; + } + if (flag & H_MATCH_DATA) { + if (match_string(flag, ep->data, argv[arg], priv)) + return 1; + } + } + return 0; +} + +ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag, char **resp, size_t size, int argc, char * const argv[]) { @@ -503,8 +602,8 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, return (-1); } - debug("EXPORT table = %p, htab.size = %d, htab.filled = %d, " - "size = %zu\n", htab, htab->size, htab->filled, size); + debug("EXPORT table = %p, htab.size = %d, htab.filled = %d, size = %lu\n", + htab, htab->size, htab->filled, (ulong)size); /* * Pass 1: * search used entries, @@ -514,17 +613,14 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, if (htab->table[i].used > 0) { ENTRY *ep = &htab->table[i].entry; - int arg, found = 0; + int found = match_entry(ep, flag, argc, argv); - for (arg = 0; arg < argc; ++arg) { - if (strcmp(argv[arg], ep->key) == 0) { - found = 1; - break; - } - } if ((argc > 0) && (found == 0)) continue; + if ((flag & H_HIDE_DOT) && ep->key[0] == '.') + continue; + list[n++] = ep; totlen += strlen(ep->key) + 2; @@ -561,8 +657,8 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, /* Check if the user supplied buffer size is sufficient */ if (size) { if (size < totlen + 1) { /* provided buffer too small */ - printf("Env export buffer too small: %zu, " - "but need %zu\n", size, totlen + 1); + printf("Env export buffer too small: %lu, but need %lu\n", + (ulong)size, (ulong)totlen + 1); __set_errno(ENOMEM); return (-1); } @@ -680,7 +776,7 @@ static int drop_var_from_set(const char *name, int nvars, char * vars[]) int himport_r(struct hsearch_data *htab, const char *env, size_t size, const char sep, int flag, - int nvars, char * const vars[]) + int crlf_is_lf, int nvars, char * const vars[]) { char *data, *sp, *dp, *name, *value; char *localvars[nvars]; @@ -693,12 +789,13 @@ int himport_r(struct hsearch_data *htab, } /* we allocate new space to make sure we can write to the array */ - if ((data = malloc(size)) == NULL) { - debug("himport_r: can't malloc %zu bytes\n", size); + if ((data = malloc(size + 1)) == NULL) { + debug("himport_r: can't malloc %lu bytes\n", (ulong)size + 1); __set_errno(ENOMEM); return 0; } memcpy(data, env, size); + data[size] = '\0'; dp = data; /* make a local copy of the list of variables */ @@ -721,11 +818,11 @@ int himport_r(struct hsearch_data *htab, * size of 8 per entry (= safety factor of ~5) should provide enough * safety margin for any existing environment definitions and still * allow for more than enough dynamic additions. Note that the - * "size" argument is supposed to give the maximum enviroment size + * "size" argument is supposed to give the maximum environment size * (CONFIG_ENV_SIZE). This heuristics will result in * unreasonably large numbers (and thus memory footprint) for * big flash environments (>8,000 entries for 64 KB - * envrionment size), so we clip it to a reasonable value. + * environment size), so we clip it to a reasonable value. * On the other hand we need to add some more entries for free * space when importing very small buffers. Both boundaries can * be overwritten in the board config file if needed. @@ -745,6 +842,23 @@ int himport_r(struct hsearch_data *htab, } } + if (!size) { + free(data); + return 1; /* everything OK */ + } + if(crlf_is_lf) { + /* Remove Carriage Returns in front of Line Feeds */ + unsigned ignored_crs = 0; + for(;dp < data + size && *dp; ++dp) { + if(*dp == '\r' && + dp < data + size - 1 && *(dp+1) == '\n') + ++ignored_crs; + else + *(dp-ignored_crs) = *dp; + } + size -= ignored_crs; + dp = data; + } /* Parse environment; allow for '\0' and 'sep' as separators */ do { ENTRY e, *rv; @@ -792,6 +906,13 @@ int himport_r(struct hsearch_data *htab, *sp++ = '\0'; /* terminate value */ ++dp; + if (*name == 0) { + debug("INSERT: unable to use an empty key\n"); + __set_errno(EINVAL); + free(data); + return 0; + } + /* Skip variables which are not supposed to be processed */ if (!drop_var_from_set(name, nvars, localvars)) continue; @@ -800,30 +921,10 @@ int himport_r(struct hsearch_data *htab, e.key = name; e.data = value; - /* if there is an apply function, check what it has to say */ - if (htab->apply != NULL) { - debug("searching before calling cb function" - " for %s\n", name); - /* - * Search for variable in existing env, so to pass - * its previous value to the apply callback - */ - hsearch_r(e, FIND, &rv, htab, 0); - debug("previous value was %s\n", rv ? rv->data : ""); - if (htab->apply(name, rv ? rv->data : NULL, - value, flag)) { - debug("callback function refused to set" - " variable %s, skipping it!\n", name); - continue; - } - } - hsearch_r(e, ENTER, &rv, htab, flag); - if (rv == NULL) { + if (rv == NULL) printf("himport_r: can't insert \"%s=%s\" into hash table\n", name, value); - return 0; - } debug("INSERT: table %p, filled %d/%d rv %p ==> name=\"%s\" value=\"%s\"\n", htab, htab->filled, htab->size, @@ -854,3 +955,27 @@ int himport_r(struct hsearch_data *htab, debug("INSERT: done\n"); return 1; /* everything OK */ } + +/* + * hwalk_r() + */ + +/* + * Walk all of the entries in the hash, calling the callback for each one. + * this allows some generic operation to be performed on each element. + */ +int hwalk_r(struct hsearch_data *htab, int (*callback)(ENTRY *)) +{ + int i; + int retval; + + for (i = 1; i <= htab->size; ++i) { + if (htab->table[i].used > 0) { + retval = callback(&htab->table[i].entry); + if (retval) + return retval; + } + } + + return 0; +}