1/* GLIB - Library of useful routines for C programming 2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Library General Public 6 * License as published by the Free Software Foundation; either 7 * version 2 of the License, or (at your option) any later version. 8 * 9 * This library 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 GNU 12 * Library General Public License for more details. 13 * 14 * You should have received a copy of the GNU Library General Public 15 * License along with this library; if not, write to the 16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 17 * Boston, MA 02111-1307, USA. 18 */ 19 20/* 21 * Modified by the GLib Team and others 1997-1999. See the AUTHORS 22 * file for a list of people on the GLib Team. See the ChangeLog 23 * files for a list of changes. These files are distributed with 24 * GLib at ftp://ftp.gtk.org/pub/gtk/. 25 */ 26 27/* 28 * MT safe 29 */ 30 31#include <string.h> 32#include "glib.h" 33 34 35#define MIN_ARRAY_SIZE 16 36 37 38typedef struct _GRealArray GRealArray; 39 40struct _GRealArray 41{ 42 guint8 *data; 43 guint len; 44 guint alloc; 45 guint elt_size; 46 guint zero_terminated : 1; 47 guint clear : 1; 48}; 49 50 51static gint g_nearest_pow (gint num); 52static void g_array_maybe_expand (GRealArray *array, 53 gint len); 54 55static GMemChunk *array_mem_chunk = NULL; 56G_LOCK_DEFINE_STATIC (array_mem_chunk); 57 58GArray* 59g_array_new (gboolean zero_terminated, 60 gboolean clear, 61 guint elt_size) 62{ 63 GRealArray *array; 64 65 G_LOCK (array_mem_chunk); 66 if (!array_mem_chunk) 67 array_mem_chunk = g_mem_chunk_new ("array mem chunk", 68 sizeof (GRealArray), 69 1024, G_ALLOC_AND_FREE); 70 71 array = g_chunk_new (GRealArray, array_mem_chunk); 72 G_UNLOCK (array_mem_chunk); 73 74 array->data = NULL; 75 array->len = 0; 76 array->alloc = 0; 77 array->zero_terminated = (zero_terminated ? 1 : 0); 78 array->clear = (clear ? 1 : 0); 79 array->elt_size = elt_size; 80 81 return (GArray*) array; 82} 83 84void 85g_array_free (GArray *array, 86 gboolean free_segment) 87{ 88 if (free_segment) 89 g_free (array->data); 90 91 G_LOCK (array_mem_chunk); 92 g_mem_chunk_free (array_mem_chunk, array); 93 G_UNLOCK (array_mem_chunk); 94} 95 96GArray* 97g_array_append_vals (GArray *farray, 98 gconstpointer data, 99 guint len) 100{ 101 GRealArray *array = (GRealArray*) farray; 102 103 g_array_maybe_expand (array, len); 104 105 memcpy (array->data + array->elt_size * array->len, data, array->elt_size * len); 106 107 array->len += len; 108 109 return farray; 110} 111 112GArray* 113g_array_prepend_vals (GArray *farray, 114 gconstpointer data, 115 guint len) 116{ 117 GRealArray *array = (GRealArray*) farray; 118 119 g_array_maybe_expand (array, len); 120 121 g_memmove (array->data + array->elt_size * len, array->data, array->elt_size * array->len); 122 123 memcpy (array->data, data, len * array->elt_size); 124 125 array->len += len; 126 127 return farray; 128} 129 130GArray* 131g_array_insert_vals (GArray *farray, 132 guint index, 133 gconstpointer data, 134 guint len) 135{ 136 GRealArray *array = (GRealArray*) farray; 137 138 g_array_maybe_expand (array, len); 139 140 g_memmove (array->data + array->elt_size * (len + index), 141 array->data + array->elt_size * index, 142 array->elt_size * (array->len - index)); 143 144 memcpy (array->data + array->elt_size * index, data, len * array->elt_size); 145 146 array->len += len; 147 148 return farray; 149} 150 151GArray* 152g_array_set_size (GArray *farray, 153 guint length) 154{ 155 GRealArray *array = (GRealArray*) farray; 156 157 if (array->len < length) 158 g_array_maybe_expand (array, length - array->len); 159 160 array->len = length; 161 162 return farray; 163} 164 165GArray* 166g_array_remove_index (GArray* farray, 167 guint index) 168{ 169 GRealArray* array = (GRealArray*) farray; 170 171 g_return_val_if_fail (array, NULL); 172 173 g_return_val_if_fail (index < array->len, NULL); 174 175 if (index != array->len - 1) 176 g_memmove (array->data + array->elt_size * index, 177 array->data + array->elt_size * (index + 1), 178 array->elt_size * (array->len - index - 1)); 179 180 if (array->zero_terminated) 181 memset (array->data + array->elt_size * (array->len - 1), 0, 182 array->elt_size); 183 184 array->len -= 1; 185 186 return farray; 187} 188 189GArray* 190g_array_remove_index_fast (GArray* farray, 191 guint index) 192{ 193 GRealArray* array = (GRealArray*) farray; 194 195 g_return_val_if_fail (array, NULL); 196 197 g_return_val_if_fail (index < array->len, NULL); 198 199 if (index != array->len - 1) 200 g_memmove (array->data + array->elt_size * index, 201 array->data + array->elt_size * (array->len - 1), 202 array->elt_size); 203 204 if (array->zero_terminated) 205 memset (array->data + array->elt_size * (array->len - 1), 0, 206 array->elt_size); 207 208 array->len -= 1; 209 210 return farray; 211} 212 213static gint 214g_nearest_pow (gint num) 215{ 216 gint n = 1; 217 218 while (n < num) 219 n <<= 1; 220 221 return n; 222} 223 224static void 225g_array_maybe_expand (GRealArray *array, 226 gint len) 227{ 228 guint want_alloc = (array->len + len + array->zero_terminated) * array->elt_size; 229 230 if (want_alloc > array->alloc) 231 { 232 guint old_alloc = array->alloc; 233 234 array->alloc = g_nearest_pow (want_alloc); 235 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE); 236 237 array->data = g_realloc (array->data, array->alloc); 238 239 if (array->clear || array->zero_terminated) 240 memset (array->data + old_alloc, 0, array->alloc - old_alloc); 241 } 242} 243 244/* Pointer Array 245 */ 246 247typedef struct _GRealPtrArray GRealPtrArray; 248 249struct _GRealPtrArray 250{ 251 gpointer *pdata; 252 guint len; 253 guint alloc; 254}; 255 256static void g_ptr_array_maybe_expand (GRealPtrArray *array, 257 gint len); 258 259static GMemChunk *ptr_array_mem_chunk = NULL; 260G_LOCK_DEFINE_STATIC (ptr_array_mem_chunk); 261 262 263GPtrArray* 264g_ptr_array_new (void) 265{ 266 GRealPtrArray *array; 267 268 G_LOCK (ptr_array_mem_chunk); 269 if (!ptr_array_mem_chunk) 270 ptr_array_mem_chunk = g_mem_chunk_new ("array mem chunk", 271 sizeof (GRealPtrArray), 272 1024, G_ALLOC_AND_FREE); 273 274 array = g_chunk_new (GRealPtrArray, ptr_array_mem_chunk); 275 G_UNLOCK (ptr_array_mem_chunk); 276 277 array->pdata = NULL; 278 array->len = 0; 279 array->alloc = 0; 280 281 return (GPtrArray*) array; 282} 283 284void 285g_ptr_array_free (GPtrArray *array, 286 gboolean free_segment) 287{ 288 g_return_if_fail (array); 289 290 if (free_segment) 291 g_free (array->pdata); 292 293 G_LOCK (ptr_array_mem_chunk); 294 g_mem_chunk_free (ptr_array_mem_chunk, array); 295 G_UNLOCK (ptr_array_mem_chunk); 296} 297 298static void 299g_ptr_array_maybe_expand (GRealPtrArray *array, 300 gint len) 301{ 302 guint old_alloc; 303 304 if ((array->len + len) > array->alloc) 305 { 306 old_alloc = array->alloc; 307 308 array->alloc = g_nearest_pow (array->len + len); 309 array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE); 310 if (array->pdata) 311 array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc); 312 else 313 array->pdata = g_new0 (gpointer, array->alloc); 314 315 memset (array->pdata + old_alloc, 0, 316 sizeof (gpointer) * (array->alloc - old_alloc)); 317 } 318} 319 320void 321g_ptr_array_set_size (GPtrArray *farray, 322 gint length) 323{ 324 GRealPtrArray* array = (GRealPtrArray*) farray; 325 326 g_return_if_fail (array); 327 328 if (length > array->len) 329 g_ptr_array_maybe_expand (array, (length - array->len)); 330 331 array->len = length; 332} 333 334gpointer 335g_ptr_array_remove_index (GPtrArray* farray, 336 guint index) 337{ 338 GRealPtrArray* array = (GRealPtrArray*) farray; 339 gpointer result; 340 341 g_return_val_if_fail (array, NULL); 342 343 g_return_val_if_fail (index < array->len, NULL); 344 345 result = array->pdata[index]; 346 347 if (index != array->len - 1) 348 g_memmove (array->pdata + index, array->pdata + index + 1, 349 sizeof (gpointer) * (array->len - index - 1)); 350 351 array->pdata[array->len - 1] = NULL; 352 353 array->len -= 1; 354 355 return result; 356} 357 358gpointer 359g_ptr_array_remove_index_fast (GPtrArray* farray, 360 guint index) 361{ 362 GRealPtrArray* array = (GRealPtrArray*) farray; 363 gpointer result; 364 365 g_return_val_if_fail (array, NULL); 366 367 g_return_val_if_fail (index < array->len, NULL); 368 369 result = array->pdata[index]; 370 371 if (index != array->len - 1) 372 array->pdata[index] = array->pdata[array->len - 1]; 373 374 array->pdata[array->len - 1] = NULL; 375 376 array->len -= 1; 377 378 return result; 379} 380 381gboolean 382g_ptr_array_remove (GPtrArray* farray, 383 gpointer data) 384{ 385 GRealPtrArray* array = (GRealPtrArray*) farray; 386 int i; 387 388 g_return_val_if_fail (array, FALSE); 389 390 for (i = 0; i < array->len; i += 1) 391 { 392 if (array->pdata[i] == data) 393 { 394 g_ptr_array_remove_index (farray, i); 395 return TRUE; 396 } 397 } 398 399 return FALSE; 400} 401 402gboolean 403g_ptr_array_remove_fast (GPtrArray* farray, 404 gpointer data) 405{ 406 GRealPtrArray* array = (GRealPtrArray*) farray; 407 int i; 408 409 g_return_val_if_fail (array, FALSE); 410 411 for (i = 0; i < array->len; i += 1) 412 { 413 if (array->pdata[i] == data) 414 { 415 g_ptr_array_remove_index_fast (farray, i); 416 return TRUE; 417 } 418 } 419 420 return FALSE; 421} 422 423void 424g_ptr_array_add (GPtrArray* farray, 425 gpointer data) 426{ 427 GRealPtrArray* array = (GRealPtrArray*) farray; 428 429 g_return_if_fail (array); 430 431 g_ptr_array_maybe_expand (array, 1); 432 433 array->pdata[array->len++] = data; 434} 435 436/* Byte arrays 437 */ 438 439GByteArray* g_byte_array_new (void) 440{ 441 return (GByteArray*) g_array_new (FALSE, FALSE, 1); 442} 443 444void g_byte_array_free (GByteArray *array, 445 gboolean free_segment) 446{ 447 g_array_free ((GArray*) array, free_segment); 448} 449 450GByteArray* g_byte_array_append (GByteArray *array, 451 const guint8 *data, 452 guint len) 453{ 454 g_array_append_vals ((GArray*) array, (guint8*)data, len); 455 456 return array; 457} 458 459GByteArray* g_byte_array_prepend (GByteArray *array, 460 const guint8 *data, 461 guint len) 462{ 463 g_array_prepend_vals ((GArray*) array, (guint8*)data, len); 464 465 return array; 466} 467 468GByteArray* g_byte_array_set_size (GByteArray *array, 469 guint length) 470{ 471 g_array_set_size ((GArray*) array, length); 472 473 return array; 474} 475 476GByteArray* g_byte_array_remove_index (GByteArray *array, 477 guint index) 478{ 479 g_array_remove_index((GArray*) array, index); 480 481 return array; 482} 483 484GByteArray* g_byte_array_remove_index_fast (GByteArray *array, 485 guint index) 486{ 487 g_array_remove_index_fast((GArray*) array, index); 488 489 return array; 490} 491