Branch data Line data Source code
1 : : // $Id: List.h 463 2004-09-26 21:04:20Z vern $
2 : :
3 : : #ifndef list_h
4 : : #define list_h
5 : :
6 : : // BaseList.h --
7 : : // Interface for class BaseList, current implementation is as an
8 : : // array of ent's. This implementation was chosen to optimize
9 : : // getting to the ent's rather than inserting and deleting.
10 : : // Also pairs of append's and get's act like push's and pop's
11 : : // and are very efficient. The only really expensive operations
12 : : // are inserting (but not appending), which requires pushing every
13 : : // element up, and resizing the list, which involves getting new space
14 : : // and moving the data. Resizing occurs automatically when inserting
15 : : // more elements than the list can currently hold. Automatic
16 : : // resizing is done one "chunk_size" of elements at a time and
17 : : // always increases the size of the list. Resizing to zero
18 : : // (or to less than the current value of num_entries)
19 : : // will decrease the size of the list to the current number of
20 : : // elements. Resize returns the new max_entries.
21 : : //
22 : : // Entries must be either a pointer to the data or nonzero data with
23 : : // sizeof(data) <= sizeof(void*).
24 : :
25 : : #include <stdarg.h>
26 : : #include "util.h"
27 : :
28 : : typedef void* ent;
29 : : typedef int (*list_cmp_func)(const void* v1, const void* v2);
30 : :
31 : : class BaseList {
32 : : public:
33 : 626260 : ~BaseList() { clear(); }
34 : :
35 : : void clear(); // remove all entries
36 : 6317083 : int length() const { return num_entries; }
37 : : int chunk() const { return chunk_size; }
38 : : int max() const { return max_entries; }
39 : : int resize(int = 0); // 0 => size to fit current number of entries
40 : :
41 : : void sort(list_cmp_func cmp_func);
42 : :
43 : 0 : int MemoryAllocation() const
44 : 0 : { return padded_sizeof(*this) + pad_size(max_entries * sizeof(ent)); }
45 : :
46 : : protected:
47 : : BaseList(int = 0);
48 : : BaseList(BaseList&);
49 : :
50 : : void insert(ent); // add at head of list
51 : :
52 : : // Assumes that the list is sorted and inserts at correct position.
53 : : void sortedinsert(ent, list_cmp_func cmp_func);
54 : :
55 : : void append(ent); // add to end of list
56 : : ent remove(ent); // delete entry from list
57 : : ent remove_nth(int); // delete nth entry from list
58 : : ent get(); // return and remove ent at end of list
59 : 16 : ent last() // return at end of list
60 : 16 : { return entry[num_entries-1]; }
61 : :
62 : : // Return 0 if ent is not in the list, ent otherwise.
63 : : ent is_member(ent) const;
64 : :
65 : : // Returns -1 if ent is not in the list, otherwise its position.
66 : : int member_pos(ent) const;
67 : :
68 : : ent replace(int, ent); // replace entry #i with a new value
69 : :
70 : : // Return nth ent of list (do not remove).
71 : 6771234 : ent operator[](int i) const
72 : : {
73 : : #ifdef SAFE_LISTS
74 : : if ( i < 0 || i > num_entries-1 )
75 : : return 0;
76 : : else
77 : : #endif
78 : 6771234 : return entry[i];
79 : : }
80 : :
81 : : void operator=(BaseList&);
82 : :
83 : : ent* entry;
84 : : int chunk_size; // increase size by this amount when necessary
85 : : int max_entries;
86 : : int num_entries;
87 : : };
88 : :
89 : :
90 : : // List.h -- interface for class List
91 : : // Use: to get a list of pointers to class foo you should:
92 : : // 1) typedef foo* Pfoo; (the macros don't like explicit pointers)
93 : : // 2) declare(List,Pfoo); (declare an interest in lists of Pfoo's)
94 : : // 3) variables are declared like:
95 : : // List(Pfoo) bar; (bar is of type list of Pfoo's)
96 : :
97 : : // For lists of "type".
98 : :
99 : : #define List(type) type ## List
100 : :
101 : : // For lists of pointers to "type"
102 : : #define PList(type) type ## PList
103 : :
104 : : #define Listdeclare(type) \
105 : : struct List(type) : BaseList \
106 : : { \
107 : : List(type)(type ...); \
108 : : List(type)() : BaseList(0) {} \
109 : : List(type)(int sz) : BaseList(sz) {} \
110 : : List(type)(List(type)& l) : BaseList((BaseList&)l) {} \
111 : : \
112 : : void operator=(List(type)& l) \
113 : : { BaseList::operator=((BaseList&)l); } \
114 : : void insert(type a) { BaseList::insert(ent(a)); } \
115 : : void sortedinsert(type a, list_cmp_func cmp_func) \
116 : : { BaseList::sortedinsert(ent(a), cmp_func); } \
117 : : void append(type a) { BaseList::append(ent(a)); } \
118 : : type remove(type a) \
119 : : { return type(BaseList::remove(ent(a))); } \
120 : : type remove_nth(int n) { return type(BaseList::remove_nth(n)); }\
121 : : type get() { return type(BaseList::get()); } \
122 : : type last() { return type(BaseList::last()); } \
123 : : type replace(int i, type new_type) \
124 : : { return type(BaseList::replace(i,ent(new_type))); } \
125 : : type is_member(type e) const \
126 : : { return type(BaseList::is_member(ent(e))); } \
127 : : int member_pos(type e) const \
128 : : { return BaseList::member_pos(ent(e)); } \
129 : : \
130 : : type operator[](int i) const \
131 : : { return type(BaseList::operator[](i)); } \
132 : : }; \
133 : :
134 : : #define Listimplement(type) \
135 : : List(type)::List(type)(type e1 ...) : BaseList() \
136 : : { \
137 : : append(e1); \
138 : : va_list ap; \
139 : : va_start(ap,e1); \
140 : : for ( type e = va_arg(ap,type); e != 0; e = va_arg(ap,type) ) \
141 : : append(e); \
142 : : resize(); \
143 : : }
144 : :
145 : : #define PListdeclare(type) \
146 : : struct PList(type) : BaseList \
147 : : { \
148 : : PList(type)(type* ...); \
149 : : PList(type)() : BaseList(0) {} \
150 : : PList(type)(int sz) : BaseList(sz) {} \
151 : : PList(type)(PList(type)& l) : BaseList((BaseList&)l) {} \
152 : : \
153 : : void operator=(PList(type)& l) \
154 : : { BaseList::operator=((BaseList&)l); } \
155 : : void insert(type* a) { BaseList::insert(ent(a)); } \
156 : : void sortedinsert(type* a, list_cmp_func cmp_func) \
157 : : { BaseList::sortedinsert(ent(a), cmp_func); } \
158 : : void append(type* a) { BaseList::append(ent(a)); } \
159 : : type* remove(type* a) \
160 : : { return (type*)BaseList::remove(ent(a)); } \
161 : : type* remove_nth(int n) { return (type*)(BaseList::remove_nth(n)); }\
162 : : type* get() { return (type*)BaseList::get(); } \
163 : : type* operator[](int i) const \
164 : : { return (type*)(BaseList::operator[](i)); } \
165 : : type* replace(int i, type* new_type) \
166 : : { return (type*)BaseList::replace(i,ent(new_type)); } \
167 : : type* is_member(type* e) \
168 : : { return (type*)BaseList::is_member(ent(e)); } \
169 : : int member_pos(type* e) \
170 : : { return BaseList::member_pos(ent(e)); } \
171 : : }; \
172 : :
173 : : #define PListimplement(type) \
174 : : PList(type)::PList(type)(type* ep1 ...) : BaseList() \
175 : : { \
176 : : append(ep1); \
177 : : va_list ap; \
178 : : va_start(ap,ep1); \
179 : : for ( type* ep = va_arg(ap,type*); ep != 0; \
180 : : ep = va_arg(ap,type*) ) \
181 : : append(ep); \
182 : : resize(); \
183 : : }
184 : :
185 : :
186 : : #define declare(metatype,type) metatype ## declare (type)
187 : :
188 : : // Popular type of list: list of strings.
189 : 28137 : declare(PList,char);
190 : : typedef PList(char) name_list;
191 : :
192 : : // Macro to visit each list element in turn.
193 : : #define loop_over_list(list, iterator) \
194 : : int iterator; \
195 : : for ( iterator = 0; iterator < (list).length(); ++iterator )
196 : :
197 : : #endif /* list_h */
|