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_contains(ObjList *objlist, Obj *obj)
 140 {
 141     return (objlist_find_node(objlist, obj)!=NULL);
 142 }
 143
 144
 145 bool objlist_insert_last(ObjList **objlist, Obj *obj)
 146 {
 147     ObjList *node=reuse(objlist);
 148
 149     if(node==NULL)
 150         node=mknode(obj);
 151
 152     if(node==NULL)
 153         return FALSE;
 154
 155     LINK_ITEM_LAST(*objlist, node, next, prev);
 156
 157     return TRUE;
 158 }
 159
 160
 161 bool objlist_insert_first(ObjList **objlist, Obj *obj)
 162 {
 163     ObjList *node=reuse(objlist);
 164
 165     if(node==NULL)
 166         node=mknode(obj);
 167
 168     if(node==NULL)
 169         return FALSE;
 170
 171     LINK_ITEM_FIRST(*objlist, node, next, prev);
 172
 173     return TRUE;
 174 }
 175
 176
 177 bool objlist_reinsert_last(ObjList **objlist, Obj *obj)
 178 {
 179     ObjList *node;
 180
 181     optimise(objlist);
 182
 183     node=objlist_find_node(*objlist, obj);
 184
 185     if(node==NULL)
 186         return objlist_insert_last(objlist, obj);
 187
 188     UNLINK_ITEM(*objlist, node, next, prev);
 189     LINK_ITEM_LAST(*objlist, node, next, prev);
 190
 191     return TRUE;
 192 }
 193
 194
 195 bool objlist_reinsert_first(ObjList **objlist, Obj *obj)
 196 {
 197     ObjList *node;
 198
 199     optimise(objlist);
 200
 201     node=objlist_find_node(*objlist, obj);
 202
 203     if(node==NULL)
 204         return objlist_insert_first(objlist, obj);
 205
 206     UNLINK_ITEM(*objlist, node, next, prev);
 207     LINK_ITEM_FIRST(*objlist, node, next, prev);
 208
 209     return TRUE;
 210 }
 211
 212
 213 bool objlist_remove(ObjList **objlist, Obj *obj)
 214 {
 215     ObjList *node=objlist_find_node(*objlist, obj);
 216
 217     if(node!=NULL)
 218         free_node(objlist, node);
 219
 220     optimise(objlist);
 221
 222     return (node!=NULL);
 223 }
 224
 225
 226 void objlist_clear(ObjList **objlist)
 227 {
 228     while(*objlist!=NULL)
 229         free_node(objlist, *objlist);
 230 }
 231
 232
 233 ObjListIterTmp objlist_iter_tmp=NULL;
 234
 235
 236 void objlist_iter_init(ObjListIterTmp *state, ObjList *objlist)
 237 {
 238     *state=objlist;
 239 }
 240
 241
 242 Obj *objlist_iter(ObjListIterTmp *state)
 243 {
 244     Obj *obj=NULL;
 245
 246     while(obj==NULL && *state!=NULL){
 247         obj=(*state)->watch.obj;
 248         (*state)=(*state)->next;
 249     }
 250
 251     return obj;
 252 }
 253
 254
 255 void objlist_iter_rev_init(ObjListIterTmp *state, ObjList *objlist)
 256 {
 257     *state=(objlist==NULL ? NULL : objlist->prev);
 258 }
 259
 260
 261 Obj *objlist_iter_rev(ObjListIterTmp *state)
 262 {
 263     Obj *obj=NULL;
 264
 265     while(obj==NULL && *state!=NULL){
 266         obj=(*state)->watch.obj;
 267         *state=(*state)->prev;
 268         if((*state)->next==NULL)
 269             *state=NULL;
 270     }
 271
 272     return obj;
 273 }
 274
 275
 276 bool objlist_empty(ObjList *objlist)
 277 {
 278     ObjListIterTmp tmp;
 279     Obj *obj;
 280
 281     FOR_ALL_ON_OBJLIST(Obj*, obj, objlist, tmp){
 282         return FALSE;
 283     }
 284
 285     return TRUE;
 286 }
 287
 288
 289 Obj *objlist_take_first(ObjList **objlist)
 290 {
 291     ObjList *node;
 292     Obj*obj;
 293
 294     optimise(objlist);
 295
 296     node=*objlist;
 297
 298     if(node==NULL)
 299         return NULL;
 300
 301     obj=node->watch.obj;
 302
 303     assert(obj!=NULL);
 304
 305     free_node(objlist, node);
 306
 307     return obj;
 308 }
 309
 310
 311 Obj *objlist_take_last(ObjList **objlist)
 312 {
 313     ObjList *node;
 314     Obj*obj;
 315
 316     optimise(objlist);
 317
 318     node=*objlist;
 319
 320     if(node==NULL)
 321         return NULL;
 322
 323     node=node->prev;
 324
 325     obj=node->watch.obj;
 326
 327     assert(obj!=NULL);
 328
 329     free_node(objlist, node);
 330
 331     return obj;
 332 }