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