tlds
Transactional Operations for Linked Data Structures
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
list.h
Go to the documentation of this file.
1 /* =============================================================================
2  *
3  * list.h
4  * -- Sorted singly linked list
5  * -- Options: -DLIST_NO_DUPLICATES (default: allow duplicates)
6  *
7  * =============================================================================
8  *
9  * Copyright (C) Stanford University, 2006. All Rights Reserved.
10  * Author: Chi Cao Minh
11  *
12  * =============================================================================
13  *
14  * For the license of bayes/sort.h and bayes/sort.c, please see the header
15  * of the files.
16  *
17  * ------------------------------------------------------------------------
18  *
19  * For the license of kmeans, please see kmeans/LICENSE.kmeans
20  *
21  * ------------------------------------------------------------------------
22  *
23  * For the license of ssca2, please see ssca2/COPYRIGHT
24  *
25  * ------------------------------------------------------------------------
26  *
27  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
28  * header of the files.
29  *
30  * ------------------------------------------------------------------------
31  *
32  * For the license of lib/rbtree.h and lib/rbtree.c, please see
33  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
34  *
35  * ------------------------------------------------------------------------
36  *
37  * Unless otherwise noted, the following license applies to STAMP files:
38  *
39  * Copyright (c) 2007, Stanford University
40  * All rights reserved.
41  *
42  * Redistribution and use in source and binary forms, with or without
43  * modification, are permitted provided that the following conditions are
44  * met:
45  *
46  * * Redistributions of source code must retain the above copyright
47  * notice, this list of conditions and the following disclaimer.
48  *
49  * * Redistributions in binary form must reproduce the above copyright
50  * notice, this list of conditions and the following disclaimer in
51  * the documentation and/or other materials provided with the
52  * distribution.
53  *
54  * * Neither the name of Stanford University nor the names of its
55  * contributors may be used to endorse or promote products derived
56  * from this software without specific prior written permission.
57  *
58  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
59  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
60  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
61  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
62  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
63  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
64  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
65  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
66  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
67  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
68  * THE POSSIBILITY OF SUCH DAMAGE.
69  *
70  * =============================================================================
71  */
72 
73 
74 #ifndef LIST_H
75 #define LIST_H 1
76 
77 #include "tm.h"
78 #include "types.h"
79 #include "lehigh.h"
80 
81 #ifdef __cplusplus
82 extern "C" {
83 #endif
84 
85 
86 typedef struct list_node {
87  void* dataPtr;
88  struct list_node* nextPtr;
89 } list_node_t;
90 
92 
93 typedef struct list {
96  long size;
97 } list_t;
98 
99 
100 /* =============================================================================
101  * list_iter_reset
102  * =============================================================================
103  */
104 void
105 list_iter_reset (list_iter_t* itPtr, list_t* listPtr);
106 
107 
108 /* =============================================================================
109  * TMlist_iter_reset
110  * =============================================================================
111  */
113 void
114 TMlist_iter_reset (TM_ARGDECL list_iter_t* itPtr, list_t* listPtr);
115 
116 
117 /* =============================================================================
118  * list_iter_hasNext
119  * =============================================================================
120  */
121 bool_t
122 list_iter_hasNext (list_iter_t* itPtr, list_t* listPtr);
123 
124 
125 /* =============================================================================
126  * TMlist_iter_hasNext
127  * =============================================================================
128  */
130 bool_t
131 TMlist_iter_hasNext (TM_ARGDECL list_iter_t* itPtr, list_t* listPtr);
132 
133 
134 /* =============================================================================
135  * list_iter_next
136  * =============================================================================
137  */
138 void*
139 list_iter_next (list_iter_t* itPtr, list_t* listPtr);
140 
141 
142 /* =============================================================================
143  * TMlist_iter_next
144  * =============================================================================
145  */
147 void*
148 TMlist_iter_next (TM_ARGDECL list_iter_t* itPtr, list_t* listPtr);
149 
150 
151 /* =============================================================================
152  * list_alloc
153  * -- If NULL passed for 'compare' function, will compare data pointer addresses
154  * -- Returns NULL on failure
155  * =============================================================================
156  */
157 // [RSTM] do we still need TMlist_alloc?
159 list_t*
161 
162 list_t*
163 list_alloc (comparator_t* comp);
164 
165 /* =============================================================================
166  * Plist_alloc
167  * -- If NULL passed for 'compare' function, will compare data pointer addresses
168  * -- Returns NULL on failure
169  * =============================================================================
170  */
171 list_t*
172 Plist_alloc (comparator_t* comp);
173 
174 
175 /* =============================================================================
176  * TMlist_alloc
177  * -- If NULL passed for 'compare' function, will compare data pointer addresses
178  * -- Returns NULL on failure
179  * =============================================================================
180  */
181 /* list_t* */
182 /* TMlist_alloc (TM_ARGDECL long (*compare)(const void*, const void*)); */
183 
184 
185 /* =============================================================================
186  * list_free
187  * =============================================================================
188  */
189 void
190 list_free (list_t* listPtr);
191 
192 
193 /* =============================================================================
194  * Plist_free
195  * -- If NULL passed for 'compare' function, will compare data pointer addresses
196  * -- Returns NULL on failure
197  * =============================================================================
198  */
199 void
200 Plist_free (list_t* listPtr);
201 
202 
203 /* =============================================================================
204  * TMlist_free
205  * -- If NULL passed for 'compare' function, will compare data pointer addresses
206  * -- Returns NULL on failure
207  * =============================================================================
208  */
210 void
211 TMlist_free (TM_ARGDECL list_t* listPtr);
212 
213 
214 
215 /* =============================================================================
216  * list_isEmpty
217  * -- Return TRUE if list is empty, else FALSE
218  * =============================================================================
219  */
220 bool_t
221 list_isEmpty (list_t* listPtr);
222 
223 
224 /* =============================================================================
225  * TMlist_isEmpty
226  * -- Return TRUE if list is empty, else FALSE
227  * =============================================================================
228  */
230 bool_t
231 TMlist_isEmpty (TM_ARGDECL list_t* listPtr);
232 
233 
234 /* =============================================================================
235  * list_getSize
236  * -- Returns size of list
237  * =============================================================================
238  */
239 long
240 list_getSize (list_t* listPtr);
241 
242 
243 /* =============================================================================
244  * TMlist_getSize
245  * -- Returns size of list
246  * =============================================================================
247  */
249 long
250 TMlist_getSize (TM_ARGDECL list_t* listPtr);
251 
252 
253 /* =============================================================================
254  * list_find
255  * -- Returns NULL if not found, else returns pointer to data
256  * =============================================================================
257  */
258 void*
259 list_find (list_t* listPtr, void* dataPtr);
260 
261 
262 /* =============================================================================
263  * TMlist_find
264  * -- Returns NULL if not found, else returns pointer to data
265  * =============================================================================
266  */
268 void*
269 TMlist_find (TM_ARGDECL list_t* listPtr, void* dataPtr);
270 
271 
272 /* =============================================================================
273  * list_insert
274  * -- Return TRUE on success, else FALSE
275  * =============================================================================
276  */
277 bool_t
278 list_insert (list_t* listPtr, void* dataPtr);
279 
280 
281 /* =============================================================================
282  * Plist_insert
283  * -- Return TRUE on success, else FALSE
284  * =============================================================================
285  */
286 bool_t
287 Plist_insert (list_t* listPtr, void* dataPtr);
288 
289 
290 /* =============================================================================
291  * TMlist_insert
292  * -- Return TRUE on success, else FALSE
293  * =============================================================================
294  */
296 bool_t
297 TMlist_insert (TM_ARGDECL list_t* listPtr, void* dataPtr);
298 
299 
300 /* =============================================================================
301  * list_remove
302  * -- Returns TRUE if successful, else FALSE
303  * =============================================================================
304  */
305 bool_t
306 list_remove (list_t* listPtr, void* dataPtr);
307 
308 
309 /* =============================================================================
310  * Plist_remove
311  * -- Returns TRUE if successful, else FALSE
312  * =============================================================================
313  */
314 bool_t
315 Plist_remove (list_t* listPtr, void* dataPtr);
316 
317 
318 /* =============================================================================
319  * TMlist_remove
320  * -- Returns TRUE if successful, else FALSE
321  * =============================================================================
322  */
324 bool_t
325 TMlist_remove (TM_ARGDECL list_t* listPtr, void* dataPtr);
326 
327 
328 /* =============================================================================
329  * list_clear
330  * -- Removes all elements
331  * =============================================================================
332  */
334 void
335 TMlist_clear (TM_ARGDECL list_t* listPtr);
336 
337 
338 /* =============================================================================
339  * Plist_clear
340  * -- Removes all elements
341  * =============================================================================
342  */
343 void
344 Plist_clear (list_t* listPtr);
345 
346 
347 #define PLIST_ALLOC(cmp) Plist_alloc(cmp)
348 #define PLIST_FREE(list) Plist_free(list)
349 #define PLIST_GETSIZE(list) list_getSize(list)
350 #define PLIST_INSERT(list, data) Plist_insert(list, data)
351 #define PLIST_REMOVE(list, data) Plist_remove(list, data)
352 #define PLIST_CLEAR(list) Plist_clear(list)
353 
354 
355 #define TMLIST_ITER_RESET(it, list) TMlist_iter_reset(TM_ARG it, list)
356 #define TMLIST_ITER_HASNEXT(it, list) TMlist_iter_hasNext(TM_ARG it, list)
357 #define TMLIST_ITER_NEXT(it, list) TMlist_iter_next(TM_ARG it, list)
358 #define TMLIST_ALLOC(cmp) TMlist_alloc(TM_ARG cmp)
359 #define TMLIST_FREE(list) TMlist_free(TM_ARG list)
360 #define TMLIST_GETSIZE(list) TMlist_getSize(TM_ARG list)
361 #define TMLIST_ISEMPTY(list) TMlist_isEmpty(TM_ARG list)
362 #define TMLIST_FIND(list, data) TMlist_find(TM_ARG list, data)
363 #define TMLIST_INSERT(list, data) TMlist_insert(TM_ARG list, data)
364 #define TMLIST_REMOVE(list, data) TMlist_remove(TM_ARG list, data)
365 #define TMLIST_CLEAR(list) TMlist_clear(TM_ARG list)
366 
367 
368 #ifdef __cplusplus
369 }
370 #endif
371 
372 
373 #endif /* LIST_H */
374 
375 
376 /* =============================================================================
377  *
378  * End of list.h
379  *
380  * =============================================================================
381  */
struct list list_t
bool_t list_remove(list_t *listPtr, void *dataPtr)
Definition: list.c:692
#define TM_CALLABLE
Definition: cxxtm.hpp:32
bool_t Plist_insert(list_t *listPtr, void *dataPtr)
Definition: list.c:623
TM_CALLABLE bool_t TMlist_iter_hasNext(TM_ARGDECL list_iter_t *itPtr, list_t *listPtr)
Definition: list.c:150
TM_CALLABLE bool_t TMlist_insert(TM_ARGDECL list_t *listPtr, void *dataPtr)
Definition: list.c:657
void list_iter_reset(list_iter_t *itPtr, list_t *listPtr)
Definition: list.c:117
TM_CALLABLE void * TMlist_iter_next(TM_ARGDECL list_iter_t *itPtr, list_t *listPtr)
Definition: list.c:176
list_node_t * list_iter_t
Definition: list.h:91
TM_CALLABLE bool_t TMlist_isEmpty(TM_ARGDECL list_t *listPtr)
Definition: list.c:453
void * list_find(list_t *listPtr, void *dataPtr)
Definition: list.c:543
struct list_node * nextPtr
Definition: list.h:88
bool_t Plist_remove(list_t *listPtr, void *dataPtr)
Definition: list.c:721
bool_t list_isEmpty(list_t *listPtr)
Definition: list.c:441
void Plist_clear(list_t *listPtr)
Definition: list.c:794
int bool_t
Definition: portable_defns.h:32
#define TM_ARGDECL
Definition: tm.h:532
TM_CALLABLE bool_t TMlist_remove(TM_ARGDECL list_t *listPtr, void *dataPtr)
Definition: list.c:750
list_node_t head
Definition: list.h:94
TM_CALLABLE void * TMlist_find(TM_ARGDECL list_t *listPtr, void *dataPtr)
Definition: list.c:565
struct list_node list_node_t
list_t * list_alloc(comparator_t *comp)
Definition: list.c:302
void * dataPtr
Definition: list.h:87
long list_getSize(list_t *listPtr)
Definition: list.c:466
void Plist_free(list_t *listPtr)
Definition: list.c:415
bool_t list_insert(list_t *listPtr, void *dataPtr)
Definition: list.c:588
TM_CALLABLE long TMlist_getSize(TM_ARGDECL list_t *listPtr)
Definition: list.c:478
Definition: list.h:86
comparator_t * comparator
Definition: list.h:95
void * list_iter_next(list_iter_t *itPtr, list_t *listPtr)
Definition: list.c:163
TM_CALLABLE void TMlist_clear(TM_ARGDECL list_t *listPtr)
Definition: list.c:780
Definition: list.h:93
TM_CALLABLE list_t * TMlist_alloc(TM_ARGDECL comparator_t *comp)
Definition: list.c:254
Definition: lehigh.h:29
TM_CALLABLE void TMlist_iter_reset(TM_ARGDECL list_iter_t *itPtr, list_t *listPtr)
Definition: list.c:128
TM_CALLABLE void TMlist_free(TM_ARGDECL list_t *listPtr)
Definition: list.c:427
bool_t list_iter_hasNext(list_iter_t *itPtr, list_t *listPtr)
Definition: list.c:139
long size
Definition: list.h:96
void list_free(list_t *listPtr)
Definition: list.c:403
list_t * Plist_alloc(comparator_t *comp)
Definition: list.c:282