Mercurial > repos > libtu-3 / changeset

--- 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 */