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