xref: /openbmc/u-boot/lib/hashtable.c (revision dd93a8e9e688f4c448092a275bf7db3e16d21c6f)
1  /*
2   * This implementation is based on code from uClibc-0.9.30.3 but was
3   * modified and extended for use within U-Boot.
4   *
5   * Copyright (C) 2010-2013 Wolfgang Denk <wd@denx.de>
6   *
7   * Original license header:
8   *
9   * Copyright (C) 1993, 1995, 1996, 1997, 2002 Free Software Foundation, Inc.
10   * This file is part of the GNU C Library.
11   * Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993.
12   *
13   * SPDX-License-Identifier:	LGPL-2.1+
14   */
15  
16  #include <errno.h>
17  #include <malloc.h>
18  
19  #ifdef USE_HOSTCC		/* HOST build */
20  # include <string.h>
21  # include <assert.h>
22  # include <ctype.h>
23  
24  # ifndef debug
25  #  ifdef DEBUG
26  #   define debug(fmt,args...)	printf(fmt ,##args)
27  #  else
28  #   define debug(fmt,args...)
29  #  endif
30  # endif
31  #else				/* U-Boot build */
32  # include <common.h>
33  # include <linux/string.h>
34  # include <linux/ctype.h>
35  #endif
36  
37  #ifndef	CONFIG_ENV_MIN_ENTRIES	/* minimum number of entries */
38  #define	CONFIG_ENV_MIN_ENTRIES 64
39  #endif
40  #ifndef	CONFIG_ENV_MAX_ENTRIES	/* maximum number of entries */
41  #define	CONFIG_ENV_MAX_ENTRIES 512
42  #endif
43  
44  #include <env_callback.h>
45  #include <env_flags.h>
46  #include <search.h>
47  #include <slre.h>
48  
49  /*
50   * [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
51   * [Knuth]	      The Art of Computer Programming, part 3 (6.4)
52   */
53  
54  /*
55   * The reentrant version has no static variables to maintain the state.
56   * Instead the interface of all functions is extended to take an argument
57   * which describes the current status.
58   */
59  
60  typedef struct _ENTRY {
61  	int used;
62  	ENTRY entry;
63  } _ENTRY;
64  
65  
66  static void _hdelete(const char *key, struct hsearch_data *htab, ENTRY *ep,
67  	int idx);
68  
69  /*
70   * hcreate()
71   */
72  
73  /*
74   * For the used double hash method the table size has to be a prime. To
75   * correct the user given table size we need a prime test.  This trivial
76   * algorithm is adequate because
77   * a)  the code is (most probably) called a few times per program run and
78   * b)  the number is small because the table must fit in the core
79   * */
80  static int isprime(unsigned int number)
81  {
82  	/* no even number will be passed */
83  	unsigned int div = 3;
84  
85  	while (div * div < number && number % div != 0)
86  		div += 2;
87  
88  	return number % div != 0;
89  }
90  
91  /*
92   * Before using the hash table we must allocate memory for it.
93   * Test for an existing table are done. We allocate one element
94   * more as the found prime number says. This is done for more effective
95   * indexing as explained in the comment for the hsearch function.
96   * The contents of the table is zeroed, especially the field used
97   * becomes zero.
98   */
99  
100  int hcreate_r(size_t nel, struct hsearch_data *htab)
101  {
102  	/* Test for correct arguments.  */
103  	if (htab == NULL) {
104  		__set_errno(EINVAL);
105  		return 0;
106  	}
107  
108  	/* There is still another table active. Return with error. */
109  	if (htab->table != NULL)
110  		return 0;
111  
112  	/* Change nel to the first prime number not smaller as nel. */
113  	nel |= 1;		/* make odd */
114  	while (!isprime(nel))
115  		nel += 2;
116  
117  	htab->size = nel;
118  	htab->filled = 0;
119  
120  	/* allocate memory and zero out */
121  	htab->table = (_ENTRY *) calloc(htab->size + 1, sizeof(_ENTRY));
122  	if (htab->table == NULL)
123  		return 0;
124  
125  	/* everything went alright */
126  	return 1;
127  }
128  
129  
130  /*
131   * hdestroy()
132   */
133  
134  /*
135   * After using the hash table it has to be destroyed. The used memory can
136   * be freed and the local static variable can be marked as not used.
137   */
138  
139  void hdestroy_r(struct hsearch_data *htab)
140  {
141  	int i;
142  
143  	/* Test for correct arguments.  */
144  	if (htab == NULL) {
145  		__set_errno(EINVAL);
146  		return;
147  	}
148  
149  	/* free used memory */
150  	for (i = 1; i <= htab->size; ++i) {
151  		if (htab->table[i].used > 0) {
152  			ENTRY *ep = &htab->table[i].entry;
153  
154  			free((void *)ep->key);
155  			free(ep->data);
156  		}
157  	}
158  	free(htab->table);
159  
160  	/* the sign for an existing table is an value != NULL in htable */
161  	htab->table = NULL;
162  }
163  
164  /*
165   * hsearch()
166   */
167  
168  /*
169   * This is the search function. It uses double hashing with open addressing.
170   * The argument item.key has to be a pointer to an zero terminated, most
171   * probably strings of chars. The function for generating a number of the
172   * strings is simple but fast. It can be replaced by a more complex function
173   * like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
174   *
175   * We use an trick to speed up the lookup. The table is created by hcreate
176   * with one more element available. This enables us to use the index zero
177   * special. This index will never be used because we store the first hash
178   * index in the field used where zero means not used. Every other value
179   * means used. The used field can be used as a first fast comparison for
180   * equality of the stored and the parameter value. This helps to prevent
181   * unnecessary expensive calls of strcmp.
182   *
183   * This implementation differs from the standard library version of
184   * this function in a number of ways:
185   *
186   * - While the standard version does not make any assumptions about
187   *   the type of the stored data objects at all, this implementation
188   *   works with NUL terminated strings only.
189   * - Instead of storing just pointers to the original objects, we
190   *   create local copies so the caller does not need to care about the
191   *   data any more.
192   * - The standard implementation does not provide a way to update an
193   *   existing entry.  This version will create a new entry or update an
194   *   existing one when both "action == ENTER" and "item.data != NULL".
195   * - Instead of returning 1 on success, we return the index into the
196   *   internal hash table, which is also guaranteed to be positive.
197   *   This allows us direct access to the found hash table slot for
198   *   example for functions like hdelete().
199   */
200  
201  int hmatch_r(const char *match, int last_idx, ENTRY ** retval,
202  	     struct hsearch_data *htab)
203  {
204  	unsigned int idx;
205  	size_t key_len = strlen(match);
206  
207  	for (idx = last_idx + 1; idx < htab->size; ++idx) {
208  		if (htab->table[idx].used <= 0)
209  			continue;
210  		if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
211  			*retval = &htab->table[idx].entry;
212  			return idx;
213  		}
214  	}
215  
216  	__set_errno(ESRCH);
217  	*retval = NULL;
218  	return 0;
219  }
220  
221  /*
222   * Compare an existing entry with the desired key, and overwrite if the action
223   * is ENTER.  This is simply a helper function for hsearch_r().
224   */
225  static inline int _compare_and_overwrite_entry(ENTRY item, ACTION action,
226  	ENTRY **retval, struct hsearch_data *htab, int flag,
227  	unsigned int hval, unsigned int idx)
228  {
229  	if (htab->table[idx].used == hval
230  	    && strcmp(item.key, htab->table[idx].entry.key) == 0) {
231  		/* Overwrite existing value? */
232  		if ((action == ENTER) && (item.data != NULL)) {
233  			/* check for permission */
234  			if (htab->change_ok != NULL && htab->change_ok(
235  			    &htab->table[idx].entry, item.data,
236  			    env_op_overwrite, flag)) {
237  				debug("change_ok() rejected setting variable "
238  					"%s, skipping it!\n", item.key);
239  				__set_errno(EPERM);
240  				*retval = NULL;
241  				return 0;
242  			}
243  
244  			/* If there is a callback, call it */
245  			if (htab->table[idx].entry.callback &&
246  			    htab->table[idx].entry.callback(item.key,
247  			    item.data, env_op_overwrite, flag)) {
248  				debug("callback() rejected setting variable "
249  					"%s, skipping it!\n", item.key);
250  				__set_errno(EINVAL);
251  				*retval = NULL;
252  				return 0;
253  			}
254  
255  			free(htab->table[idx].entry.data);
256  			htab->table[idx].entry.data = strdup(item.data);
257  			if (!htab->table[idx].entry.data) {
258  				__set_errno(ENOMEM);
259  				*retval = NULL;
260  				return 0;
261  			}
262  		}
263  		/* return found entry */
264  		*retval = &htab->table[idx].entry;
265  		return idx;
266  	}
267  	/* keep searching */
268  	return -1;
269  }
270  
271  int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
272  	      struct hsearch_data *htab, int flag)
273  {
274  	unsigned int hval;
275  	unsigned int count;
276  	unsigned int len = strlen(item.key);
277  	unsigned int idx;
278  	unsigned int first_deleted = 0;
279  	int ret;
280  
281  	/* Compute an value for the given string. Perhaps use a better method. */
282  	hval = len;
283  	count = len;
284  	while (count-- > 0) {
285  		hval <<= 4;
286  		hval += item.key[count];
287  	}
288  
289  	/*
290  	 * First hash function:
291  	 * simply take the modul but prevent zero.
292  	 */
293  	hval %= htab->size;
294  	if (hval == 0)
295  		++hval;
296  
297  	/* The first index tried. */
298  	idx = hval;
299  
300  	if (htab->table[idx].used) {
301  		/*
302  		 * Further action might be required according to the
303  		 * action value.
304  		 */
305  		unsigned hval2;
306  
307  		if (htab->table[idx].used == -1
308  		    && !first_deleted)
309  			first_deleted = idx;
310  
311  		ret = _compare_and_overwrite_entry(item, action, retval, htab,
312  			flag, hval, idx);
313  		if (ret != -1)
314  			return ret;
315  
316  		/*
317  		 * Second hash function:
318  		 * as suggested in [Knuth]
319  		 */
320  		hval2 = 1 + hval % (htab->size - 2);
321  
322  		do {
323  			/*
324  			 * Because SIZE is prime this guarantees to
325  			 * step through all available indices.
326  			 */
327  			if (idx <= hval2)
328  				idx = htab->size + idx - hval2;
329  			else
330  				idx -= hval2;
331  
332  			/*
333  			 * If we visited all entries leave the loop
334  			 * unsuccessfully.
335  			 */
336  			if (idx == hval)
337  				break;
338  
339  			/* If entry is found use it. */
340  			ret = _compare_and_overwrite_entry(item, action, retval,
341  				htab, flag, hval, idx);
342  			if (ret != -1)
343  				return ret;
344  		}
345  		while (htab->table[idx].used);
346  	}
347  
348  	/* An empty bucket has been found. */
349  	if (action == ENTER) {
350  		/*
351  		 * If table is full and another entry should be
352  		 * entered return with error.
353  		 */
354  		if (htab->filled == htab->size) {
355  			__set_errno(ENOMEM);
356  			*retval = NULL;
357  			return 0;
358  		}
359  
360  		/*
361  		 * Create new entry;
362  		 * create copies of item.key and item.data
363  		 */
364  		if (first_deleted)
365  			idx = first_deleted;
366  
367  		htab->table[idx].used = hval;
368  		htab->table[idx].entry.key = strdup(item.key);
369  		htab->table[idx].entry.data = strdup(item.data);
370  		if (!htab->table[idx].entry.key ||
371  		    !htab->table[idx].entry.data) {
372  			__set_errno(ENOMEM);
373  			*retval = NULL;
374  			return 0;
375  		}
376  
377  		++htab->filled;
378  
379  		/* This is a new entry, so look up a possible callback */
380  		env_callback_init(&htab->table[idx].entry);
381  		/* Also look for flags */
382  		env_flags_init(&htab->table[idx].entry);
383  
384  		/* check for permission */
385  		if (htab->change_ok != NULL && htab->change_ok(
386  		    &htab->table[idx].entry, item.data, env_op_create, flag)) {
387  			debug("change_ok() rejected setting variable "
388  				"%s, skipping it!\n", item.key);
389  			_hdelete(item.key, htab, &htab->table[idx].entry, idx);
390  			__set_errno(EPERM);
391  			*retval = NULL;
392  			return 0;
393  		}
394  
395  		/* If there is a callback, call it */
396  		if (htab->table[idx].entry.callback &&
397  		    htab->table[idx].entry.callback(item.key, item.data,
398  		    env_op_create, flag)) {
399  			debug("callback() rejected setting variable "
400  				"%s, skipping it!\n", item.key);
401  			_hdelete(item.key, htab, &htab->table[idx].entry, idx);
402  			__set_errno(EINVAL);
403  			*retval = NULL;
404  			return 0;
405  		}
406  
407  		/* return new entry */
408  		*retval = &htab->table[idx].entry;
409  		return 1;
410  	}
411  
412  	__set_errno(ESRCH);
413  	*retval = NULL;
414  	return 0;
415  }
416  
417  
418  /*
419   * hdelete()
420   */
421  
422  /*
423   * The standard implementation of hsearch(3) does not provide any way
424   * to delete any entries from the hash table.  We extend the code to
425   * do that.
426   */
427  
428  static void _hdelete(const char *key, struct hsearch_data *htab, ENTRY *ep,
429  	int idx)
430  {
431  	/* free used ENTRY */
432  	debug("hdelete: DELETING key \"%s\"\n", key);
433  	free((void *)ep->key);
434  	free(ep->data);
435  	ep->callback = NULL;
436  	ep->flags = 0;
437  	htab->table[idx].used = -1;
438  
439  	--htab->filled;
440  }
441  
442  int hdelete_r(const char *key, struct hsearch_data *htab, int flag)
443  {
444  	ENTRY e, *ep;
445  	int idx;
446  
447  	debug("hdelete: DELETE key \"%s\"\n", key);
448  
449  	e.key = (char *)key;
450  
451  	idx = hsearch_r(e, FIND, &ep, htab, 0);
452  	if (idx == 0) {
453  		__set_errno(ESRCH);
454  		return 0;	/* not found */
455  	}
456  
457  	/* Check for permission */
458  	if (htab->change_ok != NULL &&
459  	    htab->change_ok(ep, NULL, env_op_delete, flag)) {
460  		debug("change_ok() rejected deleting variable "
461  			"%s, skipping it!\n", key);
462  		__set_errno(EPERM);
463  		return 0;
464  	}
465  
466  	/* If there is a callback, call it */
467  	if (htab->table[idx].entry.callback &&
468  	    htab->table[idx].entry.callback(key, NULL, env_op_delete, flag)) {
469  		debug("callback() rejected deleting variable "
470  			"%s, skipping it!\n", key);
471  		__set_errno(EINVAL);
472  		return 0;
473  	}
474  
475  	_hdelete(key, htab, ep, idx);
476  
477  	return 1;
478  }
479  
480  #if !(defined(CONFIG_SPL_BUILD) && !defined(CONFIG_SPL_SAVEENV))
481  /*
482   * hexport()
483   */
484  
485  /*
486   * Export the data stored in the hash table in linearized form.
487   *
488   * Entries are exported as "name=value" strings, separated by an
489   * arbitrary (non-NUL, of course) separator character. This allows to
490   * use this function both when formatting the U-Boot environment for
491   * external storage (using '\0' as separator), but also when using it
492   * for the "printenv" command to print all variables, simply by using
493   * as '\n" as separator. This can also be used for new features like
494   * exporting the environment data as text file, including the option
495   * for later re-import.
496   *
497   * The entries in the result list will be sorted by ascending key
498   * values.
499   *
500   * If the separator character is different from NUL, then any
501   * separator characters and backslash characters in the values will
502   * be escaped by a preceding backslash in output. This is needed for
503   * example to enable multi-line values, especially when the output
504   * shall later be parsed (for example, for re-import).
505   *
506   * There are several options how the result buffer is handled:
507   *
508   * *resp  size
509   * -----------
510   *  NULL    0	A string of sufficient length will be allocated.
511   *  NULL   >0	A string of the size given will be
512   *		allocated. An error will be returned if the size is
513   *		not sufficient.  Any unused bytes in the string will
514   *		be '\0'-padded.
515   * !NULL    0	The user-supplied buffer will be used. No length
516   *		checking will be performed, i. e. it is assumed that
517   *		the buffer size will always be big enough. DANGEROUS.
518   * !NULL   >0	The user-supplied buffer will be used. An error will
519   *		be returned if the size is not sufficient.  Any unused
520   *		bytes in the string will be '\0'-padded.
521   */
522  
523  static int cmpkey(const void *p1, const void *p2)
524  {
525  	ENTRY *e1 = *(ENTRY **) p1;
526  	ENTRY *e2 = *(ENTRY **) p2;
527  
528  	return (strcmp(e1->key, e2->key));
529  }
530  
531  static int match_string(int flag, const char *str, const char *pat, void *priv)
532  {
533  	switch (flag & H_MATCH_METHOD) {
534  	case H_MATCH_IDENT:
535  		if (strcmp(str, pat) == 0)
536  			return 1;
537  		break;
538  	case H_MATCH_SUBSTR:
539  		if (strstr(str, pat))
540  			return 1;
541  		break;
542  #ifdef CONFIG_REGEX
543  	case H_MATCH_REGEX:
544  		{
545  			struct slre *slrep = (struct slre *)priv;
546  			struct cap caps[slrep->num_caps + 2];
547  
548  			if (slre_match(slrep, str, strlen(str), caps))
549  				return 1;
550  		}
551  		break;
552  #endif
553  	default:
554  		printf("## ERROR: unsupported match method: 0x%02x\n",
555  			flag & H_MATCH_METHOD);
556  		break;
557  	}
558  	return 0;
559  }
560  
561  static int match_entry(ENTRY *ep, int flag,
562  		 int argc, char * const argv[])
563  {
564  	int arg;
565  	void *priv = NULL;
566  
567  	for (arg = 0; arg < argc; ++arg) {
568  #ifdef CONFIG_REGEX
569  		struct slre slre;
570  
571  		if (slre_compile(&slre, argv[arg]) == 0) {
572  			printf("Error compiling regex: %s\n", slre.err_str);
573  			return 0;
574  		}
575  
576  		priv = (void *)&slre;
577  #endif
578  		if (flag & H_MATCH_KEY) {
579  			if (match_string(flag, ep->key, argv[arg], priv))
580  				return 1;
581  		}
582  		if (flag & H_MATCH_DATA) {
583  			if (match_string(flag, ep->data, argv[arg], priv))
584  				return 1;
585  		}
586  	}
587  	return 0;
588  }
589  
590  ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag,
591  		 char **resp, size_t size,
592  		 int argc, char * const argv[])
593  {
594  	ENTRY *list[htab->size];
595  	char *res, *p;
596  	size_t totlen;
597  	int i, n;
598  
599  	/* Test for correct arguments.  */
600  	if ((resp == NULL) || (htab == NULL)) {
601  		__set_errno(EINVAL);
602  		return (-1);
603  	}
604  
605  	debug("EXPORT  table = %p, htab.size = %d, htab.filled = %d, size = %lu\n",
606  	      htab, htab->size, htab->filled, (ulong)size);
607  	/*
608  	 * Pass 1:
609  	 * search used entries,
610  	 * save addresses and compute total length
611  	 */
612  	for (i = 1, n = 0, totlen = 0; i <= htab->size; ++i) {
613  
614  		if (htab->table[i].used > 0) {
615  			ENTRY *ep = &htab->table[i].entry;
616  			int found = match_entry(ep, flag, argc, argv);
617  
618  			if ((argc > 0) && (found == 0))
619  				continue;
620  
621  			if ((flag & H_HIDE_DOT) && ep->key[0] == '.')
622  				continue;
623  
624  			list[n++] = ep;
625  
626  			totlen += strlen(ep->key) + 2;
627  
628  			if (sep == '\0') {
629  				totlen += strlen(ep->data);
630  			} else {	/* check if escapes are needed */
631  				char *s = ep->data;
632  
633  				while (*s) {
634  					++totlen;
635  					/* add room for needed escape chars */
636  					if ((*s == sep) || (*s == '\\'))
637  						++totlen;
638  					++s;
639  				}
640  			}
641  			totlen += 2;	/* for '=' and 'sep' char */
642  		}
643  	}
644  
645  #ifdef DEBUG
646  	/* Pass 1a: print unsorted list */
647  	printf("Unsorted: n=%d\n", n);
648  	for (i = 0; i < n; ++i) {
649  		printf("\t%3d: %p ==> %-10s => %s\n",
650  		       i, list[i], list[i]->key, list[i]->data);
651  	}
652  #endif
653  
654  	/* Sort list by keys */
655  	qsort(list, n, sizeof(ENTRY *), cmpkey);
656  
657  	/* Check if the user supplied buffer size is sufficient */
658  	if (size) {
659  		if (size < totlen + 1) {	/* provided buffer too small */
660  			printf("Env export buffer too small: %lu, but need %lu\n",
661  			       (ulong)size, (ulong)totlen + 1);
662  			__set_errno(ENOMEM);
663  			return (-1);
664  		}
665  	} else {
666  		size = totlen + 1;
667  	}
668  
669  	/* Check if the user provided a buffer */
670  	if (*resp) {
671  		/* yes; clear it */
672  		res = *resp;
673  		memset(res, '\0', size);
674  	} else {
675  		/* no, allocate and clear one */
676  		*resp = res = calloc(1, size);
677  		if (res == NULL) {
678  			__set_errno(ENOMEM);
679  			return (-1);
680  		}
681  	}
682  	/*
683  	 * Pass 2:
684  	 * export sorted list of result data
685  	 */
686  	for (i = 0, p = res; i < n; ++i) {
687  		const char *s;
688  
689  		s = list[i]->key;
690  		while (*s)
691  			*p++ = *s++;
692  		*p++ = '=';
693  
694  		s = list[i]->data;
695  
696  		while (*s) {
697  			if ((*s == sep) || (*s == '\\'))
698  				*p++ = '\\';	/* escape */
699  			*p++ = *s++;
700  		}
701  		*p++ = sep;
702  	}
703  	*p = '\0';		/* terminate result */
704  
705  	return size;
706  }
707  #endif
708  
709  
710  /*
711   * himport()
712   */
713  
714  /*
715   * Check whether variable 'name' is amongst vars[],
716   * and remove all instances by setting the pointer to NULL
717   */
718  static int drop_var_from_set(const char *name, int nvars, char * vars[])
719  {
720  	int i = 0;
721  	int res = 0;
722  
723  	/* No variables specified means process all of them */
724  	if (nvars == 0)
725  		return 1;
726  
727  	for (i = 0; i < nvars; i++) {
728  		if (vars[i] == NULL)
729  			continue;
730  		/* If we found it, delete all of them */
731  		if (!strcmp(name, vars[i])) {
732  			vars[i] = NULL;
733  			res = 1;
734  		}
735  	}
736  	if (!res)
737  		debug("Skipping non-listed variable %s\n", name);
738  
739  	return res;
740  }
741  
742  /*
743   * Import linearized data into hash table.
744   *
745   * This is the inverse function to hexport(): it takes a linear list
746   * of "name=value" pairs and creates hash table entries from it.
747   *
748   * Entries without "value", i. e. consisting of only "name" or
749   * "name=", will cause this entry to be deleted from the hash table.
750   *
751   * The "flag" argument can be used to control the behaviour: when the
752   * H_NOCLEAR bit is set, then an existing hash table will kept, i. e.
753   * new data will be added to an existing hash table; otherwise, old
754   * data will be discarded and a new hash table will be created.
755   *
756   * The separator character for the "name=value" pairs can be selected,
757   * so we both support importing from externally stored environment
758   * data (separated by NUL characters) and from plain text files
759   * (entries separated by newline characters).
760   *
761   * To allow for nicely formatted text input, leading white space
762   * (sequences of SPACE and TAB chars) is ignored, and entries starting
763   * (after removal of any leading white space) with a '#' character are
764   * considered comments and ignored.
765   *
766   * [NOTE: this means that a variable name cannot start with a '#'
767   * character.]
768   *
769   * When using a non-NUL separator character, backslash is used as
770   * escape character in the value part, allowing for example for
771   * multi-line values.
772   *
773   * In theory, arbitrary separator characters can be used, but only
774   * '\0' and '\n' have really been tested.
775   */
776  
777  int himport_r(struct hsearch_data *htab,
778  		const char *env, size_t size, const char sep, int flag,
779  		int crlf_is_lf, int nvars, char * const vars[])
780  {
781  	char *data, *sp, *dp, *name, *value;
782  	char *localvars[nvars];
783  	int i;
784  
785  	/* Test for correct arguments.  */
786  	if (htab == NULL) {
787  		__set_errno(EINVAL);
788  		return 0;
789  	}
790  
791  	/* we allocate new space to make sure we can write to the array */
792  	if ((data = malloc(size + 1)) == NULL) {
793  		debug("himport_r: can't malloc %lu bytes\n", (ulong)size + 1);
794  		__set_errno(ENOMEM);
795  		return 0;
796  	}
797  	memcpy(data, env, size);
798  	data[size] = '\0';
799  	dp = data;
800  
801  	/* make a local copy of the list of variables */
802  	if (nvars)
803  		memcpy(localvars, vars, sizeof(vars[0]) * nvars);
804  
805  	if ((flag & H_NOCLEAR) == 0) {
806  		/* Destroy old hash table if one exists */
807  		debug("Destroy Hash Table: %p table = %p\n", htab,
808  		       htab->table);
809  		if (htab->table)
810  			hdestroy_r(htab);
811  	}
812  
813  	/*
814  	 * Create new hash table (if needed).  The computation of the hash
815  	 * table size is based on heuristics: in a sample of some 70+
816  	 * existing systems we found an average size of 39+ bytes per entry
817  	 * in the environment (for the whole key=value pair). Assuming a
818  	 * size of 8 per entry (= safety factor of ~5) should provide enough
819  	 * safety margin for any existing environment definitions and still
820  	 * allow for more than enough dynamic additions. Note that the
821  	 * "size" argument is supposed to give the maximum environment size
822  	 * (CONFIG_ENV_SIZE).  This heuristics will result in
823  	 * unreasonably large numbers (and thus memory footprint) for
824  	 * big flash environments (>8,000 entries for 64 KB
825  	 * environment size), so we clip it to a reasonable value.
826  	 * On the other hand we need to add some more entries for free
827  	 * space when importing very small buffers. Both boundaries can
828  	 * be overwritten in the board config file if needed.
829  	 */
830  
831  	if (!htab->table) {
832  		int nent = CONFIG_ENV_MIN_ENTRIES + size / 8;
833  
834  		if (nent > CONFIG_ENV_MAX_ENTRIES)
835  			nent = CONFIG_ENV_MAX_ENTRIES;
836  
837  		debug("Create Hash Table: N=%d\n", nent);
838  
839  		if (hcreate_r(nent, htab) == 0) {
840  			free(data);
841  			return 0;
842  		}
843  	}
844  
845  	if (!size) {
846  		free(data);
847  		return 1;		/* everything OK */
848  	}
849  	if(crlf_is_lf) {
850  		/* Remove Carriage Returns in front of Line Feeds */
851  		unsigned ignored_crs = 0;
852  		for(;dp < data + size && *dp; ++dp) {
853  			if(*dp == '\r' &&
854  			   dp < data + size - 1 && *(dp+1) == '\n')
855  				++ignored_crs;
856  			else
857  				*(dp-ignored_crs) = *dp;
858  		}
859  		size -= ignored_crs;
860  		dp = data;
861  	}
862  	/* Parse environment; allow for '\0' and 'sep' as separators */
863  	do {
864  		ENTRY e, *rv;
865  
866  		/* skip leading white space */
867  		while (isblank(*dp))
868  			++dp;
869  
870  		/* skip comment lines */
871  		if (*dp == '#') {
872  			while (*dp && (*dp != sep))
873  				++dp;
874  			++dp;
875  			continue;
876  		}
877  
878  		/* parse name */
879  		for (name = dp; *dp != '=' && *dp && *dp != sep; ++dp)
880  			;
881  
882  		/* deal with "name" and "name=" entries (delete var) */
883  		if (*dp == '\0' || *(dp + 1) == '\0' ||
884  		    *dp == sep || *(dp + 1) == sep) {
885  			if (*dp == '=')
886  				*dp++ = '\0';
887  			*dp++ = '\0';	/* terminate name */
888  
889  			debug("DELETE CANDIDATE: \"%s\"\n", name);
890  			if (!drop_var_from_set(name, nvars, localvars))
891  				continue;
892  
893  			if (hdelete_r(name, htab, flag) == 0)
894  				debug("DELETE ERROR ##############################\n");
895  
896  			continue;
897  		}
898  		*dp++ = '\0';	/* terminate name */
899  
900  		/* parse value; deal with escapes */
901  		for (value = sp = dp; *dp && (*dp != sep); ++dp) {
902  			if ((*dp == '\\') && *(dp + 1))
903  				++dp;
904  			*sp++ = *dp;
905  		}
906  		*sp++ = '\0';	/* terminate value */
907  		++dp;
908  
909  		if (*name == 0) {
910  			debug("INSERT: unable to use an empty key\n");
911  			__set_errno(EINVAL);
912  			free(data);
913  			return 0;
914  		}
915  
916  		/* Skip variables which are not supposed to be processed */
917  		if (!drop_var_from_set(name, nvars, localvars))
918  			continue;
919  
920  		/* enter into hash table */
921  		e.key = name;
922  		e.data = value;
923  
924  		hsearch_r(e, ENTER, &rv, htab, flag);
925  		if (rv == NULL)
926  			printf("himport_r: can't insert \"%s=%s\" into hash table\n",
927  				name, value);
928  
929  		debug("INSERT: table %p, filled %d/%d rv %p ==> name=\"%s\" value=\"%s\"\n",
930  			htab, htab->filled, htab->size,
931  			rv, name, value);
932  	} while ((dp < data + size) && *dp);	/* size check needed for text */
933  						/* without '\0' termination */
934  	debug("INSERT: free(data = %p)\n", data);
935  	free(data);
936  
937  	/* process variables which were not considered */
938  	for (i = 0; i < nvars; i++) {
939  		if (localvars[i] == NULL)
940  			continue;
941  		/*
942  		 * All variables which were not deleted from the variable list
943  		 * were not present in the imported env
944  		 * This could mean two things:
945  		 * a) if the variable was present in current env, we delete it
946  		 * b) if the variable was not present in current env, we notify
947  		 *    it might be a typo
948  		 */
949  		if (hdelete_r(localvars[i], htab, flag) == 0)
950  			printf("WARNING: '%s' neither in running nor in imported env!\n", localvars[i]);
951  		else
952  			printf("WARNING: '%s' not in imported env, deleting it!\n", localvars[i]);
953  	}
954  
955  	debug("INSERT: done\n");
956  	return 1;		/* everything OK */
957  }
958  
959  /*
960   * hwalk_r()
961   */
962  
963  /*
964   * Walk all of the entries in the hash, calling the callback for each one.
965   * this allows some generic operation to be performed on each element.
966   */
967  int hwalk_r(struct hsearch_data *htab, int (*callback)(ENTRY *))
968  {
969  	int i;
970  	int retval;
971  
972  	for (i = 1; i <= htab->size; ++i) {
973  		if (htab->table[i].used > 0) {
974  			retval = callback(&htab->table[i].entry);
975  			if (retval)
976  				return retval;
977  		}
978  	}
979  
980  	return 0;
981  }
982