Sat, 26 Feb 2005 21:58:19 +0100
ObjList changes.
objlist.c | file | annotate | diff | comparison | revisions | |
objlist.h | file | annotate | diff | comparison | revisions |
--- a/objlist.c Sat Feb 26 21:38:55 2005 +0100 +++ b/objlist.c Sat Feb 26 21:58:19 2005 +0100 @@ -1,7 +1,7 @@ /* * libtu/objlist.c * - * Copyright (c) Tuomo Valkonen 1999-2004. + * Copyright (c) Tuomo Valkonen 1999-2005. * * You may distribute and modify this library under the terms of either * the Clarified Artistic License or the GNU LGPL, version 2.1 or later. @@ -14,35 +14,97 @@ #include "misc.h" -static ObjList *iter_next=NULL; +static ObjList *reuse_first(ObjList **objlist) +{ + ObjList *node=*objlist; + + if(node!=NULL && node->watch.obj==NULL){ + UNLINK_ITEM(*objlist, node, next, prev); + return node; + } + + return NULL; +} + + +static ObjList *reuse_last(ObjList **objlist) +{ + ObjList *node=*objlist; + + if(node==NULL) + return NULL; + + node=node->prev; + + if(node!=NULL && node->watch.obj==NULL){ + UNLINK_ITEM(*objlist, node, next, prev); + return node; + } + + return NULL; +} + + +static ObjList *reuse(ObjList **objlist) +{ + ObjList *first=reuse_first(objlist); + ObjList *last=reuse_first(objlist); + + if(first==NULL){ + return last; + }else{ + if(last!=NULL) + free(last); + return first; + } +} + + +static void optimise(ObjList **objlist) +{ + ObjList *first=reuse_first(objlist); + ObjList *last=reuse_first(objlist); + + if(first!=NULL) + free(first); + if(last!=NULL) + free(last); +} + + +void watch_handler(Watch *watch, Obj *obj) +{ + ObjList *node=(ObjList*)watch; + + assert(node->prev!=NULL); + + if(node->next==NULL){ + /* Last item - can't free */ + }else if(node->prev->next==NULL){ + /* First item - can't free cheaply */ + }else{ + ObjList *tmp=node->prev; + node->next->prev=node->prev; + tmp->next=node->next; + free(node); + } +} static void free_node(ObjList **objlist, ObjList *node) { + watch_reset(&(node->watch)); UNLINK_ITEM(*objlist, node, next, prev); free(node); } - -void watch_handler(Watch *watch, Obj *obj) -{ - ObjList *node=(ObjList*)watch; - ObjList **list=node->list; - - if(iter_next==node) - iter_next=node->next; - - free_node(list, node); -} - - -bool objlist_insert(ObjList **objlist, Obj *obj) +static ObjList *mknode(void *obj) { ObjList *node; if(obj==NULL) - return FALSE; + return NULL; node=ALLOC(ObjList); @@ -50,9 +112,92 @@ return FALSE; watch_init(&(node->watch)); - watch_setup(&(node->watch), obj, watch_handler); - node->list=objlist; + + if(!watch_setup(&(node->watch), obj, watch_handler)){ + free(node); + return NULL; + } + + return node; +} + + +static ObjList *objlist_find_node(ObjList *objlist, Obj *obj) +{ + ObjList *node=objlist; + + while(node!=NULL){ + if(node->watch.obj==obj) + break; + node=node->next; + } + + return node; +} + + +bool objlist_insert_last(ObjList **objlist, Obj *obj) +{ + ObjList *node=reuse(objlist); + + if(node==NULL) + node=mknode(obj); + + if(node==NULL) + return FALSE; + + LINK_ITEM_LAST(*objlist, node, next, prev); + return TRUE; +} + + +bool objlist_insert_first(ObjList **objlist, Obj *obj) +{ + ObjList *node=reuse(objlist); + + if(node==NULL) + node=mknode(obj); + + if(node==NULL) + return FALSE; + + LINK_ITEM_FIRST(*objlist, node, next, prev); + + return TRUE; +} + + +bool objlist_reinsert_last(ObjList **objlist, Obj *obj) +{ + ObjList *node; + + optimise(objlist); + + node=objlist_find_node(*objlist, obj); + + if(node==NULL) + return FALSE; + + UNLINK_ITEM(*objlist, node, next, prev); + LINK_ITEM_LAST(*objlist, node, next, prev); + + return TRUE; +} + + +bool objlist_reinsert_first(ObjList **objlist, Obj *obj) +{ + ObjList *node; + + optimise(objlist); + + node=objlist_find_node(*objlist, obj); + + if(node==NULL) + return FALSE; + + UNLINK_ITEM(*objlist, node, next, prev); LINK_ITEM_FIRST(*objlist, node, next, prev); return TRUE; @@ -61,52 +206,73 @@ void objlist_remove(ObjList **objlist, Obj *obj) { - ObjList *node=*objlist; + ObjList *node=objlist_find_node(*objlist, obj); - while(node!=NULL){ - if(node->watch.obj==obj){ - watch_reset(&(node->watch)); - free_node(objlist, node); - return; - } - node=node->next; - } + if(node!=NULL) + free_node(objlist, node); + + optimise(objlist); } void objlist_clear(ObjList **objlist) { - while(*objlist!=NULL){ - watch_reset(&((*objlist)->watch)); + while(*objlist!=NULL) free_node(objlist, *objlist); +} + + +ObjListIterTmp objlist_iter_tmp=NULL; + + +void objlist_iter_init(ObjListIterTmp *state, ObjList *objlist) +{ + *state=objlist; +} + + +Obj *objlist_iter(ObjListIterTmp *state) +{ + Obj *obj=NULL; + + while(obj==NULL && *state!=NULL){ + obj=(*state)->watch.obj; + (*state)=(*state)->next; } + + return obj; } -/* Warning: not thread-safe */ - - -Obj *objlist_init_iter(ObjList *objlist) +void objlist_iter_rev_init(ObjListIterTmp *state, ObjList *objlist) { - if(objlist==NULL){ - iter_next=NULL; - return NULL; - } - - iter_next=objlist->next; - return objlist->watch.obj; + *state=(objlist==NULL ? NULL : objlist->prev); } -Obj *objlist_iter() +Obj *objlist_iter_rev(ObjListIterTmp *state) { - ObjList *ret; + Obj *obj=NULL; + + while(obj==NULL && *state!=NULL){ + obj=(*state)->watch.obj; + *state=(*state)->prev; + if((*state)->next==NULL) + *state=NULL; + } - if(iter_next==NULL) - return NULL; + return obj; +} + + +bool objlist_empty(ObjList *objlist) +{ + ObjListIterTmp tmp; + Obj *obj; - ret=iter_next; - iter_next=iter_next->next; + FOR_ALL_ON_OBJLIST(Obj*, obj, objlist, tmp){ + return FALSE; + } - return ret->watch.obj; + return TRUE; }
--- a/objlist.h Sat Feb 26 21:38:55 2005 +0100 +++ b/objlist.h Sat Feb 26 21:58:19 2005 +0100 @@ -1,7 +1,7 @@ /* * libtu/objlist.h * - * Copyright (c) Tuomo Valkonen 1999-2004. + * Copyright (c) Tuomo Valkonen 1999-2005. * * You may distribute and modify this library under the terms of either * the Clarified Artistic License or the GNU LGPL, version 2.1 or later. @@ -24,16 +24,39 @@ }; -#define FOR_ALL_ON_OBJLIST(TYPE, VAR, LIST) \ - for((VAR)=(TYPE)objlist_init_iter(LIST); \ - (VAR)!=NULL; \ - (VAR)=(TYPE)objlist_iter()) +typedef ObjList* ObjListIterTmp; + +#define OBJLIST_FIRST(TYPE, LL) ((LL)==NULL ? NULL : (TYPE)(LL)->watch.obj) +#define OBJLIST_LAST(TYPE, LL) ((LL)==NULL ? NULL : (TYPE)(LL)->prev->watch.obj) +#define OBJLIST_EMPTY(LIST) objlist_empty(LIST) +#define FOR_ALL_ON_OBJLIST(TYPE, VAR, LL, TMP) \ + for(objlist_iter_init(&(TMP), LL), \ + VAR=(TYPE)objlist_iter(&(TMP)); \ + VAR!=NULL; \ + VAR=(TYPE)objlist_iter(&(TMP))) -bool objlist_insert(ObjList **objlist, Obj *obj); -void objlist_remove(ObjList **objlist, Obj *obj); -void objlist_clear(ObjList **objlist); -Obj *objlist_init_iter(ObjList *objlist); -Obj *objlist_iter(); +#define FOR_ALL_ON_OBJLIST_REV(TYPE, VAR, LL, TMP) \ + for(objlist_iter_rev_init(&(TMP), LL), \ + VAR=(TYPE)objlist_iter_rev(&(TMP)); \ + VAR!=NULL; \ + VAR=(TYPE)objlist_iter_rev(&(TMP))) + +#define FOR_ALL_ON_OBJLIST_UNSAFE(TYPE, VAR, LL) \ + FOR_ALL_ON_OBJLIST(TYPE, VAR, LL, objlist_iter_tmp) + +extern ObjListIterTmp objlist_iter_tmp; + +extern bool objlist_insert_last(ObjList **objlist, Obj *obj); +extern bool objlist_insert_first(ObjList **objlist, Obj *obj); +extern bool objlist_reinsert_last(ObjList **objlist, Obj *obj); +extern bool objlist_reinsert_first(ObjList **objlist, Obj *obj); +extern void objlist_remove(ObjList **objlist, Obj *obj); +extern void objlist_clear(ObjList **objlist); +extern void objlist_iter_init(ObjListIterTmp *state, ObjList *objlist); +extern Obj *objlist_iter(ObjListIterTmp *state); +extern void objlist_iter_rev_init(ObjListIterTmp *state, ObjList *objlist); +extern Obj *objlist_iter_rev(ObjListIterTmp *state); +extern bool objlist_empty(ObjList *objlist); #endif /* LIBTU_OBJLIST_H */