Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 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 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 | * The GNU C Library is free software; you can redistribute it and/or |
| 14 | * modify it under the terms of the GNU Lesser General Public |
| 15 | * License as published by the Free Software Foundation; either |
| 16 | * version 2.1 of the License, or (at your option) any later version. |
| 17 | * |
| 18 | * The GNU C Library is distributed in the hope that it will be useful, |
| 19 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 20 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 21 | * Lesser General Public License for more details. |
| 22 | * |
| 23 | * You should have received a copy of the GNU Lesser General Public |
| 24 | * License along with the GNU C Library; if not, write to the Free |
| 25 | * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 26 | * 02111-1307 USA. |
| 27 | */ |
| 28 | |
| 29 | #include <errno.h> |
| 30 | #include <malloc.h> |
| 31 | |
| 32 | #ifdef USE_HOSTCC /* HOST build */ |
| 33 | # include <string.h> |
| 34 | # include <assert.h> |
| 35 | |
| 36 | # ifndef debug |
| 37 | # ifdef DEBUG |
| 38 | # define debug(fmt,args...) printf(fmt ,##args) |
| 39 | # else |
| 40 | # define debug(fmt,args...) |
| 41 | # endif |
| 42 | # endif |
| 43 | #else /* U-Boot build */ |
| 44 | # include <common.h> |
| 45 | # include <linux/string.h> |
| 46 | #endif |
| 47 | |
Andreas Bießmann | fc5fc76 | 2010-10-01 22:51:02 +0200 | [diff] [blame] | 48 | #ifndef CONFIG_ENV_MIN_ENTRIES /* minimum number of entries */ |
| 49 | #define CONFIG_ENV_MIN_ENTRIES 64 |
| 50 | #endif |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 51 | #ifndef CONFIG_ENV_MAX_ENTRIES /* maximum number of entries */ |
| 52 | #define CONFIG_ENV_MAX_ENTRIES 512 |
| 53 | #endif |
| 54 | |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 55 | #include "search.h" |
| 56 | |
| 57 | /* |
| 58 | * [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986 |
Wolfgang Denk | 071bc92 | 2010-10-27 22:48:30 +0200 | [diff] [blame^] | 59 | * [Knuth] The Art of Computer Programming, part 3 (6.4) |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 60 | */ |
| 61 | |
| 62 | /* |
| 63 | * The non-reentrant version use a global space for storing the hash table. |
| 64 | */ |
| 65 | static struct hsearch_data htab; |
| 66 | |
| 67 | /* |
| 68 | * The reentrant version has no static variables to maintain the state. |
| 69 | * Instead the interface of all functions is extended to take an argument |
| 70 | * which describes the current status. |
| 71 | */ |
| 72 | typedef struct _ENTRY { |
| 73 | unsigned int used; |
| 74 | ENTRY entry; |
| 75 | } _ENTRY; |
| 76 | |
| 77 | |
| 78 | /* |
| 79 | * hcreate() |
| 80 | */ |
| 81 | |
| 82 | /* |
| 83 | * For the used double hash method the table size has to be a prime. To |
| 84 | * correct the user given table size we need a prime test. This trivial |
| 85 | * algorithm is adequate because |
| 86 | * a) the code is (most probably) called a few times per program run and |
| 87 | * b) the number is small because the table must fit in the core |
| 88 | * */ |
| 89 | static int isprime(unsigned int number) |
| 90 | { |
| 91 | /* no even number will be passed */ |
| 92 | unsigned int div = 3; |
| 93 | |
| 94 | while (div * div < number && number % div != 0) |
| 95 | div += 2; |
| 96 | |
| 97 | return number % div != 0; |
| 98 | } |
| 99 | |
| 100 | int hcreate(size_t nel) |
| 101 | { |
| 102 | return hcreate_r(nel, &htab); |
| 103 | } |
| 104 | |
| 105 | /* |
| 106 | * Before using the hash table we must allocate memory for it. |
| 107 | * Test for an existing table are done. We allocate one element |
| 108 | * more as the found prime number says. This is done for more effective |
| 109 | * indexing as explained in the comment for the hsearch function. |
| 110 | * The contents of the table is zeroed, especially the field used |
| 111 | * becomes zero. |
| 112 | */ |
| 113 | int hcreate_r(size_t nel, struct hsearch_data *htab) |
| 114 | { |
| 115 | /* Test for correct arguments. */ |
| 116 | if (htab == NULL) { |
| 117 | __set_errno(EINVAL); |
| 118 | return 0; |
| 119 | } |
| 120 | |
| 121 | /* There is still another table active. Return with error. */ |
| 122 | if (htab->table != NULL) |
| 123 | return 0; |
| 124 | |
| 125 | /* Change nel to the first prime number not smaller as nel. */ |
| 126 | nel |= 1; /* make odd */ |
| 127 | while (!isprime(nel)) |
| 128 | nel += 2; |
| 129 | |
| 130 | htab->size = nel; |
| 131 | htab->filled = 0; |
| 132 | |
| 133 | /* allocate memory and zero out */ |
| 134 | htab->table = (_ENTRY *) calloc(htab->size + 1, sizeof(_ENTRY)); |
| 135 | if (htab->table == NULL) |
| 136 | return 0; |
| 137 | |
| 138 | /* everything went alright */ |
| 139 | return 1; |
| 140 | } |
| 141 | |
| 142 | |
| 143 | /* |
| 144 | * hdestroy() |
| 145 | */ |
| 146 | void hdestroy(void) |
| 147 | { |
| 148 | hdestroy_r(&htab); |
| 149 | } |
| 150 | |
| 151 | /* |
| 152 | * After using the hash table it has to be destroyed. The used memory can |
| 153 | * be freed and the local static variable can be marked as not used. |
| 154 | */ |
| 155 | void hdestroy_r(struct hsearch_data *htab) |
| 156 | { |
| 157 | int i; |
| 158 | |
| 159 | /* Test for correct arguments. */ |
| 160 | if (htab == NULL) { |
| 161 | __set_errno(EINVAL); |
| 162 | return; |
| 163 | } |
| 164 | |
| 165 | /* free used memory */ |
| 166 | for (i = 1; i <= htab->size; ++i) { |
| 167 | if (htab->table[i].used) { |
| 168 | ENTRY *ep = &htab->table[i].entry; |
| 169 | |
| 170 | free(ep->key); |
| 171 | free(ep->data); |
| 172 | } |
| 173 | } |
| 174 | free(htab->table); |
| 175 | |
| 176 | /* the sign for an existing table is an value != NULL in htable */ |
| 177 | htab->table = NULL; |
| 178 | } |
| 179 | |
| 180 | /* |
| 181 | * hsearch() |
| 182 | */ |
| 183 | |
| 184 | /* |
| 185 | * This is the search function. It uses double hashing with open addressing. |
| 186 | * The argument item.key has to be a pointer to an zero terminated, most |
| 187 | * probably strings of chars. The function for generating a number of the |
| 188 | * strings is simple but fast. It can be replaced by a more complex function |
| 189 | * like ajw (see [Aho,Sethi,Ullman]) if the needs are shown. |
| 190 | * |
| 191 | * We use an trick to speed up the lookup. The table is created by hcreate |
| 192 | * with one more element available. This enables us to use the index zero |
| 193 | * special. This index will never be used because we store the first hash |
| 194 | * index in the field used where zero means not used. Every other value |
| 195 | * means used. The used field can be used as a first fast comparison for |
| 196 | * equality of the stored and the parameter value. This helps to prevent |
| 197 | * unnecessary expensive calls of strcmp. |
| 198 | * |
| 199 | * This implementation differs from the standard library version of |
| 200 | * this function in a number of ways: |
| 201 | * |
| 202 | * - While the standard version does not make any assumptions about |
| 203 | * the type of the stored data objects at all, this implementation |
| 204 | * works with NUL terminated strings only. |
| 205 | * - Instead of storing just pointers to the original objects, we |
| 206 | * create local copies so the caller does not need to care about the |
| 207 | * data any more. |
| 208 | * - The standard implementation does not provide a way to update an |
| 209 | * existing entry. This version will create a new entry or update an |
| 210 | * existing one when both "action == ENTER" and "item.data != NULL". |
| 211 | * - Instead of returning 1 on success, we return the index into the |
| 212 | * internal hash table, which is also guaranteed to be positive. |
| 213 | * This allows us direct access to the found hash table slot for |
| 214 | * example for functions like hdelete(). |
| 215 | */ |
| 216 | |
| 217 | ENTRY *hsearch(ENTRY item, ACTION action) |
| 218 | { |
| 219 | ENTRY *result; |
| 220 | |
| 221 | (void) hsearch_r(item, action, &result, &htab); |
| 222 | |
| 223 | return result; |
| 224 | } |
| 225 | |
| 226 | int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, |
| 227 | struct hsearch_data *htab) |
| 228 | { |
| 229 | unsigned int hval; |
| 230 | unsigned int count; |
| 231 | unsigned int len = strlen(item.key); |
| 232 | unsigned int idx; |
| 233 | |
| 234 | /* Compute an value for the given string. Perhaps use a better method. */ |
| 235 | hval = len; |
| 236 | count = len; |
| 237 | while (count-- > 0) { |
| 238 | hval <<= 4; |
| 239 | hval += item.key[count]; |
| 240 | } |
| 241 | |
| 242 | /* |
| 243 | * First hash function: |
| 244 | * simply take the modul but prevent zero. |
| 245 | */ |
| 246 | hval %= htab->size; |
| 247 | if (hval == 0) |
| 248 | ++hval; |
| 249 | |
| 250 | /* The first index tried. */ |
| 251 | idx = hval; |
| 252 | |
| 253 | if (htab->table[idx].used) { |
| 254 | /* |
Wolfgang Denk | 071bc92 | 2010-10-27 22:48:30 +0200 | [diff] [blame^] | 255 | * Further action might be required according to the |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 256 | * action value. |
| 257 | */ |
| 258 | unsigned hval2; |
| 259 | |
| 260 | if (htab->table[idx].used == hval |
| 261 | && strcmp(item.key, htab->table[idx].entry.key) == 0) { |
| 262 | /* Overwrite existing value? */ |
| 263 | if ((action == ENTER) && (item.data != NULL)) { |
| 264 | free(htab->table[idx].entry.data); |
| 265 | htab->table[idx].entry.data = |
| 266 | strdup(item.data); |
| 267 | if (!htab->table[idx].entry.data) { |
| 268 | __set_errno(ENOMEM); |
| 269 | *retval = NULL; |
| 270 | return 0; |
| 271 | } |
| 272 | } |
| 273 | /* return found entry */ |
| 274 | *retval = &htab->table[idx].entry; |
| 275 | return idx; |
| 276 | } |
| 277 | |
| 278 | /* |
| 279 | * Second hash function: |
| 280 | * as suggested in [Knuth] |
| 281 | */ |
| 282 | hval2 = 1 + hval % (htab->size - 2); |
| 283 | |
| 284 | do { |
| 285 | /* |
Wolfgang Denk | 071bc92 | 2010-10-27 22:48:30 +0200 | [diff] [blame^] | 286 | * Because SIZE is prime this guarantees to |
| 287 | * step through all available indices. |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 288 | */ |
| 289 | if (idx <= hval2) |
| 290 | idx = htab->size + idx - hval2; |
| 291 | else |
| 292 | idx -= hval2; |
| 293 | |
| 294 | /* |
| 295 | * If we visited all entries leave the loop |
| 296 | * unsuccessfully. |
| 297 | */ |
| 298 | if (idx == hval) |
| 299 | break; |
| 300 | |
| 301 | /* If entry is found use it. */ |
| 302 | if ((htab->table[idx].used == hval) |
| 303 | && strcmp(item.key, htab->table[idx].entry.key) == 0) { |
| 304 | /* Overwrite existing value? */ |
| 305 | if ((action == ENTER) && (item.data != NULL)) { |
| 306 | free(htab->table[idx].entry.data); |
| 307 | htab->table[idx].entry.data = |
| 308 | strdup(item.data); |
| 309 | if (!htab->table[idx].entry.data) { |
| 310 | __set_errno(ENOMEM); |
| 311 | *retval = NULL; |
| 312 | return 0; |
| 313 | } |
| 314 | } |
| 315 | /* return found entry */ |
| 316 | *retval = &htab->table[idx].entry; |
| 317 | return idx; |
| 318 | } |
| 319 | } |
| 320 | while (htab->table[idx].used); |
| 321 | } |
| 322 | |
| 323 | /* An empty bucket has been found. */ |
| 324 | if (action == ENTER) { |
| 325 | /* |
Wolfgang Denk | 071bc92 | 2010-10-27 22:48:30 +0200 | [diff] [blame^] | 326 | * If table is full and another entry should be |
| 327 | * entered return with error. |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 328 | */ |
| 329 | if (htab->filled == htab->size) { |
| 330 | __set_errno(ENOMEM); |
| 331 | *retval = NULL; |
| 332 | return 0; |
| 333 | } |
| 334 | |
| 335 | /* |
| 336 | * Create new entry; |
| 337 | * create copies of item.key and item.data |
| 338 | */ |
| 339 | htab->table[idx].used = hval; |
| 340 | htab->table[idx].entry.key = strdup(item.key); |
| 341 | htab->table[idx].entry.data = strdup(item.data); |
| 342 | if (!htab->table[idx].entry.key || |
| 343 | !htab->table[idx].entry.data) { |
| 344 | __set_errno(ENOMEM); |
| 345 | *retval = NULL; |
| 346 | return 0; |
| 347 | } |
| 348 | |
| 349 | ++htab->filled; |
| 350 | |
| 351 | /* return new entry */ |
| 352 | *retval = &htab->table[idx].entry; |
| 353 | return 1; |
| 354 | } |
| 355 | |
| 356 | __set_errno(ESRCH); |
| 357 | *retval = NULL; |
| 358 | return 0; |
| 359 | } |
| 360 | |
| 361 | |
| 362 | /* |
| 363 | * hdelete() |
| 364 | */ |
| 365 | |
| 366 | /* |
| 367 | * The standard implementation of hsearch(3) does not provide any way |
| 368 | * to delete any entries from the hash table. We extend the code to |
| 369 | * do that. |
| 370 | */ |
| 371 | |
| 372 | int hdelete(const char *key) |
| 373 | { |
| 374 | return hdelete_r(key, &htab); |
| 375 | } |
| 376 | |
| 377 | int hdelete_r(const char *key, struct hsearch_data *htab) |
| 378 | { |
| 379 | ENTRY e, *ep; |
| 380 | int idx; |
| 381 | |
| 382 | debug("hdelete: DELETE key \"%s\"\n", key); |
| 383 | |
| 384 | e.key = (char *)key; |
| 385 | |
| 386 | if ((idx = hsearch_r(e, FIND, &ep, htab)) == 0) { |
| 387 | __set_errno(ESRCH); |
| 388 | return 0; /* not found */ |
| 389 | } |
| 390 | |
| 391 | /* free used ENTRY */ |
| 392 | debug("hdelete: DELETING key \"%s\"\n", key); |
| 393 | |
| 394 | free(ep->key); |
| 395 | free(ep->data); |
| 396 | htab->table[idx].used = 0; |
| 397 | |
| 398 | --htab->filled; |
| 399 | |
| 400 | return 1; |
| 401 | } |
| 402 | |
| 403 | /* |
| 404 | * hexport() |
| 405 | */ |
| 406 | |
| 407 | /* |
| 408 | * Export the data stored in the hash table in linearized form. |
| 409 | * |
| 410 | * Entries are exported as "name=value" strings, separated by an |
| 411 | * arbitrary (non-NUL, of course) separator character. This allows to |
| 412 | * use this function both when formatting the U-Boot environment for |
| 413 | * external storage (using '\0' as separator), but also when using it |
| 414 | * for the "printenv" command to print all variables, simply by using |
| 415 | * as '\n" as separator. This can also be used for new features like |
| 416 | * exporting the environment data as text file, including the option |
| 417 | * for later re-import. |
| 418 | * |
| 419 | * The entries in the result list will be sorted by ascending key |
| 420 | * values. |
| 421 | * |
| 422 | * If the separator character is different from NUL, then any |
| 423 | * separator characters and backslash characters in the values will |
| 424 | * be escaped by a preceeding backslash in output. This is needed for |
| 425 | * example to enable multi-line values, especially when the output |
| 426 | * shall later be parsed (for example, for re-import). |
| 427 | * |
| 428 | * There are several options how the result buffer is handled: |
| 429 | * |
| 430 | * *resp size |
| 431 | * ----------- |
| 432 | * NULL 0 A string of sufficient length will be allocated. |
| 433 | * NULL >0 A string of the size given will be |
| 434 | * allocated. An error will be returned if the size is |
| 435 | * not sufficient. Any unused bytes in the string will |
| 436 | * be '\0'-padded. |
| 437 | * !NULL 0 The user-supplied buffer will be used. No length |
| 438 | * checking will be performed, i. e. it is assumed that |
| 439 | * the buffer size will always be big enough. DANGEROUS. |
| 440 | * !NULL >0 The user-supplied buffer will be used. An error will |
| 441 | * be returned if the size is not sufficient. Any unused |
| 442 | * bytes in the string will be '\0'-padded. |
| 443 | */ |
| 444 | |
| 445 | ssize_t hexport(const char sep, char **resp, size_t size) |
| 446 | { |
| 447 | return hexport_r(&htab, sep, resp, size); |
| 448 | } |
| 449 | |
| 450 | static int cmpkey(const void *p1, const void *p2) |
| 451 | { |
| 452 | ENTRY *e1 = *(ENTRY **) p1; |
| 453 | ENTRY *e2 = *(ENTRY **) p2; |
| 454 | |
| 455 | return (strcmp(e1->key, e2->key)); |
| 456 | } |
| 457 | |
| 458 | ssize_t hexport_r(struct hsearch_data *htab, const char sep, |
| 459 | char **resp, size_t size) |
| 460 | { |
| 461 | ENTRY *list[htab->size]; |
| 462 | char *res, *p; |
| 463 | size_t totlen; |
| 464 | int i, n; |
| 465 | |
| 466 | /* Test for correct arguments. */ |
| 467 | if ((resp == NULL) || (htab == NULL)) { |
| 468 | __set_errno(EINVAL); |
| 469 | return (-1); |
| 470 | } |
| 471 | |
| 472 | debug("EXPORT table = %p, htab.size = %d, htab.filled = %d, size = %d\n", |
| 473 | htab, htab->size, htab->filled, size); |
| 474 | /* |
| 475 | * Pass 1: |
| 476 | * search used entries, |
| 477 | * save addresses and compute total length |
| 478 | */ |
| 479 | for (i = 1, n = 0, totlen = 0; i <= htab->size; ++i) { |
| 480 | |
| 481 | if (htab->table[i].used) { |
| 482 | ENTRY *ep = &htab->table[i].entry; |
| 483 | |
| 484 | list[n++] = ep; |
| 485 | |
| 486 | totlen += strlen(ep->key) + 2; |
| 487 | |
| 488 | if (sep == '\0') { |
| 489 | totlen += strlen(ep->data); |
| 490 | } else { /* check if escapes are needed */ |
| 491 | char *s = ep->data; |
| 492 | |
| 493 | while (*s) { |
| 494 | ++totlen; |
| 495 | /* add room for needed escape chars */ |
| 496 | if ((*s == sep) || (*s == '\\')) |
| 497 | ++totlen; |
| 498 | ++s; |
| 499 | } |
| 500 | } |
| 501 | totlen += 2; /* for '=' and 'sep' char */ |
| 502 | } |
| 503 | } |
| 504 | |
| 505 | #ifdef DEBUG |
| 506 | /* Pass 1a: print unsorted list */ |
| 507 | printf("Unsorted: n=%d\n", n); |
| 508 | for (i = 0; i < n; ++i) { |
| 509 | printf("\t%3d: %p ==> %-10s => %s\n", |
| 510 | i, list[i], list[i]->key, list[i]->data); |
| 511 | } |
| 512 | #endif |
| 513 | |
| 514 | /* Sort list by keys */ |
| 515 | qsort(list, n, sizeof(ENTRY *), cmpkey); |
| 516 | |
| 517 | /* Check if the user supplied buffer size is sufficient */ |
| 518 | if (size) { |
| 519 | if (size < totlen + 1) { /* provided buffer too small */ |
| 520 | debug("### buffer too small: %d, but need %d\n", |
| 521 | size, totlen + 1); |
| 522 | __set_errno(ENOMEM); |
| 523 | return (-1); |
| 524 | } |
| 525 | } else { |
| 526 | size = totlen + 1; |
| 527 | } |
| 528 | |
| 529 | /* Check if the user provided a buffer */ |
| 530 | if (*resp) { |
| 531 | /* yes; clear it */ |
| 532 | res = *resp; |
| 533 | memset(res, '\0', size); |
| 534 | } else { |
| 535 | /* no, allocate and clear one */ |
| 536 | *resp = res = calloc(1, size); |
| 537 | if (res == NULL) { |
| 538 | __set_errno(ENOMEM); |
| 539 | return (-1); |
| 540 | } |
| 541 | } |
| 542 | /* |
| 543 | * Pass 2: |
| 544 | * export sorted list of result data |
| 545 | */ |
| 546 | for (i = 0, p = res; i < n; ++i) { |
| 547 | char *s; |
| 548 | |
| 549 | s = list[i]->key; |
| 550 | while (*s) |
| 551 | *p++ = *s++; |
| 552 | *p++ = '='; |
| 553 | |
| 554 | s = list[i]->data; |
| 555 | |
| 556 | while (*s) { |
| 557 | if ((*s == sep) || (*s == '\\')) |
| 558 | *p++ = '\\'; /* escape */ |
| 559 | *p++ = *s++; |
| 560 | } |
| 561 | *p++ = sep; |
| 562 | } |
| 563 | *p = '\0'; /* terminate result */ |
| 564 | |
| 565 | return size; |
| 566 | } |
| 567 | |
| 568 | |
| 569 | /* |
| 570 | * himport() |
| 571 | */ |
| 572 | |
| 573 | /* |
| 574 | * Import linearized data into hash table. |
| 575 | * |
| 576 | * This is the inverse function to hexport(): it takes a linear list |
| 577 | * of "name=value" pairs and creates hash table entries from it. |
| 578 | * |
| 579 | * Entries without "value", i. e. consisting of only "name" or |
| 580 | * "name=", will cause this entry to be deleted from the hash table. |
| 581 | * |
| 582 | * The "flag" argument can be used to control the behaviour: when the |
| 583 | * H_NOCLEAR bit is set, then an existing hash table will kept, i. e. |
| 584 | * new data will be added to an existing hash table; otherwise, old |
| 585 | * data will be discarded and a new hash table will be created. |
| 586 | * |
| 587 | * The separator character for the "name=value" pairs can be selected, |
| 588 | * so we both support importing from externally stored environment |
| 589 | * data (separated by NUL characters) and from plain text files |
| 590 | * (entries separated by newline characters). |
| 591 | * |
| 592 | * To allow for nicely formatted text input, leading white space |
| 593 | * (sequences of SPACE and TAB chars) is ignored, and entries starting |
| 594 | * (after removal of any leading white space) with a '#' character are |
| 595 | * considered comments and ignored. |
| 596 | * |
| 597 | * [NOTE: this means that a variable name cannot start with a '#' |
| 598 | * character.] |
| 599 | * |
| 600 | * When using a non-NUL separator character, backslash is used as |
| 601 | * escape character in the value part, allowing for example for |
| 602 | * multi-line values. |
| 603 | * |
| 604 | * In theory, arbitrary separator characters can be used, but only |
| 605 | * '\0' and '\n' have really been tested. |
| 606 | */ |
| 607 | |
| 608 | int himport(const char *env, size_t size, const char sep, int flag) |
| 609 | { |
| 610 | return himport_r(&htab, env, size, sep, flag); |
| 611 | } |
| 612 | |
| 613 | int himport_r(struct hsearch_data *htab, |
| 614 | const char *env, size_t size, const char sep, int flag) |
| 615 | { |
| 616 | char *data, *sp, *dp, *name, *value; |
| 617 | |
| 618 | /* Test for correct arguments. */ |
| 619 | if (htab == NULL) { |
| 620 | __set_errno(EINVAL); |
| 621 | return 0; |
| 622 | } |
| 623 | |
| 624 | /* we allocate new space to make sure we can write to the array */ |
| 625 | if ((data = malloc(size)) == NULL) { |
| 626 | debug("himport_r: can't malloc %d bytes\n", size); |
| 627 | __set_errno(ENOMEM); |
| 628 | return 0; |
| 629 | } |
| 630 | memcpy(data, env, size); |
| 631 | dp = data; |
| 632 | |
| 633 | if ((flag & H_NOCLEAR) == 0) { |
| 634 | /* Destroy old hash table if one exists */ |
| 635 | debug("Destroy Hash Table: %p table = %p\n", htab, |
| 636 | htab->table); |
| 637 | if (htab->table) |
| 638 | hdestroy_r(htab); |
| 639 | } |
| 640 | |
| 641 | /* |
| 642 | * Create new hash table (if needed). The computation of the hash |
| 643 | * table size is based on heuristics: in a sample of some 70+ |
| 644 | * existing systems we found an average size of 39+ bytes per entry |
| 645 | * in the environment (for the whole key=value pair). Assuming a |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 646 | * size of 8 per entry (= safety factor of ~5) should provide enough |
| 647 | * safety margin for any existing environment definitions and still |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 648 | * allow for more than enough dynamic additions. Note that the |
| 649 | * "size" argument is supposed to give the maximum enviroment size |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 650 | * (CONFIG_ENV_SIZE). This heuristics will result in |
| 651 | * unreasonably large numbers (and thus memory footprint) for |
| 652 | * big flash environments (>8,000 entries for 64 KB |
Andreas Bießmann | fc5fc76 | 2010-10-01 22:51:02 +0200 | [diff] [blame] | 653 | * envrionment size), so we clip it to a reasonable value. |
| 654 | * On the other hand we need to add some more entries for free |
| 655 | * space when importing very small buffers. Both boundaries can |
| 656 | * be overwritten in the board config file if needed. |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 657 | */ |
| 658 | |
| 659 | if (!htab->table) { |
Andreas Bießmann | fc5fc76 | 2010-10-01 22:51:02 +0200 | [diff] [blame] | 660 | int nent = CONFIG_ENV_MIN_ENTRIES + size / 8; |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 661 | |
| 662 | if (nent > CONFIG_ENV_MAX_ENTRIES) |
| 663 | nent = CONFIG_ENV_MAX_ENTRIES; |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 664 | |
| 665 | debug("Create Hash Table: N=%d\n", nent); |
| 666 | |
| 667 | if (hcreate_r(nent, htab) == 0) { |
| 668 | free(data); |
| 669 | return 0; |
| 670 | } |
| 671 | } |
| 672 | |
| 673 | /* Parse environment; allow for '\0' and 'sep' as separators */ |
| 674 | do { |
| 675 | ENTRY e, *rv; |
| 676 | |
| 677 | /* skip leading white space */ |
| 678 | while ((*dp == ' ') || (*dp == '\t')) |
| 679 | ++dp; |
| 680 | |
| 681 | /* skip comment lines */ |
| 682 | if (*dp == '#') { |
| 683 | while (*dp && (*dp != sep)) |
| 684 | ++dp; |
| 685 | ++dp; |
| 686 | continue; |
| 687 | } |
| 688 | |
| 689 | /* parse name */ |
| 690 | for (name = dp; *dp != '=' && *dp && *dp != sep; ++dp) |
| 691 | ; |
| 692 | |
| 693 | /* deal with "name" and "name=" entries (delete var) */ |
| 694 | if (*dp == '\0' || *(dp + 1) == '\0' || |
| 695 | *dp == sep || *(dp + 1) == sep) { |
| 696 | if (*dp == '=') |
| 697 | *dp++ = '\0'; |
| 698 | *dp++ = '\0'; /* terminate name */ |
| 699 | |
| 700 | debug("DELETE CANDIDATE: \"%s\"\n", name); |
| 701 | |
| 702 | if (hdelete_r(name, htab) == 0) |
| 703 | debug("DELETE ERROR ##############################\n"); |
| 704 | |
| 705 | continue; |
| 706 | } |
| 707 | *dp++ = '\0'; /* terminate name */ |
| 708 | |
| 709 | /* parse value; deal with escapes */ |
| 710 | for (value = sp = dp; *dp && (*dp != sep); ++dp) { |
| 711 | if ((*dp == '\\') && *(dp + 1)) |
| 712 | ++dp; |
| 713 | *sp++ = *dp; |
| 714 | } |
| 715 | *sp++ = '\0'; /* terminate value */ |
| 716 | ++dp; |
| 717 | |
| 718 | /* enter into hash table */ |
| 719 | e.key = name; |
| 720 | e.data = value; |
| 721 | |
| 722 | hsearch_r(e, ENTER, &rv, htab); |
| 723 | if (rv == NULL) { |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 724 | printf("himport_r: can't insert \"%s=%s\" into hash table\n", |
| 725 | name, value); |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 726 | return 0; |
| 727 | } |
| 728 | |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 729 | debug("INSERT: table %p, filled %d/%d rv %p ==> name=\"%s\" value=\"%s\"\n", |
| 730 | htab, htab->filled, htab->size, |
| 731 | rv, name, value); |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 732 | } while ((dp < data + size) && *dp); /* size check needed for text */ |
| 733 | /* without '\0' termination */ |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 734 | debug("INSERT: free(data = %p)\n", data); |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 735 | free(data); |
| 736 | |
Wolfgang Denk | ea882ba | 2010-06-20 23:33:59 +0200 | [diff] [blame] | 737 | debug("INSERT: done\n"); |
Wolfgang Denk | a6826fb | 2010-06-20 13:17:12 +0200 | [diff] [blame] | 738 | return 1; /* everything OK */ |
| 739 | } |