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