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