rm 0011-XXX-libports-cuckoo-hashing.patch

2 files changed, 1 insertions, 465 deletions

diff --git a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch
deleted file mode 100644
index dd11c0e7..00000000
--- a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch
+++ /dev/null
@@ -1,464 +0,0 @@
-From a1f9b63d2068df17f6a4bcc221c808b49dccaee0 Mon Sep 17 00:00:00 2001
-From: Justus Winter <4winter@informatik.uni-hamburg.de>
-Date: Sat, 10 May 2014 10:05:07 +0200
-Subject: [PATCH 11/11] XXX libports: cuckoo hashing
-
----
- libihash/Makefile |   1 +
- libihash/ihash.c  | 248 +++++++++++++++++++++++++++++++++++-------------------
- libihash/ihash.h  |  37 +++++---
- 3 files changed, 186 insertions(+), 100 deletions(-)
-
-diff --git a/libihash/Makefile b/libihash/Makefile
-index 09bb136..ca528f7 100644
---- a/libihash/Makefile
-+++ b/libihash/Makefile
-@@ -24,5 +24,6 @@ SRCS = ihash.c
- installhdrs = ihash.h
- 
- OBJS = $(SRCS:.c=.o)
-+LDLIBS += -lm
- 
- include ../Makeconf
-diff --git a/libihash/ihash.c b/libihash/ihash.c
-index e74a2c5..6068894 100644
---- a/libihash/ihash.c
-+++ b/libihash/ihash.c
-@@ -26,6 +26,7 @@
- #endif
- 
- #include <errno.h>
-+#include <math.h>
- #include <stdlib.h>
- #include <stdint.h>
- #include <assert.h>
-@@ -69,6 +70,18 @@ index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
-   return !index_empty (ht, idx) && ht->items[idx].key == key;
- }
- 
-+static inline unsigned int
-+hash0 (hurd_ihash_t ht, hurd_ihash_key_t key)
-+{
-+  return hash_int32 (key ^ ht->salt0, ht->size - 1);
-+}
-+
-+static inline unsigned int
-+hash1 (hurd_ihash_t ht, hurd_ihash_key_t key)
-+{
-+  return hash_int32 (key ^ ht->salt1, ht->size - 1)
-+    | (1U << (ht->size - 1));	/* add offset */
-+}
- 
- /* Given a hash table HT, and a key KEY, find the index in the table
-    of that key.  You must subsequently check with index_valid() if the
-@@ -76,29 +89,13 @@ index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
- static inline int
- find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
- {
--  unsigned int idx;
--  unsigned int up_idx;
--  unsigned int mask = ht->size - 1;
--
--  idx = hash_int32 (key, 32) & mask;
-+  unsigned int idx0, idx1;
-+  idx0 = hash0 (ht, key);
-+  idx1 = hash1 (ht, key);
- 
--  if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
--    return idx;
--
--  up_idx = idx;
--
--  do
--    {
--      up_idx = (up_idx + 1) & mask;
--      if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
--	  || ht->items[up_idx].key == key)
--	return up_idx;
--    }
--  while (up_idx != idx);
--
--  /* If we end up here, the item could not be found.  Return any
--     invalid index.  */
--  return idx;
-+  if (ht->items[idx0].key == key)
-+    return idx0;
-+  return idx1;
- }
- 
- 
-@@ -126,6 +123,9 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
-   ht->locp_offset = locp_offs;
-   ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT;
-   ht->cleanup = 0;
-+  ht->salt0 = 0;
-+  ht->salt1 = ~0;
-+  ht->max_loop = 0;
- }
- 
- 
-@@ -186,14 +186,15 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
- }
- 
- 
--/* Set the maximum load factor in percent to MAX_LOAD, which should be
--   between 1 and 100.  The default is HURD_IHASH_MAX_LOAD_DEFAULT.
-+ /* Set the maximum load factor in percent to MAX_LOAD, which must be
-+   between 1 and HURD_IHASH_MAX_LOAD_DEFAULT.  The default is
-+   HURD_IHASH_MAX_LOAD_DEFAULT.  If MAX_LOAD is invalid, the maximum
-+   load factor is not changed.
-+
-    New elements are only added to the hash table while the number of
-    hashed elements is that much percent of the total size of the hash
-    table.  If more elements are added, the hash table is first
--   expanded and reorganized.  A MAX_LOAD of 100 will always fill the
--   whole table before enlarging it, but note that this will increase
--   the cost of operations significantly when the table is almost full.
-+   expanded and reorganized.
- 
-    If the value is set to a smaller value than the current load
-    factor, the next reorganization will happen when a new item is
-@@ -201,86 +202,157 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
- void
- hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load)
- {
--  ht->max_load = max_load;
-+  if (0 < max_load && max_load < HURD_IHASH_MAX_LOAD_DEFAULT)
-+    ht->max_load = max_load;
- }
- 
- 
--/* Helper function for hurd_ihash_add.  Return 1 if the item was
--   added, and 0 if it could not be added because no empty slot was
--   found.  The arguments are identical to hurd_ihash_add.
-+/* Fill the IDXth slot of HT with ITEM.  Updates the location pointer
-+   if necessary.  */
-+static inline void
-+set_item (hurd_ihash_t ht, unsigned int idx, struct _hurd_ihash_item *item)
-+{
-+  ht->items[idx] = *item;
-+  if (__builtin_expect (ht->locp_offset != HURD_IHASH_NO_LOCP, 1))
-+    *((hurd_ihash_locp_t *) (((char *) item->value) + ht->locp_offset))
-+      = &ht->items[idx].value;
-+}
-+
-+/* Insert ITEM into HT at its preferred location.  If this location is
-+   currently occupied, move that item to it's alternate location.
-+   This process is repeated until no item has to be moved.
- 
--   We are using open address hashing.  As the hash function we use the
--   division method with quadratic probe.  This is guaranteed to try
--   all slots in the hash table if the prime number is 3 mod 4.  */
-+   If this succeeds within MAX_LOOP steps, return 1.  Otherwise return
-+   0.  On failure, ITEM contains an item (not the same as the one
-+   supplied by the caller).  It is the responsibility of the callee to
-+   add this item to HT.  */
- static inline int
--add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
-+add_item (hurd_ihash_t ht, struct _hurd_ihash_item *item,
-+	  unsigned int max_loop)
- {
--  unsigned int idx;
--  unsigned int first_free;
--  unsigned int mask = ht->size - 1;
--
--  idx = hash_int32 (key, 32) & mask;
--  first_free = idx;
-+  unsigned int i;
-+  struct _hurd_ihash_item old;
-+  unsigned int idx0, idx1;
- 
--  if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
-+  for (i = 0; i < max_loop; i++)
-     {
--      unsigned int up_idx = idx;
-- 
--      do
-+      idx0 = hash0 (ht, item->key);
-+      if (index_empty (ht, idx0))
- 	{
--        up_idx = (up_idx + 1) & mask;
--	  if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
--	      || ht->items[up_idx].key == key)
--	    {
--	      idx = up_idx;
--	      break;
--	    }
-+	  set_item (ht, idx0, item);
-+	  return 1;
- 	}
--      while (up_idx != idx);
--    }
- 
--  /* Remove the old entry for this key if necessary.  */
--  if (index_valid (ht, idx, key))
--    locp_remove (ht, &ht->items[idx].value);
-+      old = ht->items[idx0];
-+      set_item (ht, idx0, item);
-+      *item = old;
- 
--  /* If we have not found an empty slot, maybe the last one we
--     looked at was empty (or just got deleted).  */
--  if (!index_empty (ht, first_free))
--    first_free = idx;
-- 
--  if (index_empty (ht, first_free))
--    {
--      ht->nr_items++;
--      ht->items[first_free].value = value;
--      ht->items[first_free].key = key;
-+      idx1 = hash1 (ht, item->key);
-+      if (index_empty (ht, idx1))
-+	{
-+	  set_item (ht, idx1, item);
-+	  return 1;
-+	}
-+
-+      old = ht->items[idx1];
-+      set_item (ht, idx1, item);
-+      *item = old;
-+    }
-+
-+  return 0;
-+}
- 
--      if (ht->locp_offset != HURD_IHASH_NO_LOCP)
--	*((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset))
--	  = &ht->items[first_free].value;
- 
-+/* Helper function for hurd_ihash_add.  Return 1 if the item was
-+   added, and 0 if it could not be added because no empty slot was
-+   found.  On failure, ITEM contains an item (not the same as the one
-+   supplied by the caller).  It is the responsibility of the callee to
-+   add this item to HT.  */
-+static inline int
-+add_one (hurd_ihash_t ht, struct _hurd_ihash_item *item)
-+{
-+  unsigned int idx = find_index (ht, item->key);
-+  if (index_valid (ht, idx, item->key))
-+    {
-+      /* Update the entry.  */
-+      locp_remove (ht, &ht->items[idx].value);
-+      set_item (ht, idx, item);
-+      ht->nr_items += 1;
-       return 1;
-     }
- 
--  return 0;
-+  /* No matter what, we will insert this item.  */
-+  ht->nr_items += 1;
-+
-+  int added = add_item (ht, item, ht->max_loop);
-+  if (added)
-+    return 1;
-+
-+  /* We failed.  */
-+  size_t size = 1U << ht->size;
-+  int tries = 3;
-+
-+ retry:
-+  if (tries == 0)
-+    /* Give up.  The callee will resize the table and incorporate
-+       *item.  */
-+    return 0;
-+
-+  tries -= 1;
-+
-+  /* Pick different hash functions.  */
-+  ht->salt0 = hash_int32 (ht->salt0, 32);
-+  ht->salt1 = hash_int32 (ht->salt1, 32);
-+
-+  error (0, 0, "Rehashing table %p with salts %x %x.",
-+	 ht, ht->salt0, ht->salt1);
-+
-+  /* Try to insert the new or stashed item.  */
-+  added = add_item (ht, item, size);
-+  if (! added)
-+    goto retry;
-+
-+  /* Rehash the table.  */
-+  for (idx = 0; idx < size; idx++)
-+    if (! index_empty (ht, idx)
-+	/* For each non-empty slot, check if the item there is not at
-+	   the correct (new) index.  */
-+	&& (idx < (size >> 1)	/* select the appropriate function */
-+	    ? hash0 (ht, ht->items[idx].key) != idx
-+	    : hash1 (ht, ht->items[idx].key) != idx))
-+      {
-+	*item = ht->items[idx];
-+	ht->items[idx].value = _HURD_IHASH_EMPTY;
-+	added = add_item (ht, item, size);
-+	if (! added)
-+	  goto retry;
-+      }
-+
-+  return 1;
- }
- 
--  
--/* Add ITEM to the hash table HT under the key KEY.  If there already
-+
-+/* Add VALUE to the hash table HT under the key KEY.  If there already
-    is an item under this key, call the cleanup function (if any) for
-    it before overriding the value.  If a memory allocation error
-    occurs, ENOMEM is returned, otherwise 0.  */
- error_t
--hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
-+hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
- {
-   struct hurd_ihash old_ht = *ht;
-   int was_added;
--  unsigned int i;
-+
-+  /* The item that needs to be added.  Also, if we remove an item from
-+     the table, we store it here.  If we fail to insert it again, we
-+     start over.  */
-+  struct _hurd_ihash_item item =
-+    (struct _hurd_ihash_item){ .key = key, .value = value};
- 
-   if (ht->size)
-     {
-       /* Only fill the hash table up to its maximum load factor.  */
--      if (ht->nr_items * 100 / ht->size <= ht->max_load)
--	if (add_one (ht, key, item))
-+      if ((ht->nr_items * 100) >> ht->size <= ht->max_load)
-+	if (add_one (ht, &item))
- 	  return 0;
-     }
- 
-@@ -289,10 +361,15 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
-   if (ht->size == 0)
-       ht->size = HURD_IHASH_MIN_SIZE;
-   else
--      ht->size <<= 1;
-+      ht->size += 1;	/* double the size */
-+
-+  /* Recompute the threshold for rehashing.  */
-+  size_t size = 1U << ht->size;
-+  float epsilon = (float) (50 - ht->max_load) / 2;
-+  ht->max_loop = ceilf (3 * logf (size) / log1pf (epsilon));
- 
-   /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitely.  */
--  ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item));
-+  ht->items = calloc (size, sizeof (struct _hurd_ihash_item));
- 
-   if (ht->items == NULL)
-     {
-@@ -301,15 +378,14 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
-     }
- 
-   /* We have to rehash the old entries.  */
--  for (i = 0; i < old_ht.size; i++)
--    if (!index_empty (&old_ht, i))
--      {
--	was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value);
--	assert (was_added);
--      }
-+  HURD_IHASH_ITERATE_ITEMS (&old_ht, i)
-+    {
-+      was_added = add_one (ht, i);
-+      assert (was_added);
-+    }
- 
-   /* Finally add the new element!  */
--  was_added = add_one (ht, key, item);
-+  was_added = add_one (ht, &item);
-   assert (was_added);
- 
-   if (old_ht.size > 0)
-diff --git a/libihash/ihash.h b/libihash/ihash.h
-index 057babc..4077234 100644
---- a/libihash/ihash.h
-+++ b/libihash/ihash.h
-@@ -73,7 +73,7 @@ struct hurd_ihash
-   /* An array of (key, value) pairs.  */
-   _hurd_ihash_item_t items;
- 
--  /* The length of the array ITEMS.  */
-+  /* Log2 of the length of the array ITEMS.  */
-   size_t size;
- 
-   /* The offset of the location pointer from the hash value.  */
-@@ -87,18 +87,24 @@ struct hurd_ihash
-      second argument.  This does not happen if CLEANUP is NULL.  */
-   hurd_ihash_cleanup_t cleanup;
-   void *cleanup_data;
-+
-+  /* Salts for the hash function.  */
-+  uint32_t salt0, salt1;
-+
-+  /* Rehash threshold.  */
-+  unsigned int max_loop;
- };
- typedef struct hurd_ihash *hurd_ihash_t;
- 
- 
- /* Construction and destruction of hash tables.  */
- 
--/* The size of the initial allocation in number of items.  This must
--   be a power of two.  */
--#define HURD_IHASH_MIN_SIZE	32
-+/* Log2 of the size of the initial allocation in number of items.  */
-+#define HURD_IHASH_MIN_SIZE	6
- 
--/* The default value for the maximum load factor in percent.  */
--#define HURD_IHASH_MAX_LOAD_DEFAULT 75
-+/* The default value for the maximum load factor in percent.  Must be
-+   below 50.  */
-+#define HURD_IHASH_MAX_LOAD_DEFAULT 42
- 
- /* The LOCP_OFFS to use if no location pointer is available.  */
- #define HURD_IHASH_NO_LOCP	INTPTR_MIN
-@@ -107,7 +113,8 @@ typedef struct hurd_ihash *hurd_ihash_t;
- #define HURD_IHASH_INITIALIZER(locp_offs)				\
-   { .nr_items = 0, .size = 0, .cleanup = (hurd_ihash_cleanup_t) 0,	\
-     .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,				\
--    .locp_offset = (locp_offs)}
-+    .locp_offset = (locp_offs),						\
-+    .salt0 = 0, .salt1 = ~0, .max_loop = 0 }
- 
- /* Initialize the hash table at address HT.  If LOCP_OFFSET is not
-    HURD_IHASH_NO_LOCP, then this is an offset (in bytes) from the
-@@ -143,14 +150,16 @@ void hurd_ihash_free (hurd_ihash_t ht);
- void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
- 			     void *cleanup_data);
- 
--/* Set the maximum load factor in percent to MAX_LOAD, which should be
--   between 50 and 100.  The default is HURD_IHASH_MAX_LOAD_DEFAULT.
-+
-+/* Set the maximum load factor in percent to MAX_LOAD, which must be
-+   at least 1, and at most HURD_IHASH_MAX_LOAD_DEFAULT.  The default
-+   is HURD_IHASH_MAX_LOAD_DEFAULT.  If MAX_LOAD is invalid, the
-+   maximum load factor is not changed.
-+
-    New elements are only added to the hash table while the number of
-    hashed elements is that much percent of the total size of the hash
-    table.  If more elements are added, the hash table is first
--   expanded and reorganized.  A MAX_LOAD of 100 will always fill the
--   whole table before enlarging it, but note that this will increase
--   the cost of operations significantly when the table is almost full.
-+   expanded and reorganized.
- 
-    If the value is set to a smaller value than the current load
-    factor, the next reorganization will happen when a new item is
-@@ -216,7 +225,7 @@ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key);
-          *_hurd_ihash_valuep = (ht)->size ? &(ht)->items[0].value : 0;	\
-        (ht)->size							\
-          && ((_hurd_ihash_item_t) _hurd_ihash_valuep) - &(ht)->items[0]	\
--            < (ht)->size						\
-+         < (1 << (ht)->size)                                            \
-          && (val = *_hurd_ihash_valuep, 1);				\
-        _hurd_ihash_valuep = (hurd_ihash_value_t *)			\
- 	 (((_hurd_ihash_item_t) _hurd_ihash_valuep) + 1))		\
-@@ -234,7 +243,7 @@ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key);
-    ITEM->value.  */
- #define HURD_IHASH_ITERATE_ITEMS(ht, item)                              \
-   for (_hurd_ihash_item_t item = (ht)->size? &(ht)->items[0]: 0;	\
--       (ht)->size && item - &(ht)->items[0] < (ht)->size;               \
-+       (ht)->size && item - &(ht)->items[0] < (1 << (ht)->size);        \
-        item++)                                                          \
-     if (item->value != _HURD_IHASH_EMPTY &&                             \
-         item->value != _HURD_IHASH_DELETED)
--- 
-2.0.0.rc0
-
diff --git a/debian/patches/series b/debian/patches/series
index b55ee129..1c6ce664 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -51,4 +51,4 @@ ext2fs-cache-superblock.patch
 0008-libihash-use-linear-probing-and-fast-modulo-operatio.patch
 0009-ext2fs-improve-enable-disable-_caching.patch
 0010-fatfs-improve-enable-disable-_caching.patch
-0011-XXX-libports-cuckoo-hashing.patch
+