GList - double linked abstract list implementation
[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 if ( l->tail == c ) {
122                 tassert( c->next == NULL );
123                 l->tail = c->prev;
124                 if ( l->tail )
125                         l->tail->next = NULL;
126         } else {
127                 c->prev->next = c->next;
128                 c->next->prev = c->prev;
129         }
130
131         c->prev = c->next = NULL;
132
133         l->length--;
134
135         return l;
136 }
137
138 GListCell*
139 GListPop(GList *l) {
140         GListCell       *c = NULL;
141
142         if (GLIST_LENGTH(l) > 0) {
143                 c = l->tail;
144                 GListDelete(l, c);
145         }
146
147         return c;
148 }
149
150 GListCell*
151 GListShift(GList *l) {
152         GListCell       *c = NULL;
153
154         if (GLIST_LENGTH(l) > 0) {
155                 c = l->head;
156                 GListDelete(l, c);
157         }
158
159         return c;
160 }
161
162 GListCell*
163 GListGet(GList *l, int n) {
164         GListCell       *c;
165
166         GListForeach(c, l) {
167                 if ( n-- == 0 )
168                         return c;
169         }
170
171         return NULL;
172 }
173
174 GListCell*
175 GListFind(GList *l, void *ptr) {
176         GListCell    *c;
177
178         if ( l && l->cmpFunc ) {
179                 GListForeach(c, l) {
180                         if ( l->cmpFunc(ptr, c->data) == 0 )
181                                 return c;
182                 }
183         } else {
184                 GListForeach(c, l) {
185                         if ( ptr == c->data )
186                                 return c;
187                 }
188         }
189
190         return NULL;
191 }
192
193 static GListCellComparator curComparator;
194
195 static int
196 compareData( const void *a, const void *b ) {
197         if ( *(void**)a == *(void**)b )
198                 return 0;
199         return curComparator( *(void**)a, *(void**)b );
200 }
201
202 GList*
203 GListSort(GList *l) {
204         GListCell       *c;
205         void    **arrptr, **array;
206
207         if (GLIST_LENGTH(l) <= 1)
208                 return l;
209                 
210         tassert(l->cmpFunc != NULL);
211
212         arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
213         GListForeach(c, l) 
214                 *arrptr++ = c->data;
215
216         tassert( arrptr - array == GLIST_LENGTH(l) );
217
218         curComparator = l->cmpFunc;
219         qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData); 
220
221         arrptr = array;
222         GListForeach(c, l)
223                 c->data = *arrptr++;
224
225         tfree(array);
226
227         return l;
228 }
229
230 GList*
231 GListUniq(GList *l) {
232         GListCell   *c;
233
234         GListForeach(c, l) {
235                 for(;;) {
236                         GListCell       *next = c->next;
237
238                         if ( next == NULL )
239                                 break;
240
241                         if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
242                                 GListDelete( l, next );
243                                 GListFreeCell( l, next );
244                         } else
245                                 break;
246                 }
247                 
248         }
249
250         return l;
251 }
252
253 void
254 GListFree(GList *l) {
255         GListCell   *c = GLIST_HEAD(l), *tmp;
256
257         while( c != NULL ) {
258                 tmp = c->next;
259                 GListFreeCell(l, c);
260                 c = tmp;
261         }
262
263         if (l)
264                 tfree(l);
265 }
266
267 void
268 GListFreeCell(GList *l, GListCell* c) {
269         if (l && l->freeFunc) 
270                 l->freeFunc(c->data);
271
272         tfree(c);
273 }
274
275 GList*
276 GListTruncate(GList *l, int n) {
277         while( GLIST_LENGTH(l) > n ) {
278                 GListCell       *c = l->tail;
279
280                 GListDelete(l, c);
281                 GListFreeCell(l, c);
282         }
283
284         return l;
285 }
286
287 GList*
288 GListCopy(GList *l) {
289         GList   *n = NULL;
290         GListCell       *c;
291
292         GListForeach(c,l) 
293                 n = GListPush(n, c->data);      
294
295         if ( n && l) {
296                 n->cmpFunc = l->cmpFunc;
297                 n->freeFunc = l->freeFunc;
298         }
299
300         return n;
301 }
302
303 GList*
304 GListConcat(GList *l1, GList *l2) {
305
306         if ( l1 == l2 )
307                 tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
308         if ( GLIST_LENGTH(l1) == 0 )
309                 return l2;
310         if ( GLIST_LENGTH(l2) == 0 ) {
311                 GListFree(l2);
312                 return l1;
313         }
314
315         l1->tail->next = l2->head;
316         l2->head->prev = l1->tail;
317         l1->tail = l2->tail;
318         l1->length += l2->length;
319
320         l2->head = l2->tail = NULL;
321         l2->length=0;
322         GListFree(l2);
323
324         return l1;
325 }
326
327 GList*
328 GListDifference(GList *l1, GList *l2) {
329         GList   *l = NULL;
330         GListCell       *c;
331
332         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
333                 tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");
334
335         if (GLIST_LENGTH(l2) == 0 )
336                 return GListCopy(l1);
337
338         GListForeach(c,l1) {
339                 if ( GListFind(l2, c->data) == NULL )
340                         l = GListPush(l, c->data);
341         }
342
343         return l;
344 }
345
346 GList*
347 GListUnion(GList *l1, GList *l2) {
348         GList   *l = GListCopy(l1);
349         GListCell       *c;
350
351         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
352                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
353
354         if (GLIST_LENGTH(l2) == 0 )
355                 return l;
356         
357         GListForeach(c,l2) {
358                 if ( GListFind(l1, c->data) == NULL )
359                         l = GListPush(l, c->data);
360         }
361
362         return l;
363 }
364
365 GList*
366 GListIntersect(GList *l1, GList *l2) {
367         GList   *l = checkGList(NULL);
368         GListCell   *c;
369
370         if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
371                 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
372
373         if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
374                 return l;
375
376         GListForeach(c,l1) {
377                 if ( GListFind(l2, c->data) != NULL )
378                         l = GListPush(l, c->data);
379         }
380
381         return l;
382 }
383
384
385
386