libs/queue.c

   1 /* -*-c-*- */
   2 /* This program is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License as published by
   4  * the Free Software Foundation; either version 2 of the License, or
   5  * (at your option) any later version.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program; if not, write to the Free Software
  14  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  15  */
  16
  17 /* ---------------------------- included header files ---------------------- */
  18
  19 #include "config.h"
  20
  21 #include <stdio.h>
  22
  23 #include "safemalloc.h"
  24 #include "queue.h"
  25
  26 /* ---------------------------- local definitions -------------------------- */
  27
  28 /* ---------------------------- local macros ------------------------------- */
  29
  30 /* ---------------------------- imports ------------------------------------ */
  31
  32 /* ---------------------------- included code files ------------------------ */
  33
  34 /* ---------------------------- local types -------------------------------- */
  35
  36 /* ---------------------------- forward declarations ----------------------- */
  37
  38 /* ---------------------------- local variables ---------------------------- */
  39
  40 typedef struct fqueue_record
  41 {
  42         struct fqueue_record *next;
  43         void *object;
  44         struct
  45         {
  46                 unsigned is_scheduled_for_deletion;
  47                 unsigned is_just_created;
  48         } flags;
  49 } fqueue_record;
  50
  51 /* ---------------------------- exported variables (globals) --------------- */
  52
  53 /* ---------------------------- local functions ---------------------------- */
  54
  55 /* ---------------------------- interface functions ------------------------ */
  56
  57 /* Make newly added items permanent and destroy items scheduled for deletion. */
  58 static void fqueue_cleanup_queue(
  59         fqueue *fq, destroy_fqueue_object_t destroy_func)
  60 {
  61         fqueue_record *head;
  62         fqueue_record *tail;
  63         fqueue_record *prev;
  64         fqueue_record *next;
  65         fqueue_record *rec;
  66
  67         for (head = NULL, tail = NULL, prev = NULL, rec = fq->first;
  68              rec != NULL; rec = next)
  69         {
  70                 if (rec->flags.is_scheduled_for_deletion)
  71                 {
  72                         /* destroy and skip it */
  73                         next = rec->next;
  74                         if (rec->object != NULL && destroy_func != NULL)
  75                         {
  76                                 destroy_func(rec->object);
  77                         }
  78                         if (prev != NULL)
  79                         {
  80                                 prev->next = next;
  81                         }
  82                         free(rec);
  83                 }
  84                 else
  85                 {
  86                         rec->flags.is_just_created = 0;
  87                         if (head == NULL)
  88                         {
  89                                 head = rec;
  90                         }
  91                         tail = rec;
  92                         prev = rec;
  93                         next = rec->next;
  94                 }
  95         }
  96         fq->first = head;
  97         fq->last = tail;
  98
  99         return;
 100 }
 101
 102 /* Recursively lock the queue.  While locked, objects are not deleted from the
 103  * queue but marked for later deletion.  New objects are marked as such and are
 104  * skipped by the queue functions. */
 105 static void fqueue_lock_queue(fqueue *fq)
 106 {
 107         fq->lock_level++;
 108
 109         return;
 110 }
 111
 112 /* Remove one lock level */
 113 static void fqueue_unlock_queue(
 114         fqueue *fq, destroy_fqueue_object_t destroy_func)
 115 {
 116         switch (fq->lock_level)
 117         {
 118         case 0:
 119                 /* bug */
 120                 break;
 121         case 1:
 122                 if (fq->flags.is_dirty)
 123                 {
 124                         fqueue_cleanup_queue(fq, destroy_func);
 125                 }
 126                 /* fall through */
 127         default:
 128                 fq->lock_level--;
 129                 return;
 130         }
 131
 132         return;
 133 }
 134
 135 /* Chack and possibly execute the action associated with a queue object.
 136  * Schedule the object for deletion if it was executed. */
 137 static void fqueue_operate(
 138         fqueue *fq, fqueue_record *rec,
 139         check_fqueue_object_t check_func,
 140         operate_fqueue_object_t operate_func,
 141         void *operate_args)
 142 {
 143         if (rec == NULL || rec->flags.is_scheduled_for_deletion)
 144         {
 145                 return;
 146         }
 147         if (check_func == NULL || check_func(rec->object, operate_args) == 1)
 148         {
 149                 if (operate_func != NULL)
 150                 {
 151                         operate_func(rec->object, operate_args);
 152                 }
 153                 rec->flags.is_scheduled_for_deletion = 1;
 154                 fq->flags.is_dirty = 1;
 155         }
 156
 157         return;
 158 }
 159
 160 /* ---------------------------- builtin commands --------------------------- */
 161
 162 /*
 163  * Basic queue management
 164  */
 165
 166 void fqueue_init(fqueue *fq)
 167 {
 168         memset(fq, 0, sizeof(*fq));
 169
 170         return;
 171 }
 172
 173 unsigned int fqueue_get_length(fqueue *fq)
 174 {
 175         unsigned int len;
 176         fqueue_record *t;
 177
 178         for (t = fq->first, len = 0; t != NULL; t = t->next)
 179         {
 180                 if (!t->flags.is_scheduled_for_deletion)
 181                 {
 182                         len++;
 183                 }
 184         }
 185
 186         return len;
 187 }
 188
 189 /*
 190  * Add record to queue
 191  */
 192
 193 void fqueue_add_at_front(
 194         fqueue *fq, void *object)
 195 {
 196         fqueue_record *rec;
 197
 198         rec = (fqueue_record *)safemalloc(sizeof(fqueue_record));
 199         memset(rec, 0, sizeof(*rec));
 200         rec->object = object;
 201         rec->next = fq->first;
 202         if (fq->lock_level > 0)
 203         {
 204                 rec->flags.is_just_created = 1;
 205                 fq->flags.is_dirty = 1;
 206         }
 207         fq->first = rec;
 208
 209         return;
 210 }
 211
 212 void fqueue_add_at_end(
 213         fqueue *fq, void *object)
 214 {
 215         fqueue_record *rec;
 216
 217         rec = (fqueue_record *)safemalloc(sizeof(fqueue_record));
 218         memset(rec, 0, sizeof(*rec));
 219         rec->object = object;
 220         if (fq->lock_level > 0)
 221         {
 222                 rec->flags.is_just_created = 1;
 223                 fq->flags.is_dirty = 1;
 224         }
 225         if (fq->first == NULL)
 226         {
 227                 fq->first = rec;
 228         }
 229         else
 230         {
 231                 fq->last->next = rec;
 232         }
 233         fq->last = rec;
 234         rec->next = NULL;
 235
 236         return;
 237 }
 238
 239 void fqueue_add_inside(
 240         fqueue *fq, void *object, cmp_objects_t cmp_objects, void *cmp_args)
 241 {
 242         fqueue_record *rec;
 243         fqueue_record *p;
 244         fqueue_record *t;
 245
 246         rec = (fqueue_record *)safemalloc(sizeof(fqueue_record));
 247         memset(rec, 0, sizeof(*rec));
 248         rec->object = object;
 249         if (fq->lock_level > 0)
 250         {
 251                 rec->flags.is_just_created = 1;
 252                 fq->flags.is_dirty = 1;
 253         }
 254
 255         /* search place to insert record */
 256         for (p = NULL, t = fq->first;
 257              t != NULL && cmp_objects(object, t->object, cmp_args) >= 0;
 258              p = t, t = t->next)
 259         {
 260                 /* nothing to do here */
 261         }
 262         /* insert record */
 263         if (p == NULL)
 264         {
 265                 /* insert at start */
 266                 rec->next = fq->first;
 267                 fq->first = rec;
 268         }
 269         else
 270         {
 271                 /* insert after p */
 272                 rec->next = p->next;
 273                 p->next = rec;
 274         }
 275         if (t == NULL)
 276         {
 277                 fq->last = rec;
 278         }
 279
 280         return;
 281 }
 282
 283 /*
 284  * Fetch queue objects
 285  */
 286
 287 /* Returns the object of the first queue record throuch *ret_object.  Returns
 288  * 0 if the queue is empty and 1 otherwise. */
 289 int fqueue_get_first(
 290         fqueue *fq, void **ret_object)
 291 {
 292         fqueue_record *rec;
 293
 294         for (rec = fq->first;
 295              rec != NULL && rec->flags.is_scheduled_for_deletion;
 296              rec = rec->next)
 297         {
 298                 /* nothing */
 299         }
 300         if (rec == NULL)
 301         {
 302                 return 0;
 303         }
 304         *ret_object = rec->object;
 305
 306         return 1;
 307 }
 308
 309 /*
 310  * Operate on queue objects and possibly remove them from the queue
 311  */
 312
 313 /* Runs the operate_func on the first record in the queue.  If that function
 314  * is NULL or returns 1, the record is removed from the queue.  The object of
 315  * the queue record must have been freed in operate_func. */
 316 void fqueue_remove_or_operate_from_front(
 317         fqueue *fq,
 318         check_fqueue_object_t check_func,
 319         operate_fqueue_object_t operate_func,
 320         destroy_fqueue_object_t destroy_func,
 321         void *operate_args)
 322 {
 323         fqueue_lock_queue(fq);
 324         fqueue_operate(fq, fq->first, check_func, operate_func, operate_args);
 325         fqueue_unlock_queue(fq, destroy_func);
 326
 327         return;
 328 }
 329
 330 /* Same as above but operates on last record in queue */
 331 void fqueue_remove_or_operate_from_end(
 332         fqueue *fq,
 333         check_fqueue_object_t check_func,
 334         operate_fqueue_object_t operate_func,
 335         destroy_fqueue_object_t destroy_func,
 336         void *operate_args)
 337 {
 338         fqueue_lock_queue(fq);
 339         fqueue_operate( fq, fq->last, check_func, operate_func, operate_args);
 340         fqueue_unlock_queue(fq, destroy_func);
 341
 342         return;
 343 }
 344
 345 /* Same as above but operates on all records in the queue. */
 346 void fqueue_remove_or_operate_all(
 347         fqueue *fq,
 348         check_fqueue_object_t check_func,
 349         operate_fqueue_object_t operate_func,
 350         destroy_fqueue_object_t destroy_func,
 351         void *operate_args)
 352 {
 353         fqueue_record *t;
 354
 355         if (fq->first == NULL)
 356         {
 357                 return;
 358         }
 359         fqueue_lock_queue(fq);
 360         /* search record(s) to remove */
 361         for (t = fq->first; t != NULL; t = t->next)
 362         {
 363                 if (t->flags.is_just_created ||
 364                     t->flags.is_scheduled_for_deletion)
 365                 {
 366                         /* skip */
 367                         continue;
 368                 }
 369                 fqueue_operate(fq, t, check_func, operate_func, operate_args);
 370         }
 371         fqueue_unlock_queue(fq, destroy_func);
 372
 373         return;
 374 }