eglib/src/gptrarray.c

   1 /*
   2  * Pointer Array
   3  *
   4  * Author:
   5  *   Aaron Bockover (abockover@novell.com)
   6  *   Gonzalo Paniagua Javier (gonzalo@novell.com)
   7  *   Jeffrey Stedfast (fejj@novell.com)
   8  *
   9  * (C) 2006,2011 Novell, Inc.
  10  *
  11  * Permission is hereby granted, free of charge, to any person obtaining
  12  * a copy of this software and associated documentation files (the
  13  * "Software"), to deal in the Software without restriction, including
  14  * without limitation the rights to use, copy, modify, merge, publish,
  15  * distribute, sublicense, and/or sell copies of the Software, and to
  16  * permit persons to whom the Software is furnished to do so, subject to
  17  * the following conditions:
  18  *
  19  * The above copyright notice and this permission notice shall be
  20  * included in all copies or substantial portions of the Software.
  21  *
  22  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  23  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  24  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  25  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  26  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  27  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  28  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  29  */
  30
  31 #include <stdlib.h>
  32 #include <glib.h>
  33
  34 typedef struct _GPtrArrayPriv {
  35         gpointer *pdata;
  36         guint len;
  37         guint size;
  38 } GPtrArrayPriv;
  39
  40 static void
  41 g_ptr_array_grow(GPtrArrayPriv *array, guint length)
  42 {
  43         guint new_length = array->len + length;
  44
  45         g_return_if_fail(array != NULL);
  46
  47         if(new_length <= array->size) {
  48                 return;
  49         }
  50
  51         array->size = 1;
  52
  53         while(array->size < new_length) {
  54                 array->size <<= 1;
  55         }
  56
  57         array->size = MAX(array->size, 16);
  58         array->pdata = g_realloc(array->pdata, array->size * sizeof(gpointer));
  59 }
  60
  61 GPtrArray *
  62 g_ptr_array_new(void)
  63 {
  64         return g_ptr_array_sized_new(0);
  65 }
  66
  67 GPtrArray *
  68 g_ptr_array_sized_new(guint reserved_size)
  69 {
  70         GPtrArrayPriv *array = g_new0(GPtrArrayPriv, 1);
  71
  72         array->pdata = NULL;
  73         array->len = 0;
  74         array->size = 0;
  75
  76         if(reserved_size > 0) {
  77                 g_ptr_array_grow(array, reserved_size);
  78         }
  79
  80         return (GPtrArray *)array;
  81 }
  82
  83 gpointer *
  84 g_ptr_array_free(GPtrArray *array, gboolean free_seg)
  85 {
  86         gpointer *data = NULL;
  87
  88         g_return_val_if_fail(array != NULL, NULL);
  89
  90         if(free_seg) {
  91                 g_free(array->pdata);
  92         } else {
  93                 data = array->pdata;
  94         }
  95
  96         g_free(array);
  97
  98         return data;
  99 }
 100
 101 void
 102 g_ptr_array_set_size(GPtrArray *array, gint length)
 103 {
 104         g_return_if_fail(array != NULL);
 105
 106         if((size_t)length > array->len) {
 107                 g_ptr_array_grow((GPtrArrayPriv *)array, length);
 108                 memset(array->pdata + array->len, 0, (length - array->len)
 109                         * sizeof(gpointer));
 110         }
 111
 112         array->len = length;
 113 }
 114
 115 void
 116 g_ptr_array_add(GPtrArray *array, gpointer data)
 117 {
 118         g_return_if_fail(array != NULL);
 119         g_ptr_array_grow((GPtrArrayPriv *)array, 1);
 120         array->pdata[array->len++] = data;
 121 }
 122
 123 gpointer
 124 g_ptr_array_remove_index(GPtrArray *array, guint index)
 125 {
 126         gpointer removed_node;
 127
 128         g_return_val_if_fail(array != NULL, NULL);
 129         g_return_val_if_fail(index >= 0 || index < array->len, NULL);
 130
 131         removed_node = array->pdata[index];
 132
 133         if(index != array->len - 1) {
 134                 g_memmove(array->pdata + index, array->pdata + index + 1,
 135                         (array->len - index - 1) * sizeof(gpointer));
 136         }
 137
 138         array->len--;
 139         array->pdata[array->len] = NULL;
 140
 141         return removed_node;
 142 }
 143
 144 gpointer
 145 g_ptr_array_remove_index_fast(GPtrArray *array, guint index)
 146 {
 147         gpointer removed_node;
 148
 149         g_return_val_if_fail(array != NULL, NULL);
 150         g_return_val_if_fail(index >= 0 || index < array->len, NULL);
 151
 152         removed_node = array->pdata[index];
 153
 154         if(index != array->len - 1) {
 155                 g_memmove(array->pdata + index, array->pdata + array->len - 1,
 156                         sizeof(gpointer));
 157         }
 158
 159         array->len--;
 160         array->pdata[array->len] = NULL;
 161
 162         return removed_node;
 163 }
 164
 165 gboolean
 166 g_ptr_array_remove(GPtrArray *array, gpointer data)
 167 {
 168         guint i;
 169
 170         g_return_val_if_fail(array != NULL, FALSE);
 171
 172         for(i = 0; i < array->len; i++) {
 173                 if(array->pdata[i] == data) {
 174                         g_ptr_array_remove_index(array, i);
 175                         return TRUE;
 176                 }
 177         }
 178
 179         return FALSE;
 180 }
 181
 182 gboolean
 183 g_ptr_array_remove_fast(GPtrArray *array, gpointer data)
 184 {
 185         guint i;
 186
 187         g_return_val_if_fail(array != NULL, FALSE);
 188
 189         for(i = 0; i < array->len; i++) {
 190                 if(array->pdata[i] == data) {
 191                         array->len--;
 192                         if (array->len > 0)
 193                                 array->pdata [i] = array->pdata [array->len];
 194                         else
 195                                 array->pdata [i] = NULL;
 196                         return TRUE;
 197                 }
 198         }
 199
 200         return FALSE;
 201 }
 202
 203 void
 204 g_ptr_array_foreach(GPtrArray *array, GFunc func, gpointer user_data)
 205 {
 206         guint i;
 207
 208         for(i = 0; i < array->len; i++) {
 209                 func(g_ptr_array_index(array, i), user_data);
 210         }
 211 }
 212
 213 void
 214 g_ptr_array_sort(GPtrArray *array, GCompareFunc compare)
 215 {
 216         g_return_if_fail(array != NULL);
 217         qsort(array->pdata, array->len, sizeof(gpointer), compare);
 218 }
 219
 220 static void
 221 g_qsort_swap (char *a, char *b, size_t n)
 222 {
 223         char *an = a + n;
 224         char tmp;
 225
 226         do {
 227                 tmp = *a;
 228                 *a++ = *b;
 229                 *b++ = tmp;
 230         } while (a < an);
 231 }
 232
 233 static char *
 234 g_qsort_median (char *a, char *b, char *c, GCompareDataFunc compare, gpointer user_data)
 235 {
 236         if (compare (a, b, user_data) < 0) {
 237                 /* a < b < c */
 238                 if (compare (b, c, user_data) < 0)
 239                         return b;
 240
 241                 /* a < c < b */
 242                 if (compare (a, c, user_data) < 0)
 243                         return c;
 244
 245                 /* c < a < b */
 246                 return a;
 247         } else {
 248                 /* b < a < c */
 249                 if (compare (a, c, user_data) < 0)
 250                         return a;
 251
 252                 /* b < c < a */
 253                 if (compare (b, c, user_data) < 0)
 254                         return c;
 255
 256                 /* c < b < a */
 257                 return b;
 258         }
 259 }
 260
 261 void
 262 g_qsort_with_data (gpointer base, size_t nmemb, size_t size, GCompareDataFunc compare, gpointer user_data)
 263 {
 264         char *middle = ((char *) base) + (nmemb / 2) * size;
 265         char *last = ((char *) base) + (nmemb - 1) * size;
 266         char *first = (char *) base;
 267         register char *i = first + size;
 268         register char *k = last;
 269         register char *pivot;
 270
 271         if (nmemb <= 1)
 272                 return;
 273
 274         /* determine which element contains the median value */
 275         pivot = g_qsort_median (first, middle, last, compare, user_data);
 276
 277         /* swap pivot value into first element (so the location stays constant) */
 278         g_qsort_swap (first, pivot, size);
 279         pivot = first;
 280
 281         do {
 282                 /* find the first element with a value > pivot value */
 283                 while (compare (i, pivot, user_data) <= 0 && i < last && i < k)
 284                         i += size;
 285
 286                 /* find the last element with a value <= pivot value */
 287                 while (compare (k, pivot, user_data) > 0 && k > first && k >= i)
 288                         k -= size;
 289
 290                 if (k <= i)
 291                         break;
 292
 293                 g_qsort_swap (i, k, size);
 294         } while (1);
 295
 296         /* swap the pivot with the last element in the first partition */
 297         g_qsort_swap (pivot, k, size);
 298
 299         /* sort the first partition */
 300         g_qsort_with_data (first, (k - first) / size, size, compare, user_data);
 301
 302         /* sort the second partition */
 303         g_qsort_with_data (k + size, (last - k) / size, size, compare, user_data);
 304 }
 305
 306 void
 307 g_ptr_array_sort_with_data (GPtrArray *array, GCompareDataFunc compare, gpointer user_data)
 308 {
 309         g_return_if_fail (array != NULL);
 310
 311         g_qsort_with_data (array->pdata, array->len, sizeof (gpointer), compare, user_data);
 312 }
 313