Mercurial > hg > Members > kent > CbCTaskManager

comparison List.c @ 2:803d6bf22e6d default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
second commit. it's far to complete..
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 22 Dec 2009 16:19:56 +0900
parents aef83aed7a07
children
comparison
equal deleted inserted replaced
1:aef83aed7a07 2:803d6bf22e6d
1 #include<stdlib.h> 1 #include<stdlib.h>
2 2 /* TODO: malloc. */
3 #include"List.h" 3 #include"List.h"
4 4
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 */
28
5 List * 29 List *
6 _listAddFirst(List* top, void *data) 30 _listAddFirst(List* top, void *data)
7 { 31 {
8 List *newlist; 32 List *newlist;
33 List *last;
34 newlist = malloc(sizeof(struct _List));
35 newlist->data = data;
36
9 if (!top) { 37 if (!top) {
10 newlist = malloc(sizeof(struct _List));
11 newlist->data = data;
12 newlist->next = newlist; 38 newlist->next = newlist;
13 newlist->prev = newlist; 39 newlist->prev = newlist;
14 return newlist; 40 return newlist;
15 } 41 }
16 List *last = top->prev; 42 last = top->prev;
17
18 newlist = malloc(sizeof(struct _List));
19 newlist->data = data;
20 newlist->next = top; 43 newlist->next = top;
21 newlist->prev = last; 44 newlist->prev = last;
22 45
23 top->prev = newlist; 46 top->prev = newlist;
24 last->next = newlist; 47 last->next = newlist;
68 { 91 {
69 if (!top) return NULL; 92 if (!top) return NULL;
70 return top->prev->data; 93 return top->prev->data;
71 } 94 }
72 95
73 void * 96 List *
74 _listMoveLasttoFirst(List *top) 97 _listMoveLasttoFirst(List *top)
75 { 98 {
76 if (!top) return NULL; 99 if (!top) return NULL;
77 return top->prev; 100 return top->prev;
78 } 101 }
79 102
80 void 103 void
81 _listApply(List *top, ApplyFn fn, void *arg) { 104 _listApply(List *top, ApplyFn fn, void *arg)
105 {
82 List *t = top; 106 List *t = top;
83 do { 107 do {
84 fn(t->data, arg); 108 fn(t->data, arg);
85 t = t->next; 109 t = t->next;
86 } while ( t!=top ); 110 } while ( t!=top );
87 } 111 }
88 112
89 113 /*
90 114 * Iterator's functions.
91 115 *
92 116 * iter = _listIterator(list);
93 117 * while ( (data=_listIterNext(iter)!=NULL ) {
94 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 }
133
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 }
175
176
177 /*
178 * for DEBUG
179 */
180
181 int
182 _listRingCheck(List *head)
183 {
184 List *cur = head;
185
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);
193
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