diff options
| -rw-r--r-- | doc/info/mds.texinfo | 49 | ||||
| -rw-r--r-- | src/libmdsserver/hash-list.h | 117 |
2 files changed, 142 insertions, 24 deletions
diff --git a/doc/info/mds.texinfo b/doc/info/mds.texinfo index 62210a9..9fe6382 100644 --- a/doc/info/mds.texinfo +++ b/doc/info/mds.texinfo @@ -7800,6 +7800,19 @@ The number of slots that have been used, even if no longer used. This element is transparent to the user of the class. +@item @code{last} [@code{size_t}] +@vrindex @code{last} +@vrindex @code{hash_list_t.last} +@fnindex @code{hash_list_get} +@fnindex @code{hash_list_put} +@fnindex @code{hash_list_remove} +This variable is used for optimisation, any +time @code{hash_list_get} finds an element, its +will be stored, and it will be the first +inspected element by @code{hash_list_put} and +@code{hash_list_remove}. This element is +transparent to the user of the class. + @item @code{slots} [@code{hash_list_entry_t*}] @vrindex @code{slots} @vrindex @code{hash_list_t.slots} @@ -7864,13 +7877,15 @@ on error. Errors are however non-fatal and can be ignored, it only means that the capacity could not be reduces, because a called to @code{realloc} failed. -@item @code{hash_list_get} [(@code{const this, const KEY_T key, VALUE_T* restrict value}) @arrow{} @code{int}] +@item @code{hash_list_get} [(@code{this, const KEY_T key, VALUE_T* restrict value}) @arrow{} @code{int}] @fnindex @code{hash_list_get} Look up a value, with the key @code{key}, in the hash list @code{this}. The found value will be stored in @code{*value}. This method cannot fail, therefore it cannot return a value indicating that it failed. Instead it returns one if the entry was found and nought if it was not found. +Note that @code{this} is not specified with @code{const}; +this is because internal caching is done. @item @code{hash_list_put} [(@code{this, KEY_T key, const VALUE_T* restrict value}) @arrow{} @code{int}] @fnindex @code{hash_list_put} @@ -7954,8 +7969,8 @@ will it would return after the unmarshalling. The function shall return zero on error. @end table -@file{<libmdsserver/hash-list.h>} also defines a -macro that is uneffected by @code{CREATE_HASH_LIST_SUBCLASS}. +@file{<libmdsserver/hash-list.h>} also defines two +macros that is uneffected by @code{CREATE_HASH_LIST_SUBCLASS}. @table @asis @item @code{foreach_hash_list_entry} [(@code{hash_list_t this, size_t i, hash_list_entry_t* entry})] @@ -7992,6 +8007,34 @@ void print_hash_list(hash_list_t* table) Note thay the data type for the parameter @code{this} is not a pointer. + +@item @code{HASH_LIST_EXPECTED} [(@code{...})] +This macro is defined as @code{__builtin_expect(__VA_ARGS__, 1)}. +This means that the input value is evaluated, and may +contain the sequence-operator (comma-operator), and the +the value is expected to evaluate to @code{1}. + +It is encourage to run @code{hash_list_get} before +@code{hash_list_put} and @code{hash_list_remove}. +This way, you know exactly what is happening. +There is an optimisation in place to let +@code{hash_list_put} and @code{hash_list_remove} +skip the search for the item (unless it is the first +element) if @code{hash_list_get} was used directly +prior to @code{hash_list_put} or @code{hash_list_remove} +to find the element. This macro used to tell the +compiler that position of the element is most likely +already known but is not zero. + +If you however choose to not call @code{hash_list_get} +before @code{hash_list_put} and @code{hash_list_remove} +you should define this macro before including the header +file, but with the @code{1} changed to a @code{0}. If +you on the other hand do not know if you are going to +call @code{hash_list_get} before @code{hash_list_put} +and @code{hash_list_remove} you should define it to +expand to the input verbatim, that is, have the value +@code{__VA_ARGS__}. @end table diff --git a/src/libmdsserver/hash-list.h b/src/libmdsserver/hash-list.h index fcd9eb4..a9ae256 100644 --- a/src/libmdsserver/hash-list.h +++ b/src/libmdsserver/hash-list.h @@ -37,6 +37,33 @@ # define HASH_LIST_DEFAULT_INITIAL_CAPACITY 128 #endif +/** + * It is encourage to run `hash_list_get` before + * `hash_list_put` and `hash_list_remove`. This + * way, you know exactly what is happening. + * There is an optimisation in place to let + * `hash_list_put` and `hash_list_remove` skip + * the search for the item (unless it is the first + * element) if `hash_list_get` was used directly + * prior to `hash_list_put` or `hash_list_remove` + * to find the element. This macro used to tell + * the compiler that position of the element is + * most likely already known but is not zero. + * + * If you however choose to not call `hash_list_get` + * before `hash_list_put` and `hash_list_remove` + * you should define this macro before including + * this header file, but with the `1` changed to + * a `0`. If you on the other hand do not know + * if you are going to call `hash_list_get` before + * `hash_list_put` and `hash_list_remove` you + * should define it to expand to the input verbatim, + * that is, have the value `__VA_ARGS__`. + */ +#ifndef HASH_LIST_EXPECTED +# define HASH_LIST_EXPECTED(...) __builtin_expect((__VA_ARGS__), 1) +#endif + #define HASH_LIST_HASH(key) (this->hasher != NULL ? this->hasher(key) : (size_t)key) @@ -171,6 +198,15 @@ typedef struct T\ size_t used;\ \ /** + * This variable is used for optimisation, any + * time `hash_list_get` finds an element, its + * will be stored, and it will be the first + * inspected element by `hash_list_put` and + * `hash_list_remove` + */\ + size_t last;\ + \ + /** * The slots */\ T##_entry_t* slots;\ @@ -215,6 +251,7 @@ T##_create(T##_t* restrict this, size_t capacity)\ this->allocated = 0;\ this->unused = 0;\ this->used = 0;\ + this->last = 0;\ \ this->slots = malloc(capacity * sizeof(T##_t));\ if (this->slots == NULL)\ @@ -241,6 +278,7 @@ T##_destroy(T##_t* restrict this)\ this->used = 0;\ this->unused = 0;\ this->allocated = 0;\ + this->last = 0;\ free(this->slots);\ this->slots = NULL;\ }\ @@ -260,6 +298,7 @@ T##_clone(const T##_t* restrict this, T##_t* restrict out)\ return -1;\ out->used = this->used;\ out->unused = this->unused;\ + out->last = this->last;\ memcpy(out->slots, this->slots, this->used * sizeof(T##_entry_t));\ }\ \ @@ -289,6 +328,7 @@ T##_pack(T##_t* restrict this)\ \ this->used -= this->unused;\ this->unused = 0;\ + this->last = 0;\ }\ \ if (this->used < this->allocated)\ @@ -313,14 +353,14 @@ T##_pack(T##_t* restrict this)\ * @return Whether the key was found, error is impossible */\ static inline int __attribute__((unused))\ -T##_get(const T##_t* restrict this, CKEY_T key, T##_value_t* restrict value)\ +T##_get(T##_t* restrict this, CKEY_T key, T##_value_t* restrict value)\ {\ size_t i, n, hash = HASH_LIST_HASH(key);\ for (i = 0, n = this->used; i < n; i++)\ if ((this->slots[i].key_hash == hash) && this->slots[i].key)\ if (T##_key_comparer(this->slots[i].key, key))\ - return *value = this->slots[i].value, 1;\ - return 0;\ + return *value = this->slots[this->last = i].value, 1;\ + return this->last = 0, 0;\ }\ \ \ @@ -333,20 +373,37 @@ T##_get(const T##_t* restrict this, CKEY_T key, T##_value_t* restrict value)\ static inline void __attribute__((unused))\ T##_remove(T##_t* restrict this, CKEY_T key)\ {\ - size_t i, n, hash = HASH_LIST_HASH(key);\ + size_t i = this->last, n, hash = HASH_LIST_HASH(key);\ T##_entry_t* slots = this->slots;\ + \ + /* First, try cached index */\ + if (HASH_LIST_EXPECTED(i && (slots[i].key_hash == hash) && (slots[i].key != NULL)))\ + if (HASH_LIST_EXPECTED(T##_key_comparer(slots[i].key, key)))\ + goto do_remove;\ + /* It is discouraged to use put or remove without + * doing a get before it, otherwise you do not know + * what is happening. So we do not expect to get + * get to the next line. However, if do not expect to + * run get before put or remove, you should modify the + * HASH_LIST_EXPECTED macro. However, this is single + * case where will will get to the next line, when the + * index of the item is zero. */\ + \ + /* Then, search */\ for (i = 0, n = this->used; i < n; i++)\ if ((slots[i].key_hash == hash) && (slots[i].key != NULL))\ if (T##_key_comparer(slots[i].key, key))\ - {\ - if (this->freer != NULL)\ - this->freer(slots + i);\ - slots[i].key = NULL;\ - this->unused++;\ - if ((this->unused >> 1) >= this->used)\ - T##_pack(this);\ - return;\ - }\ + goto do_remove;\ + \ + return;\ + do_remove:\ + if (this->freer != NULL)\ + this->freer(slots + i);\ + slots[i].key = NULL;\ + this->unused++;\ + if ((this->unused >> 1) >= this->used)\ + T##_pack(this);\ + this->last = 0;\ }\ \ \ @@ -362,7 +419,7 @@ T##_remove(T##_t* restrict this, CKEY_T key)\ static inline int __attribute__((unused))\ T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* restrict value)\ {\ - size_t i, n, empty, hash;\ + size_t i = this->last, n, empty = this->used, hash;\ T##_entry_t* slots = this->slots;\ \ /* Remove entry if no value is passed */\ @@ -372,18 +429,30 @@ T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* restrict value)\ return 0;\ }\ \ + /* Hash the input key */\ + hash = HASH_LIST_HASH(key);\ + \ + /* Try cached index */\ + if (HASH_LIST_EXPECTED(i && (slots[i].key != NULL)))\ + if (HASH_LIST_EXPECTED(slots[i].key_hash == hash))\ + if (HASH_LIST_EXPECTED(T##_key_comparer(slots[i].key, key)))\ + goto put;\ + /* It is discouraged to use put or remove without + * doing a get before it, otherwise you do not know + * what is happening. So we do not expect to get + * get to the next line. However, if do not expect to + * run get before put or remove, you should modify the + * HASH_LIST_EXPECTED macro. However, this is single + * case where will will get to the next line, when the + * index of the item is zero. */\ + \ /* Find an unused slot or the current slot */\ - empty = this->used, hash = HASH_LIST_HASH(key);\ for (i = 0, n = this->used; i < n; i++)\ if (slots[i].key == NULL)\ empty = i;\ else if (slots[i].key_hash == hash)\ if (T##_key_comparer(slots[i].key, key))\ - {\ - if (this->freer != NULL)\ - this->freer(slots + i);\ - goto put;\ - }\ + goto put;\ \ /* Grow slot allocation is required */\ if (empty == this->allocated)\ @@ -399,7 +468,11 @@ T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* restrict value)\ \ /* Store entry */\ i = empty;\ + goto put_no_free;\ put:\ + if (this->freer != NULL)\ + this->freer(slots + i);\ + put_no_free:\ slots[i].key = key;\ slots[i].key_hash = hash;\ slots[i].value = *value;\ @@ -417,7 +490,7 @@ static inline size_t __attribute__((unused))\ T##_marshal_size(const T##_t* restrict this)\ {\ size_t i, n = this->used;\ - size_t rc = sizeof(int) + 3 * sizeof(size_t);\ + size_t rc = sizeof(int) + 4 * sizeof(size_t);\ for (i = 0; i < n; i++)\ if (this->slots[i].key != NULL)\ rc += T##_submarshal_size(this->slots + i);\ @@ -440,6 +513,7 @@ T##_marshal(const T##_t* restrict this, char* restrict data)\ buf_set_next(data, size_t, this->allocated);\ buf_set_next(data, size_t, this->unused);\ buf_set_next(data, size_t, this->used);\ + buf_set_next(data, size_t, this->last);\ \ for (i = 0; i < n; i++)\ if (this->slots[i].key != NULL)\ @@ -477,6 +551,7 @@ T##_unmarshal(T##_t* restrict this, char* restrict data)\ buf_get_next(data, size_t, this->allocated);\ buf_get_next(data, size_t, this->unused);\ buf_get_next(data, size_t, this->used);\ + buf_get_next(data, size_t, this->last);\ \ this->slots = calloc(this->allocated, sizeof(T##_entry_t));\ if (this->slots == NULL)\ |