diff options
4 files changed, 0 insertions, 313 deletions
diff --git a/debian/patches/nodeihash0001-libihash-add-hurd_ihash_value_valid.patch b/debian/patches/nodeihash0001-libihash-add-hurd_ihash_value_valid.patch deleted file mode 100644 index 18552150..00000000 --- a/debian/patches/nodeihash0001-libihash-add-hurd_ihash_value_valid.patch +++ /dev/null @@ -1,47 +0,0 @@ -From 12caea4ff224ba598199d2dc7752b442f09f3ee0 Mon Sep 17 00:00:00 2001 -From: Justus Winter <4winter@informatik.uni-hamburg.de> -Date: Thu, 15 May 2014 17:55:45 +0200 -Subject: [PATCH hurd 1/3] libihash: add hurd_ihash_value_valid - -* libihash/ihash.h (hurd_ihash_value_valid): New function. -* libihash/ihash.c (index_empty): Use hurd_ihash_value_valid. ---- - libihash/ihash.c | 3 +-- - libihash/ihash.h | 7 +++++++ - 2 files changed, 8 insertions(+), 2 deletions(-) - -diff --git a/libihash/ihash.c b/libihash/ihash.c -index fa29257..74e9edd 100644 ---- a/libihash/ihash.c -+++ b/libihash/ihash.c -@@ -37,8 +37,7 @@ - static inline int - index_empty (hurd_ihash_t ht, unsigned int idx) - { -- return ht->items[idx].value == _HURD_IHASH_EMPTY -- || ht->items[idx].value == _HURD_IHASH_DELETED; -+ return ! hurd_ihash_value_valid (ht->items[idx].value); - } - - -diff --git a/libihash/ihash.h b/libihash/ihash.h -index 849a55a..128027a 100644 ---- a/libihash/ihash.h -+++ b/libihash/ihash.h -@@ -41,6 +41,13 @@ typedef void *hurd_ihash_value_t; - #define _HURD_IHASH_EMPTY ((hurd_ihash_value_t) 0) - #define _HURD_IHASH_DELETED ((hurd_ihash_value_t) -1) - -+/* Test if VALUE is valid. */ -+static inline int -+hurd_ihash_value_valid (hurd_ihash_value_t value) -+{ -+ return value != _HURD_IHASH_EMPTY && value != _HURD_IHASH_DELETED; -+} -+ - /* The type of integer we want to use for the keys. */ - typedef uintptr_t hurd_ihash_key_t; - --- -2.1.4 - diff --git a/debian/patches/nodeihash0002-libihash-optimize-lookup-or-insert-operations.patch b/debian/patches/nodeihash0002-libihash-optimize-lookup-or-insert-operations.patch deleted file mode 100644 index 78ef91cb..00000000 --- a/debian/patches/nodeihash0002-libihash-optimize-lookup-or-insert-operations.patch +++ /dev/null @@ -1,198 +0,0 @@ -From 6ef35d1f13a89301a599f3df7fdf309254cb7e05 Mon Sep 17 00:00:00 2001 -From: Justus Winter <4winter@informatik.uni-hamburg.de> -Date: Wed, 14 May 2014 16:24:21 +0200 -Subject: [PATCH hurd 2/3] libihash: optimize lookup-or-insert operations - -If libihash is used to implement a cache, a insertion is always -preceeded by a lookup. hurd_ihash_add has to do the lookup again. - -Provide a new pair of functions, hurd_ihash_locp_add and -hurd_ihash_locp_find, that can be used in combination to avoid the -second lookup. - -* libihash/ihash.c (hurd_ihash_locp_add): New function using a -location pointer... -(hurd_ihash_locp_find): ... that has been returned by this function. -* libihash/ihash.h (hurd_ihash_locp_add): New declaration. -(hurd_ihash_locp_find): Likewise. -(hurd_ihash_locp_value): New function. ---- - libihash/ihash.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++++- - libihash/ihash.h | 52 ++++++++++++++++++++++++++++++++++++ - 2 files changed, 131 insertions(+), 1 deletion(-) - -diff --git a/libihash/ihash.c b/libihash/ihash.c -index 74e9edd..76c695a 100644 ---- a/libihash/ihash.c -+++ b/libihash/ihash.c -@@ -244,7 +244,56 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) - return 0; - } - -- -+ -+/* Add VALUE to the hash table HT under the key KEY at LOCP. If there -+ already is an item under this key, call the cleanup function (if -+ any) for it before overriding the value. This function is faster -+ than hurd_ihash_add. -+ -+ If LOCP is NULL, fall back to hurd_ihash_add. Otherwise, LOCP must -+ be valid and may either be obtained from hurd_ihash_locp_find, or -+ from an item that is currently in the hash table. If an item is -+ replaced, KEY must match the key of the previous item. -+ -+ If a memory allocation error occurs, ENOMEM is returned, otherwise -+ 0. */ -+error_t -+hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, -+ hurd_ihash_key_t key, hurd_ihash_value_t value) -+{ -+ struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp; -+ -+ /* In case of complications, fall back to hurd_ihash_add. */ -+ if (ht->size == 0 -+ || item == NULL -+ || item->value == _HURD_IHASH_DELETED -+ || (item->value != _HURD_IHASH_EMPTY -+ && item->key != key) -+ || hurd_ihash_get_load (ht) > ht->max_load) -+ return hurd_ihash_add (ht, key, value); -+ -+ if (item->value == _HURD_IHASH_EMPTY) -+ { -+ item->key = key; -+ ht->nr_items += 1; -+ } -+ else -+ { -+ assert (item->key == key); -+ if (ht->cleanup) -+ (*ht->cleanup) (locp, ht->cleanup_data); -+ } -+ -+ item->value = value; -+ -+ if (ht->locp_offset != HURD_IHASH_NO_LOCP) -+ *((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset)) -+ = locp; -+ -+ return 0; -+} -+ -+ - /* Add ITEM 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 -@@ -313,6 +362,35 @@ 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. -+ -+ If the lookup is successful, the returned location can be used with -+ hurd_ihash_locp_add to update the item, and with -+ hurd_ihash_locp_remove to remove it. -+ -+ If the lookup is not successful, the returned location can be used -+ with hurd_ihash_locp_add to add the item. -+ -+ 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) -+{ -+ int idx; -+ -+ if (ht->size == 0) -+ return NULL; -+ -+ idx = find_index (ht, key); -+ return &ht->items[idx].value; -+} -+ - - /* Remove the entry with the key KEY from the hash table HT. If such - an entry was found and removed, 1 is returned, otherwise 0. */ -diff --git a/libihash/ihash.h b/libihash/ihash.h -index 128027a..1dbc348 100644 ---- a/libihash/ihash.h -+++ b/libihash/ihash.h -@@ -26,6 +26,7 @@ - #include <sys/types.h> - #include <limits.h> - #include <stdint.h> -+#include <stddef.h> - - - /* The type of the values corresponding to the keys. Must be a -@@ -198,10 +199,61 @@ hurd_ihash_get_load (hurd_ihash_t ht) - error_t hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, - hurd_ihash_value_t item); - -+/* Add VALUE to the hash table HT under the key KEY at LOCP. If there -+ already is an item under this key, call the cleanup function (if -+ any) for it before overriding the value. This function is faster -+ than hurd_ihash_add. -+ -+ If LOCP is NULL, fall back to hurd_ihash_add. Otherwise, LOCP must -+ be valid and may either be obtained from hurd_ihash_locp_find, or -+ from an item that is currently in the hash table. If an item is -+ replaced, KEY must match the key of the previous item. -+ -+ If a memory allocation error occurs, ENOMEM is returned, otherwise -+ 0. */ -+error_t hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, -+ hurd_ihash_key_t key, hurd_ihash_value_t value); -+ - /* Find and return the item in the hash table HT with key KEY, or NULL - 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. -+ -+ If the lookup is successful, the returned location can be used with -+ hurd_ihash_locp_add to update the item, and with -+ hurd_ihash_locp_remove to remove it. -+ -+ If the lookup is not successful, the returned location can be used -+ with hurd_ihash_locp_add to add the item. -+ -+ 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; -+} -+ - /* 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/nodeihash0003-libihash-prefer-performance-degradation-over-failure.patch b/debian/patches/nodeihash0003-libihash-prefer-performance-degradation-over-failure.patch deleted file mode 100644 index d4c78df9..00000000 --- a/debian/patches/nodeihash0003-libihash-prefer-performance-degradation-over-failure.patch +++ /dev/null @@ -1,65 +0,0 @@ -From 920d550d22576e0bd5d09597cf8ce2c91a893713 Mon Sep 17 00:00:00 2001 -From: Justus Winter <4winter@informatik.uni-hamburg.de> -Date: Sun, 7 Jun 2015 00:58:36 +0200 -Subject: [PATCH hurd 3/3] libihash: prefer performance degradation over - failure - -* libihash/ihash.c (hurd_ihash_add): Add the item even though we are -above the load factor if resizing failed. ---- - libihash/ihash.c | 18 +++++++++++++++--- - 1 file changed, 15 insertions(+), 3 deletions(-) - -diff --git a/libihash/ihash.c b/libihash/ihash.c -index 76c695a..289fce5 100644 ---- a/libihash/ihash.c -+++ b/libihash/ihash.c -@@ -303,18 +303,19 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) - { - struct hurd_ihash old_ht = *ht; - int was_added; -+ int fatal = 0; /* bail out on allocation errors */ - unsigned int i; - - if (ht->size) - { - /* Only fill the hash table up to its maximum load factor. */ - if (hurd_ihash_get_load (ht) <= ht->max_load) -+ add_one: - if (add_one (ht, key, item)) - return 0; - } - - /* The hash table is too small, and we have to increase it. */ -- ht->nr_items = 0; - if (ht->size == 0) - ht->size = HURD_IHASH_MIN_SIZE; - else -@@ -325,11 +326,22 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) - - if (ht->items == NULL) - { -- *ht = old_ht; -- return ENOMEM; -+ if (fatal || old_ht.size == 0) -+ { -+ *ht = old_ht; -+ return ENOMEM; -+ } -+ -+ /* We prefer performance degradation over failure. Therefore, -+ we add the item even though we are above the load factor. If -+ the table is full, this will fail. We set the fatal flag to -+ avoid looping. */ -+ fatal = 1; -+ goto add_one; - } - - /* We have to rehash the old entries. */ -+ ht->nr_items = 0; - for (i = 0; i < old_ht.size; i++) - if (!index_empty (&old_ht, i)) - { --- -2.1.4 - diff --git a/debian/patches/series b/debian/patches/series index 63ae958b..b73278e2 100644 --- a/debian/patches/series +++ b/debian/patches/series @@ -75,9 +75,6 @@ introspection0009-fixup_libports.patch introspection0010-fixup_libintrospection.patch introspection0011-fixup_libintrospection.patch introspection0012-fixup_libintrospection.patch -nodeihash0001-libihash-add-hurd_ihash_value_valid.patch -nodeihash0002-libihash-optimize-lookup-or-insert-operations.patch -nodeihash0003-libihash-prefer-performance-degradation-over-failure.patch ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch |