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