Re: [PATCH 4/5] libihash: optimize lookup-or-insert operations

[Samuel Thibault]

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