summaryrefslogtreecommitdiffstats
path: root/sql/hash_filo.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--sql/hash_filo.h214
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