Compilation fixes for gcc 3.1, MSVC 6.0 & 7.0
[dyninst.git] / common / h / list.h
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /*
43  * list.h - list ADT
44  *
45  * list.h,v
46  * Revision 1.22  1995/02/16  09:27:07  markc
47  * Modified code to remove compiler warnings.
48  * Added #defines to simplify inlining.
49  * Cleaned up Object file classes.
50  *
51  * Revision 1.21  1994/09/22  03:17:22  markc
52  * added postfix ++ operator
53  *
54  * Revision 1.20  1994/08/17  18:22:54  markc
55  * Moved the definitions of the << operator into the class declaration to
56  * keep gcc happy.
57  *
58  * Revision 1.19  1994/07/26  20:07:42  hollings
59  * added cast to ensure hash table pointers are positive.
60  *
61  * Revision 1.18  1994/07/11  23:00:57  jcargill
62  * Fixed bug where added two lists with (+=) operator could result in
63  * duplicate key entries
64  *
65  * Revision 1.17  1994/07/07  03:20:36  markc
66  * Added removeAll function to list class.
67  * Added machineType headers to specify pvm, cm5, ...
68  *
69  * Revision 1.16  1994/05/30  19:37:39  hollings
70  * added pragma for external g++ functions.
71  *
72  */
73
74 #ifndef LIST_H
75 #define LIST_H
76
77 #include <iostream.h>
78
79 #if defined(external_templates)
80 #pragma interface
81 #endif
82
83 #if !defined(DO_INLINE_P)
84 #define DO_INLINE_P
85 #endif
86
87 #if !defined(DO_INLINE_F)
88 #define DO_INLINE_F
89 #endif
90
91 #define ListHash(ptr, size) (((unsigned int)(ptr) % (unsigned int)(size)))
92
93 template <class Type> class List;
94 template <class Type> class StringList;
95 template <class Type> class HTable;
96
97 template <class Type> class ListItem {
98     friend class List<Type>;
99     friend class StringList<Type>;
100     private:
101         Type            data;
102         void            *key;
103         ListItem<Type>  *next;
104 };
105
106 template <class Type> class List {
107     public:
108         List() { head = NULL; }
109         DO_INLINE_F int  empty();
110         friend ostream &operator<<(ostream &os, List<Type> &data) {
111           List<Type> curr;
112           for (curr= data; *curr; ++curr) {
113             os << *curr << endl;
114           }
115           return os;
116         }
117         DO_INLINE_F void add(Type data, void *key);
118         DO_INLINE_F void add(Type data);
119         DO_INLINE_F bool addUnique(Type data);
120         bool addUnique(Type data, void *key) {
121             Type temp;
122
123             temp = find(key);
124             if (!temp) {
125                 add(data, key);
126                 return(true);
127             } else {
128                 return(false);
129             }
130         }
131         DO_INLINE_F Type find(void *key);
132         DO_INLINE_F bool remove(void *key);
133         DO_INLINE_F void removeAll();
134         int count()     {
135             int c;
136             ListItem<Type> *curr;
137
138             for (curr=head,c=0; curr; curr=curr->next) c++;
139             return(c);
140         }
141         Type operator *() { 
142             if (head) 
143                 return(head->data); 
144             else
145                 return((Type) NULL);
146         }
147         void operator +=(List<Type> mergee) {
148             ListItem<Type> *curr;
149
150             for (curr=mergee.head; curr; curr=curr->next) {
151                 addUnique(curr->data, curr->key);
152             }
153         }
154         // postfix - the beauty of c++ 
155         Type operator ++(int) { 
156             Type ret = (Type) NULL;
157             if (head) {
158                 ret = head->data;
159                 head = head->next; 
160             }
161             return(ret); 
162         }
163         // prefix
164         Type operator ++() { 
165             Type ret = (Type) NULL;
166             if (head) {
167                 ret = head->data;
168                 head = head->next; 
169             }
170             return(ret); 
171         }
172         void map (void (*map_function)(const Type item)) {
173           const ListItem<Type> *temp_ptr = 0;
174
175           if (!map_function) return;
176           for (temp_ptr = head; temp_ptr && temp_ptr->data; temp_ptr = temp_ptr->next)
177             map_function (temp_ptr->data);
178         }
179     protected:
180         ListItem<Type>  *head;
181 };
182
183 template <class Type> DO_INLINE_F int List<Type>::empty()
184
185     return (head == NULL);
186 }
187
188 template <class Type> DO_INLINE_F void List<Type>::add(Type data, void *key)
189 {
190     ListItem<Type> *ni;
191
192     ni = new(ListItem<Type>);
193     ni->data = data;
194     ni->key = key;
195
196     ni->next = head;
197     head = ni;
198 }
199
200 template <class Type> DO_INLINE_F  void List<Type>::add(Type data) 
201
202     add(data, (void *) data); 
203 }
204
205 template <class Type> DO_INLINE_F  bool List<Type>::addUnique(Type data) 
206
207     return(addUnique(data, (void *) data)); 
208 }
209
210 template <class Type> DO_INLINE_F  void List<Type>::removeAll()
211 {
212   ListItem<Type> *curr, *nx;
213
214   curr = head;
215   while (curr) {
216     nx = curr->next;
217     delete (curr);
218     curr = nx;
219   }
220   head = 0;
221 }
222
223 template <class Type> DO_INLINE_F  bool List<Type>::remove(void *key)
224 {
225     ListItem<Type> *lag;
226     ListItem<Type> *curr;
227
228     for (curr=head, lag = NULL; curr; curr=curr->next) {
229         if (curr->key == key) {
230             break;
231         }
232         lag = curr;
233     }
234
235     if (curr) {
236         if (lag) {
237             lag->next = curr->next;
238         } else {
239             head = curr->next;
240         }
241         delete(curr);
242         return(true);
243     } else {
244         return(false);
245     }
246 }
247
248 template <class Type> DO_INLINE_F  Type List<Type>::find(void *data)
249 {
250     ListItem<Type> *curr;
251
252     for (curr=head; curr; curr=curr->next) {
253         if (curr->key == data) {
254             return(curr->data);
255         }
256     }
257     return((Type) 0);
258 }
259
260 template <class Type> ostream &operator<<(ostream &os, HTable<Type> &data);
261
262 template <class Type> class HTable {
263
264     public:
265         // placing function def here makes gcc happy 
266   // VG(06/15/02): that nonstandard hack doesn't work with gcc 3.1...
267   // let's do this properly:
268   // (1) the function needs to be already declared (above)
269   // (2) add <> after name here, so only that instantiation is friended
270   // (3) the function is defined after this class
271   // Of course, old broken compilers don't like the standard, so we just
272   // write something that compiles (as was the case before).
273 #if defined(i386_unknown_nt4_0) && _MSC_VER < 1300
274   friend ostream& operator<< (ostream &os, HTable<Type> &data);
275 #else
276   friend ostream& operator<< <> (ostream &os, HTable<Type> &data);
277 #endif
278
279         HTable(Type data) { (void) HTable(); add(data, (void *) data); }
280         DO_INLINE_F void add(Type data, void *key);
281         DO_INLINE_F HTable(); 
282         bool addUnique(Type data, void *key) {
283             Type temp;
284
285             temp = find(key);
286             if (temp ) {
287                 return(false);
288             } else {
289                 add(data, key);
290                 return(true);
291             }
292         }
293         DO_INLINE_F Type find(void *key);
294         DO_INLINE_F bool remove(void *key);
295         DO_INLINE_F HTable<Type> operator =(HTable<Type> arg); 
296         Type operator *() {
297             return(*currList);
298         }
299         // postfix
300         Type operator ++(int) {
301           Type curr;
302           
303           ++currList;
304           curr = *currList;
305           if (curr) return(curr);
306           for (currHid++; currHid < tableSize; currHid++) {
307             if (table[currHid]) {
308               currList = *table[currHid];
309               curr = *currList;
310               if (curr) return(curr);
311             }
312           }
313           return(NULL);
314         }
315         // prefix
316         Type operator ++() {
317             Type curr;
318
319             ++currList;
320             curr = *currList;
321             if (curr) return(curr);
322             for (currHid++; currHid < tableSize; currHid++) {
323                 if (table[currHid]) {
324                     currList = *table[currHid];
325                     curr = *currList;
326                     if (curr) return(curr);
327                 }
328             }
329             return(NULL);
330         }
331         int count()     {
332             int i, total;
333
334             total = 0;
335             for (i=0; i < tableSize; i++) {
336                 if (table[i]) {
337                     total += table[i]->count();
338                 }
339             }
340             return(total);
341         }
342
343     private:
344         List<Type> **table;
345         List<Type> currList;
346         int currHid;
347         int tableSize;
348 };
349
350
351 template <class Type> ostream &operator<<(ostream &os,
352                                           HTable<Type> &data) {
353   int i, total;
354   
355   total = 0;
356   for (i=0; i < data.tableSize; i++) {
357     if (data.table[i]) {
358       os << *data.table[i];
359     }
360   }
361   return os;
362 }
363
364
365 template <class Type> DO_INLINE_F HTable<Type> HTable<Type>::operator =(HTable<Type> arg) {
366     table = arg.table;
367     tableSize = arg.tableSize;
368
369     // find the first item.
370     currHid = -1;
371     ++(*this);
372     return(*this);
373 }
374
375 template <class Type> DO_INLINE_F  HTable<Type>::HTable()
376
377     table = NULL;
378     currHid = 0;
379     tableSize = 0;
380 }
381
382 template <class Type> DO_INLINE_F  Type HTable<Type>::find(void *key)
383 {
384     int hid;
385
386     if (!tableSize) return(NULL);
387     hid = ListHash(key, tableSize);
388     if (hid <0 || hid > tableSize) abort();
389     if (!table[hid]) {
390         return(NULL);
391     } else {
392         return(table[hid]->find(key));
393     }
394 }
395
396 template <class Type> DO_INLINE_F  void HTable<Type>::add(Type data, void *key)
397 {
398     int hid;
399
400     if (!tableSize) {
401         tableSize = 97;
402         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
403     }
404     hid = ListHash(key, tableSize);
405     if (hid <0 || hid > tableSize) abort();
406     if (!table[hid]) {
407         table[hid] = new(List<Type>);
408     }
409     table[hid]->add(data, key);
410 }
411
412
413 template <class Type> DO_INLINE_F  bool HTable<Type>::remove(void *key)
414 {
415     int hid;
416
417     hid = ListHash(key, tableSize);
418     if (hid <0 || hid > tableSize) abort();
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         DO_INLINE_F Type find(void *key);
428 };
429
430 template <class Type> DO_INLINE_F 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 */