diff options
Diffstat (limited to 'sql/hash_filo.h')
| -rw-r--r-- | sql/hash_filo.h | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/sql/hash_filo.h b/sql/hash_filo.h new file mode 100644 index 00000000..ac84e5cc --- /dev/null +++ b/sql/hash_filo.h @@ -0,0 +1,214 @@ +/* Copyright (c) 2000, 2011, 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-1335 USA */ + + +/* +** A class for static sized hash tables where old entries are deleted in +** first-in-last-out to usage. +*/ + +#ifndef HASH_FILO_H +#define HASH_FILO_H + +#ifdef USE_PRAGMA_INTERFACE +#pragma interface /* gcc class interface */ +#endif + +#include "hash.h" /* my_hash_get_key, my_hash_free_key, HASH */ +#include "m_string.h" /* bzero */ +#include "mysqld.h" /* key_hash_filo_lock */ + +class hash_filo_element +{ +private: + hash_filo_element *next_used,*prev_used; + public: + hash_filo_element() {} + hash_filo_element *next() + { return next_used; } + hash_filo_element *prev() + { return prev_used; } + + friend class hash_filo; +}; + + +class hash_filo +{ +private: + PSI_memory_key m_psi_key; + const uint key_offset, key_length; + const my_hash_get_key get_key; + /** Size of this hash table. */ + uint m_size; + my_hash_free_key free_element; + bool init; + CHARSET_INFO *hash_charset; + + hash_filo_element *first_link,*last_link; +public: + mysql_mutex_t lock; + HASH cache; + + hash_filo(PSI_memory_key psi_key, uint size_arg, uint key_offset_arg, + uint key_length_arg, my_hash_get_key get_key_arg, + my_hash_free_key free_element_arg, CHARSET_INFO *hash_charset_arg) + : m_psi_key(psi_key), key_offset(key_offset_arg), + key_length(key_length_arg), get_key(get_key_arg), m_size(size_arg), + free_element(free_element_arg),init(0), hash_charset(hash_charset_arg), + first_link(NULL), last_link(NULL) + { + bzero((char*) &cache,sizeof(cache)); + } + + ~hash_filo() + { + if (init) + { + if (cache.array.buffer) /* Avoid problems with thread library */ + (void) my_hash_free(&cache); + mysql_mutex_destroy(&lock); + } + } + void clear(bool locked=0) + { + if (!init) + { + init=1; + mysql_mutex_init(key_hash_filo_lock, &lock, MY_MUTEX_INIT_FAST); + } + if (!locked) + mysql_mutex_lock(&lock); + first_link= NULL; + last_link= NULL; + (void) my_hash_free(&cache); + (void) my_hash_init(m_psi_key, &cache,hash_charset,m_size,key_offset, + key_length, get_key, free_element, 0); + if (!locked) + mysql_mutex_unlock(&lock); + } + + hash_filo_element *first() + { + mysql_mutex_assert_owner(&lock); + return first_link; + } + + hash_filo_element *last() + { + mysql_mutex_assert_owner(&lock); + return last_link; + } + + hash_filo_element *search(uchar* key, size_t length) + { + mysql_mutex_assert_owner(&lock); + + hash_filo_element *entry=(hash_filo_element*) + my_hash_search(&cache,(uchar*) key,length); + if (entry) + { // Found; link it first + DBUG_ASSERT(first_link != NULL); + DBUG_ASSERT(last_link != NULL); + if (entry != first_link) + { // Relink used-chain + if (entry == last_link) + { + last_link= last_link->prev_used; + /* + The list must have at least 2 elements, + otherwise entry would be equal to first_link. + */ + DBUG_ASSERT(last_link != NULL); + last_link->next_used= NULL; + } + else + { + DBUG_ASSERT(entry->next_used != NULL); + DBUG_ASSERT(entry->prev_used != NULL); + entry->next_used->prev_used = entry->prev_used; + entry->prev_used->next_used = entry->next_used; + } + entry->prev_used= NULL; + entry->next_used= first_link; + + first_link->prev_used= entry; + first_link=entry; + } + } + return entry; + } + + bool add(hash_filo_element *entry) + { + if (!m_size) return 1; + if (cache.records == m_size) + { + hash_filo_element *tmp=last_link; + last_link= last_link->prev_used; + if (last_link != NULL) + { + last_link->next_used= NULL; + } + else + { + /* Pathological case, m_size == 1 */ + first_link= NULL; + } + my_hash_delete(&cache,(uchar*) tmp); + } + if (my_hash_insert(&cache,(uchar*) entry)) + { + if (free_element) + (*free_element)(entry); // This should never happen + return 1; + } + entry->prev_used= NULL; + entry->next_used= first_link; + if (first_link != NULL) + first_link->prev_used= entry; + else + last_link= entry; + first_link= entry; + + return 0; + } + + uint size() + { return m_size; } + + void resize(uint new_size) + { + mysql_mutex_lock(&lock); + m_size= new_size; + clear(true); + mysql_mutex_unlock(&lock); + } +}; + +template <class T> class Hash_filo: public hash_filo +{ +public: + Hash_filo(PSI_memory_key psi_key, uint size_arg, uint key_offset_arg, uint + key_length_arg, my_hash_get_key get_key_arg, my_hash_free_key + free_element_arg, CHARSET_INFO *hash_charset_arg) : + hash_filo(psi_key, size_arg, key_offset_arg, key_length_arg, + get_key_arg, free_element_arg, hash_charset_arg) {} + T* first() { return (T*)hash_filo::first(); } + T* last() { return (T*)hash_filo::last(); } + T* search(uchar* key, size_t len) { return (T*)hash_filo::search(key, len); } +}; + +#endif |