slist.c

   1 #include <stdio.h>
   2 #include <unistd.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include "slist.h"
   6
   7 struct sorted_list {
   8         int (*compare)(const void *, const void *);
   9         void **list;
  10         unsigned int alloc, pos;
  11         int is_sorted;
  12 };
  13
  14 void slist_sort(slist *sl)
  15 {
  16         /* ignore empty and already sorted lists */
  17         if (!sl || !sl->list || !sl->pos || sl->is_sorted) {
  18                 return;
  19         }
  20
  21         qsort(sl->list, sl->pos, sizeof(void *), sl->compare);
  22         sl->is_sorted = 1;
  23 }
  24
  25 /*
  26  * The engine of the "sorted list lookup". Arrives at the right
  27  * conclusion by bisecting its way around inside the sorted list.
  28  */
  29 int slist_find_pos(slist *sl, const void *key)
  30 {
  31         int value;
  32         unsigned int high, low = 0;
  33
  34         if (!sl || !sl->pos || !sl->list) {
  35                 return -1;
  36         }
  37
  38         if (!sl->is_sorted)
  39                 slist_sort(sl);
  40
  41         high = sl->pos;
  42         while (high - low > 0) {
  43                 unsigned int mid = low + ((high - low) / 2);
  44
  45                 value = sl->compare(&key, &sl->list[mid]);
  46                 if (value > 0) {
  47                         low = mid + 1;
  48                         continue;
  49                 } else if (value < 0) {
  50                         high = mid;
  51                         continue;
  52                 } else {
  53                         return mid;
  54                 }
  55         }
  56
  57         return -1;
  58 }
  59
  60 void *slist_find(slist *sl, const void *key)
  61 {
  62         int slot = slist_find_pos(sl, key);
  63
  64         if (slot < 0)
  65                 return NULL;
  66         return sl->list[slot];
  67 }
  68
  69 static int slist_grow(slist *sl, unsigned int hint)
  70 {
  71         void *ptr;
  72
  73         if (!hint)
  74                 return 0;
  75
  76         ptr = realloc(sl->list, (sl->alloc + hint) * sizeof(void *));
  77         if (!ptr)
  78                 return -1;
  79         sl->list = ptr;
  80         sl->alloc += hint;
  81         return 0;
  82 }
  83
  84 int slist_push(slist *sl, void *item)
  85 {
  86         if (sl->pos >= sl->alloc - 1 && slist_grow(sl, 5) < 0) {
  87                 return -1;
  88         }
  89
  90         /*
  91          * No sorting is required when there's either only
  92          * one item in the list, or when the list is added
  93          * to in sequential order.
  94          */
  95         sl->list[sl->pos] = item;
  96         if (sl->is_sorted && sl->pos
  97             && sl->compare(&sl->list[sl->pos - 1], &sl->list[sl->pos]) > 0)
  98         {
  99                 sl->is_sorted = 0;
 100         }
 101         sl->pos++;
 102         return 0;
 103 }
 104
 105 void *slist_pop(slist *sl)
 106 {
 107         void *item;
 108
 109         if (!sl->pos)
 110                 return NULL;
 111         sl->pos--;
 112         item = sl->list[sl->pos];
 113         sl->list[sl->pos] = NULL;
 114         return item;
 115 }
 116
 117 slist *slist_init(unsigned int hint, int (*cmp)(const void *, const void *))
 118 {
 119         slist *sl;
 120
 121         sl = calloc(1, sizeof(*sl));
 122         if (!sl)
 123                 return NULL;
 124         if (hint)
 125                 slist_grow(sl, hint);
 126
 127         sl->compare = cmp;
 128
 129         return sl;
 130 }
 131
 132 int slist_set_list(slist *sl, void **list, unsigned int items, int sorted)
 133 {
 134         if (!sl || !list || !items)
 135                 return -1;
 136
 137         sl->list = list;
 138         sl->pos = items;
 139         sl->alloc = 0;
 140         if (!sorted) {
 141                 slist_sort(sl);
 142         }
 143         return 0;
 144 }
 145
 146 void slist_release(slist *sl)
 147 {
 148         if (!sl)
 149                 return;
 150
 151         if (sl->list)
 152                 free(sl->list);
 153         sl->list = NULL;
 154         sl->pos = sl->alloc = 0;
 155         sl->is_sorted = 1;
 156 }
 157
 158 void slist_free_items(slist *sl)
 159 {
 160         unsigned int i;
 161
 162         if (!sl || !sl->list)
 163                 return;
 164         for (i = 0; i < sl->pos; i++)
 165                 free(sl->list[i]);
 166         sl->pos = 0;
 167 }
 168
 169 void *slist_destroy(slist *sl, int items_too)
 170 {
 171         if (!sl)
 172                 return NULL;
 173
 174         if (items_too)
 175                 slist_free_items(sl);
 176
 177         slist_release(sl);
 178         free(sl);
 179
 180         return NULL;
 181 }
 182
 183 unsigned int slist_entries(slist *sl)
 184 {
 185         if (!sl)
 186                 return 0;
 187
 188         return sl->pos;
 189 }
 190
 191 void *slist_get_list(slist *sl)
 192 {
 193         if (!sl)
 194                 return NULL;
 195
 196         return sl->list;
 197 }
 198
 199 void slist_walk(slist *sl, void *arg, int (*cb)(void *, void *))
 200 {
 201         unsigned int i;
 202
 203         if (!sl || !sl->list || !sl->pos)
 204                 return;
 205
 206         for (i = 0; i < sl->pos; i++) {
 207                 cb(arg, sl->list[i]);
 208         }
 209 }