1 // Copyright (C)2004 Landmark Graphics Corporation 2 // Copyright (C)2005 Sun Microsystems, Inc. 3 // Copyright (C)2011, 2014, 2019-2020 D. R. Commander 4 // 5 // This library is free software and may be redistributed and/or modified under 6 // the terms of the wxWindows Library License, Version 3.1 or (at your option) 7 // any later version. The full license is in the LICENSE.txt file included 8 // with this distribution. 9 // 10 // This library is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // wxWindows Library License for more details. 14 15 #ifndef __HASH_H__ 16 #define __HASH_H__ 17 18 #include "Mutex.h" 19 #include "Error.h" 20 21 22 // Generic hash table template class 23 24 namespace vglfaker 25 { 26 template <class HashKeyType1, class HashKeyType2, class HashValueType> 27 class Hash 28 { 29 public: 30 31 typedef struct HashEntryStruct 32 { 33 HashKeyType1 key1; 34 HashKeyType2 key2; 35 HashValueType value; 36 int refCount; 37 struct HashEntryStruct *prev, *next; 38 } HashEntry; 39 kill(void)40 void kill(void) 41 { 42 vglutil::CriticalSection::SafeLock l(mutex); 43 while(start != NULL) killEntry(start); 44 } 45 46 protected: 47 Hash(void)48 Hash(void) 49 { 50 start = end = NULL; 51 count = 0; 52 } 53 ~Hash(void)54 virtual ~Hash(void) 55 { 56 kill(); 57 } 58 59 int add(HashKeyType1 key1, HashKeyType2 key2, HashValueType value, 60 bool useRef = false) 61 { 62 HashEntry *entry = NULL; 63 64 if(!key1) THROW("Invalid argument"); 65 vglutil::CriticalSection::SafeLock l(mutex); 66 67 if((entry = findEntry(key1, key2)) != NULL) 68 { 69 if(value) entry->value = value; 70 if(useRef) entry->refCount++; 71 return 0; 72 } 73 entry = new HashEntry; 74 memset(entry, 0, sizeof(HashEntry)); 75 entry->prev = end; if(end) end->next = entry; 76 if(!start) start = entry; 77 end = entry; 78 end->key1 = key1; end->key2 = key2; end->value = value; 79 if(useRef) end->refCount = 1; 80 count++; 81 return 1; 82 } 83 find(HashKeyType1 key1,HashKeyType2 key2)84 HashValueType find(HashKeyType1 key1, HashKeyType2 key2) 85 { 86 HashEntry *entry = NULL; 87 vglutil::CriticalSection::SafeLock l(mutex); 88 89 if((entry = findEntry(key1, key2)) != NULL) 90 { 91 if(!entry->value) entry->value = attach(key1, key2); 92 return entry->value; 93 } 94 return (HashValueType)0; 95 } 96 97 void remove(HashKeyType1 key1, HashKeyType2 key2, bool useRef = false) 98 { 99 HashEntry *entry = NULL; 100 vglutil::CriticalSection::SafeLock l(mutex); 101 102 if((entry = findEntry(key1, key2)) != NULL) 103 { 104 if(useRef && entry->refCount > 0) entry->refCount--; 105 if(!useRef || entry->refCount <= 0) killEntry(entry); 106 } 107 } 108 getCount(void)109 int getCount(void) { return count; } 110 findEntry(HashKeyType1 key1,HashKeyType2 key2)111 HashEntry *findEntry(HashKeyType1 key1, HashKeyType2 key2) 112 { 113 HashEntry *entry = NULL; 114 vglutil::CriticalSection::SafeLock l(mutex); 115 116 entry = start; 117 while(entry != NULL) 118 { 119 if((entry->key1 == key1 && entry->key2 == key2) 120 || compare(key1, key2, entry)) 121 { 122 return entry; 123 } 124 entry = entry->next; 125 } 126 return NULL; 127 } 128 killEntry(HashEntry * entry)129 void killEntry(HashEntry *entry) 130 { 131 vglutil::CriticalSection::SafeLock l(mutex); 132 133 if(entry->prev) entry->prev->next = entry->next; 134 if(entry->next) entry->next->prev = entry->prev; 135 if(entry == start) start = entry->next; 136 if(entry == end) end = entry->prev; 137 detach(entry); 138 memset(entry, 0, sizeof(HashEntry)); 139 delete entry; 140 count--; 141 } 142 attach(HashKeyType1 key1,HashKeyType2 key2)143 virtual HashValueType attach(HashKeyType1 key1, HashKeyType2 key2) 144 { 145 return 0; 146 } 147 148 virtual void detach(HashEntry *entry) = 0; 149 virtual bool compare(HashKeyType1 key1, HashKeyType2 key2, 150 HashEntry *entry) = 0; 151 152 int count; 153 HashEntry *start, *end; 154 vglutil::CriticalSection mutex; 155 }; 156 } 157 158 #endif // __HASH_H__ 159