Comments
Patch
@@ -66,12 +66,16 @@ extern int hcreate_r(size_t __nel, struct
hsearch_data *__htab);
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 int hsearch_r(ENTRY __item, ACTION __action, ENTRY ** __retval,
+ * Search for entry matching ITEM.key in internal hash table. Return
+ * found entry or signal error by returning NULL.
+ */
+extern int hfind_r(ENTRY __item, ENTRY ** __retval,
+ struct hsearch_data *__htab);
+/*
+ * Add entry matching ITEM.key in internal hash table. Replace
+ * existing data (if any) with ITEM.data.
+ */
+extern int henter_r(ENTRY __item, ENTRY ** __retval,
struct hsearch_data *__htab);
/*
@@ -65,7 +65,7 @@
* which describes the current status.
*/
typedef struct _ENTRY {
- unsigned int used;
+ int used;
ENTRY entry;
} _ENTRY;
@@ -152,7 +152,7 @@ void hdestroy_r(struct hsearch_data *htab)
/* free used memory */
for (i = 1; i <= htab->size; ++i) {
- if (htab->table[i].used) {
+ if (htab->table[i].used > 0) {
ENTRY *ep = &htab->table[i].entry;
free(ep->key);
@@ -165,77 +165,20 @@ void hdestroy_r(struct hsearch_data *htab)
htab->table = NULL;
}
-/*
- * hsearch()
- */
-
-/*
- * This is the search function. It uses double hashing with open
addressing.
- * The argument item.key has to be a pointer to an zero terminated, most
- * probably strings of chars. The function for generating a number of the
- * strings is simple but fast. It can be replaced by a more complex
function
- * like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
- *
- * We use an trick to speed up the lookup. The table is created by hcreate
- * with one more element available. This enables us to use the index zero
- * special. This index will never be used because we store the first hash
- * index in the field used where zero means not used. Every other value
- * means used. The used field can be used as a first fast comparison for
- * equality of the stored and the parameter value. This helps to prevent
- * unnecessary expensive calls of strcmp.
- *
- * This implementation differs from the standard library version of
- * this function in a number of ways:
- *
- * - 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".
- * - 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().
- */
-
-int hmatch_r(const char *match, int last_idx, ENTRY ** retval,
- struct hsearch_data *htab)
-{
- unsigned int idx;
- size_t key_len = strlen(match);
-
- for (idx = last_idx + 1; idx < htab->size; ++idx) {
- if (!htab->table[idx].used)
- continue;
- if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
- *retval = &htab->table[idx].entry;
- return idx;
- }
- }
-
- __set_errno(ESRCH);
- *retval = NULL;
- return 0;
-}
-int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
- struct hsearch_data *htab)
+/* Primary hash function */
+int hash_primary(ENTRY *item, struct hsearch_data *htab)
{
+ int len = strlen(item->key);
unsigned int hval;
unsigned int count;
- unsigned int len = strlen(item.key);
- unsigned int idx;
- /* Compute an value for the given string. Perhaps use a better
method. */
+ /* Compute a value for the given string. Perhaps use a better
method. */
hval = len;
count = len;
while (count-- > 0) {
hval <<= 4;