mono/eglib/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 < 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 < 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 void
 221 g_ptr_array_sort_with_data (GPtrArray *array, GCompareDataFunc compare, gpointer user_data)
 222 {
 223         g_return_if_fail (array != NULL);
 224
 225         g_qsort_with_data (array->pdata, array->len, sizeof (gpointer), compare, user_data);
 226 }
 227