include 64bit type limit defines and literal defining macros
[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> class HTable {
261
262     public:
263         // placing function def here makes gcc happy 
264         friend ostream &operator<<(ostream &os,
265                                    HTable<Type> &data) {
266             int i, total;
267
268             total = 0;
269             for (i=0; i < data.tableSize; i++) {
270               if (data.table[i]) {
271                 os << *data.table[i];
272               }
273             }
274             return os;
275           }
276         HTable(Type data) { (void) HTable(); add(data, (void *) data); }
277         DO_INLINE_F void add(Type data, void *key);
278         DO_INLINE_F HTable(); 
279         bool addUnique(Type data, void *key) {
280             Type temp;
281
282             temp = find(key);
283             if (temp ) {
284                 return(false);
285             } else {
286                 add(data, key);
287                 return(true);
288             }
289         }
290         DO_INLINE_F Type find(void *key);
291         DO_INLINE_F bool remove(void *key);
292         DO_INLINE_F HTable<Type> operator =(HTable<Type> arg); 
293         Type operator *() {
294             return(*currList);
295         }
296         // postfix
297         Type operator ++(int) {
298           Type curr;
299           
300           ++currList;
301           curr = *currList;
302           if (curr) return(curr);
303           for (currHid++; currHid < tableSize; currHid++) {
304             if (table[currHid]) {
305               currList = *table[currHid];
306               curr = *currList;
307               if (curr) return(curr);
308             }
309           }
310           return(NULL);
311         }
312         // prefix
313         Type operator ++() {
314             Type curr;
315
316             ++currList;
317             curr = *currList;
318             if (curr) return(curr);
319             for (currHid++; currHid < tableSize; currHid++) {
320                 if (table[currHid]) {
321                     currList = *table[currHid];
322                     curr = *currList;
323                     if (curr) return(curr);
324                 }
325             }
326             return(NULL);
327         }
328         int count()     {
329             int i, total;
330
331             total = 0;
332             for (i=0; i < tableSize; i++) {
333                 if (table[i]) {
334                     total += table[i]->count();
335                 }
336             }
337             return(total);
338         }
339
340     private:
341         List<Type> **table;
342         List<Type> currList;
343         int currHid;
344         int tableSize;
345 };
346
347
348 template <class Type> DO_INLINE_F HTable<Type> HTable<Type>::operator =(HTable<Type> arg) {
349     table = arg.table;
350     tableSize = arg.tableSize;
351
352     // find the first item.
353     currHid = -1;
354     ++(*this);
355     return(*this);
356 }
357
358 template <class Type> DO_INLINE_F  HTable<Type>::HTable()
359
360     table = NULL;
361     currHid = 0;
362     tableSize = 0;
363 }
364
365 template <class Type> DO_INLINE_F  Type HTable<Type>::find(void *key)
366 {
367     int hid;
368
369     if (!tableSize) return(NULL);
370     hid = ListHash(key, tableSize);
371     if (hid <0 || hid > tableSize) abort();
372     if (!table[hid]) {
373         return(NULL);
374     } else {
375         return(table[hid]->find(key));
376     }
377 }
378
379 template <class Type> DO_INLINE_F  void HTable<Type>::add(Type data, void *key)
380 {
381     int hid;
382
383     if (!tableSize) {
384         tableSize = 97;
385         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
386     }
387     hid = ListHash(key, tableSize);
388     if (hid <0 || hid > tableSize) abort();
389     if (!table[hid]) {
390         table[hid] = new(List<Type>);
391     }
392     table[hid]->add(data, key);
393 }
394
395
396 template <class Type> DO_INLINE_F  bool HTable<Type>::remove(void *key)
397 {
398     int hid;
399
400     hid = ListHash(key, tableSize);
401     if (hid <0 || hid > tableSize) abort();
402     if (table[hid]) {
403         return(table[hid]->remove(key));
404     }
405     return(false);
406 }
407
408 template <class Type> class StringList: public List<Type> {
409     public:
410         DO_INLINE_F Type find(void *key);
411 };
412
413 template <class Type> DO_INLINE_F Type StringList<Type>::find(void *data) 
414 {
415     ListItem<Type> *curr;
416
417     for (curr=head; curr; curr=curr->next) {
418         if (!strcmp((char *) curr->key, (char *) data)) {
419             return(curr->data);
420         }
421     }
422     return((Type) 0);
423 }
424
425 #endif /* LIST_H */