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