Fix bug in GListTruncate, extends templates tests
[tedtools.git] / glist.c
1 /*
2  * Copyright (c) 2006 Teodor Sigaev <teodor@sigaev.ru>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *        notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *        notice, this list of conditions and the following disclaimer in the
12  *        documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the author nor the names of any co-contributors
14  *        may be used to endorse or promote products derived from this software
15  *        without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
18  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
23  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
27  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <unistd.h>
32 #include <sys/types.h>
33
34 #include "tlog.h"
35 #include "tmalloc.h"
36
37 #include "glist.h"
38
39 static GList*
40 checkGList(GList *l) {
41         if ( l==NULL ) 
42                 l = t0malloc(sizeof(GList));
43
44         tassert( GLIST_LENGTH(l) >= 0 );
45         tassert( 
46                 ( GLIST_LENGTH(l) == 0 && GLIST_HEAD(l) == NULL && GLIST_TAIL(l) == NULL ) ||
47                 ( GLIST_LENGTH(l) > 0  && GLIST_HEAD(l) != NULL && GLIST_TAIL(l) != NULL )
48         );
49
50         return l;
51 }
52
53 static GListCell*
54 makeCell(void *ptr) {
55         GListCell       *cell = tmalloc(sizeof(GListCell));
56         cell->data = ptr;
57         return cell;
58 }
59
60 static GList*
61 insertCell(GList *l, GListCell *prev, GListCell *cell) {
62         l = checkGList(l);
63
64         if ( prev == NULL ) {
65                 /* insert into head */
66                 if ( GLIST_LENGTH(l) == 0 ) {
67                                 l->head = l->tail = cell;
68                                 cell->next = cell->prev = NULL;
69                 } else {
70                         cell->next = l->head;
71                         cell->prev = NULL;
72                         l->head->prev = cell;
73                         l->head = cell;
74                 }
75         } else if ( prev == l->tail ) {
76                 /* insert into tail */
77
78                 tassert( GLIST_LENGTH(l) > 0 );
79                 cell->next = NULL;
80                 cell->prev = l->tail;
81                 l->tail->next = cell;
82                 l->tail = cell;
83         } else {
84                 tassert( GLIST_LENGTH(l) > 0 );
85                 cell->next = prev->next;
86                 cell->next->prev = cell;
87                 cell->prev = prev;
88                 prev->next = cell;
89         }
90
91         l->length++;    
92
93         return l;
94 }
95
96 GList*
97 GListInsert(GList *l, GListCell *prev, void *ptr) {
98         return insertCell(l, prev, makeCell(ptr));
99 }
100
101 GList*
102 GListPush(GList *l, void *ptr) {
103         return insertCell(l, GLIST_TAIL(l), makeCell(ptr));
104 }
105
106 GList*
107 GListUnshift(GList *l, void *ptr) {
108         return insertCell(l, NULL, makeCell(ptr));
109 }
110
111 GList*
112 GListDelete(GList *l, GListCell *c) {
113         if (GLIST_LENGTH(l) <= 0)
114                 return l;
115
116         if ( l->head == c ) {
117                 tassert( c->prev == NULL );
118                 l->head = c->next;
119                 if ( l->head ) 
120                         l->head->prev = NULL;
121                 else
122                         l->tail = NULL;
123         } else if ( l->tail == c ) {
124                 tassert( c->next == NULL );
125                 l->tail = c->prev;
126                 if ( l->tail )
127                         l->tail->next = NULL;
128                 else
129                         l->head = NULL;
130         } else {
131                 c->prev->next = c->next;
132                 c->next->prev = c->prev;
133         }
134
135         c->prev = c->next = NULL;
136
137         l->length--;
138
139         return l;
140 }
141
142 GListCell*
143 GListPop(GList *l) {
144         GListCell       *c = NULL;
145
146         if (GLIST_LENGTH(l) > 0) {
147                 c = l->tail;
148                 GListDelete(l, c);
149         }
150
151         return c;
152 }
153
154 GListCell*
155 GListShift(GList *l) {
156         GListCell       *c = NULL;
157
158         if (GLIST_LENGTH(l) > 0) {
159                 c = l->head;
160                 GListDelete(l, c);
161         }
162
163         return c;
164 }
165
166 GListCell*
167 GListGet(GList *l, int n) {
168         GListCell       *c;
169
170         GListForeach(c, l) {
171                 if ( n-- == 0 )
172                         return c;
173         }
174
175         return NULL;
176 }
177
178 GListCell*
179 GListFind(GList *l, void *ptr) {
180         GListCell    *c;
181
182         if ( l && l->cmpFunc ) {
183                 GListForeach(c, l) {
184                         if ( l->cmpFunc(ptr, c->data) == 0 )
185                                 return c;
186                 }
187         } else {
188                 GListForeach(c, l) {
189                         if ( ptr == c->data )
190                                 return c;
191                 }
192         }
193
194         return NULL;
195 }
196
197 static GListCellComparator curComparator;
198
199 static int
200 compareData( const void *a, const void *b ) {
201         if ( *(void**)a == *(void**)b )
202                 return 0;
203         return curComparator( *(void**)a, *(void**)b );
204 }
205
206 GList*
207 GListSort(GList *l) {
208         GListCell       *c;
209         void    **arrptr, **array;
210
211         if (GLIST_LENGTH(l) <= 1)
212                 return l;
213                 
214         tassert(l->cmpFunc != NULL);
215
216         arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
217         GListForeach(c, l) 
218                 *arrptr++ = c->data;
219
220         tassert( arrptr - array == GLIST_LENGTH(l) );
221
222         curComparator = l->cmpFunc;
223         qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData); 
224
225         arrptr = array;
226         GListForeach(c, l)
227                 c->data = *arrptr++;
228
229         tfree(array);
230
231         return l;
232 }
233
234 GList*
235 GListUniq(GList *l) {
236         GListCell   *c;
237
238         GListForeach(c, l) {
239                 for(;;) {
240                         GListCell       *next = c->next;
241
242                         if ( next == NULL )
243                                 break;
244
245                         if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
246                                 GListDelete( l, next );
247                                 GListFreeCell( l, next );
248                         } else
249                                 break;
250                 }
251                 
252         }
253
254         return l;
255 }
256
257 void
258 GListFree(GList *l) {
259         GListCell   *c = GLIST_HEAD(l), *tmp;
260
261         while( c != NULL ) {
262                 tmp = c->next;
263                 GListFreeCell(l, c);
264                 c = tmp;
265         }
266
267         if (l)
268                 tfree(l);
269 }
270
271 void
272 GListFreeCell(GList *l, GListCell* c) {
273         if (l && l->freeFunc) 
274                 l->freeFunc(c->data);
275
276         tfree(c);
277 }
278
279 GList*
280 GListTruncate(GList *l, int n) {
281         while( GLIST_LENGTH(l) > n ) {
282                 GListCell       *c = l->tail;
283
284                 GListDelete(l, c);
285                 GListFreeCell(l, c);
286         }
287
288         checkGList(l);
289         return l;
290 }
291
292 GList*
293 GListCopy(GList *l) {
294         GList   *n = NULL;
295         GListCell       *c;
296
297         GListForeach(c,l) 
298                 n = GListPush(n, c->data);      
299
300         if ( n && l) {
301                 n->cmpFunc = l->cmpFunc;
302                 n->freeFunc = l->freeFunc;
303         }
304
305         return n;
306 }
307
308 GList*
309 GListConcat(GList *l1, GList *l2) {
310
311         if ( l1 == l2 )
312                 tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
313         if ( GLIST_LENGTH(l1) == 0 )
314                 return l2;
315         if ( GLIST_LENGTH(l2) == 0 ) {
316                 GListFree(l2);
317                 return l1;
318         }
319
320         l1->tail->next = l2->head;
321         l2->head->prev = l1->tail;
322         l1->tail = l2->tail;
323         l1->length += l2->length;
324
325         l2->head = l2->tail = NULL;
326         l2->length=0;
327         GListFree(l2);
328
329         return l1;
330 }
331
332 GList*
333 GListDifference(GList *l1, GList *l2) {
334         GList   *l = NULL;
335         GListCell       *c;
336
337         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
338                 tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");
339
340         if (GLIST_LENGTH(l2) == 0 )
341                 return GListCopy(l1);
342
343         GListForeach(c,l1) {
344                 if ( GListFind(l2, c->data) == NULL )
345                         l = GListPush(l, c->data);
346         }
347
348         return l;
349 }
350
351 GList*
352 GListUnion(GList *l1, GList *l2) {
353         GList   *l = GListCopy(l1);
354         GListCell       *c;
355
356         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
357                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
358
359         if (GLIST_LENGTH(l2) == 0 )
360                 return l;
361         
362         GListForeach(c,l2) {
363                 if ( GListFind(l1, c->data) == NULL )
364                         l = GListPush(l, c->data);
365         }
366
367         return l;
368 }
369
370 GList*
371 GListIntersect(GList *l1, GList *l2) {
372         GList   *l = checkGList(NULL);
373         GListCell   *c;
374
375         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
376                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
377
378         if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
379                 return l;
380
381         GListForeach(c,l1) {
382                 if ( GListFind(l2, c->data) != NULL )
383                         l = GListPush(l, c->data);
384         }
385
386         return l;
387 }
388
389
390
391