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 /* Look up vector.  */
 140 void *vector_lookup(vector v, unsigned int i)
 141 {
 142         if (i >= v->active)
 143                 return NULL;
 144         return v->index[i];
 145 }
 146
 147 /* Lookup vector, ensure it. */
 148 void *vector_lookup_ensure(vector v, unsigned int i)
 149 {
 150         vector_ensure(v, i);
 151         return v->index[i];
 152 }
 153
 154 /* Unset value at specified index slot. */
 155 void vector_unset(vector v, unsigned int i)
 156 {
 157         if (i >= v->alloced)
 158                 return;
 159
 160         if (v->index[i])
 161                 v->count--;
 162
 163         v->index[i] = NULL;
 164
 165         if (i + 1 == v->active) {
 166                 v->active--;
 167                 while (i && v->index[--i] == NULL && v->active--)
 168                         ; /* Is this ugly ? */
 169         }
 170 }
 171
 172 void vector_remove(vector v, unsigned int ix)
 173 {
 174         if (ix >= v->active)
 175                 return;
 176
 177         if (v->index[ix])
 178                 v->count--;
 179
 180         int n = (--v->active) - ix;
 181
 182         memmove(&v->index[ix], &v->index[ix + 1], n * sizeof(void *));
 183         v->index[v->active] = NULL;
 184 }
 185
 186 void vector_compact(vector v)
 187 {
 188         for (unsigned int i = 0; i < vector_active(v); ++i) {
 189                 if (vector_slot(v, i) == NULL) {
 190                         vector_remove(v, i);
 191                         --i;
 192                 }
 193         }
 194 }
 195
 196 void vector_unset_value(vector v, void *val)
 197 {
 198         size_t i;
 199
 200         for (i = 0; i < v->active; i++)
 201                 if (v->index[i] == val) {
 202                         v->index[i] = NULL;
 203                         v->count--;
 204                         break;
 205                 }
 206
 207         if (i + 1 == v->active)
 208                 do
 209                         v->active--;
 210                 while (i && v->index[--i] == NULL);
 211 }
 212
 213 void vector_to_array(vector v, void ***dest, int *argc)
 214 {
 215         *dest = XCALLOC(MTYPE_TMP, sizeof(void *) * v->active);
 216         memcpy(*dest, v->index, sizeof(void *) * v->active);
 217         *argc = v->active;
 218 }
 219
 220 vector array_to_vector(void **src, int argc)
 221 {
 222         vector v = vector_init(VECTOR_MIN_SIZE);
 223
 224         for (int i = 0; i < argc; i++)
 225                 vector_set_index(v, i, src[i]);
 226         return v;
 227 }