src/vppinfra/vec.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #include <vppinfra/vec.h>
  39 #include <vppinfra/mem.h>
  40
  41 #ifndef CLIB_VECTOR_GROW_BY_ONE
  42 #define CLIB_VECTOR_GROW_BY_ONE 0
  43 #endif
  44
  45 /* Vector resize operator.  Called as needed by various macros such as
  46    vec_add1() when we need to allocate memory. */
  47 __clib_export void *
  48 vec_resize_allocate_memory (void *v, word length_increment, uword data_bytes,
  49                             uword header_bytes, uword data_align)
  50 {
  51   vec_header_t *vh = _vec_find (v);
  52   uword old_alloc_bytes, new_alloc_bytes;
  53   void *old, *new;
  54
  55   header_bytes = vec_header_bytes (header_bytes);
  56   data_align = data_align == 0 ? 1 : data_align;
  57
  58   data_bytes += header_bytes;
  59
  60   /* alignment must be power of 2 */
  61   ASSERT (count_set_bits (data_align) == 1);
  62
  63   if (!v)
  64     {
  65       new = clib_mem_alloc_aligned_at_offset (data_bytes, data_align, header_bytes, 1   /* yes, call os_out_of_memory */
  66         );
  67       new_alloc_bytes = clib_mem_size (new);
  68       CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes);
  69       clib_memset (new, 0, new_alloc_bytes);
  70       CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes);
  71       v = new + header_bytes;
  72       _vec_len (v) = length_increment;
  73       ASSERT (header_bytes / VEC_HEADER_ROUND <= 255);
  74       _vec_find (v)->hdr_size = header_bytes / VEC_HEADER_ROUND;
  75       _vec_find (v)->log2_align = min_log2 (data_align);
  76       return v;
  77     }
  78
  79   ASSERT (_vec_find (v)->hdr_size * VEC_HEADER_ROUND == header_bytes);
  80   header_bytes = _vec_find (v)->hdr_size * VEC_HEADER_ROUND;
  81
  82   ASSERT (data_align == (1 << _vec_find (v)->log2_align));
  83   data_align = 1 << _vec_find (v)->log2_align;
  84
  85   vh->len += length_increment;
  86   old = v - header_bytes;
  87
  88   /* Vector header must start heap object. */
  89   ASSERT (clib_mem_is_heap_object (old));
  90
  91   old_alloc_bytes = clib_mem_size (old);
  92
  93   /* Need to resize? */
  94   if (data_bytes <= old_alloc_bytes)
  95     {
  96       CLIB_MEM_UNPOISON (v, data_bytes);
  97       return v;
  98     }
  99
 100 #if CLIB_VECTOR_GROW_BY_ONE > 0
 101   new_alloc_bytes = data_bytes;
 102 #else
 103   new_alloc_bytes = (old_alloc_bytes * 3) / 2;
 104   if (new_alloc_bytes < data_bytes)
 105     new_alloc_bytes = data_bytes;
 106 #endif
 107
 108   new =
 109     clib_mem_alloc_aligned_at_offset (new_alloc_bytes, data_align,
 110                                       header_bytes,
 111                                       1 /* yes, call os_out_of_memory */ );
 112
 113   /* FIXME fail gracefully. */
 114   if (!new)
 115     clib_panic
 116       ("vec_resize fails, length increment %d, data bytes %d, alignment %d",
 117        length_increment, data_bytes, data_align);
 118
 119   CLIB_MEM_UNPOISON (old, old_alloc_bytes);
 120   clib_memcpy_fast (new, old, old_alloc_bytes);
 121   clib_mem_free (old);
 122
 123   /* Allocator may give a bit of extra room. */
 124   new_alloc_bytes = clib_mem_size (new);
 125   v = new;
 126
 127   /* Zero new memory. */
 128   CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes);
 129   memset (v + old_alloc_bytes, 0, new_alloc_bytes - old_alloc_bytes);
 130   CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes);
 131
 132   return v + header_bytes;
 133 }
 134
 135 __clib_export u32
 136 vec_len_not_inline (void *v)
 137 {
 138   return vec_len (v);
 139 }
 140
 141 __clib_export void
 142 vec_free_not_inline (void *v)
 143 {
 144   vec_free (v);
 145 }
 146
 147 /** \cond */
 148
 149 #ifdef TEST
 150
 151 #include <stdio.h>
 152
 153 void
 154 main (int argc, char *argv[])
 155 {
 156   word n = atoi (argv[1]);
 157   word i, *x = 0;
 158
 159   typedef struct
 160   {
 161     word x, y, z;
 162   } FOO;
 163
 164   FOO *foos = vec_init (FOO, 10), *f;
 165
 166   vec_validate (foos, 100);
 167   foos[100].x = 99;
 168
 169   _vec_len (foos) = 0;
 170   for (i = 0; i < n; i++)
 171     {
 172       vec_add1 (x, i);
 173       vec_add2 (foos, f, 1);
 174       f->x = 2 * i;
 175       f->y = 3 * i;
 176       f->z = 4 * i;
 177     }
 178
 179   {
 180     word n = 2;
 181     word m = 42;
 182     vec_delete (foos, n, m);
 183   }
 184
 185   {
 186     word n = 2;
 187     word m = 42;
 188     vec_insert (foos, n, m);
 189   }
 190
 191   vec_free (x);
 192   vec_free (foos);
 193   exit (0);
 194 }
 195 #endif
 196 /** \endcond */
 197
 198 /*
 199  * fd.io coding-style-patch-verification: ON
 200  *
 201  * Local Variables:
 202  * eval: (c-set-style "gnu")
 203  * End:
 204  */