1 | /******************************************************************* |
---|
2 | * File: omList.h |
---|
3 | * Purpose: declaration of routines for operations on linked lists |
---|
4 | * Author: obachman (Olaf Bachmann) |
---|
5 | * Created: 11/99 |
---|
6 | *******************************************************************/ |
---|
7 | |
---|
8 | #ifndef OM_LIST_H |
---|
9 | #define OM_LIST_H |
---|
10 | |
---|
11 | #define OM_LIST_OFFSET(ptr, name_of_offset_field) \ |
---|
12 | (ptr != NULL ? ((char*) &(ptr->name_of_offset_field)) - ((char*) ptr) : 0) |
---|
13 | |
---|
14 | /******************************************************************** |
---|
15 | * |
---|
16 | * Primitve routines -- don't use directly, use om macros, instead |
---|
17 | * |
---|
18 | ********************************************************************/ |
---|
19 | /* Returns the length of a memory list; assumes list has no cycles */ |
---|
20 | int _omListLength(void* list, int next); |
---|
21 | /* Returns last non-NULL element of list; assumes list has no cycles */ |
---|
22 | void* _omListLast(void* list, int next); |
---|
23 | /* Checks whether memory list has cycles: If yes, returns address of |
---|
24 | * first element of list which is contained at least twice in memory |
---|
25 | * list. If no, NULL is returned */ |
---|
26 | void* _omListHasCycle(void* list, int next); |
---|
27 | /* returns addr, if addr is contained in memory list |
---|
28 | * 0, otherwise */ |
---|
29 | void* _omIsOnList(void* list, int next, void* addr); |
---|
30 | /* Removes addr from list, if contained in it and returns new list */ |
---|
31 | void* _omRemoveFromList(void* list, int next, void* addr); |
---|
32 | /* |
---|
33 | * The following cast list->long_field to a pointer to unsigned long |
---|
34 | */ |
---|
35 | /* Find element with that value in list and return it, if found (else NULL) */ |
---|
36 | void* _omFindInList(void* list, int next, int long_field, |
---|
37 | unsigned long what); |
---|
38 | /* |
---|
39 | * The following assume that list is ordered increasingly w.r.t. long_field |
---|
40 | */ |
---|
41 | /* Finds element in sorted list */ |
---|
42 | void* _omFindInSortedList(void* list, int next, int long_field, |
---|
43 | unsigned long what); |
---|
44 | /* Remove element with that value from list and return new list */ |
---|
45 | void* _omRemoveFromSortedList(void* list,int next,int long_field, |
---|
46 | void* addr); |
---|
47 | /* Inserts addr at the right place, returns list assumes addr != NULL */ |
---|
48 | void* _omInsertInSortedList(void* list, int next, int long_field, |
---|
49 | void* addr); |
---|
50 | #ifndef OM_NDEBUG |
---|
51 | /* Check whether list is ok, i.e. whether addr of lists are aligned and in valid range */ |
---|
52 | omError_t _omCheckList(void* list, int next, int level, omError_t report, OM_FLR_DECL); |
---|
53 | /* like above, but also check that sorting is ok */ |
---|
54 | omError_t _omCheckSortedList(void* list, int next, int long_field, int level, omError_t report, OM_FLR_DECL); |
---|
55 | #endif |
---|
56 | |
---|
57 | /******************************************************************** |
---|
58 | * |
---|
59 | * The following routines assume that Next(list) == *((void**) list) |
---|
60 | * |
---|
61 | ********************************************************************/ |
---|
62 | #define omListLength(ptr) \ |
---|
63 | _omListLength(ptr, 0) |
---|
64 | #define omListLast(ptr) \ |
---|
65 | _omListLast(ptr, 0) |
---|
66 | #define omListHasCycle(ptr) \ |
---|
67 | _omListHasCycle(ptr, 0) |
---|
68 | #define omIsOnList(ptr, addr) \ |
---|
69 | _omIsOnList(ptr, 0, addr) |
---|
70 | #define omRemoveFromList(ptr, addr) \ |
---|
71 | _omRemoveFromList(ptr, 0, addr) |
---|
72 | #define omFindInList(ptr, what, value) \ |
---|
73 | _omFindInList(ptr, 0, OM_LIST_OFFSET(ptr, what), (unsigned long) value) |
---|
74 | #define omInsertInSortedList(ptr, what, addr) \ |
---|
75 | _omInsertInSortedList(ptr, 0, OM_LIST_OFFSET(ptr, what), addr) |
---|
76 | #define omFindInSortedList(ptr, what, value) \ |
---|
77 | _omFindInSortedList(ptr, 0, OM_LIST_OFFSET(ptr, what), value) |
---|
78 | #define omRemoveFromSortedList(ptr, what, addr) \ |
---|
79 | _omRemoveFromSortedList(ptr, 0, OM_LIST_OFFSET(ptr, what), addr) |
---|
80 | #ifndef OM_NDEBUG |
---|
81 | #define omTestList(ptr, level) \ |
---|
82 | _omCheckList(ptr, 0, level, omError_NoError, OM_FLR) |
---|
83 | #define omCheckList(ptr, level, report, OM_FLR_VAL) \ |
---|
84 | _omCheckList(ptr, 0, level, report, OM_FLR_VAL) |
---|
85 | #define omCheckSortedList(ptr, what, level, report, OM_FLR_VAL) \ |
---|
86 | _omCheckSortedList(ptr, 0, OM_LIST_OFFSET(ptr, what), level, report, OM_FLR_VAL) |
---|
87 | #endif |
---|
88 | |
---|
89 | /******************************************************************** |
---|
90 | * |
---|
91 | * The following routines have name of next field as argument |
---|
92 | * |
---|
93 | ********************************************************************/ |
---|
94 | #define omGListLength(ptr, next) \ |
---|
95 | _omListLength(ptr, OM_LIST_OFFSET(ptr, next)) |
---|
96 | #define omGListLast(ptr, next) \ |
---|
97 | _omListLast(ptr, OM_LIST_OFFSET(ptr, next)) |
---|
98 | #define omGListHasCycle(ptr, next) \ |
---|
99 | _omListHasCycle(ptr, OM_LIST_OFFSET(ptr, next)) |
---|
100 | #define omIsOnGList(ptr, next, addr) \ |
---|
101 | _omIsOnList(ptr, OM_LIST_OFFSET(ptr, next), addr) |
---|
102 | #define omRemoveFromGList(ptr, next, addr) \ |
---|
103 | _omRemoveFromList(ptr, OM_LIST_OFFSET(ptr, next), addr) |
---|
104 | #define omFindInGList(ptr, next, what, value) \ |
---|
105 | _omFindInList(ptr, OM_LIST_OFFSET(ptr, next), OM_LIST_OFFSET(ptr, what), (unsigned long) value) |
---|
106 | #define omInsertInSortedGList(ptr, next, what, addr) \ |
---|
107 | _omInsertInSortedList(ptr, OM_LIST_OFFSET(ptr, next), OM_LIST_OFFSET(ptr, what), addr) |
---|
108 | #define omFindInSortedGList(ptr, next, what, value) \ |
---|
109 | _omFindInSortedList(ptr, OM_LIST_OFFSET(ptr, next),OM_LIST_OFFSET(ptr,what),value) |
---|
110 | #define omRemoveFromSortedGList(ptr, next, what, addr) \ |
---|
111 | _omRemoveFromSortedList(ptr, OM_LIST_OFFSET(addr,next),OM_LIST_OFFSET(addr,what),addr) |
---|
112 | #ifndef OM_NDEBUG |
---|
113 | #define omTestGList(ptr, next, level) \ |
---|
114 | omCheckGList(ptr, next, level, omError_NoError, OM_FLR) |
---|
115 | #define omCheckGList(ptr, next, level, report, OM_FLR_VAL) \ |
---|
116 | _omCheckList(ptr, OM_LIST_OFFSET(ptr,next), level, report, OM_FLR_VAL) |
---|
117 | #define omCheckSortedGList(ptr, next, what, level, report, OM_FLR_VAL) \ |
---|
118 | _omCheckSortedList(ptr, OM_LIST_OFFSET(ptr,next), OM_LIST_OFFSET(ptr,what), level, report, OM_FLR_VAL) |
---|
119 | #else |
---|
120 | #define omTestGList(ptr, next, val) (omError_NoError) |
---|
121 | #endif |
---|
122 | |
---|
123 | #endif /* OM_LIST_H */ |
---|