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