blob: e0189ea13f8ab44d5c57fb7842f301aa6e236811 [file] [log] [blame]
Ernesto Posse8a4f2962015-05-12 13:28:46 -04001// umlrthashmap.hh
2
3/*******************************************************************************
4* Copyright (c) 2015 Zeligsoft (2009) Limited and others.
5* All rights reserved. This program and the accompanying materials
6* are made available under the terms of the Eclipse Public License v1.0
7* which accompanies this distribution, and is available at
8* http://www.eclipse.org/legal/epl-v10.html
9*******************************************************************************/
10
11#include "umlrthashmap.hh"
12#include "umlrtguard.hh"
13#include "basefatal.hh"
14#include <stdlib.h>
15#include <string.h>
16
17UMLRTHashMap::~UMLRTHashMap()
18{
19 mutex.take();
20
21 for (int i = 0; i < mapSize; ++i)
22 {
23 if (map[i].object != NULL)
24 {
25 free( (void *)map[i].object );
26 }
27 }
28 if (mapSize)
29 {
30 free( map );
31 }
32}
33
34/*static*/ int UMLRTHashMap::compareString( const void * k1, const void * k2 )
35{
36 if ((k1 == NULL) && (k2 != NULL))
37 {
38 return -1;
39 }
40 else if ((k1 != NULL) && (k2 == NULL))
41 {
42 return 1;
43 }
44 else if ((k1 == NULL) && (k2 == NULL))
45 {
46 return 0;
47 }
48 return strcmp((const char *)k1, (const char *)k2);
49}
50
51/*static*/ int UMLRTHashMap::compareValue( const void * k1, const void * k2 )
52{
53 return (char *)k1 - (char *)k2;
54}
55
56UMLRTHashMap::MapEntry * UMLRTHashMap::getEntry( const void * key ) const
57{
58 // Assumes mutex is taken.
59 MapEntry * entry = NULL;
60
61 int location = locate(key);
62
63 if ((location >= 0) && (location < mapSize))
64 {
65 if (compare(map[location].key, key) == 0)
66 {
67 entry = &map[location];
68 }
69 }
70 return entry;
71}
72
73void * UMLRTHashMap::getFirstObject() const
74{
75 // Return object associated with key. Return NULL if entry not found.
76 UMLRTGuard g(mutex);
77
78 void * object = NULL;
79 if (mapSize > 0)
80 {
81 object = map[0].object;
82 }
83 return object;
84}
85
86void * UMLRTHashMap::getObject( const void * key ) const
87{
88 // Return object associated with key. Return NULL if entry not found.
89 UMLRTGuard g(mutex);
90
91 void * object = NULL;
92 MapEntry * entry = getEntry(key);
93
94 if (entry != NULL)
95 {
96 object = entry->object;
97 }
98 return object;
99}
100
101const void * UMLRTHashMap::getKey( int location ) const
102{
103 // Return key associated with entry at location.
104 UMLRTGuard g(mutex);
105
106 const void * key = NULL;
107
108 if ((location >= 0) && (location < mapSize))
109 {
110 key = map[location].key;
111 }
112 return key;
113}
114
115void * UMLRTHashMap::getObject( int location ) const
116{
117 // Return key associated with entry at location.
118 UMLRTGuard g(mutex);
119
120 void * object = NULL;
121
122 if ((location >= 0) && (location < mapSize))
123 {
124 object = map[location].object;
125 }
126 return object;
127}
128
129void UMLRTHashMap::insert( const void * key, void * object )
130{
131 UMLRTGuard g(mutex);
132
133 MapEntry * entry = getEntry(key);
134 if (entry)
135 {
136 entry->object = object;
137 }
138 else
139 {
140 // Entry not find. Insert it.
141 int location = locate(key);
142
143 if (mapSize == 0)
144 {
145 map = (MapEntry *)malloc(sizeof(MapEntry));
146 }
147 else
148 {
149 map = (MapEntry *)realloc(map, (mapSize + 1) * sizeof(MapEntry));
150 memmove(&map[location + 1], &map[location], (mapSize - location) * sizeof(MapEntry));
151 }
152 ++mapSize;
153 map[location].key = key;
154 map[location].object = object;
155 }
156}
157
158int UMLRTHashMap::locate( const void * key ) const
159{
160 // Assumes mutex is taken.
161 // Returns either location of entry holding 'key' or the location where 'key' belongs (first entry where entry->key > input key).
162 int min, max, mid;
163 int location = -1;
164
165 min = 0;
166 max = mapSize - 1;
167
168 while (location == -1)
169 {
170 if (min > max)
171 {
172 // Zeroed in on location. It's 'min' or the one after.
173 location = min;
174 if (min < (mapSize-1))
175 {
176 if (compare(map[min].key, key) < 0)
177 {
178 // 'min' was one before location we want.
179 location = min + 1;
180 }
181 }
182 }
183 else
184 {
185 mid = (min + max) / 2;
186 if (compare(map[mid].key, key) == 0)
187 {
188 // located it
189 location = mid;
190 }
191 else if (compare(map[mid].key, key) < 0)
192 {
193 // location must be after 'mid'.
194 if ((min = (mid + 1)) >= mapSize)
195 {
196 // location falls after last item
197 location = mapSize;
198 }
199 }
200 else if ((max = (mid - 1)) < 0)
201 {
202 // location falls before first item
203 location = 0;
204 }
205 }
206 }
207 return location;
208}
209
210const void * UMLRTHashMap::remove( const void * key )
211{
212 UMLRTGuard g(mutex);
213
214 int location = locate(key);
215 const void * keyRemoved = NULL;
216
217 if (mapSize)
218 {
219 if (location < mapSize)
220 {
221 if (compare(map[location].key, key) == 0)
222 {
223 keyRemoved = map[location].key;
224 memmove(&map[location], &map[location + 1], (mapSize - location) * sizeof(MapEntry));
225 if ((--mapSize) == 0)
226 {
227 free(map);
228 map = NULL;
229 }
230 }
231 }
232 }
233 return keyRemoved;
234}
235
236UMLRTHashMap::Iterator UMLRTHashMap::getIterator() const
237{
238 if (!mapSize)
239 {
240 return Iterator(this, -1);
241 }
242 return Iterator(this, 0);
243}
244
245UMLRTHashMap::Iterator UMLRTHashMap::Iterator::end() const
246{
247 return Iterator(map, -1);
248}
249
250UMLRTHashMap::Iterator UMLRTHashMap::Iterator::next() const
251{
252 if (index == -1)
253 {
254 return end();
255 }
256 else if (map->isEmpty())
257 {
258 return end();
259 }
260 else if (index == (map->getSize() - 1))
261 {
262 return end();
263 }
264 return Iterator(map, index + 1);
265}
266
267const void * UMLRTHashMap::Iterator::getKey() const
268{
269 const void * key = NULL;
270
271 if (index != -1)
272 {
273 key = map->getKey(index);
274 }
275 return key;
276}
277
278void * UMLRTHashMap::Iterator::getObject() const
279{
280 void * object = NULL;
281
282 if (index != -1)
283 {
284 if (map->getSize() > 0)
285 {
286 object = map->getObject(index);
287 }
288 }
289 return object;
290}