]> git.sur5r.net Git - u-boot/blob - lib/hashtable.c
efi_selftest: avoid superfluous messages for task priority levels
[u-boot] / lib / hashtable.c
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 }