tlds
Transactional Operations for Linked Data Structures
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
map.h
Go to the documentation of this file.
1 /* =============================================================================
2  *
3  * map.h
4  * -- Utility defines to use various data structures as map
5  *
6  * =============================================================================
7  *
8  * Copyright (C) Stanford University, 2006. All Rights Reserved.
9  * Author: Chi Cao Minh
10  *
11  * =============================================================================
12  *
13  * For the license of bayes/sort.h and bayes/sort.c, please see the header
14  * of the files.
15  *
16  * ------------------------------------------------------------------------
17  *
18  * For the license of kmeans, please see kmeans/LICENSE.kmeans
19  *
20  * ------------------------------------------------------------------------
21  *
22  * For the license of ssca2, please see ssca2/COPYRIGHT
23  *
24  * ------------------------------------------------------------------------
25  *
26  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
27  * header of the files.
28  *
29  * ------------------------------------------------------------------------
30  *
31  * For the license of lib/rbtree.h and lib/rbtree.c, please see
32  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
33  *
34  * ------------------------------------------------------------------------
35  *
36  * Unless otherwise noted, the following license applies to STAMP files:
37  *
38  * Copyright (c) 2007, Stanford University
39  * All rights reserved.
40  *
41  * Redistribution and use in source and binary forms, with or without
42  * modification, are permitted provided that the following conditions are
43  * met:
44  *
45  * * Redistributions of source code must retain the above copyright
46  * notice, this list of conditions and the following disclaimer.
47  *
48  * * Redistributions in binary form must reproduce the above copyright
49  * notice, this list of conditions and the following disclaimer in
50  * the documentation and/or other materials provided with the
51  * distribution.
52  *
53  * * Neither the name of Stanford University nor the names of its
54  * contributors may be used to endorse or promote products derived
55  * from this software without specific prior written permission.
56  *
57  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
58  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
59  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
60  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
61  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
62  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
63  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
64  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
65  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
66  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
67  * THE POSSIBILITY OF SUCH DAMAGE.
68  *
69  * =============================================================================
70  */
71 
72 
73 #ifndef MAP_H
74 #define MAP_H 1
75 
76 
77 #include <stdlib.h>
78 #include "pair.h"
79 #include "types.h"
80 
81 
82 #if defined(MAP_USE_HASHTABLE)
83 
84 # include "hashtable.h"
85 
86 # define MAP_T hashtable_t
87 # define MAP_ALLOC(hash, cmp) hashtable_alloc(1, hash, cmp, 2, 2)
88 # define MAP_FREE(map) hashtable_free(map)
89 # define MAP_CONTAINS(map, key) hashtable_containsKey(map, (void*)(key))
90 # define MAP_FIND(map, key) hashtable_find(map, (void*)(key))
91 # define MAP_INSERT(map, key, data) hashtable_insert(map, (void*)(key), (void*)(data))
92 # define MAP_REMOVE(map, key) hashtable_remove(map, (void*)(key))
93 
94 #elif defined(MAP_USE_ATREE)
95 
96 # include "atree.h"
97 
98 # define MAP_T jsw_atree_t
99 # define MAP_ALLOC(hash, cmp) jsw_anew((cmp_f)cmp)
100 # define MAP_FREE(map) jsw_adelete(map)
101 # define MAP_CONTAINS(map, key) \
102  ({ \
103  bool_t success = FALSE; \
104  pair_t searchPair; \
105  searchPair.firstPtr = (void*)key; \
106  if (jsw_afind(map, (void*)&searchPair) != NULL) { \
107  success = TRUE; \
108  } \
109  success; \
110  })
111 # define MAP_FIND(map, key) \
112  ({ \
113  void* dataPtr = NULL; \
114  pair_t searchPair; \
115  searchPair.firstPtr = (void*)(key); \
116  pair_t* pairPtr = (pair_t*)jsw_afind(map, (void*)&searchPair); \
117  if (pairPtr != NULL) { \
118  dataPtr = pairPtr->secondPtr; \
119  } \
120  dataPtr; \
121  })
122 # define MAP_INSERT(map, key, data) \
123  ({ \
124  bool_t success = FALSE; \
125  pair_t* insertPtr = pair_alloc((void*)(key), (void*)data); \
126  if (insertPtr != NULL) { \
127  if (jsw_ainsert(map, (void*)insertPtr)) { \
128  success = TRUE; \
129  } \
130  } \
131  success; \
132  })
133 # define MAP_REMOVE(map, key) \
134  ({ \
135  bool_t success = FALSE; \
136  pair_t searchPair; \
137  searchPair.firstPtr = (void*)(key); \
138  pair_t* pairPtr = (pair_t*)jsw_afind(map, (void*)&searchPair); \
139  if (jsw_aerase(map, (void*)&searchPair)) { \
140  pair_free(pairPtr); \
141  success = TRUE; \
142  } \
143  success; \
144  })
145 
146 #elif defined(MAP_USE_AVLTREE)
147 
148 # include "avltree.h"
149 
150 # define MAP_T jsw_avltree_t
151 # define MAP_ALLOC(hash, cmp) jsw_avlnew((cmp_f)cmp)
152 # define MAP_FREE(map) jsw_avldelete(map)
153 # define MAP_CONTAINS(map, key) \
154  ({ \
155  bool_t success = FALSE; \
156  pair_t searchPair; \
157  searchPair.firstPtr = (void*)key; \
158  if (jsw_avlfind(map, (void*)&searchPair) != NULL) { \
159  success = TRUE; \
160  } \
161  success; \
162  })
163 # define MAP_FIND(map, key) \
164  ({ \
165  void* dataPtr = NULL; \
166  pair_t searchPair; \
167  searchPair.firstPtr = (void*)(key); \
168  pair_t* pairPtr = (pair_t*)jsw_avlfind(map, (void*)&searchPair); \
169  if (pairPtr != NULL) { \
170  dataPtr = pairPtr->secondPtr; \
171  } \
172  dataPtr; \
173  })
174 # define MAP_INSERT(map, key, data) \
175  ({ \
176  bool_t success = FALSE; \
177  pair_t* insertPtr = pair_alloc((void*)(key), (void*)data); \
178  if (insertPtr != NULL) { \
179  if (jsw_avlinsert(map, (void*)insertPtr)) { \
180  success = TRUE; \
181  } \
182  } \
183  success; \
184  })
185 # define MAP_REMOVE(map, key) \
186  ({ \
187  bool_t success = FALSE; \
188  pair_t searchPair; \
189  searchPair.firstPtr = (void*)(key); \
190  pair_t* pairPtr = (pair_t*)jsw_avlfind(map, (void*)&searchPair); \
191  if (jsw_avlerase(map, (void*)&searchPair)) { \
192  pair_free(pairPtr); \
193  success = TRUE; \
194  } \
195  success; \
196  })
197 
198 # define PMAP_ALLOC(hash, cmp) Pjsw_avlnew((cmp_f)cmp)
199 # define PMAP_FREE(map) Pjsw_avldelete(map)
200 # define PMAP_INSERT(map, key, data) \
201  ({ \
202  bool_t success = FALSE; \
203  pair_t* insertPtr = PPAIR_ALLOC((void*)(key), (void*)data); \
204  if (insertPtr != NULL) { \
205  if (Pjsw_avlinsert(map, (void*)insertPtr)) { \
206  success = TRUE; \
207  } \
208  } \
209  success; \
210  })
211 # define PMAP_REMOVE(map, key) \
212  ({ \
213  bool_t success = FALSE; \
214  pair_t searchPair; \
215  searchPair.firstPtr = (void*)(key); \
216  pair_t* pairPtr = (pair_t*)jsw_avlfind(map, (void*)&searchPair); \
217  if (Pjsw_avlerase(map, (void*)&searchPair)) { \
218  PPAIR_FREE(pairPtr); \
219  success = TRUE; \
220  } \
221  success; \
222  })
223 
224 
225 #elif defined(MAP_USE_RBTREE)
226 
227 # include "rbtree.h"
228 
229 # define MAP_T rbtree_t
230 
231 # define MAP_ALLOC(hash, cmp) rbtree_alloc(cmp)
232 # define MAP_FREE(map) rbtree_free(map)
233 # define MAP_CONTAINS(map, key) rbtree_contains(map, (void*)(key))
234 # define MAP_FIND(map, key) rbtree_get(map, (void*)(key))
235 # define MAP_INSERT(map, key, data) \
236  rbtree_insert(map, (void*)(key), (void*)(data))
237 # define MAP_REMOVE(map, key) rbtree_delete(map, (void*)(key))
238 
239 # define TMMAP_CONTAINS(map, key) TMRBTREE_CONTAINS(map, (void*)(key))
240 # define TMMAP_FIND(map, key) TMRBTREE_GET(map, (void*)(key))
241 # define TMMAP_INSERT(map, key, data) \
242  TMRBTREE_INSERT(map, (void*)(key), (void*)(data))
243 # define TMMAP_REMOVE(map, key) TMRBTREE_DELETE(map, (void*)(key))
244 
245 
246 #elif defined(MAP_USE_SKIPLIST)
247 
248 # include "skiplist.h"
249 
250 # define SKIPLIST_MAX_HEIGHT (64)
251 
252 # define MAP_T jsw_skip_t
253 # define MAP_ALLOC(hash, cmp) jsw_snew(SKIPLIST_MAX_HEIGHT, (cmp_f)cmp)
254 # define MAP_FREE(map) jsw_sdelete(map)
255 # define MAP_CONTAINS(map, key) \
256  ({ \
257  bool_t success = FALSE; \
258  pair_t searchPair; \
259  searchPair.firstPtr = (void*)key; \
260  if (jsw_sfind(map, (void*)&searchPair) != NULL) { \
261  success = TRUE; \
262  } \
263  success; \
264  })
265 # define MAP_FIND(map, key) \
266  ({ \
267  void* dataPtr = NULL; \
268  pair_t* pairPtr; \
269  pair_t searchPair; \
270  searchPair.firstPtr = (void*)(key); \
271  pairPtr = (pair_t*)jsw_sfind(map, (void*)&searchPair); \
272  if (pairPtr != NULL) { \
273  dataPtr = pairPtr->secondPtr; \
274  } \
275  dataPtr; \
276  })
277 # define MAP_INSERT(map, key, data) \
278  ({ \
279  bool_t success = FALSE; \
280  pair_t* insertPtr = pair_alloc((void*)(key), (void*)data); \
281  if (insertPtr != NULL) { \
282  if (jsw_sinsert(map, (void*)insertPtr)) { \
283  success = TRUE; \
284  } \
285  } \
286  success; \
287  })
288 # define MAP_REMOVE(map, key) \
289  ({ \
290  bool_t success = FALSE; \
291  pair_t searchPair; \
292  searchPair.firstPtr = (void*)(key); \
293  pairPtr = (pair_t*)jsw_sfind(map, (void*)&searchPair); \
294  if (jsw_serase(map, (void*)&searchPair)) { \
295  pair_free(pairPtr); \
296  success = TRUE; \
297  } \
298  success; \
299  })
300 
301 #else
302 
303 # error "MAP type is not specified"
304 
305 #endif
306 
307 
308 #endif /* MAP_H */
309 
310 
311 /* =============================================================================
312  *
313  * End of map.h
314  *
315  * =============================================================================
316  */