2 * Copyright (c) 2006 Teodor Sigaev <teodor@sigaev.ru>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
32 #include <sys/types.h>
40 checkGList(GList *l) {
42 l = t0malloc(sizeof(GList));
44 tassert( GLIST_LENGTH(l) >= 0 );
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 )
55 GListCell *cell = tmalloc(sizeof(GListCell));
61 insertCell(GList *l, GListCell *prev, GListCell *cell) {
65 /* insert into head */
66 if ( GLIST_LENGTH(l) == 0 ) {
67 l->head = l->tail = cell;
68 cell->next = cell->prev = NULL;
75 } else if ( prev == l->tail ) {
76 /* insert into tail */
78 tassert( GLIST_LENGTH(l) > 0 );
84 tassert( GLIST_LENGTH(l) > 0 );
85 cell->next = prev->next;
86 cell->next->prev = cell;
97 GListInsert(GList *l, GListCell *prev, void *ptr) {
98 return insertCell(l, prev, makeCell(ptr));
102 GListPush(GList *l, void *ptr) {
103 return insertCell(l, GLIST_TAIL(l), makeCell(ptr));
107 GListUnshift(GList *l, void *ptr) {
108 return insertCell(l, NULL, makeCell(ptr));
112 GListDelete(GList *l, GListCell *c) {
113 if (GLIST_LENGTH(l) <= 0)
116 if ( l->head == c ) {
117 tassert( c->prev == NULL );
120 l->head->prev = NULL;
121 } else if ( l->tail == c ) {
122 tassert( c->next == NULL );
125 l->tail->next = NULL;
127 c->prev->next = c->next;
128 c->next->prev = c->prev;
131 c->prev = c->next = NULL;
142 if (GLIST_LENGTH(l) > 0) {
151 GListShift(GList *l) {
154 if (GLIST_LENGTH(l) > 0) {
163 GListGet(GList *l, int n) {
175 GListFind(GList *l, void *ptr) {
178 if ( l && l->cmpFunc ) {
180 if ( l->cmpFunc(ptr, c->data) == 0 )
185 if ( ptr == c->data )
193 static GListCellComparator curComparator;
196 compareData( const void *a, const void *b ) {
197 if ( *(void**)a == *(void**)b )
199 return curComparator( *(void**)a, *(void**)b );
203 GListSort(GList *l) {
205 void **arrptr, **array;
207 if (GLIST_LENGTH(l) <= 1)
210 tassert(l->cmpFunc != NULL);
212 arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
216 tassert( arrptr - array == GLIST_LENGTH(l) );
218 curComparator = l->cmpFunc;
219 qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData);
231 GListUniq(GList *l) {
236 GListCell *next = c->next;
241 if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
242 GListDelete( l, next );
243 GListFreeCell( l, next );
254 GListFree(GList *l) {
255 GListCell *c = GLIST_HEAD(l), *tmp;
268 GListFreeCell(GList *l, GListCell* c) {
269 if (l && l->freeFunc)
270 l->freeFunc(c->data);
276 GListTruncate(GList *l, int n) {
277 while( GLIST_LENGTH(l) > n ) {
278 GListCell *c = l->tail;
288 GListCopy(GList *l) {
293 n = GListPush(n, c->data);
296 n->cmpFunc = l->cmpFunc;
297 n->freeFunc = l->freeFunc;
304 GListConcat(GList *l1, GList *l2) {
307 tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
308 if ( GLIST_LENGTH(l1) == 0 )
310 if ( GLIST_LENGTH(l2) == 0 ) {
315 l1->tail->next = l2->head;
316 l2->head->prev = l1->tail;
318 l1->length += l2->length;
320 l2->head = l2->tail = NULL;
328 GListDifference(GList *l1, GList *l2) {
332 if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
333 tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");
335 if (GLIST_LENGTH(l2) == 0 )
336 return GListCopy(l1);
339 if ( GListFind(l2, c->data) == NULL )
340 l = GListPush(l, c->data);
347 GListUnion(GList *l1, GList *l2) {
348 GList *l = GListCopy(l1);
351 if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
352 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
354 if (GLIST_LENGTH(l2) == 0 )
358 if ( GListFind(l1, c->data) == NULL )
359 l = GListPush(l, c->data);
366 GListIntersect(GList *l1, GList *l2) {
367 GList *l = checkGList(NULL);
370 if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
371 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
373 if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
377 if ( GListFind(l2, c->data) != NULL )
378 l = GListPush(l, c->data);