|
0
|
1 #include<stdlib.h>
|
|
2
|
2 /* TODO: malloc. */
|
|
|
3 #include"List.h"
|
|
0
|
4
|
|
2
|
5 /*
|
|
|
6 * doubly-linked list.
|
|
|
7 * interfaces of these routines is based on glib.
|
|
|
8 *
|
|
|
9 * Usage:
|
|
|
10 * create new list.
|
|
|
11 * list = NULL
|
|
|
12 * add new data
|
|
|
13 * list = _listAddFirst(list, data)
|
|
|
14 * remove data from the list
|
|
|
15 * list = _listRemove(list, data)
|
|
|
16 * get n-th data
|
|
|
17 * data = _listGetnthData(list, n)
|
|
|
18 *
|
|
|
19 *
|
|
|
20 * NOTE:
|
|
|
21 * Although `struct List' is a doubly-linked List, the List
|
|
|
22 * is made as a Ring. An User's variable is treated as a
|
|
|
23 * head of the list. And head->prev is last. And then if
|
|
|
24 * list have only one data, both next and prev field of
|
|
|
25 * head will point to oneself.
|
|
|
26 * If the variable is NULL, it means no data.
|
|
|
27 */
|
|
0
|
28
|
|
|
29 List *
|
|
|
30 _listAddFirst(List* top, void *data)
|
|
|
31 {
|
|
|
32 List *newlist;
|
|
2
|
33 List *last;
|
|
|
34 newlist = malloc(sizeof(struct _List));
|
|
|
35 newlist->data = data;
|
|
|
36
|
|
0
|
37 if (!top) {
|
|
|
38 newlist->next = newlist;
|
|
|
39 newlist->prev = newlist;
|
|
|
40 return newlist;
|
|
|
41 }
|
|
2
|
42 last = top->prev;
|
|
0
|
43 newlist->next = top;
|
|
|
44 newlist->prev = last;
|
|
|
45
|
|
|
46 top->prev = newlist;
|
|
|
47 last->next = newlist;
|
|
|
48 return newlist;
|
|
|
49 }
|
|
|
50
|
|
|
51 List *
|
|
|
52 _listRemove(List *top, void *data)
|
|
|
53 {
|
|
|
54 List *t;
|
|
|
55 if (top->data==data) {
|
|
|
56 if (top->next==top) {
|
|
|
57 free(top);
|
|
|
58 return NULL;
|
|
|
59 }
|
|
|
60 List *newtop = top->next;
|
|
|
61 top->next->prev = top->prev;
|
|
|
62 top->prev->next = top->next;
|
|
|
63 free(top);
|
|
|
64 return newtop;
|
|
|
65 }
|
|
|
66 for (t=top->next; t!=top; t=t->next) {
|
|
|
67 if (t->data==data) {
|
|
|
68 t->next->prev = t->prev;
|
|
|
69 t->prev->next = t->next;
|
|
|
70 free(t);
|
|
|
71 return top;
|
|
|
72 }
|
|
|
73 }
|
|
|
74 return top;
|
|
|
75 }
|
|
|
76
|
|
|
77 void *
|
|
|
78 _listGetnthData(List *top, int n)
|
|
|
79 {
|
|
|
80 List *t;
|
|
|
81
|
|
|
82 for (t=top; n>0; n--) {
|
|
|
83 t = t->next;
|
|
|
84 if (t==top) return NULL;
|
|
|
85 }
|
|
|
86
|
|
|
87 return t->data;
|
|
|
88 }
|
|
1
|
89 void *
|
|
|
90 _listGetLastData(List *top)
|
|
|
91 {
|
|
|
92 if (!top) return NULL;
|
|
|
93 return top->prev->data;
|
|
|
94 }
|
|
|
95
|
|
2
|
96 List *
|
|
1
|
97 _listMoveLasttoFirst(List *top)
|
|
|
98 {
|
|
|
99 if (!top) return NULL;
|
|
|
100 return top->prev;
|
|
|
101 }
|
|
0
|
102
|
|
|
103 void
|
|
2
|
104 _listApply(List *top, ApplyFn fn, void *arg)
|
|
|
105 {
|
|
0
|
106 List *t = top;
|
|
|
107 do {
|
|
|
108 fn(t->data, arg);
|
|
|
109 t = t->next;
|
|
|
110 } while ( t!=top );
|
|
|
111 }
|
|
|
112
|
|
2
|
113 /*
|
|
|
114 * Iterator's functions.
|
|
|
115 *
|
|
|
116 * iter = _listIterator(list);
|
|
|
117 * while ( (data=_listIterNext(iter)!=NULL ) {
|
|
|
118 * exe(data);
|
|
|
119 * if (data...) {
|
|
|
120 * list = _listIterRemove(iter);
|
|
|
121 * }
|
|
|
122 * }
|
|
|
123 */
|
|
|
124 ListIter *
|
|
|
125 _listIterator(List *top)
|
|
|
126 {
|
|
|
127 ListIter *iter;
|
|
|
128 iter = malloc(sizeof(struct _ListIter));
|
|
|
129 iter->head = top;
|
|
|
130 iter->next = top;
|
|
|
131 return iter;
|
|
|
132 }
|
|
0
|
133
|
|
2
|
134 void *
|
|
|
135 _listIterNext(ListIter *iter)
|
|
|
136 {
|
|
|
137 void *rtn;
|
|
|
138 if (!iter->next) return NULL;
|
|
|
139
|
|
|
140 rtn = iter->next->data;
|
|
|
141 iter->next = iter->next->next;
|
|
|
142 if (iter->next==iter->head) {
|
|
|
143 iter->next = NULL;
|
|
|
144 }
|
|
|
145 return rtn;
|
|
|
146 }
|
|
|
147
|
|
|
148 void
|
|
|
149 _listIterEnd(ListIter *iter)
|
|
|
150 {
|
|
|
151 free(iter);
|
|
|
152 }
|
|
|
153
|
|
|
154 List *
|
|
|
155 _listIterRemoveCurrent(ListIter *iter)
|
|
|
156 {
|
|
|
157 List *cur, *p, *n;
|
|
|
158 if (!iter->head) return NULL;
|
|
|
159 else if (!iter->next) cur = iter->head->prev;
|
|
|
160 else cur = iter->next->prev;
|
|
|
161
|
|
|
162 if (cur==iter->head) {
|
|
|
163 if (cur->next==iter->head) {
|
|
|
164 free(iter->head);
|
|
|
165 return NULL;
|
|
|
166 }
|
|
|
167 iter->head = iter->head->next;
|
|
|
168 }
|
|
|
169 cur->prev->next = cur->next;
|
|
|
170 cur->next->prev = cur->prev;
|
|
|
171
|
|
|
172 free(cur);
|
|
|
173 return iter->head;
|
|
|
174 }
|
|
0
|
175
|
|
|
176
|
|
2
|
177 /*
|
|
|
178 * for DEBUG
|
|
|
179 */
|
|
0
|
180
|
|
2
|
181 int
|
|
|
182 _listRingCheck(List *head)
|
|
|
183 {
|
|
|
184 List *cur = head;
|
|
0
|
185
|
|
2
|
186 if (cur->prev->next!=cur) return 0;
|
|
|
187 if (cur->next->prev!=cur) return 0;
|
|
|
188 do {
|
|
|
189 if (cur->prev->next!=cur) return 0;
|
|
|
190 if (cur->next->prev!=cur) return 0;
|
|
|
191 cur = cur->prev;
|
|
|
192 } while (cur!=head);
|
|
0
|
193
|
|
2
|
194 if (cur->prev->next!=cur) return 0;
|
|
|
195 if (cur->next->prev!=cur) return 0;
|
|
|
196 cur = cur->next;
|
|
|
197 if (cur->prev->next!=cur) return 0;
|
|
|
198 if (cur->next->prev!=cur) return 0;
|
|
|
199
|
|
|
200 return 1;
|
|
|
201 }
|
|
|
202
|
