libs/libmpa/ptr_array.h

   1 /* **************************************************************************
   2  * Copyright (c) 2007, David Waite
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  *  met:
   8  *
   9  * * Redistributions of source code must retain the above copyright notice,
  10  *   this list of conditions and the following disclaimer.
  11  * * Redistributions in binary form must reproduce the above copyright notice
  12  *   this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * * The name(s) of contributors may not be used to endorse or promote
  15  *   products derived from this software without specific prior written
  16  *   permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  20  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  22  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  23  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  24  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  25  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  26  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  27  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  28  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  ************************************************************************* */
  30 #ifndef _POINTER_ARRAY_
  31 #define _POINTER_ARRAY_
  32 #include <sys/types.h>
  33 #include <stddef.h>
  34
  35 /* Pointer Array
  36  * *************
  37  *
  38  * This type is meant to provide an automatically growing array of
  39  * pointers, to be used by various software. It is somewhat equivalent
  40  * to GPtrArray in GNU glib; however, several pieces of functionality
  41  * are not implemented as they were not needed for the particular
  42  * project at hand.
  43  *
  44  * Structure:
  45  *
  46  *     The library is built to allow for multiple references to be
  47  *     able to point at the array, even if the array is enlarged (and
  48  *     as a side effect, moved around memory) multiple times. Arrays
  49  *     currently cannot be shrunk - it is recommended that an array be
  50  *     destroyed and recreated if its space requirements decrease
  51  *     dramatically.
  52  */
  53 typedef struct ptr_array_t *ptr_array;
  54
  55 struct ptr_array_t
  56 {
  57   const void **array;
  58   size_t length;
  59   size_t size;
  60 };
  61
  62 /* Create a new, empty pointer array. The returned value must be freed
  63  * by a call to ptr_array_free.
  64  *
  65  * Arguments: initial_size, the initial number of entries to
  66  *            support. This is useful to plan out initial usage to
  67  *            avoid unnececssary reallocation calls.
  68  * Result: the pointer array, or NULL if allocation failed for some
  69  *            reason.
  70  */
  71 ptr_array ptr_array_new(size_t initial_size);
  72 /* Free an existing pointer array.
  73  *
  74  * Arguments: self, the pointer array to free. Can be NULL. Multiple
  75  *            calls to free has undefined platform results.
  76  */
  77 void ptr_array_free(ptr_array self);
  78
  79 /* Remove an entry by value from the array, preserving the order of
  80  * items following the removal point.
  81  *
  82  * Arguments: self, the pointer array.
  83  *            obj, the object to search for in the array.
  84  * Result: obj if the value was found, otherwise NULL. Note that if
  85  *            obj is NULL, success is not possible to determine.
  86  */
  87 void * ptr_array_remove_ordered(ptr_array self, const void *obj);
  88 /* Remove an entry by value from the array, preferring speed over
  89  * preserving order.
  90  *
  91  * Arguments: self, the pointer array
  92  *            obj, the object to search for in the array.
  93  * Result: obj if the value was found, otherwise NULL. Note that if
  94  *            obj is NULL, success is not possible to determine.
  95  */
  96 void * ptr_array_remove_fast(ptr_array self, const void *obj);
  97
  98 /* Remove an entry at a certain index from the array, preserving the
  99  * order of items following the removal point.
 100  *
 101  * Arguments: self, the pointer array.
 102  *            index, the position of the object to remove.
 103  * Result: the value which was removed, otherwise NULL. Note if the
 104  *            value removed is NULL, success is not possible to
 105  *            determine.
 106  */
 107 void * ptr_array_remove_index_ordered(ptr_array self, size_t index);
 108
 109 /* Remove an entry at a certain index from the array, preferring speed over
 110  * preserving order.
 111  *
 112  * Arguments: self, the pointer array.
 113  *            index, the position of the object to remove.
 114  * Result: the value which was removed, otherwise NULL. Note if the
 115  *            value removed is NULL, success is not possible to
 116  *            determine.
 117  */
 118 void * ptr_array_remove_index_fast(ptr_array self, size_t index);
 119
 120 /* Retrieve the pointer at a certain index.
 121  *
 122  * Arguments: self, the pointer array
 123  *            index, the position of the object to retrieve.
 124  * Result: the value which exists at the given index.
 125  */
 126 void * ptr_array_get_index(const ptr_array self, size_t index);
 127
 128 /* Modify the pointer at a certain index.
 129  *
 130  * Arguments: self, the pointer array
 131  *            index, the position of the object to overwrite
 132  *            value, the value to overwrite at the specified index
 133  * Result: the value which was at the index before.
 134  */
 135 void * ptr_array_set_index(ptr_array self, size_t index, const void *value);
 136
 137 /* Determine if the pointer array contains a particular value
 138  *
 139  * Arguments: self, the pointer array
 140  *            value, the value which is being searched for in the
 141  *            array.
 142  * Result: Non-zero if found, zero if not found.
 143  */
 144 int ptr_array_contains(const ptr_array self, const void *value);
 145
 146 /* Determine length (number of pointers) of the array.
 147  *
 148  * Arguments: self, the pointer array
 149  * Result: number of entries within the array.
 150  */
 151 static inline size_t ptr_array_length(const ptr_array self)
 152 {
 153   return self->length;
 154 }
 155
 156 /* Internal method for appending a value which causes array growth */
 157 int _ptr_array_growing_append(ptr_array self, const void *value);
 158
 159 /* Append a new value to the end of the array.
 160  *
 161  * Arguments: self, the pointer array
 162  *            value, the pointer to append at the end
 163  * Result: Non-zero on success, zero on failure.
 164  */
 165 static inline int ptr_array_append(ptr_array self, const void *value)
 166 {
 167         if (self->length == self->size)
 168                 return _ptr_array_growing_append(self, value);
 169
 170         self->array[self->length] = value;
 171         self->length++;
 172         return 1;
 173 }
 174
 175 /* Clear all entries from the array. This does not reduce the
 176  * array size.
 177  *
 178  * Arguments: self, the pointer array
 179  */
 180 void ptr_array_clear(ptr_array self);
 181 #endif