summaryrefslogtreecommitdiff
path: root/include/search.h
diff options
context:
space:
mode:
authorWolfgang Denk <wd@denx.de>2010-06-20 13:17:12 +0200
committerWolfgang Denk <wd@denx.de>2010-09-19 19:29:47 +0200
commita6826fbc5c3802075d98e86488e1116ed0ad6fe5 (patch)
treea5cd2a296f38dec7de45cd3509c6a126e94c5e55 /include/search.h
parent54c6977e9ca41fb38b45f1746d90f2806be3b5cb (diff)
downloadu-boot-imx-a6826fbc5c3802075d98e86488e1116ed0ad6fe5.zip
u-boot-imx-a6826fbc5c3802075d98e86488e1116ed0ad6fe5.tar.gz
u-boot-imx-a6826fbc5c3802075d98e86488e1116ed0ad6fe5.tar.bz2
Add hash table support as base for new environment code
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>
Diffstat (limited to 'include/search.h')
-rw-r--r--include/search.h106
1 files changed, 106 insertions, 0 deletions
diff --git a/include/search.h b/include/search.h
new file mode 100644
index 0000000..fccc757
--- /dev/null
+++ b/include/search.h
@@ -0,0 +1,106 @@
+/*
+ * Declarations for System V style searching functions.
+ * Copyright (C) 1995-1999, 2000 Free Software Foundation, Inc.
+ * This file is part of the GNU C Library.
+ *
+ * The GNU C Library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * The GNU C Library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with the GNU C Library; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ * 02111-1307 USA.
+ */
+
+/*
+ * Based on code from uClibc-0.9.30.3
+ * Extensions for use within U-Boot
+ * Copyright (C) 2010 Wolfgang Denk <wd@denx.de>
+ */
+
+#ifndef _SEARCH_H
+#define _SEARCH_H 1
+
+#include <stddef.h>
+
+#define __set_errno(val) do { errno = val; } while (0)
+
+/*
+ * Prototype structure for a linked-list data structure.
+ * This is the type used by the `insque' and `remque' functions.
+ */
+
+/* For use with hsearch(3). */
+typedef int (*__compar_fn_t) (__const void *, __const void *);
+typedef __compar_fn_t comparison_fn_t;
+
+/* Action which shall be performed in the call the hsearch. */
+typedef enum {
+ FIND,
+ ENTER
+} ACTION;
+
+typedef struct entry {
+ char *key;
+ char *data;
+} ENTRY;
+
+/* Opaque type for internal use. */
+struct _ENTRY;
+
+/*
+ * Family of hash table handling functions. The functions also
+ * have reentrant counterparts ending with _r. The non-reentrant
+ * functions all work on a signle internal hashing table.
+ */
+
+/* Data type for reentrant functions. */
+struct hsearch_data {
+ struct _ENTRY *table;
+ unsigned int size;
+ unsigned int filled;
+};
+
+/* Create a new hashing table which will at most contain NEL elements. */
+extern int hcreate(size_t __nel);
+extern int hcreate_r(size_t __nel, struct hsearch_data *__htab);
+
+/* Destroy current internal hashing table. */
+extern void hdestroy(void);
+extern void hdestroy_r(struct hsearch_data *__htab);
+
+/*
+ * Search for entry matching ITEM.key in internal hash table. If
+ * ACTION is `FIND' return found entry or signal error by returning
+ * NULL. If ACTION is `ENTER' replace existing data (if any) with
+ * ITEM.data.
+ * */
+extern ENTRY *hsearch(ENTRY __item, ACTION __action);
+extern int hsearch_r(ENTRY __item, ACTION __action, ENTRY ** __retval,
+ struct hsearch_data *__htab);
+
+/* Search and delete entry matching ITEM.key in internal hash table. */
+extern int hdelete(const char *__key);
+extern int hdelete_r(const char *__key, struct hsearch_data *__htab);
+
+extern ssize_t hexport(const char __sep, char **__resp, size_t __size);
+extern ssize_t hexport_r(struct hsearch_data *__htab,
+ const char __sep, char **__resp, size_t __size);
+
+extern int himport(const char *__env, size_t __size, const char __sep,
+ int __flag);
+extern int himport_r(struct hsearch_data *__htab,
+ const char *__env, size_t __size, const char __sep,
+ int __flag);
+
+/* Flags for himport() / himport_r() */
+#define H_NOCLEAR 1 /* do not clear hash table before importing */
+
+#endif /* search.h */