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