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