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

   1 /*
   2  * FCRON - periodic command scheduler
   3  *
   4  *  Copyright 2000-2013 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  * Unordered list of generic items
  27  */
  28
  29 #include "global.h"
  30 #include "mem.h"
  31 #include "log.h"
  32 #include "u_list.h"
  33
  34 /* private functions: */
  35 int u_list_resize_array(u_list_t * l);
  36 u_list_entry_t *u_list_last(u_list_t * l);
  37
  38 u_list_t *
  39 u_list_init(size_t entry_size, int init_size, int grow_size)
  40 /* Create a new unordered list
  41  * Returns the newly created unorderd 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     u_list_t *l = NULL;
  47
  48     /* sanity check */
  49     if (entry_size < 1 || init_size < 1 || grow_size < 1)
  50         die("Invalid arguments for u_list_init(): entry_size=%d, init_size=%d, "
  51             "grow_size=%d", entry_size, init_size, grow_size);
  52
  53     /* Allocate the list structure: */
  54     l = alloc_safe(sizeof(struct u_list_t), "new u_list_t");
  55
  56     /* Initialize the structure and allocate the array: */
  57     l->array_size = init_size;
  58     l->entry_size = entry_size;
  59     l->grow_size = grow_size;
  60     l->cur_entry = NULL;
  61     l->cur_removed = 0;
  62     l->entries_array = alloc_safe(init_size * entry_size, "new u_list_t array");
  63
  64     return l;
  65 }
  66
  67 u_list_t *
  68 u_list_copy(u_list_t * list)
  69 {
  70     u_list_t *new_list = NULL;
  71
  72     if (list == NULL)
  73         return NULL;
  74
  75     new_list = alloc_safe(sizeof(struct u_list_t), "u_list_t copy");
  76     memcpy(new_list, list, sizeof(struct u_list_t));
  77
  78     new_list->cur_entry = NULL;
  79
  80     new_list->entries_array = alloc_safe(list->array_size * list->entry_size,
  81                                          "u_list_t copy (array)");
  82     memcpy(new_list->entries_array, list->entries_array,
  83            (list->array_size * list->entry_size));
  84
  85     return new_list;
  86 }
  87
  88
  89 int
  90 u_list_resize_array(u_list_t * l)
  91 /* Resize l's entries_array up to l->max_entries
  92  * Returns OK on success, ERR if the array is already at maximum size */
  93 {
  94     int offset = 0;
  95     int old_size = l->array_size;
  96
  97     /* sanity check */
  98     if (l == NULL)
  99         die("Invalid argument for u_list_resize_array(): list=%d", l);
 100     if (l->max_entries > 0 && l->array_size >= l->max_entries) {
 101         debug
 102             ("Resizing u_list_t failed because it is already at max size (size: %d)",
 103              l->array_size);
 104         return ERR;
 105     }
 106
 107     if (l->cur_entry != NULL)
 108         /* Compute cur_entry's offset so as we can set cur_entry to the right place
 109          * after we have allocated a new chunk of memory for the entries_array */
 110         offset = (char *)l->cur_entry - (char *)l->entries_array;
 111
 112     l->array_size = (l->array_size + l->grow_size);
 113     if (l->max_entries > 0 && l->array_size > l->max_entries)
 114         l->array_size = l->max_entries;
 115
 116     debug("Resizing u_list_t (old size: %d, new size: %d)...", old_size,
 117           l->array_size);
 118
 119     l->entries_array =
 120         realloc_safe(l->entries_array, (l->array_size * l->entry_size),
 121                      "larger u_list_t array");
 122     /* allocate newly allocated memory */
 123     memset((char *)l->entries_array + (old_size * l->entry_size), '\0',
 124            (l->array_size - old_size) * l->entry_size);
 125
 126     if (l->cur_entry != NULL)
 127         l->cur_entry = (u_list_entry_t *) ((char *)l->entries_array + offset);
 128
 129     return OK;
 130 }
 131
 132 u_list_entry_t *
 133 u_list_last(u_list_t * l)
 134 /* Returns the pointer of the last entry in the list, or NULL if l is empty */
 135 {
 136     if (l->num_entries <= 0)
 137         return NULL;
 138     else
 139         return (u_list_entry_t *)
 140             ((char *)l->entries_array + l->entry_size * (l->num_entries - 1));
 141 }
 142
 143 u_list_entry_t *
 144 u_list_add(u_list_t * l, u_list_entry_t * e)
 145 /* Add one entry to the list
 146  * Returns a pointer to the added element, or NULL if list is already at max size */
 147 {
 148     u_list_entry_t *new = NULL;
 149
 150     /* sanity check */
 151     if (l == NULL || e == NULL)
 152         die("Invalid arguments for u_list_add(): list=%d, entry=%d", l, e);
 153
 154     /* Check there is some space left, or resize the array */
 155     if (l->num_entries >= l->array_size) {
 156         /* no more space: attempt to grow (the following function dies on error: */
 157         if (u_list_resize_array(l) != OK)
 158             return NULL;
 159     }
 160
 161     l->num_entries++;
 162     new = u_list_last(l);
 163     memcpy(new, e, l->entry_size);
 164
 165     return new;
 166 }
 167
 168 int
 169 u_list_is_iterating(u_list_t * l)
 170 {
 171     /* sanity check */
 172     if (l == NULL)
 173         die("Invalid argument for u_list_iterating(): list=%d", l);
 174
 175     return (l->cur_entry != NULL);
 176 }
 177
 178 u_list_entry_t *
 179 u_list_first(u_list_t * l)
 180 /* Return the first entry of the list (then u_list_next() can be used) */
 181 {
 182     /* sanity check */
 183     if (l == NULL)
 184         die("Invalid argument for u_list_first(): list=%d", l);
 185     if (l->cur_entry != NULL)
 186         die("u_list_first() called but there is already an iteration");
 187
 188     if (l->num_entries > 0) {
 189         l->cur_entry = l->entries_array;
 190     }
 191
 192     return l->cur_entry;
 193 }
 194
 195 u_list_entry_t *
 196 u_list_next(u_list_t * l)
 197 /* Return the entry after e */
 198 {
 199     /* sanity checks */
 200     if (l == NULL)
 201         die("Invalid arguments for u_list_next(): list=%d", l);
 202     if (l->cur_entry == NULL)
 203         die("u_list_next() called outside an iteration: l->cur_entry=%d",
 204             l->cur_entry);
 205
 206     if (l->cur_removed > 0) {
 207         l->cur_removed = 0;
 208         /* the current entry has just been removed and replaced by another one:
 209          * we can return the same pointer again.
 210          * However if the removed entry was the last one then we reached the end
 211          * of the list */
 212         if (l->cur_entry > u_list_last(l))
 213             l->cur_entry = NULL;
 214     }
 215     else {
 216         /* cur_entry *not* removed (standard behavior) */
 217
 218         if (l->cur_entry < u_list_last(l))
 219             l->cur_entry =
 220                 (u_list_entry_t *) ((char *)l->cur_entry + l->entry_size);
 221         else
 222             /* reached the end of the list */
 223             l->cur_entry = NULL;
 224     }
 225
 226     return l->cur_entry;
 227 }
 228
 229 void
 230 u_list_end_iteration(u_list_t * list)
 231     /* Stop an iteration before _next() reached the end of the list by itself */
 232 {
 233     list->cur_entry = NULL;
 234     list->cur_removed = 0;
 235 }
 236
 237
 238 void
 239 u_list_remove_cur(u_list_t * l)
 240 {
 241     u_list_entry_t *last = NULL;
 242
 243     /* sanity checks */
 244     if (l == NULL)
 245         die("Invalid arguments for u_list_remove(): list=%d", l);
 246     if (l->cur_entry == NULL)
 247         die("u_list_remove_cur() called outside of an iteration");
 248
 249     last = u_list_last(l);
 250     if (l->cur_entry < last) {
 251         /* Override e with the last entry */
 252         memcpy(l->cur_entry, last, l->entry_size);
 253     }
 254     /* erase the last entry and update the number of entries */
 255     memset(last, 0, l->entry_size);
 256     l->num_entries--;
 257     l->cur_removed = 1;
 258
 259 }
 260
 261 u_list_t *
 262 u_list_destroy(u_list_t * list)
 263     /* free() the memory allocated for list and returns NULL */
 264 {
 265     if (list == NULL)
 266         die("Invalid argument for u_list_destroy(): list=%d", list);
 267
 268     Free_safe(list->entries_array);
 269     Free_safe(list);
 270     return NULL;
 271 }