src/vector.h

   1 /*--- vector.h -----------------------------------------------------------------
   2 Copyright (C) 2004, 2005, 2006 Sylvain Fourmanoit <syfou@users.sourceforge.net>
   3
   4 Permission is hereby granted, free of charge, to any person obtaining a copy
   5 of this software and associated documentation files (the "Software"), to
   6 deal in the Software without restriction, including without limitation the
   7 rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   8 sell copies of the Software, and to permit persons to whom the Software is
   9 furnished to do so, subject to the following conditions:
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies of the Software and its documentation and acknowledgment shall be
  13 given in the documentation and software packages that this Software was
  14 used.
  15
  16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  19 THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  20 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22 ------------------------------------------------------------------------------*/
  23 /* This implements a minimalistic vector API with error checking,
  24    useful for storing dynamic collections of structures.
  25    STL does not exist in pure C!
  26
  27    Basically, what we call a vector here is only a dynamic array
  28    of references to undefined data structures (therefore cast to 'void')...
  29    As you see, it is pretty similar to a vector in STL, and you can
  30    expect the same kind of limitations. Please note that:
  31
  32         - vector_push and vector_pop are O(1), while vector_insert
  33         and vector_delete are O(n) at best.
  34
  35         - 'pos' and 'size' should never be modified by external
  36         routines. 'content' could, but using the limited API
  37         is better...Of course, you are totally on your own
  38         for the data itself.
  39
  40         - Data elements pushed or added into a vector should always
  41         be dynamically allocated OR the vector_free_item function
  42         pointer be redefined.
  43
  44         - If freeing data elements requires more than calling free(),
  45         the user should supply its own vector_free_item_func function,
  46         and store its reference into the vector_free_item field of
  47         the vector.
  48
  49         - Memory allocation/reallocation of the reference array
  50         is automatically taken care of.
  51
  52         - VECTOR_CHUNK macro should be modified for vectors
  53         of typically more than a couple references,
  54         because memory allocation calls would then become
  55         very expensive. Default value of 5 fits adesklets frugality!
  56 */
  57
  58 /*----------------------------------------------------------------------------*/
  59 #ifndef HAVE_VECTOR_H
  60 #define HAVE_VECTOR_H
  61
  62 #ifndef HAVE_CONFIG_H
  63 #error Autogenerated config.h should be used.
  64 #endif
  65
  66 /*----------------------------------------------------------------------------*/
  67 #include "config.h"                     /* Autoconf header */
  68
  69 #ifdef HAVE_STDLIB_H
  70 #include <stdlib.h>                     /* C includes: malloc, free, realloc */
  71 #endif
  72
  73 #include "types.h"                      /* Various typedef */
  74 #include "error.h"                      /* Error wrapper */
  75
  76 /*----------------------------------------------------------------------------*/
  77 #define VECTOR_CHUNK 5                  /* Number of additional elements */
  78                                         /* to allocate in one shot when
  79                                            more space is needed */
  80
  81 /*----------------------------------------------------------------------------*/
  82 typedef int (*vector_search_func) (void*,void*);
  83 typedef void * (*vector_free_item_func) (void*);
  84
  85 typedef struct s_vector {
  86   void ** content;                      /* Ref. to dynamic, unspecified data */
  87   uint pos,                             /* First unused element */
  88     size;                               /* Number of allocated ref. */
  89   vector_free_item_func                 /* The item freeing function */
  90     vector_free_item;
  91 } vector;
  92
  93 /*----------------------------------------------------------------------------*/
  94 /* Create a vector.
  95    Return the vector address, or NULL in case of failure.
  96    A default wrapping of free() is put in place as the vector_free_item
  97    function reference. Users needing different desallocation should
  98    overwrite it.
  99 */
 100 vector * vector_init(void);
 101
 102 /* Push a reference to an untyped element into a vector.
 103    Return 1 if successful, 0 otherwise.
 104 */
 105 int      vector_push(vector *, void *);
 106
 107 /* Pop the last reference out of a vector.
 108    Return 1 if successful, 0 otherwise.
 109 */
 110 int      vector_pop(vector *);
 111
 112 /* Insert a reference to a untyped element into a vector at a given position.
 113    Return 1 if successful, 0 otherwise.
 114 */
 115 int      vector_insert(vector *, uint, void *);
 116
 117 /* Delete a reference to a untyped element from a vector at a given position.
 118    Return 1 if successful, 0 otherwise.
 119 */
 120 int      vector_delete(vector *, uint);
 121
 122 /* Go through all the elements of a vector (from the first to the last)
 123    until the first that matches a critera according to a search function,
 124    passing an unspecified callback argument. Second argument will contain
 125    the index of matching element, if found.
 126    Return this element's address, or NULL if unfound.
 127 */
 128 void *   vector_find(vector *, uint *, vector_search_func, void*);
 129
 130 /* Destruct a vector.
 131    Returns NULL if successful, original vector otherwise.
 132 */
 133 vector * vector_free(vector *);
 134
 135 /*----------------------------------------------------------------------------*/
 136 #endif