[U-Boot] [PATCH 3/5] Add hash table support as base for new environment code

[Wolfgang Denk <wd@denx.de>]

Dear Wolfgang Denk,

In message <1279395948-25864-4-git-send-email-wd@denx.de> you wrote:
> This implementation is based on code from uClibc-0.9.30.3 but was
> modified and extended for use within U-Boot.
> 
> Major modifications and extensions:
> 
> * hsearch() [modified / extended]:
>   - While the standard version does not make any assumptions about
>     the type of the stored data objects at all, this implementation
>     works with NUL terminated strings only.
>   - Instead of storing just pointers to the original objects, we
>     create local copies so the caller does not need to care about the
>     data any more.
>   - The standard implementation does not provide a way to update an
>     existing entry.  This version will create a new entry or update an
>     existing one when both "action == ENTER" and "item.data != NULL".
>   - hsearch_r(): Instead of returning 1 on success, we return the
>     index into the internal hash table, which is also guaranteed to be
>     positive.  This allows us direct access to the found hash table
>     slot for example for functions like hdelete().
> * hdelete() [added]:
>   - The standard implementation of hsearch(3) does not provide any way
>     to delete any entries from the hash table.  We extend the code to
>     do that.
> * hexport() [added]:
>   - Export the data stored in the hash table in linearized form:
>     Entries are exported as "name=value" strings, separated by an
>     arbitrary (non-NUL, of course) separator character. This allows to
>     use this function both when formatting the U-Boot environment for
>     external storage (using '\0' as separator), but also when using it
>     for the "printenv" command to print all variables, simply by using
>     as '\n" as separator. This can also be used for new features like
>     exporting the environment data as text file, including the option
>     for later re-import.
>   - The entries in the result list will be sorted by ascending key
>     values.
> * himport() [added]:
>   - Import linearized data into hash table.  This is the inverse
>     function to hexport(): it takes a linear list of "name=value"
>     pairs and creates hash table entries from it.
>   - Entries without "value", i. e. consisting of only "name" or
>     "name=", will cause this entry to be deleted from the hash table.
>   - The "flag" argument can be used to control the behaviour: when
>     the H_NOCLEAR bit is set, then an existing hash table will kept,
>     i. e. new data will be added to an existing hash table;
>     otherwise, old data will be discarded and a new hash table will
>     be created.
>   - The separator character for the "name=value" pairs can be
>     selected, so we both support importing from externally stored
>     environment data (separated by NUL characters) and from plain text
>     files (entries separated by newline characters).
>   - To allow for nicely formatted text input, leading white space
>     (sequences of SPACE and TAB chars) is ignored, and entries
>     starting (after removal of any leading white space) with a '#'
>     character are considered comments and ignored.
>   - NOTE: this means that a variable name cannot start with a '#'
>     character.
>   - When using a non-NUL separator character, backslash is used as
>     escape character in the value part, allowing for example fo
>     multi-line values.
>   - In theory, arbitrary separator characters can be used, but only
>     '\0' and '\n' have really been tested.
> 
> Signed-off-by: Wolfgang Denk <wd@denx.de>
> ---
>  include/search.h |  106 ++++++++
>  lib/Makefile     |    1 +
>  lib/hashtable.c  |  721 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 828 insertions(+), 0 deletions(-)
>  create mode 100644 include/search.h
>  create mode 100644 lib/hashtable.c

Applied to "next" branch.

Best regards,

Wolfgang Denk

-- 
DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
It seems intuitively obvious to me, which  means  that  it  might  be
wrong.                                                 -- Chris Torek