Changed Boolean from int to char to match X11 convention.
[dyninst.git] / pdutil / h / list.h
1 /*
2  *  Copyright 1993 Jeff Hollingsworth.  All rights reserved.
3  *
4  */
5
6 /*
7  * list.h - list ADT
8  *
9  * $Log: list.h,v $
10  * Revision 1.15  1994/03/11 21:01:23  hollings
11  * Changed Boolean from int to char to match X11 convention.
12  *
13  * Revision 1.14  1994/02/25  00:25:57  hollings
14  * added tunable constants.
15  *
16  * Revision 1.13  1994/02/24  07:05:28  markc
17  * Man page for librpcUtil.a
18  * Extended list class to provide map function.  rpcUtil supports internet domain
19  * sockets.
20  *
21  * Revision 1.12  1994/02/10  23:08:21  hollings
22  * Fixed list.h ++ function to work when a hash table has an element at
23  * slot zero in the table.
24  *
25  * Removed unused fields in hist class.
26  *
27  * Revision 1.11  1994/02/09  22:37:09  hollings
28  * Added print routines to list and hash table.
29  *
30  * Revision 1.10  1994/02/08  00:30:32  hollings
31  * Make libutil more compatable with ATT CC.
32  *
33  * Revision 1.9  1994/02/03  23:30:43  hollings
34  * changed listHash to a macro to work with g++ 2.5.2.
35  *
36  * Revision 1.8  1994/01/25  20:49:40  hollings
37  * First real version of utility library.
38  *
39  * Revision 1.7  1994/01/19  20:46:17  hollings
40  * guardef defn of true/false.
41  *
42  * Revision 1.6  1993/12/15  21:06:54  hollings
43  * removed destructors.  Our current list semantics don't support auto
44  * destruction of list comonents since list elements can be shared between
45  * lists.
46  *
47  * Revision 1.5  1993/12/13  20:11:14  hollings
48  * added destructor for List class.
49  *
50  * Revision 1.4  1993/10/19  15:31:52  hollings
51  * assorted small fixes.
52  *
53  * Revision 1.3  1993/08/02  22:46:37  hollings
54  * added remove which was missing.
55  *
56  * Revision 1.2  1993/07/01  17:02:36  hollings
57  * ansi endif comments
58  *
59  * Revision 1.1  1993/05/07  20:21:15  hollings
60  * Initial revision
61  *
62  * Revision 1.1  1993/03/19  22:51:05  hollings
63  * Initial revision
64  *
65  *
66  */
67 #ifndef LIST_H
68 #define LIST_H
69 #include <stdio.h>
70 #include <iostream.h>
71 #include <stdlib.h>
72
73 typedef char Boolean;
74
75 #ifndef FALSE
76 #define FALSE 0
77 #define TRUE  1
78 #endif
79
80 #define ListHash(ptr, size) (((int)(ptr) % (int)(size)))
81
82 template <class Type> class List;
83 template <class Type> class StringList;
84
85 template <class Type> class ListItem {
86     friend class List<Type>;
87     friend class StringList<Type>;
88     private:
89         Type            data;
90         void            *key;
91         ListItem<Type>  *next;
92 };
93
94 template <class Type> class List {
95     public:
96         List() { head = NULL; current = NULL; }
97         int  empty() { return (head == NULL);}
98         friend ostream &operator<<(ostream&, List<Type>&);
99         void print();
100         void add(Type data, void *key);
101         void add(Type data);
102         Boolean addUnique(Type data);
103         Boolean addUnique(Type data, void *key) {
104             Type temp;
105
106             temp = find(key);
107             if (!temp) {
108                 add(data, key);
109                 return(TRUE);
110             } else {
111                 return(FALSE);
112             }
113         }
114         Type find(void *key);
115         Boolean remove(void *key);
116         int count()     {
117             int c;
118             ListItem<Type> *curr;
119
120             for (curr=head,c=0; curr; curr=curr->next) c++;
121             return(c);
122         }
123         Type operator *() { 
124             if (head) 
125                 return(head->data); 
126             else
127                 return((Type) NULL);
128         }
129         void operator +=(List<Type> mergee) {
130             ListItem<Type> *curr;
131
132             for (curr=mergee.head; curr; curr=curr->next) {
133                 add(curr->data, curr->key);
134             }
135         }
136         Type operator ++() { 
137             Type ret = (Type) NULL;
138             if (head) {
139                 ret = head->data;
140                 head = head->next; 
141             }
142             return(ret); 
143         }
144         void map (void (*map_function)(const Type item)) {
145           const ListItem<Type> *temp_ptr = 0;
146
147           if (!map_function) return;
148           for (temp_ptr = head; temp_ptr && temp_ptr->data; temp_ptr = temp_ptr->next)
149             map_function (temp_ptr->data);
150         }
151         void setCurrent() { current = head;}
152         const Type getCurrent() { 
153           if (current) return ( (const Type) current->data);
154           else return 0;
155         }
156         const Type next() {
157           advanceCurrent();
158           return getCurrent();
159         }
160         void advanceCurrent() { if (current) current = current->next;}
161     protected:
162         ListItem<Type>  *head;
163         ListItem<Type>  *current;
164 };
165
166 template <class Type> ostream &operator<<(ostream &os, List<Type> &data)
167 {
168     List<Type> curr;
169
170     for (curr= data; *curr; curr++) {
171         os << *curr << endl;
172     }
173     return os;
174 }
175
176 //
177 // Warning this function should be replaced by the stream operator above, but
178 //   g++ is broken and won't create it.
179 // 
180 template <class Type> void List<Type>::print()
181 {
182     ListItem<Type> *curr;
183
184     for (curr=head; curr; curr=curr->next) {
185         cout << (curr->data) << endl;
186     }
187 }
188
189 template <class Type> void List<Type>::add(Type data, void *key)
190 {
191     ListItem<Type> *ni;
192
193     ni = new(ListItem<Type>);
194     ni->data = data;
195     ni->key = key;
196
197     ni->next = head;
198     head = ni;
199 }
200
201 template <class Type> void List<Type>::add(Type data) 
202
203     add(data, (void *) data); 
204 }
205
206 template <class Type> Boolean List<Type>::addUnique(Type data) 
207
208     return(addUnique(data, (void *) data)); 
209 }
210
211 template <class Type> Boolean List<Type>::remove(void *key)
212 {
213     ListItem<Type> *lag;
214     ListItem<Type> *curr;
215
216     for (curr=head, lag = NULL; curr; curr=curr->next) {
217         if (curr->key == key) {
218             break;
219         }
220         lag = curr;
221     }
222
223     if (curr) {
224         if (lag) {
225             lag->next = curr->next;
226         } else {
227             head = curr->next;
228         }
229         // if the 'current' pointer is this element, advance it
230         if (current == curr)
231           advanceCurrent();
232         delete(curr);
233         return(TRUE);
234     } else {
235         return(FALSE);
236     }
237 }
238
239 template <class Type> Type List<Type>::find(void *data)
240 {
241     ListItem<Type> *curr;
242
243     for (curr=head; curr; curr=curr->next) {
244         if (curr->key == data) {
245             return(curr->data);
246         }
247     }
248     return((Type) 0);
249 }
250
251 template <class Type> class HTable {
252
253     public:
254         friend ostream &operator<<(ostream&, HTable<Type>&);
255         void print();
256         HTable(Type data) { (void) HTable(); add(data, (void *) data); }
257         void add(Type data, void *key);
258         HTable(); 
259         Boolean addUnique(Type data, void *key) {
260             Type temp;
261
262             temp = find(key);
263             if (temp ) {
264                 return(0);
265             } else {
266                 add(data, key);
267                 return(1);
268             }
269         }
270         Type find(void *key);
271         Boolean remove(void *key);
272         HTable<Type> operator =(HTable<Type> arg) {
273             table = arg.table;
274             tableSize = arg.tableSize;
275
276             // find the first item.
277             currHid = -1;
278             (*this)++;
279             return(*this);
280         }
281         Type operator *() {
282             return(*currList);
283         }
284         Type operator ++() {
285             Type curr;
286
287             currList++;
288             curr = *currList;
289             if (curr) return(curr);
290             for (currHid++; currHid < tableSize; currHid++) {
291                 if (table[currHid]) {
292                     currList = *table[currHid];
293                     curr = *currList;
294                     if (curr) return(curr);
295                 }
296             }
297             return(NULL);
298         }
299         int count()     {
300             int i, total;
301
302             total = 0;
303             for (i=0; i < tableSize; i++) {
304                 if (table[i]) {
305                     total += table[i]->count();
306                 }
307             }
308             return(total);
309         }
310     private:
311         List<Type> **table;
312         List<Type> currList;
313         int currHid;
314         int tableSize;
315 };
316
317 template <class Type> ostream &operator<<(ostream &os, HTable<Type> &data)
318 {
319     int i, total;
320
321     total = 0;
322     for (i=0; i < data.tableSize; i++) {
323         if (data.table[i]) {
324             os << *data.table[i];
325         }
326     }
327     return os;
328 }
329
330
331 //
332 // Warning this function should be replaced by the stream operator above, but
333 //   g++ is broken and won't create it.
334 // 
335 template <class Type> void HTable<Type>::print()
336 {
337     int i, total;
338
339     total = 0;
340     for (i=0; i < tableSize; i++) {
341         if (table[i]) {
342             table[i]->print();
343         }
344     }
345 }
346
347 template <class Type> HTable<Type>::HTable()
348
349     table = NULL;
350     currHid = 0;
351     tableSize = 0;
352 }
353
354 template <class Type> Type HTable<Type>::find(void *key)
355 {
356     int hid;
357
358     if (!tableSize) return(NULL);
359     hid = ListHash(key, tableSize);
360     if (!table[hid]) {
361         return(NULL);
362     } else {
363         return(table[hid]->find(key));
364     }
365 }
366
367 template <class Type> void HTable<Type>::add(Type data, void *key)
368 {
369     int hid;
370
371     if (!tableSize) {
372         tableSize = 97;
373         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
374     }
375     hid = ListHash(key, tableSize);
376     if (!table[hid]) {
377         table[hid] = new(List<Type>);
378     }
379     table[hid]->add(data, key);
380 }
381
382
383 template <class Type> Boolean HTable<Type>::remove(void *key)
384 {
385     int hid;
386
387     hid = ListHash(key, tableSize);
388     if (table[hid]) {
389         return(table[hid]->remove(key));
390     }
391     return(FALSE);
392 }
393
394 template <class Type> class StringList: public List<Type> {
395     public:
396         Type find(void *key);
397 };
398
399 template <class Type> Type StringList<Type>::find(void *data) 
400 {
401     ListItem<Type> *curr;
402
403     for (curr=head; curr; curr=curr->next) {
404         if (!strcmp((char *) curr->key, (char *) data)) {
405             return(curr->data);
406         }
407     }
408     return((Type) 0);
409 }
410
411 #endif /* LIST_H */