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 <peter.barada@logicpd.com>
Tested-by: Wolfgang Denk <wd@denx.de>
diff --git a/lib/hashtable.c b/lib/hashtable.c
index 9f069c0..fcdb53c 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 @@
/* 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 @@
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 @@
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 @@
*/
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 @@
* 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 @@
free(ep->key);
free(ep->data);
- htab->table[idx].used = 0;
+ htab->table[idx].used = -1;
--htab->filled;
@@ -467,7 +475,7 @@
*/
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;