Justus Winter, le Thu 15 May 2014 23:10:50 +0200, a écrit :
> 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.
Ack.
> * 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 | 78
> +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> libihash/ihash.h | 52 +++++++++++++++++++++++++++++++++++++
> 2 files changed, 129 insertions(+), 1 deletion(-)
>
> diff --git a/libihash/ihash.c b/libihash/ihash.c
> index 5b7b542..167c872 100644
> --- a/libihash/ihash.c
> +++ b/libihash/ihash.c
> @@ -258,7 +258,54 @@ 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
> + || 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
> @@ -327,6 +374,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 394bcf9..f7ecf1b 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.0.0.rc0
>
--
Samuel
mdiym42: note to self
mdiym42: make sure your cat is not sleeping in the bass drum before you start
playing them
