hphp/neo/ulist.c

   1 /*
   2  * Copyright 2001-2004 Brandon Long
   3  * All Rights Reserved.
   4  *
   5  * ClearSilver Templating System
   6  *
   7  * This code is made available under the terms of the ClearSilver License.
   8  * http://www.clearsilver.net/license.hdf
   9  *
  10  */
  11
  12 #include "cs_config.h"
  13
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include <errno.h>
  17
  18 #include "neo_misc.h"
  19 #include "neo_err.h"
  20 #include "ulist.h"
  21
  22 #define ULIST_DEFAULT_SIZE 10
  23
  24 static NEOERR *check_resize (ULIST *ul, int size)
  25 {
  26   if (size > ul->max)
  27   {
  28     void **new_items;
  29     int new_size = 0;
  30
  31     new_size = ul->max*2;
  32     if (size > new_size)
  33     {
  34       new_size = size + ul->max;
  35     }
  36
  37     new_items = (void **) realloc ((void *)(ul->items), new_size * sizeof(void *));
  38     if (new_items == NULL)
  39     {
  40       return nerr_raise(NERR_NOMEM,
  41           "Unable to resize ULIST to %d: Out of memory", new_size);
  42     }
  43     ul->items = new_items;
  44     ul->max = new_size;
  45   }
  46
  47   return STATUS_OK;
  48 }
  49
  50
  51 NEOERR *uListInit(ULIST **ul, int size, int flags)
  52 {
  53   ULIST *r_ul;
  54
  55   *ul = NULL;
  56   if (size == 0)
  57   {
  58     size = ULIST_DEFAULT_SIZE;
  59   }
  60
  61   r_ul = (ULIST *) calloc (1, sizeof (ULIST));
  62   if (r_ul == NULL)
  63   {
  64     return nerr_raise(NERR_NOMEM, "Unable to create ULIST: Out of memory");
  65   }
  66   r_ul->items = (void **) calloc (size, sizeof(void *));
  67   if (r_ul->items == NULL)
  68   {
  69     free (r_ul);
  70     return nerr_raise(NERR_NOMEM, "Unable to create ULIST: Out of memory");
  71   }
  72
  73   r_ul->num = 0;
  74   r_ul->max = size;
  75   r_ul->flags = flags;
  76   *ul = r_ul;
  77
  78   return STATUS_OK;
  79 }
  80
  81 NEOERR *uListvInit(ULIST **ul, ...)
  82 {
  83   NEOERR *err;
  84   va_list ap;
  85   void *it;
  86
  87   err = uListInit (ul, 0, 0);
  88   if (err) return nerr_pass (err);
  89
  90   va_start (ap, ul);
  91
  92   it = va_arg (ap, void *);
  93
  94   while (it)
  95   {
  96     err = uListAppend (*ul, it);
  97     if (err)
  98     {
  99       uListDestroy(ul, 0);
 100       return nerr_pass (err);
 101     }
 102     it = va_arg (ap, void *);
 103   }
 104   return STATUS_OK;
 105 }
 106
 107 NEOERR *uListAppend (ULIST *ul, void *data)
 108 {
 109   NEOERR *r;
 110
 111   r = check_resize (ul, ul->num + 1);
 112   if (r != STATUS_OK)
 113     return r;
 114
 115   ul->items[ul->num] = data;
 116   ul->num++;
 117
 118   return STATUS_OK;
 119 }
 120
 121 NEOERR *uListPop (ULIST *ul, void **data)
 122 {
 123   if (ul->num == 0)
 124     return nerr_raise(NERR_OUTOFRANGE, "uListPop: empty list");
 125
 126   *data = ul->items[ul->num - 1];
 127   ul->num--;
 128
 129   return STATUS_OK;
 130 }
 131
 132 NEOERR *uListInsert (ULIST *ul, int x, void *data)
 133 {
 134   void **start;
 135   NEOERR *r;
 136
 137   if (x < 0)
 138     x = ul->num + x;
 139
 140   if (x >= ul->num)
 141     return nerr_raise(NERR_OUTOFRANGE, "uListInsert: past end (%d > %d)",
 142         x, ul->num);
 143
 144   r = check_resize (ul, ul->num + 1);
 145   if (r != STATUS_OK)
 146     return r;
 147
 148   start = &(ul->items[x]);
 149   memmove (start + 1, start, (ul->num - x) * sizeof(void *));
 150   ul->items[x] = data;
 151   ++ul->num;
 152
 153   return STATUS_OK;
 154 }
 155
 156 NEOERR *uListDelete (ULIST *ul, int x, void **data)
 157 {
 158   void **start;
 159
 160   if (x < 0)
 161     x = ul->num + x;
 162
 163   if (x >= ul->num)
 164     return nerr_raise(NERR_OUTOFRANGE, "uListDelete: past end (%d > %d)",
 165         x, ul->num);
 166
 167   if (data != NULL)
 168     *data = ul->items[x];
 169
 170   start = &(ul->items[x]);
 171   memmove (start, start+1, (ul->num - x - 1) * sizeof(void *));
 172   --ul->num;
 173
 174   return STATUS_OK;
 175 }
 176
 177 NEOERR *uListGet (ULIST *ul, int x, void **data)
 178 {
 179   if (x < 0)
 180     x = ul->num + x;
 181
 182   if (x >= ul->num)
 183     return nerr_raise(NERR_OUTOFRANGE, "uListGet: past end (%d > %d)",
 184         x, ul->num);
 185
 186   if (x < 0)
 187     return nerr_raise(NERR_OUTOFRANGE, "uListGet: past beginning (%d < 0)", x);
 188
 189   *data = ul->items[x];
 190
 191   return STATUS_OK;
 192 }
 193
 194 NEOERR *uListSet (ULIST *ul, int x, void *data)
 195 {
 196   if (x >= ul->num)
 197     return nerr_raise(NERR_OUTOFRANGE, "uListSet: past end (%d > %d)",
 198         x, ul->num);
 199
 200   ul->items[x] = data;
 201
 202   return STATUS_OK;
 203 }
 204
 205 NEOERR *uListReverse (ULIST *ul)
 206 {
 207   int i;
 208
 209   for (i = 0; i < ul->num/2; ++i) {
 210     void *tmp = ul->items[i];
 211     ul->items[i] = ul->items[ul->num-1-i];
 212     ul->items[ul->num-1-i] = tmp;
 213   }
 214
 215   return STATUS_OK;
 216 }
 217
 218 NEOERR *uListSort (ULIST *ul, int (*compareFunc)(const void *, const void*)) {
 219   qsort(ul->items, ul->num, sizeof(void *), compareFunc);
 220   return STATUS_OK;
 221 }
 222
 223 void *uListSearch (ULIST *ul, const void *key, int
 224     (*compareFunc)(const void *, const void*)) {
 225   return bsearch(key, ul->items, ul->num, sizeof(void *), compareFunc);
 226 }
 227
 228 void *uListIn (ULIST *ul, const void *key, int (*compareFunc)(const void *, const void*)) {
 229   int i;
 230
 231   for (i = 0; i < ul->num; ++i) {
 232     if (!compareFunc(key, &ul->items[i])) {
 233       return &ul->items[i];
 234     }
 235   }
 236   return NULL;
 237 }
 238
 239 int uListIndex (ULIST *ul, const void *key, int (*compareFunc)(const void *, const void*)) {
 240   void **p = uListIn(ul, key, compareFunc);
 241   return p ? (p - ul->items) : -1;
 242 }
 243
 244
 245
 246 NEOERR *uListDestroy (ULIST **ul, int flags)
 247 {
 248   if (flags & ULIST_FREE)
 249   {
 250     return uListDestroyFunc(ul, free);
 251   }
 252   else
 253   {
 254     return uListDestroyFunc(ul, NULL);
 255   }
 256 }
 257
 258 NEOERR *uListDestroyFunc (ULIST **ul, void (*destroyFunc)(void *))
 259 {
 260   ULIST *r_ul;
 261
 262   r_ul = *ul;
 263
 264   if (r_ul == NULL)
 265     return STATUS_OK;
 266
 267   if (destroyFunc != NULL)
 268   {
 269     int x;
 270     for (x = 0; x < r_ul->num; x++)
 271     {
 272       (*destroyFunc)(r_ul->items[x]);
 273     }
 274   }
 275   free (r_ul->items);
 276   free (r_ul);
 277   *ul = NULL;
 278
 279   return STATUS_OK;
 280 }
 281
 282 int uListLength (ULIST *ul)
 283 {
 284   if (ul == NULL) return 0;
 285   return ul->num;
 286 }