src/vector.c

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