1 2 /** 3 * Tencent is pleased to support the open source community by making MSEC available. 4 * 5 * Copyright (C) 2016 THL A29 Limited, a Tencent company. All rights reserved. 6 * 7 * Licensed under the GNU General Public License, Version 2.0 (the "License"); 8 * you may not use this file except in compliance with the License. You may 9 * obtain a copy of the License at 10 * 11 * https://opensource.org/licenses/GPL-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software distributed under the 14 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, 15 * either express or implied. See the License for the specific language governing permissions 16 * and limitations under the License. 17 */ 18 19 20 /** 21 * @filename hash_list.h 22 * @info ����hash��, ��hash�洢ʵ��; �̳���ʵ��hashӳ��, ע�����Ԫ�ص� 23 * ��������, ��ջ�����Ȼ��Զ�������Ԫ��, ��Ҫ����ڴ�, ����ỵ�� 24 * @time 2013-06-11 25 */ 26 27 #ifndef __HASH_LIST_FILE__ 28 #define __HASH_LIST_FILE__ 29 30 #include <stdlib.h> 31 #include <math.h> 32 #include <string.h> 33 #include <stdint.h> 34 #include <assert.h> 35 36 namespace NS_MICRO_THREAD { 37 38 /** 39 * @brief Hash���Ԫ�صĻ���, �̳и�Ԫ�ؼ���ʵ����չ 40 */ 41 class HashKey 42 { 43 private: 44 HashKey* _next_entry; ///< ����hash������Ԫ�� 45 uint32_t _hash_value; ///< hash value��Ϣ, ��Լ�Ƚϵ�ʱ�� 46 void* _data_ptr; ///< hash data����ָ��, ��key - value �ۺϴ洢 47 48 public: 49 50 friend class HashList; ///< hash�����ֱ�ӷ���nextָ�� 51 52 /** 53 * @brief ���������������� 54 */ 55 HashKey():_next_entry(NULL), _hash_value(0), _data_ptr(NULL) {}; 56 virtual ~HashKey(){}; 57 58 /** 59 * @brief �ڵ�Ԫ�ص�hash�㷨, ��ȡkey��hashֵ 60 * @return �ڵ�Ԫ�ص�hashֵ 61 */ 62 virtual uint32_t HashValue() = 0; 63 64 /** 65 * @brief �ڵ�Ԫ�ص�cmp����, ͬһͰID��, ��key�Ƚ� 66 * @return �ڵ�Ԫ�ص�hashֵ 67 */ 68 virtual int HashCmp(HashKey* rhs) = 0; 69 70 /** 71 * @brief �ѱ����ӿ�, ���ڵ���, �ڱ���ÿ��Ԫ��ʱ������, ��ѡʵ�� 72 */ 73 virtual void HashIterate() { 74 return; 75 }; 76 77 /** 78 * @brief �ڵ�Ԫ�ص�ʵ������ָ���������ȡ 79 */ 80 void* GetDataPtr() { 81 return _data_ptr; 82 }; 83 void SetDataPtr(void* data) { 84 _data_ptr = data; 85 }; 86 87 88 }; 89 90 91 /** 92 * @brief Hash������, ����ʽhash, ע��ѡ����ʵ�hash����, �����ͻ���� 93 */ 94 class HashList 95 { 96 public: 97 98 /** 99 * @brief ���캯������������ 100 */ 101 explicit HashList(int max = 100000) { 102 _max = GetMaxPrimeNum((max > 2) ? max : 100000); 103 _buckets = (HashKey**)calloc(_max, sizeof(HashKey*)); 104 _count = 0; 105 }; 106 virtual ~HashList() { 107 if (_buckets) { 108 free(_buckets); 109 _buckets = NULL; 110 } 111 _count = 0; 112 }; 113 114 /** 115 * @brief ��ȡhash��Ԫ�ظ��� 116 * @return ��Ԫ��ʵ����Ŀ 117 */ 118 int HashSize() { 119 return _count; 120 }; 121 122 /** 123 * @brief hash����Ԫ��, Ҫ�ڸ�Ԫ������ǰ, ����remove 124 * @param key �������Ԫ��ָ��, ע��Ԫ�ص���������, ��Ҫ����ջ���� 125 * @return 0 �ɹ�, -1 ������Ч��δ��ʼ��, -2 �ظ������������ 126 */ 127 int HashInsert(HashKey* key) { 128 if (!key || !_buckets) { 129 return -1; 130 } 131 132 if ((key->_hash_value != 0) || (key->_next_entry != NULL)) { 133 return -2; 134 } 135 136 key->_hash_value = key->HashValue(); 137 int idx = (key->_hash_value) % _max; 138 139 HashKey* next_item = _buckets[idx]; 140 _buckets[idx] = key; 141 key->_next_entry = next_item; 142 _count++; 143 return 0; 144 } 145 146 /** 147 * @brief hash����Ԫ�� 148 * @param key ����ѯ��keyָ�� 149 * @return ��ѯ�������ָ��, NULL���������� 150 */ 151 HashKey* HashFind(HashKey* key) { 152 if (!key || !_buckets) { 153 return NULL; 154 } 155 156 uint32_t hash = key->HashValue(); 157 int idx = hash % _max; 158 HashKey* item = _buckets[idx]; 159 160 for (; item != NULL; item = item->_next_entry) { 161 if (item->_hash_value != hash) { 162 continue; 163 } 164 165 if (item->HashCmp(key) == 0) { 166 break; 167 } 168 } 169 170 return item; 171 } 172 173 /** 174 * @brief hash����Ԫ�� 175 * @param key ����ѯ��keyָ�� 176 * @return ��ѯ�������ָ��, NULL���������� 177 */ 178 void* HashFindData(HashKey* key) { 179 HashKey* item = HashFind(key); 180 if (!item) { 181 return NULL; 182 } else { 183 return item->_data_ptr; 184 } 185 }; 186 187 188 /** 189 * @brief hashɾ��Ԫ�� 190 * @param key ��ɾ����keyָ�� 191 */ 192 void HashRemove(HashKey* key) { 193 if (!key || !_buckets) { 194 return; 195 } 196 197 uint32_t hash = key->HashValue(); 198 int idx = hash % _max; 199 HashKey* item = _buckets[idx]; 200 HashKey* prev = NULL; 201 202 for (; item != NULL; prev = item, item = item->_next_entry) { 203 if ((item->_hash_value == hash) && (item->HashCmp(key) == 0)){ 204 if (prev == NULL) { 205 _buckets[idx] = item->_next_entry; 206 } else { 207 prev->_next_entry = item->_next_entry; 208 } 209 item->_hash_value = 0; 210 item->_next_entry = NULL; 211 _count--; 212 break; 213 } 214 } 215 } 216 217 /** 218 * @brief hash����Ԫ��, ���õ������� 219 */ 220 void HashForeach() { 221 if (!_buckets) { 222 return; 223 } 224 225 for (int i = 0; i < _max; i++) { 226 HashKey* item = _buckets[i]; 227 for (; item != NULL; item = item->_next_entry) { 228 item->HashIterate(); 229 } 230 } 231 } 232 233 /** 234 * @brief hash�������, ���ܵ���, ֻ�������ձ������� 235 */ 236 HashKey* HashGetFirst() { 237 if (!_buckets) { 238 return NULL; 239 } 240 241 for (int i = 0; i < _max; i++) { 242 if (_buckets[i]) { 243 return _buckets[i]; 244 } 245 } 246 247 return NULL; 248 } 249 250 private: 251 252 /** 253 * @brief ��ȡͰ���ȵ�������� 254 */ 255 int GetMaxPrimeNum(int num) 256 { 257 int sqrt_value = (int)sqrt(num); 258 for (int i = num; i > 0; i--) 259 { 260 int flag = 1; 261 for (int k = 2; k <= sqrt_value; k++) 262 { 263 if (i % k == 0) 264 { 265 flag = 0; 266 break; 267 } 268 } 269 270 if (flag == 1) 271 { 272 return i; 273 } 274 } 275 276 return 0; 277 }; 278 279 280 private: 281 HashKey** _buckets; ///< Ͱָ�� 282 int _count; ///< ��ЧԪ�ظ��� 283 int _max; ///< ���ڵ���� 284 }; 285 286 } 287 288 289 #endif 290 291