changed listHash to a macro to work with g++ 2.5.2.
[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.9  1994/02/03 23:30:43  hollings
11  * changed listHash to a macro to work with g++ 2.5.2.
12  *
13  * Revision 1.8  1994/01/25  20:49:40  hollings
14  * First real version of utility library.
15  *
16  * Revision 1.7  1994/01/19  20:46:17  hollings
17  * guardef defn of true/false.
18  *
19  * Revision 1.6  1993/12/15  21:06:54  hollings
20  * removed destructors.  Our current list semantics don't support auto
21  * destruction of list comonents since list elements can be shared between
22  * lists.
23  *
24  * Revision 1.5  1993/12/13  20:11:14  hollings
25  * added destructor for List class.
26  *
27  * Revision 1.4  1993/10/19  15:31:52  hollings
28  * assorted small fixes.
29  *
30  * Revision 1.3  1993/08/02  22:46:37  hollings
31  * added remove which was missing.
32  *
33  * Revision 1.2  1993/07/01  17:02:36  hollings
34  * ansi endif comments
35  *
36  * Revision 1.1  1993/05/07  20:21:15  hollings
37  * Initial revision
38  *
39  * Revision 1.1  1993/03/19  22:51:05  hollings
40  * Initial revision
41  *
42  *
43  */
44 #ifndef LIST_H
45 #define LIST_H
46 #include <stdio.h>
47 #include <stdlib.h>
48
49 typedef int Boolean;
50
51 #ifndef FALSE
52 #define FALSE 0
53 #define TRUE  1
54 #endif
55
56 #define ListHash(ptr, size) (((int)(ptr) % (int)(size)))
57
58 template <class Type> class List;
59
60 template <class Type> class ListItem {
61     friend class List<Type>;
62     friend class StringList<Type>;
63     private:
64         Type            data;
65         void            *key;
66         ListItem<Type>  *next;
67 };
68
69 template <class Type> class List {
70     public:
71         List() { head = NULL; }
72         void add(Type data, void *key);
73         void add(Type data) { add(data, (void *) data); }
74         Boolean addUnique(Type data) { return(addUnique(data, (void *) data)); }
75         Boolean addUnique(Type data, void *key) {
76             Type temp;
77
78             temp = find(key);
79             if (!temp) {
80                 add(data, key);
81                 return(TRUE);
82             } else {
83                 return(FALSE);
84             }
85         }
86         Type find(void *key);
87         Boolean remove(void *key);
88         int count()     {
89             int c;
90             ListItem<Type> *curr;
91
92             for (curr=head,c=0; curr; curr=curr->next) c++;
93             return(c);
94         }
95         Type operator *() { 
96             if (head) 
97                 return(head->data); 
98             else
99                 return((Type) NULL);
100         }
101         void operator +=(List<Type> mergee) {
102             ListItem<Type> *curr;
103
104             for (curr=mergee.head; curr; curr=curr->next) {
105                 add(curr->data, curr->key);
106             }
107         }
108         Type operator ++() { 
109             Type ret = (Type) NULL;
110             if (head) {
111                 ret = head->data;
112                 head = head->next; 
113             }
114             return(ret); 
115         }
116     protected:
117         ListItem<Type>  *head;
118 };
119
120 template <class Type> void List<Type>::add(Type data, void *key)
121 {
122     ListItem<Type> *ni;
123
124     ni = new(ListItem<Type>);
125     ni->data = data;
126     ni->key = key;
127
128     ni->next = head;
129     head = ni;
130 }
131
132 template <class Type> Boolean List<Type>::remove(void *key)
133 {
134     ListItem<Type> *lag;
135     ListItem<Type> *curr;
136
137     for (curr=head, lag = NULL; curr; curr=curr->next) {
138         if (curr->key == key) {
139             break;
140         }
141         lag = curr;
142     }
143
144     if (curr) {
145         if (lag) {
146             lag->next = curr->next;
147         } else {
148             head = curr->next;
149         }
150         delete(curr);
151         return(TRUE);
152     } else {
153         return(FALSE);
154     }
155 }
156
157 template <class Type> Type List<Type>::find(void *data)
158 {
159     ListItem<Type> *curr;
160
161     for (curr=head; curr; curr=curr->next) {
162         if (curr->key == data) {
163             return(curr->data);
164         }
165     }
166     return((Type) 0);
167 }
168
169 template <class Type> class HTable {
170
171     public:
172         HTable(Type data) { HTable(); add(data, (void *) data); }
173         HTable(); 
174         void add(Type data, void *key);
175         Boolean addUnique(Type data, void *key) {
176             Type temp;
177
178             temp = find(key);
179             if (temp ) {
180                 return(0);
181             } else {
182                 add(data, key);
183                 return(1);
184             }
185         }
186         Type find(void *key);
187         Boolean remove(void *key);
188         Type operator *() {
189             Type curr;
190
191             curr = *currList;
192             if (curr) return(curr);
193             for (currHid++; currHid < tableSize; currHid++) {
194                 if (table[currHid]) {
195                     currList = *table[currHid];
196                     curr = *currList;
197                     if (curr) return(curr);
198                 }
199             }
200             return(NULL);
201         }
202         Type operator ++() {
203             Type curr;
204
205             curr = *currList;
206             currList++;
207             return(curr);
208         }
209         int count()     {
210             int i, total;
211
212             total = 0;
213             for (i=0; i < tableSize; i++) {
214                 if (table[i]) {
215                     total += table[i]->count();
216                 }
217             }
218             return(total);
219         }
220     private:
221         List<Type> **table;
222         List<Type> currList;
223         int currHid;
224         int tableSize;
225 };
226
227 template <class Type> HTable<Type>::HTable()
228
229     table = NULL;
230     currHid = 0;
231     tableSize = 0;
232 }
233
234 template <class Type> Type HTable<Type>::find(void *key)
235 {
236     int hid;
237
238     if (!tableSize) return(NULL);
239     hid = ListHash(key, tableSize);
240     if (!table[hid]) {
241         return(NULL);
242     } else {
243         return(table[hid]->find(key));
244     }
245 }
246
247 template <class Type> void HTable<Type>::add(Type data, void *key)
248 {
249     int hid;
250
251     if (!tableSize) {
252         tableSize = 97;
253         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
254     }
255     hid = ListHash(key, tableSize);
256     if (!table[hid]) {
257         table[hid] = new(List<Type>);
258     }
259     table[hid]->add(data, key);
260 }
261
262
263 template <class Type> Boolean HTable<Type>::remove(void *key)
264 {
265     int hid;
266
267     hid = ListHash(key, tableSize);
268     if (table[hid]) {
269         return(table[hid]->remove(key));
270     }
271     return(FALSE);
272 }
273
274 template <class Type> class StringList: public List<Type> {
275     public:
276         Type find(void *key);
277 };
278
279 template <class Type> Type StringList<Type>::find(void *data) 
280 {
281     ListItem<Type> *curr;
282
283     for (curr=head; curr; curr=curr->next) {
284         if (!strcmp((char *) curr->key, (char *) data)) {
285             return(curr->data);
286         }
287     }
288     return((Type) 0);
289 }
290
291 #endif /* LIST_H */