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