From c81c1222427f268d29ba999c82e2477c428e7bab Mon Sep 17 00:00:00 2001 From: Peter Barada Date: Mon, 21 Mar 2011 19:05:20 -0400 Subject: [PATCH] Fix hash table deletion to prevent lost entries Use negative used value to mark deleted entry. Search keeps probing past deleted entries. Adding an entry uses first deleted entry when it hits end of probe chain. Initially found that "ramdiskimage" and "preboot" collide modulus 347, causing "preboot" to be inserted at idx 190, "ramdiskimage" at idx 191. Previous to this fix when "preboot" is deleted, "ramdiskimage" is orphaned. Signed-off-by: Peter Barada Tested-by: Wolfgang Denk --- lib/hashtable.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-) diff --git a/lib/hashtable.c b/lib/hashtable.c index 9f069c0769..fcdb53cd46 100644 --- a/lib/hashtable.c +++ b/lib/hashtable.c @@ -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); @@ -209,7 +209,7 @@ int hmatch_r(const char *match, int last_idx, ENTRY ** retval, size_t key_len = strlen(match); for (idx = last_idx + 1; idx < htab->size; ++idx) { - if (!htab->table[idx].used) + if (htab->table[idx].used > 0) continue; if (!strncmp(match, htab->table[idx].entry.key, key_len)) { *retval = &htab->table[idx].entry; @@ -229,6 +229,7 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, unsigned int count; unsigned int len = strlen(item.key); unsigned int idx; + unsigned int first_deleted = 0; /* Compute an value for the given string. Perhaps use a better method. */ hval = len; @@ -256,6 +257,10 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, */ unsigned hval2; + if (htab->table[idx].used == -1 + && !first_deleted) + first_deleted = idx; + if (htab->table[idx].used == hval && strcmp(item.key, htab->table[idx].entry.key) == 0) { /* Overwrite existing value? */ @@ -335,6 +340,9 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, * Create new entry; * create copies of item.key and item.data */ + if (first_deleted) + idx = first_deleted; + htab->table[idx].used = hval; htab->table[idx].entry.key = strdup(item.key); htab->table[idx].entry.data = strdup(item.data); @@ -387,7 +395,7 @@ int hdelete_r(const char *key, struct hsearch_data *htab) free(ep->key); free(ep->data); - htab->table[idx].used = 0; + htab->table[idx].used = -1; --htab->filled; @@ -467,7 +475,7 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep, */ for (i = 1, n = 0, totlen = 0; i <= htab->size; ++i) { - if (htab->table[i].used) { + if (htab->table[i].used > 0) { ENTRY *ep = &htab->table[i].entry; list[n++] = ep; -- 2.30.2