diff options
Diffstat (limited to 'mysql/mysys/lf_hash.c')
| -rw-r--r-- | mysql/mysys/lf_hash.c | 722 |
1 files changed, 722 insertions, 0 deletions
diff --git a/mysql/mysys/lf_hash.c b/mysql/mysys/lf_hash.c new file mode 100644 index 0000000..b55734f --- /dev/null +++ b/mysql/mysys/lf_hash.c @@ -0,0 +1,722 @@ +/* Copyright (c) 2006, 2015, Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ + +/* + extensible hash + + TODO + try to get rid of dummy nodes ? + for non-unique hash, count only _distinct_ values + (but how to do it in lf_hash_delete ?) +*/ +#include <my_global.h> +#include <m_string.h> +#include <my_sys.h> +#include <mysys_priv.h> +#include <my_bit.h> +#include <lf.h> + +LF_REQUIRE_PINS(3) + +/* An element of the list */ +typedef struct { + intptr volatile link; /* a pointer to the next element in a listand a flag */ + uint32 hashnr; /* reversed hash number, for sorting */ + const uchar *key; + size_t keylen; + /* + data is stored here, directly after the keylen. + thus the pointer to data is (void*)(slist_element_ptr+1) + */ +} LF_SLIST; + +const int LF_HASH_OVERHEAD= sizeof(LF_SLIST); + +/* + a structure to pass the context (pointers two the three successive elements + in a list) from my_lfind to linsert/ldelete +*/ +typedef struct { + intptr volatile *prev; + LF_SLIST *curr, *next; +} CURSOR; + +/* + the last bit in LF_SLIST::link is a "deleted" flag. + the helper macros below convert it to a pure pointer or a pure flag +*/ +#define PTR(V) (LF_SLIST *)((V) & (~(intptr)1)) +#define DELETED(V) ((V) & 1) + +/* + DESCRIPTION + Search for hashnr/key/keylen in the list starting from 'head' and + position the cursor. The list is ORDER BY hashnr, key + + RETURN + 0 - not found + 1 - found + + NOTE + cursor is positioned in either case + pins[0..2] are used, they are NOT removed on return +*/ +static int my_lfind(LF_SLIST * volatile *head, CHARSET_INFO *cs, uint32 hashnr, + const uchar *key, size_t keylen, CURSOR *cursor, LF_PINS *pins) +{ + uint32 cur_hashnr; + const uchar *cur_key; + size_t cur_keylen; + intptr link; + +retry: + cursor->prev= (intptr *)head; + do { /* PTR() isn't necessary below, head is a dummy node */ + cursor->curr= (LF_SLIST *)(*cursor->prev); + lf_pin(pins, 1, cursor->curr); + } while (*cursor->prev != (intptr)cursor->curr && LF_BACKOFF); + for (;;) + { + if (unlikely(!cursor->curr)) + return 0; /* end of the list */ + do { + /* QQ: XXX or goto retry ? */ + link= cursor->curr->link; + cursor->next= PTR(link); + lf_pin(pins, 0, cursor->next); + } while (link != cursor->curr->link && LF_BACKOFF); + cur_hashnr= cursor->curr->hashnr; + cur_key= cursor->curr->key; + cur_keylen= cursor->curr->keylen; + if (*cursor->prev != (intptr)cursor->curr) + { + (void)LF_BACKOFF; + goto retry; + } + if (!DELETED(link)) + { + if (cur_hashnr >= hashnr) + { + int r= 1; + if (cur_hashnr > hashnr || + (r= my_strnncoll(cs, (uchar*) cur_key, cur_keylen, (uchar*) key, + keylen)) >= 0) + return !r; + } + cursor->prev= &(cursor->curr->link); + lf_pin(pins, 2, cursor->curr); + } + else + { + /* + we found a deleted node - be nice, help the other thread + and remove this deleted node + */ + if (my_atomic_casptr((void **)cursor->prev, + (void **)&cursor->curr, cursor->next)) + lf_pinbox_free(pins, cursor->curr); + else + { + (void)LF_BACKOFF; + goto retry; + } + } + cursor->curr= cursor->next; + lf_pin(pins, 1, cursor->curr); + } +} + + +/** + Search for list element satisfying condition specified by match + function and position cursor on it. + + @param head Head of the list to search in. + @param first_hashnr Hash value to start search from. + @param last_hashnr Hash value to stop search after. + @param match Match function. + @param cursor Cursor to be position. + @param pins LF_PINS for the calling thread to be used during + search for pinning result. + + @retval 0 - not found + @retval 1 - found +*/ + +static int my_lfind_match(LF_SLIST * volatile *head, + uint32 first_hashnr, uint32 last_hashnr, + lf_hash_match_func *match, + CURSOR *cursor, LF_PINS *pins) +{ + uint32 cur_hashnr; + intptr link; + +retry: + cursor->prev= (intptr *)head; + do { /* PTR() isn't necessary below, head is a dummy node */ + cursor->curr= (LF_SLIST *)(*cursor->prev); + lf_pin(pins, 1, cursor->curr); + } while (*cursor->prev != (intptr)cursor->curr && LF_BACKOFF); + for (;;) + { + if (unlikely(!cursor->curr)) + return 0; /* end of the list */ + do { + /* QQ: XXX or goto retry ? */ + link= cursor->curr->link; + cursor->next= PTR(link); + lf_pin(pins, 0, cursor->next); + } while (link != cursor->curr->link && LF_BACKOFF); + cur_hashnr= cursor->curr->hashnr; + if (*cursor->prev != (intptr)cursor->curr) + { + (void)LF_BACKOFF; + goto retry; + } + if (!DELETED(link)) + { + if (cur_hashnr >= first_hashnr) + { + if (cur_hashnr > last_hashnr) + return 0; + + if (cur_hashnr & 1) + { + /* Normal node. Check if element matches condition. */ + if ((*match)((uchar *)(cursor->curr + 1))) + return 1; + } + else + { + /* + Dummy node. Nothing to check here. + + Still thanks to the fact that dummy nodes are never deleted we + can save it as a safe place to restart iteration if ever needed. + */ + head= (LF_SLIST * volatile *)&(cursor->curr->link); + } + } + + cursor->prev= &(cursor->curr->link); + lf_pin(pins, 2, cursor->curr); + } + else + { + /* + we found a deleted node - be nice, help the other thread + and remove this deleted node + */ + if (my_atomic_casptr((void **)cursor->prev, + (void **)&cursor->curr, cursor->next)) + lf_pinbox_free(pins, cursor->curr); + else + { + (void)LF_BACKOFF; + goto retry; + } + } + cursor->curr= cursor->next; + lf_pin(pins, 1, cursor->curr); + } +} + + +/* + DESCRIPTION + insert a 'node' in the list that starts from 'head' in the correct + position (as found by my_lfind) + + RETURN + 0 - inserted + not 0 - a pointer to a duplicate (not pinned and thus unusable) + + NOTE + it uses pins[0..2], on return all pins are removed. + if there're nodes with the same key value, a new node is added before them. +*/ +static LF_SLIST *linsert(LF_SLIST * volatile *head, CHARSET_INFO *cs, + LF_SLIST *node, LF_PINS *pins, uint flags) +{ + CURSOR cursor; + int res; + + for (;;) + { + if (my_lfind(head, cs, node->hashnr, node->key, node->keylen, + &cursor, pins) && + (flags & LF_HASH_UNIQUE)) + { + res= 0; /* duplicate found */ + break; + } + else + { + node->link= (intptr)cursor.curr; + DBUG_ASSERT(node->link != (intptr)node); /* no circular references */ + DBUG_ASSERT(cursor.prev != &node->link); /* no circular references */ + if (my_atomic_casptr((void **)cursor.prev, (void **)&cursor.curr, node)) + { + res= 1; /* inserted ok */ + break; + } + } + } + lf_unpin(pins, 0); + lf_unpin(pins, 1); + lf_unpin(pins, 2); + /* + Note that cursor.curr is not pinned here and the pointer is unreliable, + the object may dissapear anytime. But if it points to a dummy node, the + pointer is safe, because dummy nodes are never freed - initialize_bucket() + uses this fact. + */ + return res ? 0 : cursor.curr; +} + +/* + DESCRIPTION + deletes a node as identified by hashnr/keey/keylen from the list + that starts from 'head' + + RETURN + 0 - ok + 1 - not found + + NOTE + it uses pins[0..2], on return all pins are removed. +*/ +static int ldelete(LF_SLIST * volatile *head, CHARSET_INFO *cs, uint32 hashnr, + const uchar *key, uint keylen, LF_PINS *pins) +{ + CURSOR cursor; + int res; + + for (;;) + { + if (!my_lfind(head, cs, hashnr, key, keylen, &cursor, pins)) + { + res= 1; /* not found */ + break; + } + else + { + /* mark the node deleted */ + if (my_atomic_casptr((void **)&(cursor.curr->link), + (void **)&cursor.next, + (void *)(((intptr)cursor.next) | 1))) + { + /* and remove it from the list */ + if (my_atomic_casptr((void **)cursor.prev, + (void **)&cursor.curr, cursor.next)) + lf_pinbox_free(pins, cursor.curr); + else + { + /* + somebody already "helped" us and removed the node ? + Let's check if we need to help that someone too! + (to ensure the number of "set DELETED flag" actions + is equal to the number of "remove from the list" actions) + */ + my_lfind(head, cs, hashnr, key, keylen, &cursor, pins); + } + res= 0; + break; + } + } + } + lf_unpin(pins, 0); + lf_unpin(pins, 1); + lf_unpin(pins, 2); + return res; +} + +/* + DESCRIPTION + searches for a node as identified by hashnr/keey/keylen in the list + that starts from 'head' + + RETURN + 0 - not found + node - found + + NOTE + it uses pins[0..2], on return the pin[2] keeps the node found + all other pins are removed. +*/ +static LF_SLIST *my_lsearch(LF_SLIST * volatile *head, CHARSET_INFO *cs, + uint32 hashnr, const uchar *key, uint keylen, + LF_PINS *pins) +{ + CURSOR cursor; + int res= my_lfind(head, cs, hashnr, key, keylen, &cursor, pins); + if (res) + lf_pin(pins, 2, cursor.curr); + lf_unpin(pins, 0); + lf_unpin(pins, 1); + return res ? cursor.curr : 0; +} + +static inline const uchar* hash_key(const LF_HASH *hash, + const uchar *record, size_t *length) +{ + if (hash->get_key) + return (*hash->get_key)(record, length, 0); + *length= hash->key_length; + return record + hash->key_offset; +} + +/* + Compute the hash key value from the raw key. + + @note, that the hash value is limited to 2^31, because we need one + bit to distinguish between normal and dummy nodes. +*/ +static inline uint calc_hash(LF_HASH *hash, const uchar *key, size_t keylen) +{ + return (hash->hash_function(hash, key, keylen)) & INT_MAX32; +} + +#define MAX_LOAD 1.0 /* average number of elements in a bucket */ + +static int initialize_bucket(LF_HASH *, LF_SLIST * volatile*, uint, LF_PINS *); + + +/** + Adaptor function which allows to use hash function from character + set with LF_HASH. +*/ +static uint cset_hash_sort_adapter(const LF_HASH *hash, const uchar *key, + size_t length) +{ + ulong nr1=1, nr2=4; + hash->charset->coll->hash_sort(hash->charset, key, length, &nr1, &nr2); + return (uint)nr1; +} + + +/* + Initializes lf_hash, the arguments are compatible with hash_init + + @note element_size sets both the size of allocated memory block for + lf_alloc and a size of memcpy'ed block size in lf_hash_insert. Typically + they are the same, indeed. But LF_HASH::element_size can be decreased + after lf_hash_init, and then lf_alloc will allocate larger block that + lf_hash_insert will copy over. It is desireable if part of the element + is expensive to initialize - for example if there is a mutex or + DYNAMIC_ARRAY. In this case they should be initialize in the + LF_ALLOCATOR::constructor, and lf_hash_insert should not overwrite them. + See wt_init() for example. + As an alternative to using the above trick with decreasing + LF_HASH::element_size one can provide an "initialize" hook that will finish + initialization of object provided by LF_ALLOCATOR and set element key from + object passed as parameter to lf_hash_insert instead of doing simple memcpy. +*/ +void lf_hash_init2(LF_HASH *hash, uint element_size, uint flags, + uint key_offset, uint key_length, my_hash_get_key get_key, + CHARSET_INFO *charset, lf_hash_func *hash_function, + lf_allocator_func *ctor, lf_allocator_func *dtor, + lf_hash_init_func *init) +{ + lf_alloc_init2(&hash->alloc, sizeof(LF_SLIST)+element_size, + offsetof(LF_SLIST, key), ctor, dtor); + lf_dynarray_init(&hash->array, sizeof(LF_SLIST *)); + hash->size= 1; + hash->count= 0; + hash->element_size= element_size; + hash->flags= flags; + hash->charset= charset ? charset : &my_charset_bin; + hash->key_offset= key_offset; + hash->key_length= key_length; + hash->get_key= get_key; + hash->hash_function= hash_function ? hash_function : cset_hash_sort_adapter; + hash->initialize= init; + DBUG_ASSERT(get_key ? !key_offset && !key_length : key_length); +} + +void lf_hash_destroy(LF_HASH *hash) +{ + LF_SLIST *el, **head= (LF_SLIST **)lf_dynarray_value(&hash->array, 0); + + if (unlikely(!head)) + return; + el= *head; + + while (el) + { + intptr next= el->link; + if (el->hashnr & 1) + lf_alloc_direct_free(&hash->alloc, el); /* normal node */ + else + my_free(el); /* dummy node */ + el= (LF_SLIST *)next; + } + lf_alloc_destroy(&hash->alloc); + lf_dynarray_destroy(&hash->array); +} + +/* + DESCRIPTION + inserts a new element to a hash. it will have a _copy_ of + data, not a pointer to it. + + RETURN + 0 - inserted + 1 - didn't (unique key conflict) + -1 - out of memory + + NOTE + see linsert() for pin usage notes +*/ +int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data) +{ + int csize, bucket, hashnr; + LF_SLIST *node, * volatile *el; + + node= (LF_SLIST *)lf_alloc_new(pins); + if (unlikely(!node)) + return -1; + if (hash->initialize) + (*hash->initialize)((uchar*)(node + 1), (const uchar*)data); + else + memcpy(node+1, data, hash->element_size); + node->key= hash_key(hash, (uchar *)(node+1), &node->keylen); + hashnr= calc_hash(hash, node->key, node->keylen); + bucket= hashnr % hash->size; + el= lf_dynarray_lvalue(&hash->array, bucket); + if (unlikely(!el)) + return -1; + if (*el == NULL && unlikely(initialize_bucket(hash, el, bucket, pins))) + return -1; + node->hashnr= my_reverse_bits(hashnr) | 1; /* normal node */ + if (linsert(el, hash->charset, node, pins, hash->flags)) + { + lf_pinbox_free(pins, node); + return 1; + } + csize= hash->size; + if ((my_atomic_add32(&hash->count, 1)+1.0) / csize > MAX_LOAD) + my_atomic_cas32(&hash->size, &csize, csize*2); + return 0; +} + +/* + DESCRIPTION + deletes an element with the given key from the hash (if a hash is + not unique and there're many elements with this key - the "first" + matching element is deleted) + RETURN + 0 - deleted + 1 - didn't (not found) + -1 - out of memory + NOTE + see ldelete() for pin usage notes +*/ +int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen) +{ + LF_SLIST * volatile *el; + uint bucket, hashnr= calc_hash(hash, (uchar *)key, keylen); + + bucket= hashnr % hash->size; + el= lf_dynarray_lvalue(&hash->array, bucket); + if (unlikely(!el)) + return -1; + /* + note that we still need to initialize_bucket here, + we cannot return "node not found", because an old bucket of that + node may've been split and the node was assigned to a new bucket + that was never accessed before and thus is not initialized. + */ + if (*el == NULL && unlikely(initialize_bucket(hash, el, bucket, pins))) + return -1; + if (ldelete(el, hash->charset, my_reverse_bits(hashnr) | 1, + (uchar *)key, keylen, pins)) + { + return 1; + } + my_atomic_add32(&hash->count, -1); + return 0; +} + + +/** + Find hash element corresponding to the key. + + @param hash The hash to search element in. + @param pins Pins for the calling thread which were earlier + obtained from this hash using lf_hash_get_pins(). + @param key Key + @param keylen Key length + + @retval A pointer to an element with the given key (if a hash is not unique + and there're many elements with this key - the "first" matching + element). + @retval NULL - if nothing is found + @retval MY_ERRPTR - if OOM + + @note Uses pins[0..2]. On return pins[0..1] are removed and pins[2] + is used to pin object found. It is also not removed in case when + object is not found/error occurs but pin value is undefined in + this case. + So calling lf_hash_unpin() is mandatory after call to this function + in case of both success and failure. + @sa my_lsearch(). +*/ + +void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen) +{ + LF_SLIST * volatile *el, *found; + uint bucket, hashnr= calc_hash(hash, (uchar *)key, keylen); + + bucket= hashnr % hash->size; + el= lf_dynarray_lvalue(&hash->array, bucket); + if (unlikely(!el)) + return MY_ERRPTR; + if (*el == NULL && unlikely(initialize_bucket(hash, el, bucket, pins))) + return MY_ERRPTR; + found= my_lsearch(el, hash->charset, my_reverse_bits(hashnr) | 1, + (uchar *)key, keylen, pins); + return found ? found+1 : 0; +} + + +/** + Find random hash element which satisfies condition specified by + match function. + + @param hash Hash to search element in. + @param pin Pins for calling thread to be used during search + and for pinning its result. + @param match Pointer to match function. This function takes + pointer to object stored in hash as parameter + and returns 0 if object doesn't satisfy its + condition (and non-0 value if it does). + @param rand_val Random value to be used for selecting hash + bucket from which search in sort-ordered + list needs to be started. + + @retval A pointer to a random element matching condition. + @retval NULL - if nothing is found + @retval MY_ERRPTR - OOM. + + @note This function follows the same pinning protocol as lf_hash_search(), + i.e. uses pins[0..2]. On return pins[0..1] are removed and pins[2] + is used to pin object found. It is also not removed in case when + object is not found/error occurs but its value is undefined in + this case. + So calling lf_hash_unpin() is mandatory after call to this function + in case of both success and failure. +*/ + +void *lf_hash_random_match(LF_HASH *hash, LF_PINS *pins, + lf_hash_match_func *match, + uint rand_val) +{ + /* Convert random value to valid hash value. */ + uint hashnr= (rand_val & INT_MAX32); + uint bucket; + uint32 rev_hashnr; + LF_SLIST * volatile *el; + CURSOR cursor; + int res; + + bucket= hashnr % hash->size; + rev_hashnr= my_reverse_bits(hashnr); + + el= lf_dynarray_lvalue(&hash->array, bucket); + if (unlikely(!el)) + return MY_ERRPTR; + /* + Bucket might be totally empty if it has not been accessed since last + time LF_HASH::size has been increased. In this case we initialize it + by inserting dummy node for this bucket to the correct position in + split-ordered list. This should help future lf_hash_* calls trying to + access the same bucket. + */ + if (*el == NULL && unlikely(initialize_bucket(hash, el, bucket, pins))) + return MY_ERRPTR; + + /* + To avoid bias towards the first matching element in the bucket, we start + looking for elements with inversed hash value greater or equal than + inversed value of our random hash. + */ + res= my_lfind_match(el, rev_hashnr | 1, UINT_MAX32, match, &cursor, pins); + + if (! res && hashnr != 0) + { + /* + We have not found matching element - probably we were too close to + the tail of our split-ordered list. To avoid bias against elements + at the head of the list we restart our search from its head. Unless + we were already searching from it. + + To avoid going through elements at which we have already looked + twice we stop once we reach element from which we have begun our + first search. + */ + el= lf_dynarray_lvalue(&hash->array, 0); + if (unlikely(!el)) + return MY_ERRPTR; + res= my_lfind_match(el, 1, rev_hashnr, match, &cursor, pins); + } + + if (res) + lf_pin(pins, 2, cursor.curr); + lf_unpin(pins, 0); + lf_unpin(pins, 1); + + return res ? cursor.curr + 1 : 0; +} + +static const uchar *dummy_key= (uchar*)""; + +/* + RETURN + 0 - ok + -1 - out of memory +*/ +static int initialize_bucket(LF_HASH *hash, LF_SLIST * volatile *node, + uint bucket, LF_PINS *pins) +{ + uint parent= my_clear_highest_bit(bucket); + LF_SLIST *dummy= (LF_SLIST *)my_malloc(key_memory_lf_slist, + sizeof(LF_SLIST), MYF(MY_WME)); + LF_SLIST **tmp= 0, *cur; + LF_SLIST * volatile *el= lf_dynarray_lvalue(&hash->array, parent); + if (unlikely(!el || !dummy)) + return -1; + if (*el == NULL && bucket && + unlikely(initialize_bucket(hash, el, parent, pins))) + return -1; + dummy->hashnr= my_reverse_bits(bucket) | 0; /* dummy node */ + dummy->key= dummy_key; + dummy->keylen= 0; + if ((cur= linsert(el, hash->charset, dummy, pins, LF_HASH_UNIQUE))) + { + my_free(dummy); + dummy= cur; + } + my_atomic_casptr((void **)node, (void **)&tmp, dummy); + /* + note that if the CAS above failed (after linsert() succeeded), + it would mean that some other thread has executed linsert() for + the same dummy node, its linsert() failed, it picked up our + dummy node (in "dummy= cur") and executed the same CAS as above. + Which means that even if CAS above failed we don't need to retry, + and we should not free(dummy) - there's no memory leak here + */ + return 0; +} |