lib/list.c

   1 /*
   2  *  Copyright (C) 2012-2015  Thadeu Lima de Souza Cascardo <cascardo@minaslivre.org>
   3  *
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 3 of the License, or
   7  *  (at your option) any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License along
  15  *  with this program; if not, write to the Free Software Foundation, Inc.,
  16  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  17  */
  18
  19 #include "list.h"
  20 #include <stdlib.h>
  21 #include <string.h>
  22
  23 struct item {
  24         void *val;
  25 };
  26
  27 struct list {
  28         size_t alen;
  29         size_t len;
  30         struct item items[];
  31 };
  32
  33 struct list * list_new(void)
  34 {
  35         struct list *list;
  36         size_t alen = 128;
  37         list = malloc(sizeof(*list) + alen * sizeof(struct item));
  38         if (!list)
  39                 return NULL;
  40         list->alen = alen;
  41         list->len = 0;
  42         memset(list->items, 0, alen * sizeof(struct item));
  43         return list;
  44 }
  45
  46 static struct list * list_expand(struct list **list)
  47 {
  48         struct list *l = *list;
  49         struct list *nlist;
  50         size_t len = l->alen * sizeof(struct item);
  51         size_t nlen = len * 2;
  52         nlist = realloc(l, sizeof(*nlist) + nlen);
  53         if (!nlist)
  54                 goto out;
  55         *list = l = nlist;
  56         memset(&l->items[l->len], 0, len);
  57         l->alen = l->alen * 2;
  58         return l;
  59 out:
  60         return NULL;
  61 }
  62
  63 int list_add(struct list **list, void *val)
  64 {
  65         unsigned int i;
  66         struct list *l = *list;
  67         l->items[l->len].val = val;
  68         l->len++;
  69         if (l->len == l->alen) {
  70                 l = list_expand(list);
  71                 if (!l)
  72                         goto out;
  73         }
  74         return 0;
  75 out:
  76         l->items[l->len].val = NULL;
  77         return -1;
  78 }
  79
  80 int list_insert(struct list **list, int pos, void *val)
  81 {
  82         struct list *l = *list;
  83         if (pos > l->len)
  84                 return -1;
  85         if (l->len + 1 == l->alen) {
  86                 l = list_expand(list);
  87                 if (!l)
  88                         goto out;
  89         }
  90         if (pos < l->len)
  91                 memmove(&l->items[pos + 1], &l->items[pos],
  92                         (l->len - pos) * sizeof(struct item));
  93         l->items[pos].val = val;
  94         l->len++;
  95         return 0;
  96 out:
  97         return -1;
  98 }
  99
 100 int list_insert_ordered(struct list **list, void *val, sort_function_t *fn)
 101 {
 102         struct list *l = *list;
 103         int i;
 104         for (i = 0; i < l->len; i++)
 105                 if (fn(l->items[i].val, val) >= 0)
 106                         return list_insert(list, i, val);
 107         return list_add(list, val);
 108 }
 109
 110 void * list_get(struct list *list, int pos)
 111 {
 112         unsigned int i;
 113         if (pos >= list->len)
 114                 return NULL;
 115         return list->items[pos].val;
 116 }
 117
 118 void list_free(struct list *list, free_function_t *ifree)
 119 {
 120         int i;
 121         if (ifree)
 122                 for (i = 0; i < list->len; i++)
 123                         ifree(list->items[i].val);
 124         free(list);
 125 }
 126
 127 int list_size(struct list *list)
 128 {
 129         return list->len;
 130 }