lib/vector.c

   1 /* Generic vector interface routine
   2  * Copyright (C) 1997 Kunihiro Ishiguro
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include <zebra.h>
  22
  23 #include "vector.h"
  24 #include "memory.h"
  25
  26 DEFINE_MTYPE_STATIC(LIB, VECTOR, "Vector")
  27 DEFINE_MTYPE_STATIC(LIB, VECTOR_INDEX, "Vector index")
  28
  29 /* Initialize vector : allocate memory and return vector. */
  30 vector vector_init(unsigned int size)
  31 {
  32         vector v = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector));
  33
  34         /* allocate at least one slot */
  35         if (size == 0)
  36                 size = 1;
  37
  38         v->alloced = size;
  39         v->active = 0;
  40         v->index = XCALLOC(MTYPE_VECTOR_INDEX, sizeof(void *) * size);
  41         return v;
  42 }
  43
  44 void vector_free(vector v)
  45 {
  46         XFREE(MTYPE_VECTOR_INDEX, v->index);
  47         XFREE(MTYPE_VECTOR, v);
  48 }
  49
  50 vector vector_copy(vector v)
  51 {
  52         unsigned int size;
  53         vector new = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector));
  54
  55         new->active = v->active;
  56         new->alloced = v->alloced;
  57
  58         size = sizeof(void *) * (v->alloced);
  59         new->index = XCALLOC(MTYPE_VECTOR_INDEX, size);
  60         memcpy(new->index, v->index, size);
  61
  62         return new;
  63 }
  64
  65 /* Check assigned index, and if it runs short double index pointer */
  66 void vector_ensure(vector v, unsigned int num)
  67 {
  68         if (v->alloced > num)
  69                 return;
  70
  71         v->index = XREALLOC(MTYPE_VECTOR_INDEX, v->index,
  72                             sizeof(void *) * (v->alloced * 2));
  73         memset(&v->index[v->alloced], 0, sizeof(void *) * v->alloced);
  74         v->alloced *= 2;
  75
  76         if (v->alloced <= num)
  77                 vector_ensure(v, num);
  78 }
  79
  80 /* This function only returns next empty slot index.  It dose not mean
  81    the slot's index memory is assigned, please call vector_ensure()
  82    after calling this function. */
  83 int vector_empty_slot(vector v)
  84 {
  85         unsigned int i;
  86
  87         if (v->active == 0)
  88                 return 0;
  89
  90         for (i = 0; i < v->active; i++)
  91                 if (v->index[i] == 0)
  92                         return i;
  93
  94         return i;
  95 }
  96
  97 /* Set value to the smallest empty slot. */
  98 int vector_set(vector v, void *val)
  99 {
 100         unsigned int i;
 101
 102         i = vector_empty_slot(v);
 103         vector_ensure(v, i);
 104
 105         v->index[i] = val;
 106
 107         if (v->active <= i)
 108                 v->active = i + 1;
 109
 110         return i;
 111 }
 112
 113 /* Set value to specified index slot. */
 114 int vector_set_index(vector v, unsigned int i, void *val)
 115 {
 116         vector_ensure(v, i);
 117
 118         v->index[i] = val;
 119
 120         if (v->active <= i)
 121                 v->active = i + 1;
 122
 123         return i;
 124 }
 125
 126 /* Look up vector.  */
 127 void *vector_lookup(vector v, unsigned int i)
 128 {
 129         if (i >= v->active)
 130                 return NULL;
 131         return v->index[i];
 132 }
 133
 134 /* Lookup vector, ensure it. */
 135 void *vector_lookup_ensure(vector v, unsigned int i)
 136 {
 137         vector_ensure(v, i);
 138         return v->index[i];
 139 }
 140
 141 /* Unset value at specified index slot. */
 142 void vector_unset(vector v, unsigned int i)
 143 {
 144         if (i >= v->alloced)
 145                 return;
 146
 147         v->index[i] = NULL;
 148
 149         if (i + 1 == v->active) {
 150                 v->active--;
 151                 while (i && v->index[--i] == NULL && v->active--)
 152                         ; /* Is this ugly ? */
 153         }
 154 }
 155
 156 void vector_remove(vector v, unsigned int ix)
 157 {
 158         if (ix >= v->active)
 159                 return;
 160
 161         int n = (--v->active) - ix;
 162
 163         memmove(&v->index[ix], &v->index[ix + 1], n * sizeof(void *));
 164         v->index[v->active] = NULL;
 165 }
 166
 167 void vector_compact(vector v)
 168 {
 169         for (unsigned int i = 0; i < vector_active(v); ++i) {
 170                 if (vector_slot(v, i) == NULL) {
 171                         vector_remove(v, i);
 172                         --i;
 173                 }
 174         }
 175 }
 176
 177 void vector_unset_value(vector v, void *val)
 178 {
 179         size_t i;
 180
 181         for (i = 0; i < v->active; i++)
 182                 if (v->index[i] == val) {
 183                         v->index[i] = NULL;
 184                         break;
 185                 }
 186
 187         if (i + 1 == v->active)
 188                 do
 189                         v->active--;
 190                 while (i && v->index[--i] == NULL);
 191 }
 192
 193 /* Count the number of not emplty slot. */
 194 unsigned int vector_count(vector v)
 195 {
 196         unsigned int i;
 197         unsigned count = 0;
 198
 199         for (i = 0; i < v->active; i++)
 200                 if (v->index[i] != NULL)
 201                         count++;
 202
 203         return count;
 204 }
 205
 206 void vector_to_array(vector v, void ***dest, int *argc)
 207 {
 208         *dest = XCALLOC(MTYPE_TMP, sizeof(void *) * v->active);
 209         memcpy(*dest, v->index, sizeof(void *) * v->active);
 210         *argc = v->active;
 211 }
 212
 213 vector array_to_vector(void **src, int argc)
 214 {
 215         vector v = vector_init(VECTOR_MIN_SIZE);
 216
 217         for (int i = 0; i < argc; i++)
 218                 vector_set_index(v, i, src[i]);
 219         return v;
 220 }