Line data    Source code

       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         670 : DEFINE_MTYPE_STATIC(LIB, VECTOR, "Vector");
      27         670 : DEFINE_MTYPE_STATIC(LIB, VECTOR_INDEX, "Vector index");
      28             : 
      29             : /* Initialize vector : allocate memory and return vector. */
      30     5603064 : vector vector_init(unsigned int size)
      31             : {
      32     5603064 :         vector v = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector));
      33             : 
      34             :         /* allocate at least one slot */
      35     5603064 :         if (size == 0)
      36             :                 size = 1;
      37             : 
      38     5603064 :         v->alloced = size;
      39     5603064 :         v->active = 0;
      40     5603064 :         v->count = 0;
      41     5603064 :         v->index = XCALLOC(MTYPE_VECTOR_INDEX, sizeof(void *) * size);
      42     5603064 :         return v;
      43             : }
      44             : 
      45     5291468 : void vector_free(vector v)
      46             : {
      47     5291468 :         XFREE(MTYPE_VECTOR_INDEX, v->index);
      48     5291468 :         XFREE(MTYPE_VECTOR, v);
      49     5291468 : }
      50             : 
      51           0 : vector vector_copy(vector v)
      52             : {
      53           0 :         unsigned int size;
      54           0 :         vector new = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector));
      55             : 
      56           0 :         new->active = v->active;
      57           0 :         new->alloced = v->alloced;
      58           0 :         new->count = v->count;
      59             : 
      60           0 :         size = sizeof(void *) * (v->alloced);
      61           0 :         new->index = XCALLOC(MTYPE_VECTOR_INDEX, size);
      62           0 :         memcpy(new->index, v->index, size);
      63             : 
      64           0 :         return new;
      65             : }
      66             : 
      67             : /* Check assigned index, and if it runs short double index pointer */
      68    10857397 : void vector_ensure(vector v, unsigned int num)
      69             : {
      70    10857849 :         if (v->alloced > num)
      71             :                 return;
      72             : 
      73     1859181 :         v->index = XREALLOC(MTYPE_VECTOR_INDEX, v->index,
      74             :                             sizeof(void *) * (v->alloced * 2));
      75     1859181 :         memset(&v->index[v->alloced], 0, sizeof(void *) * v->alloced);
      76     1859181 :         v->alloced *= 2;
      77             : 
      78     1859181 :         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    10826318 : int vector_empty_slot(vector v)
      86             : {
      87    10826318 :         unsigned int i;
      88             : 
      89    10826318 :         if (v->active == v->count)
      90    10582732 :                 return v->active;
      91             : 
      92      243586 :         if (v->active == 0)
      93             :                 return 0;
      94             : 
      95        2206 :         for (i = 0; i < v->active; i++)
      96        1103 :                 if (v->index[i] == 0)
      97           0 :                         return i;
      98             : 
      99        1103 :         return i;
     100             : }
     101             : 
     102             : /* Set value to the smallest empty slot. */
     103    10826318 : int vector_set(vector v, void *val)
     104             : {
     105    10826318 :         unsigned int i;
     106             : 
     107    10826318 :         i = vector_empty_slot(v);
     108    10826318 :         vector_ensure(v, i);
     109             : 
     110    10826318 :         if (v->index[i])
     111           0 :                 v->count--;
     112    10826318 :         if (val)
     113    10826318 :                 v->count++;
     114    10826318 :         v->index[i] = val;
     115             : 
     116    10826318 :         if (v->active <= i)
     117    10826318 :                 v->active = i + 1;
     118             : 
     119    10826318 :         return i;
     120             : }
     121             : 
     122             : /* Set value to specified index slot. */
     123       31079 : int vector_set_index(vector v, unsigned int i, void *val)
     124             : {
     125       31079 :         vector_ensure(v, i);
     126             : 
     127       31079 :         if (v->index[i])
     128           0 :                 v->count--;
     129       31079 :         if (val)
     130       31079 :                 v->count++;
     131       31079 :         v->index[i] = val;
     132             : 
     133       31079 :         if (v->active <= i)
     134       25869 :                 v->active = i + 1;
     135             : 
     136       31079 :         return i;
     137             : }
     138             : 
     139             : /* Look up vector.  */
     140      267352 : void *vector_lookup(vector v, unsigned int i)
     141             : {
     142      267352 :         if (i >= v->active)
     143             :                 return NULL;
     144      267352 :         return v->index[i];
     145             : }
     146             : 
     147             : /* Lookup vector, ensure it. */
     148           0 : void *vector_lookup_ensure(vector v, unsigned int i)
     149             : {
     150           0 :         vector_ensure(v, i);
     151           0 :         return v->index[i];
     152             : }
     153             : 
     154             : /* Unset value at specified index slot. */
     155     1657054 : void vector_unset(vector v, unsigned int i)
     156             : {
     157     1657054 :         if (i >= v->alloced)
     158             :                 return;
     159             : 
     160     1657054 :         if (v->index[i])
     161     1654787 :                 v->count--;
     162             : 
     163     1657054 :         v->index[i] = NULL;
     164             : 
     165     1657054 :         if (i + 1 == v->active) {
     166      317351 :                 v->active--;
     167     1657054 :                 while (i && v->index[--i] == NULL && v->active--)
     168             :                         ; /* Is this ugly ? */
     169             :         }
     170             : }
     171             : 
     172           0 : void vector_remove(vector v, unsigned int ix)
     173             : {
     174           0 :         if (ix >= v->active)
     175             :                 return;
     176             : 
     177           0 :         if (v->index[ix])
     178           0 :                 v->count--;
     179             : 
     180           0 :         int n = (--v->active) - ix;
     181             : 
     182           0 :         memmove(&v->index[ix], &v->index[ix + 1], n * sizeof(void *));
     183           0 :         v->index[v->active] = NULL;
     184             : }
     185             : 
     186        5452 : void vector_compact(vector v)
     187             : {
     188       21991 :         for (unsigned int i = 0; i < vector_active(v); ++i) {
     189       16539 :                 if (vector_slot(v, i) == NULL) {
     190           0 :                         vector_remove(v, i);
     191           0 :                         --i;
     192             :                 }
     193             :         }
     194        5452 : }
     195             : 
     196           0 : void vector_unset_value(vector v, void *val)
     197             : {
     198           0 :         size_t i;
     199             : 
     200           0 :         for (i = 0; i < v->active; i++)
     201           0 :                 if (v->index[i] == val) {
     202           0 :                         v->index[i] = NULL;
     203           0 :                         v->count--;
     204           0 :                         break;
     205             :                 }
     206             : 
     207           0 :         if (i + 1 == v->active)
     208           0 :                 do
     209           0 :                         v->active--;
     210           0 :                 while (i && v->index[--i] == NULL);
     211           0 : }
     212             : 
     213           0 : void vector_to_array(vector v, void ***dest, int *argc)
     214             : {
     215           0 :         *dest = XCALLOC(MTYPE_TMP, sizeof(void *) * v->active);
     216           0 :         memcpy(*dest, v->index, sizeof(void *) * v->active);
     217           0 :         *argc = v->active;
     218           0 : }
     219             : 
     220        5452 : vector array_to_vector(void **src, int argc)
     221             : {
     222        5452 :         vector v = vector_init(VECTOR_MIN_SIZE);
     223             : 
     224       24258 :         for (int i = 0; i < argc; i++)
     225       18806 :                 vector_set_index(v, i, src[i]);
     226        5452 :         return v;
     227             : }