libtu/objlist.c

   1 /*
   2  * libtu/objlist.c
   3  *
   4  * Copyright (c) Tuomo Valkonen 1999-2005.
   5  *
   6  * You may distribute and modify this library under the terms of either
   7  * the Clarified Artistic License or the GNU LGPL, version 2.1 or later.
   8  */
   9
  10 #include "obj.h"
  11 #include "types.h"
  12 #include "objlist.h"
  13 #include "dlist.h"
  14 #include "misc.h"
  15
  16
  17 static ObjList *reuse_first(ObjList **objlist)
  18 {
  19     ObjList *node=*objlist;
  20
  21     if(node!=NULL && node->watch.obj==NULL){
  22         UNLINK_ITEM(*objlist, node, next, prev);
  23         return node;
  24     }
  25
  26     return NULL;
  27 }
  28
  29
  30 static ObjList *reuse_last(ObjList **objlist)
  31 {
  32     ObjList *node=*objlist;
  33
  34     if(node==NULL)
  35         return NULL;
  36
  37     node=node->prev;
  38
  39     if(node!=NULL && node->watch.obj==NULL){
  40         UNLINK_ITEM(*objlist, node, next, prev);
  41         return node;
  42     }
  43
  44     return NULL;
  45 }
  46
  47
  48 static ObjList *reuse(ObjList **objlist)
  49 {
  50     ObjList *first=reuse_first(objlist);
  51     ObjList *last=reuse_first(objlist);
  52
  53     if(first==NULL){
  54         return last;
  55     }else{
  56         if(last!=NULL)
  57             free(last);
  58         return first;
  59     }
  60 }
  61
  62
  63 static void optimise(ObjList **objlist)
  64 {
  65     ObjList *first=reuse_first(objlist);
  66     ObjList *last=reuse_first(objlist);
  67
  68     if(first!=NULL)
  69         free(first);
  70     if(last!=NULL)
  71         free(last);
  72 }
  73
  74
  75 void watch_handler(Watch *watch, Obj *obj)
  76 {
  77     ObjList *node=(ObjList*)watch;
  78
  79     assert(node->prev!=NULL);
  80
  81     if(node->next==NULL){
  82         /* Last item - can't free */
  83     }else if(node->prev->next==NULL){
  84         /* First item - can't free cheaply */
  85     }else{
  86         ObjList *tmp=node->prev;
  87         node->next->prev=node->prev;
  88         tmp->next=node->next;
  89         free(node);
  90     }
  91 }
  92
  93
  94 static void free_node(ObjList **objlist, ObjList *node)
  95 {
  96     watch_reset(&(node->watch));
  97     UNLINK_ITEM(*objlist, node, next, prev);
  98     free(node);
  99 }
 100
 101
 102 static ObjList *mknode(void *obj)
 103 {
 104     ObjList *node;
 105
 106     if(obj==NULL)
 107         return NULL;
 108
 109     node=ALLOC(ObjList);
 110
 111     if(node==NULL)
 112         return FALSE;
 113
 114     watch_init(&(node->watch));
 115
 116     if(!watch_setup(&(node->watch), obj, watch_handler)){
 117         free(node);
 118         return NULL;
 119     }
 120
 121     return node;
 122 }
 123
 124
 125 static ObjList *objlist_find_node(ObjList *objlist, Obj *obj)
 126 {
 127     ObjList *node=objlist;
 128
 129     while(node!=NULL){
 130         if(node->watch.obj==obj)
 131             break;
 132         node=node->next;
 133     }
 134
 135     return node;
 136 }
 137
 138
 139 bool objlist_insert_last(ObjList **objlist, Obj *obj)
 140 {
 141     ObjList *node=reuse(objlist);
 142
 143     if(node==NULL)
 144         node=mknode(obj);
 145
 146     if(node==NULL)
 147         return FALSE;
 148
 149     LINK_ITEM_LAST(*objlist, node, next, prev);
 150
 151     return TRUE;
 152 }
 153
 154
 155 bool objlist_insert_first(ObjList **objlist, Obj *obj)
 156 {
 157     ObjList *node=reuse(objlist);
 158
 159     if(node==NULL)
 160         node=mknode(obj);
 161
 162     if(node==NULL)
 163         return FALSE;
 164
 165     LINK_ITEM_FIRST(*objlist, node, next, prev);
 166
 167     return TRUE;
 168 }
 169
 170
 171 bool objlist_reinsert_last(ObjList **objlist, Obj *obj)
 172 {
 173     ObjList *node;
 174
 175     optimise(objlist);
 176
 177     node=objlist_find_node(*objlist, obj);
 178
 179     if(node==NULL)
 180         return FALSE;
 181
 182     UNLINK_ITEM(*objlist, node, next, prev);
 183     LINK_ITEM_LAST(*objlist, node, next, prev);
 184
 185     return TRUE;
 186 }
 187
 188
 189 bool objlist_reinsert_first(ObjList **objlist, Obj *obj)
 190 {
 191     ObjList *node;
 192
 193     optimise(objlist);
 194
 195     node=objlist_find_node(*objlist, obj);
 196
 197     if(node==NULL)
 198         return FALSE;
 199
 200     UNLINK_ITEM(*objlist, node, next, prev);
 201     LINK_ITEM_FIRST(*objlist, node, next, prev);
 202
 203     return TRUE;
 204 }
 205
 206
 207 bool objlist_remove(ObjList **objlist, Obj *obj)
 208 {
 209     ObjList *node=objlist_find_node(*objlist, obj);
 210
 211     if(node!=NULL)
 212         free_node(objlist, node);
 213
 214     optimise(objlist);
 215
 216     return (node!=NULL);
 217 }
 218
 219
 220 void objlist_clear(ObjList **objlist)
 221 {
 222     while(*objlist!=NULL)
 223         free_node(objlist, *objlist);
 224 }
 225
 226
 227 ObjListIterTmp objlist_iter_tmp=NULL;
 228
 229
 230 void objlist_iter_init(ObjListIterTmp *state, ObjList *objlist)
 231 {
 232     *state=objlist;
 233 }
 234
 235
 236 Obj *objlist_iter(ObjListIterTmp *state)
 237 {
 238     Obj *obj=NULL;
 239
 240     while(obj==NULL && *state!=NULL){
 241         obj=(*state)->watch.obj;
 242         (*state)=(*state)->next;
 243     }
 244
 245     return obj;
 246 }
 247
 248
 249 void objlist_iter_rev_init(ObjListIterTmp *state, ObjList *objlist)
 250 {
 251     *state=(objlist==NULL ? NULL : objlist->prev);
 252 }
 253
 254
 255 Obj *objlist_iter_rev(ObjListIterTmp *state)
 256 {
 257     Obj *obj=NULL;
 258
 259     while(obj==NULL && *state!=NULL){
 260         obj=(*state)->watch.obj;
 261         *state=(*state)->prev;
 262         if((*state)->next==NULL)
 263             *state=NULL;
 264     }
 265
 266     return obj;
 267 }
 268
 269
 270 bool objlist_empty(ObjList *objlist)
 271 {
 272     ObjListIterTmp tmp;
 273     Obj *obj;
 274
 275     FOR_ALL_ON_OBJLIST(Obj*, obj, objlist, tmp){
 276         return FALSE;
 277     }
 278
 279     return TRUE;
 280 }
 281
 282
 283 Obj *objlist_take_first(ObjList **objlist)
 284 {
 285     ObjList *node;
 286     Obj*obj;
 287
 288     optimise(objlist);
 289
 290     node=*objlist;
 291
 292     if(node==NULL)
 293         return NULL;
 294
 295     obj=node->watch.obj;
 296
 297     assert(obj!=NULL);
 298
 299     free_node(objlist, node);
 300
 301     return obj;
 302 }
 303
 304
 305 Obj *objlist_take_last(ObjList **objlist)
 306 {
 307     ObjList *node;
 308     Obj*obj;
 309
 310     optimise(objlist);
 311
 312     node=*objlist;
 313
 314     if(node==NULL)
 315         return NULL;
 316
 317     node=node->prev;
 318
 319     obj=node->watch.obj;
 320
 321     assert(obj!=NULL);
 322
 323     free_node(objlist, node);
 324
 325     return obj;
 326 }