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