1/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15
16
17/*
18** A class for static sized hash tables where old entries are deleted in
19** first-in-last-out to usage.
20*/
21
22#ifndef HASH_FILO_H
23#define HASH_FILO_H
24
25#ifdef USE_PRAGMA_INTERFACE
26#pragma interface /* gcc class interface */
27#endif
28
29#include "hash.h" /* my_hash_get_key, my_hash_free_key, HASH */
30#include "m_string.h" /* bzero */
31#include "mysqld.h" /* key_hash_filo_lock */
32
33class hash_filo_element
34{
35private:
36 hash_filo_element *next_used,*prev_used;
37 public:
38 hash_filo_element() {}
39 hash_filo_element *next()
40 { return next_used; }
41 hash_filo_element *prev()
42 { return prev_used; }
43
44 friend class hash_filo;
45};
46
47
48class hash_filo
49{
50private:
51 const uint key_offset, key_length;
52 const my_hash_get_key get_key;
53 /** Size of this hash table. */
54 uint m_size;
55 my_hash_free_key free_element;
56 bool init;
57 CHARSET_INFO *hash_charset;
58
59 hash_filo_element *first_link,*last_link;
60public:
61 mysql_mutex_t lock;
62 HASH cache;
63
64 hash_filo(uint size_arg, uint key_offset_arg , uint key_length_arg,
65 my_hash_get_key get_key_arg, my_hash_free_key free_element_arg,
66 CHARSET_INFO *hash_charset_arg)
67 :key_offset(key_offset_arg), key_length(key_length_arg),
68 get_key(get_key_arg), m_size(size_arg),
69 free_element(free_element_arg),init(0),
70 hash_charset(hash_charset_arg),
71 first_link(NULL),
72 last_link(NULL)
73 {
74 bzero((char*) &cache,sizeof(cache));
75 }
76
77 ~hash_filo()
78 {
79 if (init)
80 {
81 if (cache.array.buffer) /* Avoid problems with thread library */
82 (void) my_hash_free(&cache);
83 mysql_mutex_destroy(&lock);
84 }
85 }
86 void clear(bool locked=0)
87 {
88 if (!init)
89 {
90 init=1;
91 mysql_mutex_init(key_hash_filo_lock, &lock, MY_MUTEX_INIT_FAST);
92 }
93 if (!locked)
94 mysql_mutex_lock(&lock);
95 first_link= NULL;
96 last_link= NULL;
97 (void) my_hash_free(&cache);
98 (void) my_hash_init(&cache,hash_charset,m_size,key_offset,
99 key_length, get_key, free_element,0);
100 if (!locked)
101 mysql_mutex_unlock(&lock);
102 }
103
104 hash_filo_element *first()
105 {
106 mysql_mutex_assert_owner(&lock);
107 return first_link;
108 }
109
110 hash_filo_element *last()
111 {
112 mysql_mutex_assert_owner(&lock);
113 return last_link;
114 }
115
116 hash_filo_element *search(uchar* key, size_t length)
117 {
118 mysql_mutex_assert_owner(&lock);
119
120 hash_filo_element *entry=(hash_filo_element*)
121 my_hash_search(&cache,(uchar*) key,length);
122 if (entry)
123 { // Found; link it first
124 DBUG_ASSERT(first_link != NULL);
125 DBUG_ASSERT(last_link != NULL);
126 if (entry != first_link)
127 { // Relink used-chain
128 if (entry == last_link)
129 {
130 last_link= last_link->prev_used;
131 /*
132 The list must have at least 2 elements,
133 otherwise entry would be equal to first_link.
134 */
135 DBUG_ASSERT(last_link != NULL);
136 last_link->next_used= NULL;
137 }
138 else
139 {
140 DBUG_ASSERT(entry->next_used != NULL);
141 DBUG_ASSERT(entry->prev_used != NULL);
142 entry->next_used->prev_used = entry->prev_used;
143 entry->prev_used->next_used = entry->next_used;
144 }
145 entry->prev_used= NULL;
146 entry->next_used= first_link;
147
148 first_link->prev_used= entry;
149 first_link=entry;
150 }
151 }
152 return entry;
153 }
154
155 bool add(hash_filo_element *entry)
156 {
157 if (!m_size) return 1;
158 if (cache.records == m_size)
159 {
160 hash_filo_element *tmp=last_link;
161 last_link= last_link->prev_used;
162 if (last_link != NULL)
163 {
164 last_link->next_used= NULL;
165 }
166 else
167 {
168 /* Pathological case, m_size == 1 */
169 first_link= NULL;
170 }
171 my_hash_delete(&cache,(uchar*) tmp);
172 }
173 if (my_hash_insert(&cache,(uchar*) entry))
174 {
175 if (free_element)
176 (*free_element)(entry); // This should never happen
177 return 1;
178 }
179 entry->prev_used= NULL;
180 entry->next_used= first_link;
181 if (first_link != NULL)
182 first_link->prev_used= entry;
183 else
184 last_link= entry;
185 first_link= entry;
186
187 return 0;
188 }
189
190 uint size()
191 { return m_size; }
192
193 void resize(uint new_size)
194 {
195 mysql_mutex_lock(&lock);
196 m_size= new_size;
197 clear(true);
198 mysql_mutex_unlock(&lock);
199 }
200};
201
202template <class T> class Hash_filo: public hash_filo
203{
204public:
205 Hash_filo(uint size_arg, uint key_offset_arg, uint key_length_arg,
206 my_hash_get_key get_key_arg, my_hash_free_key free_element_arg,
207 CHARSET_INFO *hash_charset_arg) :
208 hash_filo(size_arg, key_offset_arg, key_length_arg,
209 get_key_arg, free_element_arg, hash_charset_arg) {}
210 T* first() { return (T*)hash_filo::first(); }
211 T* last() { return (T*)hash_filo::last(); }
212 T* search(uchar* key, size_t len) { return (T*)hash_filo::search(key, len); }
213};
214
215#endif
216