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
  31 vector_init (unsigned int size)
  32 {
  33   vector v = XCALLOC (MTYPE_VECTOR, sizeof (struct _vector));
  34
  35   /* allocate at least one slot */
  36   if (size == 0)
  37     size = 1;
  38
  39   v->alloced = size;
  40   v->active = 0;
  41   v->index = XCALLOC (MTYPE_VECTOR_INDEX, sizeof (void *) * size);
  42   return v;
  43 }
  44
  45 void
  46 vector_free (vector v)
  47 {
  48   XFREE (MTYPE_VECTOR_INDEX, v->index);
  49   XFREE (MTYPE_VECTOR, v);
  50 }
  51
  52 vector
  53 vector_copy (vector v)
  54 {
  55   unsigned int size;
  56   vector new = XCALLOC (MTYPE_VECTOR, sizeof (struct _vector));
  57
  58   new->active = v->active;
  59   new->alloced = v->alloced;
  60
  61   size = sizeof (void *) * (v->alloced);
  62   new->index = XCALLOC (MTYPE_VECTOR_INDEX, size);
  63   memcpy (new->index, v->index, size);
  64
  65   return new;
  66 }
  67
  68 /* Check assigned index, and if it runs short double index pointer */
  69 void
  70 vector_ensure (vector v, unsigned int num)
  71 {
  72   if (v->alloced > num)
  73     return;
  74
  75   v->index = XREALLOC (MTYPE_VECTOR_INDEX,
  76                        v->index, sizeof (void *) * (v->alloced * 2));
  77   memset (&v->index[v->alloced], 0, sizeof (void *) * v->alloced);
  78   v->alloced *= 2;
  79
  80   if (v->alloced <= num)
  81     vector_ensure (v, num);
  82 }
  83
  84 /* This function only returns next empty slot index.  It dose not mean
  85    the slot's index memory is assigned, please call vector_ensure()
  86    after calling this function. */
  87 int
  88 vector_empty_slot (vector v)
  89 {
  90   unsigned int i;
  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
 104 vector_set (vector v, void *val)
 105 {
 106   unsigned int i;
 107
 108   i = vector_empty_slot (v);
 109   vector_ensure (v, i);
 110
 111   v->index[i] = val;
 112
 113   if (v->active <= i)
 114     v->active = i + 1;
 115
 116   return i;
 117 }
 118
 119 /* Set value to specified index slot. */
 120 int
 121 vector_set_index (vector v, unsigned int i, void *val)
 122 {
 123   vector_ensure (v, i);
 124
 125   v->index[i] = val;
 126
 127   if (v->active <= i)
 128     v->active = i + 1;
 129
 130   return i;
 131 }
 132
 133 /* Look up vector.  */
 134 void *
 135 vector_lookup (vector v, unsigned int i)
 136 {
 137   if (i >= v->active)
 138     return NULL;
 139   return v->index[i];
 140 }
 141
 142 /* Lookup vector, ensure it. */
 143 void *
 144 vector_lookup_ensure (vector v, unsigned int i)
 145 {
 146   vector_ensure (v, i);
 147   return v->index[i];
 148 }
 149
 150 /* Unset value at specified index slot. */
 151 void
 152 vector_unset (vector v, unsigned int i)
 153 {
 154   if (i >= v->alloced)
 155     return;
 156
 157   v->index[i] = NULL;
 158
 159   if (i + 1 == v->active)
 160     {
 161       v->active--;
 162       while (i && v->index[--i] == NULL && v->active--)
 163         ;                               /* Is this ugly ? */
 164     }
 165 }
 166
 167 void
 168 vector_unset_value (vector v, void *val)
 169 {
 170   size_t i;
 171
 172   for (i = 0; i < v->active; i++)
 173     if (v->index[i] == val)
 174       {
 175         v->index[i] = NULL;
 176         break;
 177       }
 178
 179   if (i + 1 == v->active)
 180     do
 181       v->active--;
 182     while (i && v->index[--i] == NULL);
 183 }
 184
 185 /* Count the number of not emplty slot. */
 186 unsigned int
 187 vector_count (vector v)
 188 {
 189   unsigned int i;
 190   unsigned count = 0;
 191
 192   for (i = 0; i < v->active; i++)
 193     if (v->index[i] != NULL)
 194       count++;
 195
 196   return count;
 197 }