diff mbox

[U-Boot,v2] Fix hash table deletion to prevent lost entries

Message ID 4D385A7F.2070803@logicpd.com
State Superseded
Headers show

Commit Message

Peter Barada Jan. 20, 2011, 3:53 p.m. UTC 
On 01/19/2011 03:47 PM, Wolfgang Denk wrote:
> Dear Peter Barada,
>
> In message <4D371208.3090801@logicpd.com> you wrote:
>>>> The hash delete code is in error; instead of just removing the deleted
>>>> key, it should instead allocate a new hashtable, hash all the keys into
>>>> the new table except for the deleted key and then reclaim the old table
>>>> (and deleted key).
>>> Can you please come up with a patch?
>>

From: Peter Barada <peter.barada@logicpd.com>
Date: Thu, 20 Jan 2011 10:38:57 -0500
Subject: [PATCH] Fix hashtable to properly handle deletion.

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.

Signed-off-by: Peter Barada <peter.barada@logicpd.com>
---
 lib/hashtable.c |   18 +++++++++++++-----
 1 files changed, 13 insertions(+), 5 deletions(-)

Comments

Wolfgang Denk March 21, 2011, 9:48 p.m. UTC | #1 
Dear Peter Barada,

In message <4D385A7F.2070803@logicpd.com> you wrote:
> On 01/19/2011 03:47 PM, Wolfgang Denk wrote:
> > Dear Peter Barada,
> >
> > In message <4D371208.3090801@logicpd.com> you wrote:
> >>>> The hash delete code is in error; instead of just removing the deleted
> >>>> key, it should instead allocate a new hashtable, hash all the keys into
> >>>> the new table except for the deleted key and then reclaim the old table
> >>>> (and deleted key).
> >>> Can you please come up with a patch?
> >>
> 
> From: Peter Barada <peter.barada@logicpd.com>
> Date: Thu, 20 Jan 2011 10:38:57 -0500
> Subject: [PATCH] Fix hashtable to properly handle deletion.
> 
> 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.
> 
> Signed-off-by: Peter Barada <peter.barada@logicpd.com>

Checkpatch generates a number of errors:

	[PATCH] Fix hashtable to properly handle deletion.
	total: 8 errors, 16 warnings, 66 lines checked

Can you please fix these, and resubmit?

Also, do you happen to have a test case that can be used show the
problem in the existing code, and to test the patch?

Thanks.

Wolfgang Denk
diff mbox

Patch

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 @@  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;