src/vector.c

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