X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=lib%2Fhashtable.c;h=2caab0a4c6d3157d3de8d83757bacfa00e257265;hb=27084c03d36a7f0e4d7c1679761e81567f1d5442;hp=07ebfb218f8a6f152d915e448a2c2304a53b9f02;hpb=612404c28a64a6df300642a1550a65dcc8e01f82;p=oweals%2Fu-boot.git diff --git a/lib/hashtable.c b/lib/hashtable.c index 07ebfb218f..2caab0a4c6 100644 --- a/lib/hashtable.c +++ b/lib/hashtable.c @@ -1,29 +1,15 @@ +// SPDX-License-Identifier: LGPL-2.1+ /* * 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: * * Copyright (C) 1993, 1995, 1996, 1997, 2002 Free Software Foundation, Inc. * 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. */ #include @@ -54,9 +40,13 @@ #define CONFIG_ENV_MAX_ENTRIES 512 #endif +#define USED_FREE 0 +#define USED_DELETED -1 + #include #include #include +#include /* * [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986 @@ -69,14 +59,14 @@ * which describes the current status. */ -typedef struct _ENTRY { +struct env_entry_node { int used; - ENTRY entry; -} _ENTRY; + struct env_entry entry; +}; -static void _hdelete(const char *key, struct hsearch_data *htab, ENTRY *ep, - int idx); +static void _hdelete(const char *key, struct hsearch_data *htab, + struct env_entry *ep, int idx); /* * hcreate() @@ -130,7 +120,8 @@ int hcreate_r(size_t nel, struct hsearch_data *htab) htab->filled = 0; /* allocate memory and zero out */ - htab->table = (_ENTRY *) calloc(htab->size + 1, sizeof(_ENTRY)); + htab->table = (struct env_entry_node *)calloc(htab->size + 1, + sizeof(struct env_entry_node)); if (htab->table == NULL) return 0; @@ -161,7 +152,7 @@ void hdestroy_r(struct hsearch_data *htab) /* free used memory */ for (i = 1; i <= htab->size; ++i) { if (htab->table[i].used > 0) { - ENTRY *ep = &htab->table[i].entry; + struct env_entry *ep = &htab->table[i].entry; free((void *)ep->key); free(ep->data); @@ -203,37 +194,14 @@ void hdestroy_r(struct hsearch_data *htab) * data any more. * - The standard implementation does not provide a way to update an * existing entry. This version will create a new entry or update an - * existing one when both "action == ENTER" and "item.data != NULL". + * existing one when both "action == ENV_ENTER" and "item.data != NULL". * - Instead of returning 1 on success, we return the index into the * internal hash table, which is also guaranteed to be positive. * This allows us direct access to the found hash table slot for * 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, +int hmatch_r(const char *match, int last_idx, struct env_entry **retval, struct hsearch_data *htab) { unsigned int idx; @@ -255,16 +223,17 @@ int hmatch_r(const char *match, int last_idx, ENTRY ** retval, /* * Compare an existing entry with the desired key, and overwrite if the action - * is ENTER. This is simply a helper function for hsearch_r(). + * is ENV_ENTER. This is simply a helper function for hsearch_r(). */ -static inline int _compare_and_overwrite_entry(ENTRY item, ACTION action, - ENTRY **retval, struct hsearch_data *htab, int flag, - unsigned int hval, unsigned int idx) +static inline int _compare_and_overwrite_entry(struct env_entry item, + enum env_action action, struct env_entry **retval, + struct hsearch_data *htab, int flag, unsigned int hval, + unsigned int idx) { if (htab->table[idx].used == hval && strcmp(item.key, htab->table[idx].entry.key) == 0) { /* Overwrite existing value? */ - if ((action == ENTER) && (item.data != NULL)) { + if (action == ENV_ENTER && item.data) { /* check for permission */ if (htab->change_ok != NULL && htab->change_ok( &htab->table[idx].entry, item.data, @@ -303,8 +272,8 @@ static inline int _compare_and_overwrite_entry(ENTRY item, ACTION action, return -1; } -int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, - struct hsearch_data *htab, int flag) +int hsearch_r(struct env_entry item, enum env_action action, + struct env_entry **retval, struct hsearch_data *htab, int flag) { unsigned int hval; unsigned int count; @@ -339,7 +308,7 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, */ unsigned hval2; - if (htab->table[idx].used == -1 + if (htab->table[idx].used == USED_DELETED && !first_deleted) first_deleted = idx; @@ -371,17 +340,21 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, if (idx == hval) break; + if (htab->table[idx].used == USED_DELETED + && !first_deleted) + first_deleted = idx; + /* If entry is found use it. */ ret = _compare_and_overwrite_entry(item, action, retval, htab, flag, hval, idx); if (ret != -1) return ret; } - while (htab->table[idx].used); + while (htab->table[idx].used != USED_FREE); } /* An empty bucket has been found. */ - if (action == ENTER) { + if (action == ENV_ENTER) { /* * If table is full and another entry should be * entered return with error. @@ -460,30 +433,30 @@ 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) +static void _hdelete(const char *key, struct hsearch_data *htab, + struct env_entry *ep, int idx) { - /* free used ENTRY */ + /* 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->table[idx].used = USED_DELETED; --htab->filled; } int hdelete_r(const char *key, struct hsearch_data *htab, int flag) { - ENTRY e, *ep; + struct env_entry e, *ep; int idx; debug("hdelete: DELETE key \"%s\"\n", key); e.key = (char *)key; - idx = hsearch_r(e, FIND, &ep, htab, 0); + idx = hsearch_r(e, ENV_FIND, &ep, htab, 0); if (idx == 0) { __set_errno(ESRCH); return 0; /* not found */ @@ -512,11 +485,11 @@ int hdelete_r(const char *key, struct hsearch_data *htab, int flag) 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. * @@ -534,7 +507,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). * @@ -557,17 +530,75 @@ int hdelete_r(const char *key, struct hsearch_data *htab, int flag) static int cmpkey(const void *p1, const void *p2) { - ENTRY *e1 = *(ENTRY **) p1; - ENTRY *e2 = *(ENTRY **) p2; + struct env_entry *e1 = *(struct env_entry **)p1; + struct env_entry *e2 = *(struct env_entry **)p2; return (strcmp(e1->key, e2->key)); } +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; + + if (slre_match(slrep, str, strlen(str), NULL)) + return 1; + } + break; +#endif + default: + printf("## ERROR: unsupported match method: 0x%02x\n", + flag & H_MATCH_METHOD); + break; + } + return 0; +} + +static int match_entry(struct env_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[]) { - ENTRY *list[htab->size]; + struct env_entry *list[htab->size]; char *res, *p; size_t totlen; int i, n; @@ -578,8 +609,8 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag, 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, @@ -588,15 +619,9 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag, for (i = 1, n = 0, totlen = 0; i <= htab->size; ++i) { if (htab->table[i].used > 0) { - ENTRY *ep = &htab->table[i].entry; - int arg, found = 0; + struct env_entry *ep = &htab->table[i].entry; + 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; @@ -605,7 +630,7 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag, list[n++] = ep; - totlen += strlen(ep->key) + 2; + totlen += strlen(ep->key); if (sep == '\0') { totlen += strlen(ep->data); @@ -634,13 +659,13 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag, #endif /* Sort list by keys */ - qsort(list, n, sizeof(ENTRY *), cmpkey); + qsort(list, n, sizeof(struct env_entry *), cmpkey); /* 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); } @@ -732,8 +757,11 @@ static int drop_var_from_set(const char *name, int nvars, char * vars[]) * * The "flag" argument can be used to control the behaviour: when the * H_NOCLEAR bit is set, then an existing hash table will kept, i. e. - * new data will be added to an existing hash table; otherwise, old - * data will be discarded and a new hash table will be created. + * new data will be added to an existing hash table; otherwise, if no + * vars are passed, old data will be discarded and a new hash table + * will be created. If vars are passed, passed vars that are not in + * the linear list of "name=value" pairs will be removed from the + * current hash table. * * The separator character for the "name=value" pairs can be selected, * so we both support importing from externally stored environment @@ -758,7 +786,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]; @@ -771,19 +799,20 @@ 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 */ if (nvars) memcpy(localvars, vars, sizeof(vars[0]) * nvars); - if ((flag & H_NOCLEAR) == 0) { + if ((flag & H_NOCLEAR) == 0 && !nvars) { /* Destroy old hash table if one exists */ debug("Destroy Hash Table: %p table = %p\n", htab, htab->table); @@ -799,11 +828,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. @@ -823,9 +852,26 @@ 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; + struct env_entry e, *rv; /* skip leading white space */ while (isblank(*dp)) @@ -870,6 +916,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; @@ -878,7 +931,7 @@ int himport_r(struct hsearch_data *htab, e.key = name; e.data = value; - hsearch_r(e, ENTER, &rv, htab, flag); + hsearch_r(e, ENV_ENTER, &rv, htab, flag); if (rv == NULL) printf("himport_r: can't insert \"%s=%s\" into hash table\n", name, value); @@ -891,6 +944,9 @@ int himport_r(struct hsearch_data *htab, debug("INSERT: free(data = %p)\n", data); free(data); + if (flag & H_NOCLEAR) + goto end; + /* process variables which were not considered */ for (i = 0; i < nvars; i++) { if (localvars[i] == NULL) @@ -909,6 +965,7 @@ int himport_r(struct hsearch_data *htab, printf("WARNING: '%s' not in imported env, deleting it!\n", localvars[i]); } +end: debug("INSERT: done\n"); return 1; /* everything OK */ } @@ -921,7 +978,7 @@ int himport_r(struct hsearch_data *htab, * 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 hwalk_r(struct hsearch_data *htab, int (*callback)(struct env_entry *entry)) { int i; int retval;