From patchwork Thu Jan 20 15:53:35 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Barada X-Patchwork-Id: 79709 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from theia.denx.de (theia.denx.de [85.214.87.163]) by ozlabs.org (Postfix) with ESMTP id 83292B70E3 for ; Fri, 21 Jan 2011 02:53:48 +1100 (EST) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 69EB9280AA; Thu, 20 Jan 2011 16:53:46 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at theia.denx.de Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id WCc2UDNNYH32; Thu, 20 Jan 2011 16:53:46 +0100 (CET) Received: from theia.denx.de (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id DD88B28093; Thu, 20 Jan 2011 16:53:42 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 1F35628093 for ; Thu, 20 Jan 2011 16:53:40 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at theia.denx.de Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nCg6alcKmo91 for ; Thu, 20 Jan 2011 16:53:38 +0100 (CET) X-policyd-weight: NOT_IN_SBL_XBL_SPAMHAUS=-1.5 NOT_IN_SPAMCOP=-1.5 NOT_IN_BL_NJABL=-1.5 (only DNSBL check requested) Received: from edprlnx06.logicpd.com (unknown [174.46.170.154]) by theia.denx.de (Postfix) with ESMTP id 0AF102808A for ; Thu, 20 Jan 2011 16:53:36 +0100 (CET) Received: from [10.1.249.14] (unknown [10.1.249.14]) by edprlnx06.logicpd.com (Postfix) with ESMTP id 28DD0600095; Thu, 20 Jan 2011 09:53:33 -0600 (CST) Message-ID: <4D385A7F.2070803@logicpd.com> Date: Thu, 20 Jan 2011 10:53:35 -0500 From: Peter Barada User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.13) Gecko/20101208 Thunderbird/3.1.7 MIME-Version: 1.0 To: Wolfgang Denk References: <4D34C85E.4030408@logicpd.com> <20110119083223.DEA112FC@gemini.denx.de> <4D371208.3090801@logicpd.com> <20110119204755.B8D0DD301BF@gemini.denx.de> In-Reply-To: <20110119204755.B8D0DD301BF@gemini.denx.de> Cc: U-Boot mailing list Subject: Re: [U-Boot] [Patch v2] Fix hash table deletion to prevent lost entries X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.9 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: u-boot-bounces@lists.denx.de Errors-To: u-boot-bounces@lists.denx.de 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 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 --- lib/hashtable.c | 18 +++++++++++++----- 1 files changed, 13 insertions(+), 5 deletions(-) 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;