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->count = 0;
  41         v->index = XCALLOC(MTYPE_VECTOR_INDEX, sizeof(void *) * size);
  42         return v;
  43 }
  44
  45 void vector_free(vector v)
  46 {
  47         XFREE(MTYPE_VECTOR_INDEX, v->index);
  48         XFREE(MTYPE_VECTOR, v);
  49 }
  50
  51 vector vector_copy(vector v)
  52 {
  53         unsigned int size;
  54         vector new = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector));
  55
  56         new->active = v->active;
  57         new->alloced = v->alloced;
  58         new->count = v->count;
  59
  60         size = sizeof(void *) * (v->alloced);
  61         new->index = XCALLOC(MTYPE_VECTOR_INDEX, size);
  62         memcpy(new->index, v->index, size);
  63
  64         return new;
  65 }
  66
  67 /* Check assigned index, and if it runs short double index pointer */
  68 void vector_ensure(vector v, unsigned int num)
  69 {
  70         if (v->alloced > num)
  71                 return;
  72
  73         v->index = XREALLOC(MTYPE_VECTOR_INDEX, v->index,
  74                             sizeof(void *) * (v->alloced * 2));
  75         memset(&v->index[v->alloced], 0, sizeof(void *) * v->alloced);
  76         v->alloced *= 2;
  77
  78         if (v->alloced <= num)
  79                 vector_ensure(v, num);
  80 }
  81
  82 /* This function only returns next empty slot index.  It dose not mean
  83    the slot's index memory is assigned, please call vector_ensure()
  84    after calling this function. */
  85 int vector_empty_slot(vector v)
  86 {
  87         unsigned int i;
  88
  89         if (v->active == v->count)
  90                 return v->active;
  91
  92         if (v->active == 0)
  93                 return 0;
  94
  95         for (i = 0; i < v->active; i++)
  96                 if (v->index[i] == 0)
  97                         return i;
  98
  99         return i;
 100 }
 101
 102 /* Set value to the smallest empty slot. */
 103 int vector_set(vector v, void *val)
 104 {
 105         unsigned int i;
 106
 107         i = vector_empty_slot(v);
 108         vector_ensure(v, i);
 109
 110         if (v->index[i])
 111                 v->count--;
 112         if (val)
 113                 v->count++;
 114         v->index[i] = val;
 115
 116         if (v->active <= i)
 117                 v->active = i + 1;
 118
 119         return i;
 120 }
 121
 122 /* Set value to specified index slot. */
 123 int vector_set_index(vector v, unsigned int i, void *val)
 124 {
 125         vector_ensure(v, i);
 126
 127         if (v->index[i])
 128                 v->count--;
 129         if (val)
 130                 v->count++;
 131         v->index[i] = val;
 132
 133         if (v->active <= i)
 134                 v->active = i + 1;
 135
 136         return i;
 137 }
 138
 139 /* Make a specified index slot active and return its address. */
 140 void **vector_get_index(vector v, unsigned int i)
 141 {
 142         vector_ensure(v, i);
 143
 144         if (v->active <= i)
 145                 v->active = i + 1;
 146
 147         return &v->index[i];
 148 }
 149
 150 /* Look up vector.  */
 151 void *vector_lookup(vector v, unsigned int i)
 152 {
 153         if (i >= v->active)
 154                 return NULL;
 155         return v->index[i];
 156 }
 157
 158 /* Lookup vector, ensure it. */
 159 void *vector_lookup_ensure(vector v, unsigned int i)
 160 {
 161         vector_ensure(v, i);
 162         return v->index[i];
 163 }
 164
 165 /* Unset value at specified index slot. */
 166 void vector_unset(vector v, unsigned int i)
 167 {
 168         if (i >= v->alloced)
 169                 return;
 170
 171         if (v->index[i])
 172                 v->count--;
 173
 174         v->index[i] = NULL;
 175
 176         if (i + 1 == v->active) {
 177                 v->active--;
 178                 while (i && v->index[--i] == NULL && v->active--)
 179                         ; /* Is this ugly ? */
 180         }
 181 }
 182
 183 void vector_remove(vector v, unsigned int ix)
 184 {
 185         if (ix >= v->active)
 186                 return;
 187
 188         if (v->index[ix])
 189                 v->count--;
 190
 191         int n = (--v->active) - ix;
 192
 193         memmove(&v->index[ix], &v->index[ix + 1], n * sizeof(void *));
 194         v->index[v->active] = NULL;
 195 }
 196
 197 void vector_compact(vector v)
 198 {
 199         for (unsigned int i = 0; i < vector_active(v); ++i) {
 200                 if (vector_slot(v, i) == NULL) {
 201                         vector_remove(v, i);
 202                         --i;
 203                 }
 204         }
 205 }
 206
 207 void vector_unset_value(vector v, void *val)
 208 {
 209         size_t i;
 210
 211         for (i = 0; i < v->active; i++)
 212                 if (v->index[i] == val) {
 213                         v->index[i] = NULL;
 214                         v->count--;
 215                         break;
 216                 }
 217
 218         if (i + 1 == v->active)
 219                 do
 220                         v->active--;
 221                 while (i && v->index[--i] == NULL);
 222 }
 223
 224 void vector_to_array(vector v, void ***dest, int *argc)
 225 {
 226         *dest = XCALLOC(MTYPE_TMP, sizeof(void *) * v->active);
 227         memcpy(*dest, v->index, sizeof(void *) * v->active);
 228         *argc = v->active;
 229 }
 230
 231 vector array_to_vector(void **src, int argc)
 232 {
 233         vector v = vector_init(VECTOR_MIN_SIZE);
 234
 235         for (int i = 0; i < argc; i++)
 236                 vector_set_index(v, i, src[i]);
 237         return v;
 238 }