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 GListPushCell(GList *l, GListCell* c) {
108 return insertCell(l, GLIST_TAIL(l), c);
112 GListUnshift(GList *l, void *ptr) {
113 return insertCell(l, NULL, makeCell(ptr));
117 GListUnshiftCell(GList *l, GListCell* c) {
118 return insertCell(l, NULL, c);
122 GListDelete(GList *l, GListCell *c) {
123 if (GLIST_LENGTH(l) <= 0)
126 if ( l->head == c ) {
127 tassert( c->prev == NULL );
130 l->head->prev = NULL;
133 } else if ( l->tail == c ) {
134 tassert( c->next == NULL );
137 l->tail->next = NULL;
141 c->prev->next = c->next;
142 c->next->prev = c->prev;
145 c->prev = c->next = NULL;
156 if (GLIST_LENGTH(l) > 0) {
165 GListShift(GList *l) {
168 if (GLIST_LENGTH(l) > 0) {
177 GListGet(GList *l, int n) {
189 GListFind(GList *l, void *ptr) {
192 if ( l && l->cmpFunc ) {
194 if ( l->cmpFunc(ptr, c->data) == 0 )
199 if ( ptr == c->data )
207 static GListCellComparator curComparator;
210 compareData( const void *a, const void *b ) {
211 if ( *(void**)a == *(void**)b )
213 return curComparator( *(void**)a, *(void**)b );
217 GListSort(GList *l) {
219 void **arrptr, **array;
221 if (GLIST_LENGTH(l) <= 1)
224 tassert(l->cmpFunc != NULL);
226 arrptr = array = (void**)tmalloc(sizeof(void*)*GLIST_LENGTH(l));;
230 tassert( arrptr - array == GLIST_LENGTH(l) );
232 curComparator = l->cmpFunc;
233 qsort(array, GLIST_LENGTH(l), sizeof(void*), compareData);
245 GListUniq(GList *l) {
250 GListCell *next = c->next;
255 if ( c->data == next->data || ( l->cmpFunc && l->cmpFunc(c->data, next->data)==0 ) ) {
256 GListDelete( l, next );
257 GListFreeCell( l, next );
268 GListFree(GList *l) {
269 GListCell *c = GLIST_HEAD(l), *tmp;
282 GListFreeCell(GList *l, GListCell* c) {
283 if (l && l->freeFunc)
284 l->freeFunc(c->data);
290 GListTruncate(GList *l, int n) {
291 while( GLIST_LENGTH(l) > n ) {
292 GListCell *c = l->tail;
302 GListCopy(GList *l) {
307 n = GListPush(n, c->data);
310 n->cmpFunc = l->cmpFunc;
311 n->freeFunc = l->freeFunc;
318 GListConcat(GList *l1, GList *l2) {
321 tlog(TL_CRIT|TL_EXIT,"Can't concat list itself");
322 if ( GLIST_LENGTH(l1) == 0 )
324 if ( GLIST_LENGTH(l2) == 0 ) {
329 l1->tail->next = l2->head;
330 l2->head->prev = l1->tail;
332 l1->length += l2->length;
334 l2->head = l2->tail = NULL;
342 GListDifference(GList *l1, GList *l2) {
346 if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
347 tlog(TL_CRIT|TL_EXIT,"GListDifference: comparators aren't the same");
349 if (GLIST_LENGTH(l2) == 0 )
350 return GListCopy(l1);
353 if ( GListFind(l2, c->data) == NULL )
354 l = GListPush(l, c->data);
361 GListUnion(GList *l1, GList *l2) {
362 GList *l = GListCopy(l1);
365 if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
366 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
368 if (GLIST_LENGTH(l2) == 0 )
372 if ( GListFind(l1, c->data) == NULL )
373 l = GListPush(l, c->data);
380 GListIntersect(GList *l1, GList *l2) {
381 GList *l = checkGList(NULL);
384 if ( l1 && l2 && l1->cmpFunc != l2->cmpFunc )
385 tlog(TL_CRIT|TL_EXIT,"GListUnion: comparators aren't the same");
387 if ( GLIST_LENGTH(l1) == 0 || GLIST_LENGTH(l2) == 0 )
391 if ( GListFind(l2, c->data) != NULL )
392 l = GListPush(l, c->data);