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