granicus.if.org Git - fcron/blob - fifo_list.c

   1 /*
   2  * FCRON - periodic command scheduler
   3  *
   4  *  Copyright 2000-2014 Thibault Godouet <fcron@free.fr>
   5  *
   6  *  This program is free software; you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation; either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program; if not, write to the Free Software
  18  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  *  The GNU General Public License can also be found in the file
  21  *  `LICENSE' that comes with the fcron source distribution.
  22  */
  23
  24
  25 /*
  26  * 'First in first out' list of generic items
  27  */
  28
  29 #include "global.h"
  30 #include "fcron.h"
  31 #include "fifo_list.h"
  32
  33 /* private functions: */
  34 int fifo_list_resize_array(fifo_list_t * l);
  35 #define Sizeof_fifo_list(list) ((list)->entry_size * (list)->array_size)
  36 fifo_list_entry_t *fifo_list_last(fifo_list_t * l);
  37
  38 fifo_list_t *
  39 fifo_list_init(size_t entry_size, int init_size, int grow_size)
  40 /* Create a new fifo list
  41  * Returns the newly created unordered list
  42  * Enough memory to hold init_size entries will initially be allocated,
  43  * and it will grow by grow_size entries when more space is needed.
  44  * Dies on error. */
  45 {
  46     fifo_list_t *l = NULL;
  47
  48     /* sanity check */
  49     if (entry_size < 1 || init_size < 1 || grow_size < 1)
  50         die("Invalid arguments for fifo_list_init(): entry_size=%d, init_size=%d, " "grow_size=%d", entry_size, init_size, grow_size);
  51
  52     /* Allocate the list structure: */
  53     l = alloc_safe(sizeof(struct fifo_list_t), "new fifo_list_t");
  54
  55     /* Initialize the structure and allocate the array: */
  56     l->max_entries = l->num_entries = 0;
  57     l->array_size = init_size;
  58     l->entry_size = entry_size;
  59     l->grow_size = grow_size;
  60     l->first_entry = l->cur_entry = NULL;
  61     l->entries_array =
  62         alloc_safe(init_size * entry_size, "new fifo_list_t array");
  63
  64     return l;
  65 }
  66
  67 fifo_list_entry_t *
  68 fifo_list_last(fifo_list_t * l)
  69 /* Returns the pointer of the last entry in the list, or NULL if l is empty */
  70 {
  71     fifo_list_entry *e = NULL;
  72
  73     if (l->num_entries <= 0)
  74         return NULL;
  75
  76     e = (fifo_list_entry_t *)
  77         ((char *)l->entries_array + l->entry_size * (l->num_entries - 1));
  78     if (e >=
  79         (fifo_list_entry_t *) ((char *)l->entries_array + Sizeof_fifo_list(l)))
  80         e -= Sizeof_fifo_list(l);
  81 }
  82
  83 int
  84 fifo_list_resize_array(fifo_list_t * l)
  85 /* Resize l's entries_array up to l->max_entries
  86  * Returns OK on success, ERR if the array is already at maximum size */
  87 {
  88     fifo_list_entry_t *e = NULL;
  89     int offset = 0;
  90     int old_size = l->array_size;
  91
  92     /* sanity check */
  93     if (l == NULL)
  94         die("Invalid argument for fifo_list_resize_array(): list=%d", l);
  95     if (l->max_entries > 0 && l->array_size >= l->max_entries) {
  96         debug
  97             ("Resizing fifo_list_t failed because it is already at max size (size: %d)",
  98              l->array_size);
  99         return ERR;
 100     }
 101
 102     if (l->cur_entry != NULL)
 103         /* Compute cur_entry's offset so as we can set cur_entry to the right place
 104          * after we have allocated a new chunk of memory for the entries_array */
 105         offset = (char *)l->cur_entry - (char *)l->entries_array;
 106
 107     l->array_size = (l->array_size + l->grow_size);
 108     if (l->max_entries > 0 && l->array_size > l->max_entries)
 109         l->array_size = l->max_entries;
 110
 111     debug("Resizing fifo_list_t (old size: %d, new size: %d)...", old_size,
 112           l->array_size);
 113
 114     e = alloc_safe(l->array_size * l->entry_size, "larger fifo_list_t array");
 115     memcpy(e, l->entries_array, (l->entry_size * old_size));
 116     Free_safe(l->entries_array);
 117     l->entries_array = e;
 118
 119     if (l->cur_entry != NULL)
 120         l->cur_entry =
 121             (fifo_list_entry_t *) ((char *)l->entries_array + offset);
 122
 123     return OK;
 124 }
 125
 126
 127 fifo_list_entry_t *
 128 fifo_list_add(fifo_list_t * l, fifo_list_entry_t * e)
 129 /* Add one entry to the list
 130  * Returns a pointer to the added element, or NULL if list is already at max size */
 131 {
 132     fifo_list_entry_t *new = NULL;
 133
 134     /* sanity check */
 135     if (l == NULL || e == NULL)
 136         die("Invalid arguments for fifo_list_add(): list=%d, entry=%d", l, e);
 137
 138     /* Check there is some space left, or resize the array */
 139     if (l->num_entries >= l->array_size) {
 140         /* no more space: attempt to grow (the following function dies on error: */
 141         if (fifo_list_resize_array(l) != OK)
 142             return NULL;
 143     }
 144
 145     l->num_entries++;
 146     new = fifo_list_last(l);
 147     memcpy(new, e, l->entry_size);
 148
 149     return new;
 150 }
 151
 152 fifo_list_entry_t *
 153 fifo_list_first(fifo_list_t * l)
 154 /* Return the first entry of the list (then fifo_list_next() can be used) */
 155 {
 156     /* sanity check */
 157     if (l == NULL)
 158         die("Invalid argument for fifo_list_first(): list=%d", l);
 159     if (l->cur_entry != NULL)
 160         die("fifo_list_first() called but there is already an iteration");
 161
 162     if (l->num_entries > 0) {
 163         l->cur_entry = l->entries_array;
 164     }
 165
 166     return l->cur_entry;
 167 }
 168
 169 fifo_list_entry_t *
 170 fifo_list_next(fifo_list_t * l)
 171 /* Return the entry after e */
 172 {
 173     /* // WHAT IF I CALL _ADD() (+RESIZE?) OR _REMOVE() BETWEEN TWO _NEXT CALLS? */
 174
 175     /* sanity checks */
 176     if (l == NULL)
 177         die("Invalid arguments for fifo_list_next(): list=%d", l);
 178     if (l->cur_entry == NULL)
 179         die("fifo_list_next() called outside an iteration: l->cur_entry=%d",
 180             l->cur_entry);
 181
 182     if (l->cur_removed > 0) {
 183         l->cur_removed = 0;
 184         /* the current entry has just been removed and replaced by another one:
 185          * we can return the same pointer again.
 186          * However if the removed entry was the last one then we reached the end
 187          * of the list */
 188         if (l->cur_entry > fifo_list_last(l))
 189             l->cur_entry = NULL;
 190     }
 191     else {
 192         /* cur_entry *not* removed (standard behavior) */
 193
 194         if (l->cur_entry < fifo_list_last(l))
 195             l->cur_entry =
 196                 (fifo_list_entry_t *) ((char *)l->cur_entry + l->entry_size);
 197         else
 198             /* reached the end of the list */
 199             l->cur_entry = NULL;
 200     }
 201
 202     return l->cur_entry;
 203 }
 204
 205 void
 206 fifo_list_end_iteration(fifo_list_t * list)
 207     /* Stop an iteration before _next() reached the end of the list by itself */
 208 {
 209     list->cur_entry = NULL;
 210     list->cur_removed = 0;
 211 }
 212
 213
 214 void
 215 fifo_list_remove_first(fifo_list_t * l)
 216 {
 217     /* // MANAGE L->NEXT_ENTRY (+ SPECIAL CASE FIRST/LAST ENTRY) */
 218     fifo_list_entry_t *last = NULL;
 219
 220     /* sanity checks */
 221     if (l == NULL)
 222         die("Invalid arguments for fifo_list_remove(): list=%d", l);
 223     if (l->cur_entry == NULL)
 224         die("fifo_list_remove_cur() called outside of an iteration");
 225
 226     last = fifo_list_last(l);
 227     if (l->cur_entry < last) {
 228         /* Override e with the last entry */
 229         memcpy(l->cur_entry, last, l->entry_size);
 230     }
 231     /* erase the last entry and update the number of entries */
 232     memset(last, 0, l->entry_size);
 233     l->num_entries--;
 234     l->cur_removed = 1;
 235
 236 }
 237
 238 fifo_list_t *
 239 fifo_list_destroy(fifo_list_t * list)
 240     /* free() the memory allocated for list and returns NULL */
 241 {
 242     if (list == NULL)
 243         die("Invalid argument for fifo_list_destroy(): list=%d", list);
 244
 245     Free_safe(list->entries_array);
 246     Free_safe(list);
 247     return NULL;
 248 }