diff options
5 files changed, 0 insertions, 466 deletions
diff --git a/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch b/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch deleted file mode 100644 index bd7498c1..00000000 --- a/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch +++ /dev/null @@ -1,109 +0,0 @@ -From 5aa7e263521b934c2e23e7fb795fd9163999219a Mon Sep 17 00:00:00 2001 -From: Justus Winter <4winter@informatik.uni-hamburg.de> -Date: Sat, 21 Nov 2015 16:12:53 +0100 -Subject: [PATCH hurd 1/4] libihash: fix ill-devised locp lookup interface - -* libihash/ihash.c (hurd_ihash_locp_find): Return both the item and the slot. -* libihash/ihash.h (hurd_ihash_locp_find): Adjust prototype. -(hurd_ihash_locp_value): Remove function. ---- - libihash/ihash.c | 19 +++++++++---------- - libihash/ihash.h | 31 ++++++------------------------- - 2 files changed, 15 insertions(+), 35 deletions(-) - -diff --git a/libihash/ihash.c b/libihash/ihash.c -index 87d7abf..8b1ad1f 100644 ---- a/libihash/ihash.c -+++ b/libihash/ihash.c -@@ -370,13 +370,9 @@ hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key) - } - } - --/* Find the item in the hash table HT with key KEY. If it is found, -- return the location of its slot in the hash table. If it is not -- found, this function may still return a location. -- -- This location pointer can always be safely accessed using -- hurd_ihash_locp_value. If the lookup is successful, -- hurd_ihash_locp_value will return the value related to KEY. -+/* Find and return the item in the hash table HT with key KEY, or NULL -+ if it doesn't exist. If it is not found, this function may still -+ return a location in SLOT. - - If the lookup is successful, the returned location can be used with - hurd_ihash_locp_add to update the item, and with -@@ -387,8 +383,10 @@ hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key) - - Note that returned location is only valid until the next insertion - or deletion. */ --hurd_ihash_locp_t --hurd_ihash_locp_find (hurd_ihash_t ht, hurd_ihash_key_t key) -+hurd_ihash_value_t -+hurd_ihash_locp_find (hurd_ihash_t ht, -+ hurd_ihash_key_t key, -+ hurd_ihash_locp_t *slot) - { - int idx; - -@@ -396,7 +394,8 @@ hurd_ihash_locp_find (hurd_ihash_t ht, hurd_ihash_key_t key) - return NULL; - - idx = find_index (ht, key); -- return &ht->items[idx].value; -+ *slot = &ht->items[idx].value; -+ return index_valid (ht, idx, key) ? ht->items[idx].value : NULL; - } - - -diff --git a/libihash/ihash.h b/libihash/ihash.h -index 1dbc348..fdfc367 100644 ---- a/libihash/ihash.h -+++ b/libihash/ihash.h -@@ -218,13 +218,9 @@ error_t hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, - if it doesn't exist. */ - hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key); - --/* Find the item in the hash table HT with key KEY. If it is found, -- return the location of its slot in the hash table. If it is not -- found, this function may still return a location. -- -- This location pointer can always be safely accessed using -- hurd_ihash_locp_value. If the lookup is successful, -- hurd_ihash_locp_value will return the value related to KEY. -+/* Find and return the item in the hash table HT with key KEY, or NULL -+ if it doesn't exist. If it is not found, this function may still -+ return a location in SLOT. - - If the lookup is successful, the returned location can be used with - hurd_ihash_locp_add to update the item, and with -@@ -235,24 +231,9 @@ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key); - - Note that returned location is only valid until the next insertion - or deletion. */ --hurd_ihash_locp_t hurd_ihash_locp_find (hurd_ihash_t ht, -- hurd_ihash_key_t key); -- --/* Given an hash table bucket location LOCP, return the value stored -- there, or NULL if it is empty or LOCP is NULL. */ --static inline void * --hurd_ihash_locp_value (hurd_ihash_locp_t locp) --{ -- struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp; -- -- if (item == NULL) -- return NULL; -- -- if (hurd_ihash_value_valid (item->value)) -- return item->value; -- -- return NULL; --} -+hurd_ihash_value_t hurd_ihash_locp_find (hurd_ihash_t ht, -+ hurd_ihash_key_t key, -+ hurd_ihash_locp_t *slot); - - /* Iterate over all elements in the hash table. You use this macro - with a block, for example like this: --- -2.1.4 - diff --git a/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch b/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch deleted file mode 100644 index 341f580e..00000000 --- a/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch +++ /dev/null @@ -1,26 +0,0 @@ -From 143ea78cf3e14b9f9f7609e9fbb0a30635a92788 Mon Sep 17 00:00:00 2001 -From: Justus Winter <4winter@informatik.uni-hamburg.de> -Date: Sun, 22 Nov 2015 18:13:01 +0100 -Subject: [PATCH hurd 2/4] libihash: fix fast insertion corner case - -* libihash/ihash.c (hurd_ihash_locp_add): Fix insertion if the key -doesn't match. ---- - libihash/ihash.c | 1 + - 1 file changed, 1 insertion(+) - -diff --git a/libihash/ihash.c b/libihash/ihash.c -index 8b1ad1f..598d341 100644 ---- a/libihash/ihash.c -+++ b/libihash/ihash.c -@@ -267,6 +267,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, - if (ht->size == 0 - || item == NULL - || item->value == _HURD_IHASH_DELETED -+ || ! compare (ht, item->key, key) - || hurd_ihash_get_load (ht) > ht->max_load) - return hurd_ihash_add (ht, key, value); - --- -2.1.4 - diff --git a/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch b/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch deleted file mode 100644 index 9c0ce1e2..00000000 --- a/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch +++ /dev/null @@ -1,218 +0,0 @@ -From 5ee3f205f6aa7a15dfd7be26467000c550db7e4f Mon Sep 17 00:00:00 2001 -From: Justus Winter <4winter@informatik.uni-hamburg.de> -Date: Sat, 21 Nov 2015 16:27:40 +0100 -Subject: [PATCH hurd 3/4] libihash: generalize the interface to support - non-integer keys - -* libihash/ihash.c (hash, compare): New functions that are used -throughout libihash to hash and compare keys. -(hurd_ihash_set_gki): New function. -* libihash/ihash.h (hurd_ihash_fct_hash_t): New type for hash functions. -(hurd_ihash_fct_cmp_t): New type for comparison functions. -(struct hurd_ihash): New fields for hash and comparison functions. -(hurd_ihash_set_gki): New prototype. ---- - libihash/ihash.c | 58 +++++++++++++++++++++++++++++++++++++++++++++----------- - libihash/ihash.h | 26 ++++++++++++++++++++++++- - 2 files changed, 72 insertions(+), 12 deletions(-) - -diff --git a/libihash/ihash.c b/libihash/ihash.c -index 598d341..8e7383e 100644 ---- a/libihash/ihash.c -+++ b/libihash/ihash.c -@@ -1,5 +1,5 @@ - /* ihash.c - Integer-keyed hash table functions. -- Copyright (C) 1993-1997, 2001, 2003, 2004, 2006 -+ Copyright (C) 1993-1997, 2001, 2003, 2004, 2006, 2014, 2015 - Free Software Foundation, Inc. - Written by Michael I. Bushnell. - Revised by Miles Bader <miles@gnu.org>. -@@ -32,6 +32,21 @@ - - #include "ihash.h" - -+/* This function is used to hash the key. */ -+static inline hurd_ihash_key_t -+hash (hurd_ihash_t ht, hurd_ihash_key_t k) -+{ -+ return ht->fct_hash ? ht->fct_hash ((void *) k) : k; -+} -+ -+/* This function is used to compare the key. Returns true if A is -+ equal to B. */ -+static inline int -+compare (hurd_ihash_t ht, hurd_ihash_key_t a, hurd_ihash_key_t b) -+{ -+ return ht->fct_cmp ? (a && ht->fct_cmp (a, b)) : a == b; -+} -+ - /* Return 1 if the slot with the index IDX in the hash table HT is - empty, and 0 otherwise. */ - static inline int -@@ -46,7 +61,7 @@ index_empty (hurd_ihash_t ht, unsigned int idx) - static inline int - index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key) - { -- return !index_empty (ht, idx) && ht->items[idx].key == key; -+ return !index_empty (ht, idx) && compare (ht, ht->items[idx].key, key); - } - - -@@ -60,9 +75,10 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) - unsigned int up_idx; - unsigned int mask = ht->size - 1; - -- idx = key & mask; -+ idx = hash (ht, key) & mask; - -- if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key) -+ if (ht->items[idx].value == _HURD_IHASH_EMPTY -+ || compare (ht, ht->items[idx].key, key)) - return idx; - - up_idx = idx; -@@ -71,7 +87,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) - { - up_idx = (up_idx + 1) & mask; - if (ht->items[up_idx].value == _HURD_IHASH_EMPTY -- || ht->items[up_idx].key == key) -+ || compare (ht, ht->items[up_idx].key, key)) - return up_idx; - } - while (up_idx != idx); -@@ -88,9 +104,11 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) - static inline void - locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp) - { -+ struct _hurd_ihash_item *item = locp; - if (ht->cleanup) -- (*ht->cleanup) (*locp, ht->cleanup_data); -- *locp = _HURD_IHASH_DELETED; -+ (*ht->cleanup) (item->value, ht->cleanup_data); -+ item->value = _HURD_IHASH_DELETED; -+ item->key = 0; - ht->nr_items--; - } - -@@ -106,6 +124,8 @@ 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->fct_hash = NULL; -+ ht->fct_cmp = NULL; - } - - -@@ -166,6 +186,21 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, - } - - -+/* Use the generalized key interface. Must be called before any item -+ is inserted into the table. */ -+void -+hurd_ihash_set_gki (hurd_ihash_t ht, -+ hurd_ihash_fct_hash_t fct_hash, -+ hurd_ihash_fct_cmp_t fct_cmp) -+{ -+ assert (ht->size == 0 || !"called after insertion"); -+ assert (fct_hash); -+ assert (fct_cmp); -+ ht->fct_hash = fct_hash; -+ ht->fct_cmp = fct_cmp; -+} -+ -+ - /* Set the maximum load factor in binary percent to MAX_LOAD, which - should be between 64 and 128. The default is - HURD_IHASH_MAX_LOAD_DEFAULT. New elements are only added to the -@@ -199,10 +234,11 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) - unsigned int first_free; - unsigned int mask = ht->size - 1; - -- idx = key & mask; -+ idx = hash (ht, key) & mask; - first_free = idx; - -- if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key) -+ if (ht->items[idx].value != _HURD_IHASH_EMPTY -+ && ! compare (ht, ht->items[idx].key, key)) - { - unsigned int up_idx = idx; - -@@ -210,7 +246,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) - { - up_idx = (up_idx + 1) & mask; - if (ht->items[up_idx].value == _HURD_IHASH_EMPTY -- || ht->items[up_idx].key == key) -+ || compare (ht, ht->items[up_idx].key, key)) - { - idx = up_idx; - break; -@@ -278,7 +314,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, - } - else - { -- assert (item->key == key); -+ assert (compare (ht, item->key, key)); - if (ht->cleanup) - (*ht->cleanup) (locp, ht->cleanup_data); - } -diff --git a/libihash/ihash.h b/libihash/ihash.h -index fdfc367..986291b 100644 ---- a/libihash/ihash.h -+++ b/libihash/ihash.h -@@ -1,5 +1,5 @@ - /* ihash.h - Integer keyed hash table interface. -- Copyright (C) 1995, 2003, 2004 Free Software Foundation, Inc. -+ Copyright (C) 1995, 2003, 2004, 2014, 2015 Free Software Foundation, Inc. - Written by Miles Bader <miles@gnu.org>. - Revised by Marcus Brinkmann <marcus@gnu.org>. - -@@ -57,6 +57,20 @@ typedef uintptr_t hurd_ihash_key_t; - typedef hurd_ihash_value_t *hurd_ihash_locp_t; - - -+/* We support non-integer keys using the generalized key interface. -+ -+ To use it, supply a pair of functions matching the following -+ specification, and use pointers to the key instead of the key -+ itself in all calls to libihash. */ -+ -+/* The type of a function computing a hash for the given key. */ -+typedef hurd_ihash_key_t (*hurd_ihash_fct_hash_t) (void *); -+ -+/* The type of a function comparing two given keys. Return true if -+ both keys are equal. */ -+typedef int (*hurd_ihash_fct_cmp_t) (void *, void *); -+ -+ - /* The type of the cleanup function, which is called for every value - removed from the hash table. */ - typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg); -@@ -95,6 +109,10 @@ struct hurd_ihash - second argument. This does not happen if CLEANUP is NULL. */ - hurd_ihash_cleanup_t cleanup; - void *cleanup_data; -+ -+ /* User-supplied functions for the generalized key interface. */ -+ hurd_ihash_fct_hash_t fct_hash; -+ hurd_ihash_fct_cmp_t fct_cmp; - }; - typedef struct hurd_ihash *hurd_ihash_t; - -@@ -152,6 +170,12 @@ 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); - -+/* Use the generalized key interface. Must be called before any item -+ is inserted into the table. */ -+void hurd_ihash_set_gki (hurd_ihash_t ht, -+ hurd_ihash_fct_hash_t fct_hash, -+ hurd_ihash_fct_cmp_t fct_cmp); -+ - /* Set the maximum load factor in binary percent to MAX_LOAD, which - should be between 64 and 128. The default is - HURD_IHASH_MAX_LOAD_DEFAULT. New elements are only added to the --- -2.1.4 - diff --git a/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch b/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch deleted file mode 100644 index d278298c..00000000 --- a/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch +++ /dev/null @@ -1,109 +0,0 @@ -From 1e52fab24dd7dc549c6120ff4c2904be5f1f852b Mon Sep 17 00:00:00 2001 -From: Justus Winter <4winter@informatik.uni-hamburg.de> -Date: Sun, 22 Nov 2015 21:04:51 +0100 -Subject: [PATCH hurd 4/4] libihash: fix item insertion - -* libihash/ihash.c (find_index): Keep track and return the index where -we could insert the item. -(add_one): Use 'find_index'. ---- - libihash/ihash.c | 54 ++++++++++++++++++------------------------------------ - 1 file changed, 18 insertions(+), 36 deletions(-) - -diff --git a/libihash/ihash.c b/libihash/ihash.c -index 8e7383e..ae9f970 100644 ---- a/libihash/ihash.c -+++ b/libihash/ihash.c -@@ -73,6 +73,8 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) - { - unsigned int idx; - unsigned int up_idx; -+ unsigned int first_deleted = 0; -+ int first_deleted_set = 0; - unsigned int mask = ht->size - 1; - - idx = hash (ht, key) & mask; -@@ -86,15 +88,21 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) - do - { - up_idx = (up_idx + 1) & mask; -- if (ht->items[up_idx].value == _HURD_IHASH_EMPTY -- || compare (ht, ht->items[up_idx].key, key)) -+ if (ht->items[up_idx].value == _HURD_IHASH_EMPTY) -+ return first_deleted_set ? first_deleted : up_idx; -+ if (compare (ht, ht->items[up_idx].key, key)) - return up_idx; -+ if (! first_deleted_set -+ && ht->items[up_idx].value == _HURD_IHASH_DELETED) -+ first_deleted = up_idx, first_deleted_set = 1; - } - while (up_idx != idx); - -- /* If we end up here, the item could not be found. Return any -- invalid index. */ -- return idx; -+ /* If we end up here, the item could not be found. Return the index -+ of the first deleted item, as this is the position where we can -+ insert an item with the given key once we established that it is -+ not in the table. */ -+ return first_deleted; - } - - -@@ -231,48 +239,22 @@ static inline int - add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) - { - unsigned int idx; -- unsigned int first_free; -- unsigned int mask = ht->size - 1; -- -- idx = hash (ht, key) & mask; -- first_free = idx; -- -- if (ht->items[idx].value != _HURD_IHASH_EMPTY -- && ! compare (ht, ht->items[idx].key, key)) -- { -- unsigned int up_idx = idx; - -- do -- { -- up_idx = (up_idx + 1) & mask; -- if (ht->items[up_idx].value == _HURD_IHASH_EMPTY -- || compare (ht, ht->items[up_idx].key, key)) -- { -- idx = up_idx; -- break; -- } -- } -- while (up_idx != idx); -- } -+ idx = find_index (ht, key); - - /* Remove the old entry for this key if necessary. */ - if (index_valid (ht, idx, key)) - locp_remove (ht, &ht->items[idx].value); - -- /* 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)) -+ if (index_empty (ht, idx)) - { - ht->nr_items++; -- ht->items[first_free].value = value; -- ht->items[first_free].key = key; -+ ht->items[idx].value = value; -+ ht->items[idx].key = key; - - if (ht->locp_offset != HURD_IHASH_NO_LOCP) - *((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset)) -- = &ht->items[first_free].value; -+ = &ht->items[idx].value; - - return 1; - } --- -2.1.4 - diff --git a/debian/patches/series b/debian/patches/series index 920d9f58..c5e922b4 100644 --- a/debian/patches/series +++ b/debian/patches/series @@ -53,10 +53,6 @@ introspection0006-libpager-annotate-objects-managed-by-libports.patch introspection0007-ext2fs-annotate-objects-managed-by-libports.patch introspection0008-utils-rpctrace-support-attaching-to-servers.patch introspection0009-pflocal-annotate-objects-managed-by-libports.patch -ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch -ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch -ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch -ihash-as-cache0004-libihash-fix-item-insertion.patch nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch nodeihash0002-xxx-fix-node-iteration.patch ext2fs-optimize-bcache0001-ext2fs-improve-the-block-cache.patch |