Mailing-List: contact commits-help@qpid.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@qpid.apache.org
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: gsim@apache.org
To: commits@qpid.apache.org
Date: Fri, 01 May 2015 08:21:32 -0000
Message-Id: <1237fa47caad4904a853b83b0ffcbfe3@git.apache.org>
In-Reply-To: <9782735fabf44d1f976bcc6c7396a0e9@git.apache.org>
References: <9782735fabf44d1f976bcc6c7396a0e9@git.apache.org>
Subject: [2/2] qpid-proton git commit: PROTON-858: fix deletion of entries
 from map to preserve consistency in coalesced hashing

PROTON-858: fix deletion of entries from map to preserve consistency in coalesced hashing


Project: http://git-wip-us.apache.org/repos/asf/qpid-proton/repo
Commit: http://git-wip-us.apache.org/repos/asf/qpid-proton/commit/7d1007b4
Tree: http://git-wip-us.apache.org/repos/asf/qpid-proton/tree/7d1007b4
Diff: http://git-wip-us.apache.org/repos/asf/qpid-proton/diff/7d1007b4

Branch: refs/heads/master
Commit: 7d1007b479e42b635d9cda530197936a205e4c8e
Parents: 62ee7b4
Author: Gordon Sim <gsim@redhat.com>
Authored: Tue Apr 28 14:41:41 2015 +0100
Committer: Gordon Sim <gsim@redhat.com>
Committed: Thu Apr 30 23:53:39 2015 +0100

----------------------------------------------------------------------
 proton-c/src/object/map.c | 62 +++++++++++++++++++++++++++++++++++++-----
 1 file changed, 55 insertions(+), 7 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/7d1007b4/proton-c/src/object/map.c
----------------------------------------------------------------------
diff --git a/proton-c/src/object/map.c b/proton-c/src/object/map.c
index 1a758a1..2e3b157 100644
--- a/proton-c/src/object/map.c
+++ b/proton-c/src/object/map.c
@@ -263,28 +263,76 @@ void *pn_map_get(pn_map_t *map, void *key)
   return entry ? entry->value : NULL;
 }
 
+void pn_map_rehash(pn_map_t *map, size_t index)
+{
+  //reinsert entries in chain starting at index
+  assert(map);
+  size_t i = index;
+  bool complete = false;
+  while (!complete) {
+    pni_entry_t *entry = &map->entries[i];
+    assert(entry);
+    assert(entry->state != PNI_ENTRY_FREE);
+    size_t current = i;
+    if (entry->state == PNI_ENTRY_TAIL) {
+      complete = true;
+    } else {
+      assert(entry->state == PNI_ENTRY_LINK);
+      i = entry->next;
+    }
+    uintptr_t hashcode = map->hashcode(entry->key);
+    pni_entry_t *reloc = &map->entries[hashcode % map->addressable];
+    if (reloc->state == PNI_ENTRY_FREE) {
+      //correct addressable slot is available, copy into that...
+      reloc->state = PNI_ENTRY_TAIL;
+      reloc->key = entry->key;
+      reloc->value = entry->value;
+      //...then free the current entry
+      entry->key = NULL;
+      entry->value = NULL;
+      entry->state = PNI_ENTRY_FREE;
+      entry->next = 0;
+    } else {
+      //iterate to end of chain...
+      while (reloc->state == PNI_ENTRY_LINK) {
+        reloc = &map->entries[reloc->next];
+      }
+      assert(reloc->state == PNI_ENTRY_TAIL);
+      //... and append current entry
+      reloc->state = PNI_ENTRY_LINK;
+      reloc->next = current;
+      entry->state = PNI_ENTRY_TAIL;
+      entry->next = 0;
+    }
+  }
+}
+
 void pn_map_del(pn_map_t *map, void *key)
 {
   assert(map);
   pni_entry_t *prev = NULL;
   pni_entry_t *entry = pni_map_entry(map, key, &prev, false);
   if (entry) {
+    uint8_t orig_state = entry->state;
+    size_t orig_next = entry->next;
+
     void *dref_key = entry->key;
     void *dref_value = entry->value;
     if (prev) {
-      prev->next = entry->next;
-      prev->state = entry->state;
-    } else if (entry->next) {
-      assert(entry->state == PNI_ENTRY_LINK);
-      pni_entry_t *next = &map->entries[entry->next];
-      *entry = *next;
-      entry = next;
+      prev->next = 0;
+      prev->state = PNI_ENTRY_TAIL;
     }
     entry->state = PNI_ENTRY_FREE;
     entry->next = 0;
     entry->key = NULL;
     entry->value = NULL;
     map->size--;
+
+    if (orig_state == PNI_ENTRY_LINK) {
+      pn_map_rehash(map, orig_next);
+    }
+
+    // do this last as it may trigger further deletions
     pn_class_decref(map->key, dref_key);
     pn_class_decref(map->value, dref_value);
   }


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org