lib/vector.c

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