1 /* Copyright (c) 2000, 2021, Oracle and/or its affiliates. 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 PSI_memory_key m_psi_key; 54 const uint key_offset, key_length; 55 const my_hash_get_key get_key; 56 /** Size of this hash table. */ 57 uint m_size; 58 my_hash_free_key free_element; 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(PSI_memory_key psi_key,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(PSI_memory_key psi_key, 67 uint size, uint key_offset_arg , uint key_length_arg, 68 my_hash_get_key get_key_arg, my_hash_free_key free_element_arg, 69 CHARSET_INFO *hash_charset_arg) 70 : m_psi_key(psi_key), 71 key_offset(key_offset_arg), key_length(key_length_arg), 72 get_key(get_key_arg), m_size(size), 73 free_element(free_element_arg), 74 hash_charset(hash_charset_arg), 75 first_link(NULL), 76 last_link(NULL) 77 { 78 memset(&cache, 0, sizeof(cache)); 79 mysql_mutex_init(key_hash_filo_lock, &lock, MY_MUTEX_INIT_FAST); 80 } 81 ~hash_filo()82 ~hash_filo() 83 { 84 if (cache.array.buffer) /* Avoid problems with thread library */ 85 my_hash_free(&cache); 86 mysql_mutex_destroy(&lock); 87 } 88 void clear(bool locked=0) 89 { 90 if (!locked) 91 mysql_mutex_lock(&lock); 92 first_link= NULL; 93 last_link= NULL; 94 my_hash_free(&cache); 95 (void) my_hash_init(&cache, hash_charset, m_size, key_offset, 96 key_length, get_key, free_element, 0, m_psi_key); 97 if (!locked) 98 mysql_mutex_unlock(&lock); 99 } 100 first()101 hash_filo_element *first() 102 { 103 mysql_mutex_assert_owner(&lock); 104 return first_link; 105 } 106 last()107 hash_filo_element *last() 108 { 109 mysql_mutex_assert_owner(&lock); 110 return last_link; 111 } 112 search(uchar * key,size_t length)113 hash_filo_element *search(uchar* key, size_t length) 114 { 115 mysql_mutex_assert_owner(&lock); 116 117 hash_filo_element *entry=(hash_filo_element*) 118 my_hash_search(&cache, key, length); 119 if (entry) 120 { // Found; link it first 121 assert(first_link != NULL); 122 assert(last_link != NULL); 123 if (entry != first_link) 124 { // Relink used-chain 125 if (entry == last_link) 126 { 127 last_link= last_link->prev_used; 128 /* 129 The list must have at least 2 elements, 130 otherwise entry would be equal to first_link. 131 */ 132 assert(last_link != NULL); 133 last_link->next_used= NULL; 134 } 135 else 136 { 137 assert(entry->next_used != NULL); 138 assert(entry->prev_used != NULL); 139 entry->next_used->prev_used = entry->prev_used; 140 entry->prev_used->next_used = entry->next_used; 141 } 142 entry->prev_used= NULL; 143 entry->next_used= first_link; 144 145 first_link->prev_used= entry; 146 first_link=entry; 147 } 148 } 149 return entry; 150 } 151 add(hash_filo_element * entry)152 my_bool add(hash_filo_element *entry) 153 { 154 if (!m_size) return 1; 155 if (cache.records == m_size) 156 { 157 hash_filo_element *tmp=last_link; 158 last_link= last_link->prev_used; 159 if (last_link != NULL) 160 { 161 last_link->next_used= NULL; 162 } 163 else 164 { 165 /* Pathological case, m_size == 1 */ 166 first_link= NULL; 167 } 168 my_hash_delete(&cache,(uchar*) tmp); 169 } 170 if (my_hash_insert(&cache,(uchar*) entry)) 171 { 172 if (free_element) 173 (*free_element)(entry); // This should never happen 174 return 1; 175 } 176 entry->prev_used= NULL; 177 entry->next_used= first_link; 178 if (first_link != NULL) 179 first_link->prev_used= entry; 180 else 181 last_link= entry; 182 first_link= entry; 183 184 return 0; 185 } 186 size()187 uint size() 188 { return m_size; } 189 resize(uint new_size)190 void resize(uint new_size) 191 { 192 mysql_mutex_lock(&lock); 193 m_size= new_size; 194 clear(true); 195 mysql_mutex_unlock(&lock); 196 } 197 }; 198 199 #endif 200