X-Git-Url: https://git.kernelconcepts.de/?a=blobdiff_plain;f=lib%2Fhashtable.c;h=644330a17e8ce7a6bdb8f0112094d5c1e884435e;hb=ee8b1e29597bcf18bfebd6fd8eccc8e245046352;hp=94a7b61717a8b9f0ecc6312c9dfda2130a6e6767;hpb=198166877768cf4d0197289a524df8a6ca0e2f19;p=karo-tx-uboot.git

diff --git a/lib/hashtable.c b/lib/hashtable.c
index 94a7b61717..644330a17e 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 <wd@denx.de>
+ * Copyright (C) 2010-2013 Wolfgang Denk <wd@denx.de>
  *
  * Original license header:
  *
@@ -10,20 +10,7 @@
  * This file is part of the GNU C Library.
  * Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 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 <errno.h>
@@ -54,7 +41,10 @@
 #define	CONFIG_ENV_MAX_ENTRIES 512
 #endif
 
-#include "search.h"
+#include <env_callback.h>
+#include <env_flags.h>
+#include <search.h>
+#include <slre.h>
 
 /*
  * [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()
  */
@@ -142,7 +136,7 @@ int hcreate_r(size_t nel, struct hsearch_data *htab)
  * be freed and the local static variable can be marked as not used.
  */
 
-void hdestroy_r(struct hsearch_data *htab, int do_apply)
+void hdestroy_r(struct hsearch_data *htab)
 {
 	int i;
 
@@ -156,10 +150,7 @@ void hdestroy_r(struct hsearch_data *htab, int do_apply)
 	for (i = 1; i <= htab->size; ++i) {
 		if (htab->table[i].used > 0) {
 			ENTRY *ep = &htab->table[i].entry;
-			if (do_apply && htab->apply != NULL) {
-				/* deletion is always forced */
-				htab->apply(ep->key, ep->data, NULL, H_FORCE);
-			}
+
 			free((void *)ep->key);
 			free(ep->data);
 		}
@@ -207,19 +198,16 @@ void hdestroy_r(struct hsearch_data *htab, int do_apply)
  *   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)
+int hmatch_r(const char *match, int last_idx, ENTRY ** retval,
+	     struct hsearch_data *htab)
 {
 	unsigned int idx;
+	size_t key_len = strlen(match);
 
 	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)) {
+		if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
 			*retval = &htab->table[idx].entry;
 			return idx;
 		}
@@ -230,34 +218,65 @@ int hstrstr_r(const char *match, int last_idx, ENTRY ** retval,
 	return 0;
 }
 
-int hmatch_r(const char *match, int last_idx, ENTRY ** retval,
-	     struct hsearch_data *htab)
+/*
+ * Compare an existing entry with the desired key, and overwrite if the action
+ * is 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)
 {
-	unsigned int idx;
-	size_t key_len = strlen(match);
+	if (htab->table[idx].used == hval
+	    && 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;
+			}
 
-	for (idx = last_idx + 1; idx < htab->size; ++idx) {
-		if (htab->table[idx].used <= 0)
-			continue;
-		if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
-			*retval = &htab->table[idx].entry;
-			return idx;
+			/* 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) {
+				__set_errno(ENOMEM);
+				*retval = NULL;
+				return 0;
+			}
 		}
+		/* return found entry */
+		*retval = &htab->table[idx].entry;
+		return idx;
 	}
-
-	__set_errno(ESRCH);
-	*retval = NULL;
-	return 0;
+	/* keep searching */
+	return -1;
 }
 
 int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
-	      struct hsearch_data *htab)
+	      struct hsearch_data *htab, int flag)
 {
 	unsigned int hval;
 	unsigned int count;
 	unsigned int len = strlen(item.key);
 	unsigned int idx;
 	unsigned int first_deleted = 0;
+	int ret;
 
 	/* Compute an value for the given string. Perhaps use a better method. */
 	hval = len;
@@ -289,23 +308,10 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 		    && !first_deleted)
 			first_deleted = 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)) {
-				free(htab->table[idx].entry.data);
-				htab->table[idx].entry.data =
-					strdup(item.data);
-				if (!htab->table[idx].entry.data) {
-					__set_errno(ENOMEM);
-					*retval = NULL;
-					return 0;
-				}
-			}
-			/* return found entry */
-			*retval = &htab->table[idx].entry;
-			return idx;
-		}
+		ret = _compare_and_overwrite_entry(item, action, retval, htab,
+			flag, hval, idx);
+		if (ret != -1)
+			return ret;
 
 		/*
 		 * Second hash function:
@@ -331,23 +337,10 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 				break;
 
 			/* If entry is found use it. */
-			if ((htab->table[idx].used == hval)
-			    && strcmp(item.key, htab->table[idx].entry.key) == 0) {
-				/* Overwrite existing value? */
-				if ((action == ENTER) && (item.data != NULL)) {
-					free(htab->table[idx].entry.data);
-					htab->table[idx].entry.data =
-						strdup(item.data);
-					if (!htab->table[idx].entry.data) {
-						__set_errno(ENOMEM);
-						*retval = NULL;
-						return 0;
-					}
-				}
-				/* return found entry */
-				*retval = &htab->table[idx].entry;
-				return idx;
-			}
+			ret = _compare_and_overwrite_entry(item, action, retval,
+				htab, flag, hval, idx);
+			if (ret != -1)
+				return ret;
 		}
 		while (htab->table[idx].used);
 	}
@@ -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,7 +425,21 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
  * do that.
  */
 
-int hdelete_r(const char *key, struct hsearch_data *htab, int do_apply)
+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;
 	int idx;
@@ -413,20 +448,31 @@ int hdelete_r(const char *key, struct hsearch_data *htab, int do_apply)
 
 	e.key = (char *)key;
 
-	if ((idx = hsearch_r(e, FIND, &ep, htab)) == 0) {
+	idx = hsearch_r(e, FIND, &ep, htab, 0);
+	if (idx == 0) {
 		__set_errno(ESRCH);
 		return 0;	/* not found */
 	}
 
-	/* free used ENTRY */
-	debug("hdelete: DELETING key \"%s\"\n", key);
-	if (do_apply && htab->apply != NULL)
-		htab->apply(ep->key, ep->data, NULL, H_FORCE);
-	free((void *)ep->key);
-	free(ep->data);
-	htab->table[idx].used = -1;
+	/* Check for permission */
+	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;
+	}
 
-	--htab->filled;
+	/* 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;
+	}
+
+	_hdelete(key, htab, ep, idx);
 
 	return 1;
 }
@@ -482,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 = 1; 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[])
 {
@@ -508,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;
@@ -674,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 do_apply)
+		int nvars, char * const vars[])
 {
 	char *data, *sp, *dp, *name, *value;
 	char *localvars[nvars];
@@ -704,7 +806,7 @@ int himport_r(struct hsearch_data *htab,
 		debug("Destroy Hash Table: %p table = %p\n", htab,
 		       htab->table);
 		if (htab->table)
-			hdestroy_r(htab, do_apply);
+			hdestroy_r(htab);
 	}
 
 	/*
@@ -770,7 +872,7 @@ int himport_r(struct hsearch_data *htab,
 			if (!drop_var_from_set(name, nvars, localvars))
 				continue;
 
-			if (hdelete_r(name, htab, do_apply) == 0)
+			if (hdelete_r(name, htab, flag) == 0)
 				debug("DELETE ERROR ##############################\n");
 
 			continue;
@@ -786,6 +888,12 @@ 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);
+			return 0;
+		}
+
 		/* Skip variables which are not supposed to be processed */
 		if (!drop_var_from_set(name, nvars, localvars))
 			continue;
@@ -794,30 +902,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 (do_apply && 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);
-			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);
-		if (rv == NULL) {
+		hsearch_r(e, ENTER, &rv, htab, flag);
+		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,
@@ -839,7 +927,7 @@ int himport_r(struct hsearch_data *htab,
 		 * b) if the variable was not present in current env, we notify
 		 *    it might be a typo
 		 */
-		if (hdelete_r(localvars[i], htab, do_apply) == 0)
+		if (hdelete_r(localvars[i], htab, flag) == 0)
 			printf("WARNING: '%s' neither in running nor in imported env!\n", localvars[i]);
 		else
 			printf("WARNING: '%s' not in imported env, deleting it!\n", localvars[i]);
@@ -848,3 +936,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;
+}