src/vector.c

   1 /*!
   2  * \file src/vector.c
   3  *
   4  * \brief Operations on vectors.
   5  *
   6  * \author this file, vector.c, was written and is
   7  * Copyright (c) 2001 C. Scott Ananian.
   8  *
   9  * <hr>
  10  *
  11  * <h1><b>Copyright.</b></h1>\n
  12  *
  13  * PCB, interactive printed circuit board design
  14  *
  15  * Copyright (C) 1994,1995,1996 Thomas Nau
  16  *
  17  * Copyright (C) 1998,1999,2000,2001 harry eaton
  18  *
  19  * This program is free software; you can redistribute it and/or modify
  20  * it under the terms of the GNU General Public License as published by
  21  * the Free Software Foundation; either version 2 of the License, or
  22  * (at your option) any later version.
  23  *
  24  * This program is distributed in the hope that it will be useful,
  25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  27  * GNU General Public License for more details.
  28  *
  29  * You should have received a copy of the GNU General Public License
  30  * along with this program; if not, write to the Free Software
  31  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  32  *
  33  * Contact addresses for paper mail and Email:
  34  *
  35  * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
  36  *
  37  * haceaton@aplcomm.jhuapl.edu
  38  */
  39
  40 #ifdef HAVE_CONFIG_H
  41 #include "config.h"
  42 #endif
  43
  44 #include <assert.h>
  45 #include <stdlib.h>
  46 #ifdef HAVE_STRING_H
  47 #include <string.h>
  48 #endif
  49
  50 #include "global.h"
  51 #include "vector.h"
  52
  53 #ifdef HAVE_LIBDMALLOC
  54 #include <dmalloc.h>
  55 #endif
  56
  57 /* ---------------------------------------------------------------------------
  58  * some local prototypes
  59  */
  60
  61 /* ---------------------------------------------------------------------------
  62  * some local types
  63  */
  64 struct vector_struct
  65 {
  66   vector_element_t *element;
  67   int size, max;
  68 };
  69
  70 /* ---------------------------------------------------------------------------
  71  * some local identifiers
  72  */
  73
  74 /* ---------------------------------------------------------------------------
  75  * functions.
  76  */
  77
  78 #ifndef NDEBUG
  79 /*!
  80  * \brief Helper function for assertions.
  81  */
  82 static int
  83 __vector_is_good (vector_t * vector)
  84 {
  85   return vector && (vector->max == 0 || vector->element) &&
  86     (vector->max >= 0) && (vector->size >= 0) &&
  87     (vector->size <= vector->max) && 1;
  88 }
  89 #endif /* !NDEBUG */
  90
  91 /*!
  92  * \brief Create an empty vector.
  93  */
  94 vector_t *
  95 vector_create ()
  96 {
  97   vector_t *vector;
  98   /* okay, create empty vector */
  99   vector = (vector_t *)calloc (1, sizeof (*vector));
 100   assert (vector);
 101   assert (__vector_is_good (vector));
 102   return vector;
 103 }
 104
 105 /*!
 106  * \brief Destroy a vector.
 107  */
 108 void
 109 vector_destroy (vector_t ** vector)
 110 {
 111   assert (vector && *vector);
 112   assert (__vector_is_good (*vector));
 113   if ((*vector)->element)
 114     free ((*vector)->element);
 115   free (*vector);
 116   *vector = NULL;
 117 }
 118
 119 /* -- interrogation -- */
 120 int
 121 vector_is_empty (vector_t * vector)
 122 {
 123   assert (__vector_is_good (vector));
 124   return (vector->size == 0);
 125 }
 126
 127 int
 128 vector_size (vector_t * vector)
 129 {
 130   assert (__vector_is_good (vector));
 131   return (vector->size);
 132 }
 133
 134 vector_element_t
 135 vector_element (vector_t * vector, int N)
 136 {
 137   assert (__vector_is_good (vector));
 138   assert (N < vector->size);
 139   return vector->element[N];
 140 }
 141
 142 /*!
 143  * \brief Return the first element of the vector.
 144  */
 145 vector_element_t
 146 vector_element_first (vector_t * vector)
 147 {
 148   assert (__vector_is_good (vector));
 149   assert (vector->size > 0);
 150   return vector_element (vector, 0);
 151 }
 152
 153 /*!
 154  * \brief Return the last element of the vector.
 155  */
 156 vector_element_t
 157 vector_element_last (vector_t * vector)
 158 {
 159   assert (__vector_is_good (vector));
 160   assert (vector->size > 0);
 161   return vector_element (vector, vector->size - 1);
 162 }
 163
 164 /* -- mutation -- */
 165 /*!
 166  * \brief Add data to end of vector.
 167  */
 168 void
 169 vector_append (vector_t * vector, vector_element_t data)
 170 {
 171   vector_insert_many (vector, vector->size, &data, 1);
 172 }
 173
 174 /*!
 175  * \brief Add multiple elements to end of vector.
 176  */
 177 void
 178 vector_append_many (vector_t * vector, vector_element_t data[], int count)
 179 {
 180   vector_insert_many (vector, vector->size, data, count);
 181 }
 182
 183 /*!
 184  * \brief Add a vector of elements to the end of vector.
 185  */
 186 void
 187 vector_append_vector (vector_t * vector, vector_t * other_vector)
 188 {
 189   vector_append_many (vector, other_vector->element, other_vector->size);
 190 }
 191
 192 /*!
 193  * \brief Add data at specified position of vector.
 194  */
 195 void
 196 vector_insert (vector_t * vector, int N, vector_element_t data)
 197 {
 198   vector_insert_many (vector, N, &data, 1);
 199 }
 200
 201 /*!
 202  * \brief Add data at specified position of vector.
 203  */
 204 void
 205 vector_insert_many (vector_t * vector, int N,
 206                     vector_element_t data[], int count)
 207 {
 208   assert (__vector_is_good (vector));
 209   assert (N <= vector->size);
 210   if (count == 0)
 211     return;
 212   assert (data && count > 0);
 213   if (vector->size + count > vector->max)
 214     {
 215       vector->max = MAX (32, MAX (vector->size + count, vector->max * 2));
 216       vector->element = (void **)realloc (vector->element,
 217                                  vector->max * sizeof (*vector->element));
 218     }
 219   memmove (vector->element + N + count, vector->element + N,
 220            (vector->size - N) * sizeof (*vector->element));
 221   memmove (vector->element + N, data, count * sizeof (*data));
 222   vector->size += count;
 223   assert (__vector_is_good (vector));
 224 }
 225
 226 /*!
 227  * \brief Copy a vector.
 228  */
 229 vector_t *
 230 vector_duplicate (vector_t * orig)
 231 {
 232   vector_t * newone = vector_create();
 233   if (!orig)
 234     return newone;
 235   newone->element = (void **)malloc (orig->max * sizeof (*orig->element));
 236   newone->max = orig->max;
 237   newone->size = orig->size;
 238   memcpy (newone->element, orig->element, orig->size * sizeof (vector_element_t));
 239   assert (__vector_is_good (newone));
 240   return newone;
 241 }
 242
 243 /*!
 244  * \brief Return and delete the *last* element of vector.
 245  */
 246 vector_element_t
 247 vector_remove_last (vector_t * vector)
 248 {
 249   assert (vector->size > 0);
 250   return vector_remove (vector, vector->size - 1);
 251 }
 252
 253 /*!
 254  * \brief Rreturn and delete data at specified position of vector.
 255  */
 256 vector_element_t
 257 vector_remove (vector_t * vector, int N)
 258 {
 259   vector_element_t old;
 260   assert (__vector_is_good (vector));
 261   assert (N < vector->size);
 262   old = vector->element[N];
 263   memmove (vector->element + N, vector->element + N + 1,
 264            (vector->size - (N + 1)) * sizeof (*vector->element));
 265   vector->size--;
 266   assert (__vector_is_good (vector));
 267   return old;
 268 }
 269
 270 /*!
 271  * \brief Replace the data at the specified position with the given
 272  * data.
 273  *
 274  * \return the old data.
 275  */
 276 vector_element_t
 277 vector_replace (vector_t * vector, vector_element_t data, int N)
 278 {
 279   vector_element_t old;
 280   assert (__vector_is_good (vector));
 281   assert (N < vector->size);
 282   old = vector->element[N];
 283   vector->element[N] = data;
 284   assert (__vector_is_good (vector));
 285   return old;
 286 }