1/***************************************************************************** 2 3Copyright (c) 2006, 2019, Oracle and/or its affiliates. All Rights Reserved. 4 5This program is free software; you can redistribute it and/or modify it under 6the terms of the GNU General Public License, version 2.0, as published by the 7Free Software Foundation. 8 9This program is also distributed with certain software (including but not 10limited to OpenSSL) that is licensed under separate terms, as designated in a 11particular file or component or in included license documentation. The authors 12of MySQL hereby grant you an additional permission to link the program and 13your derivative works with the separately licensed software that they have 14included with MySQL. 15 16This program is distributed in the hope that it will be useful, but WITHOUT 17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0, 19for more details. 20 21You should have received a copy of the GNU General Public License along with 22this program; if not, write to the Free Software Foundation, Inc., 2351 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 24 25*****************************************************************************/ 26 27/** @file include/ut0vec.ic 28 A vector of pointers to data items 29 30 Created 4/6/2006 Osku Salerma 31 ************************************************************************/ 32 33#include "ut0new.h" 34 35#define IB_VEC_OFFSET(v, i) (vec->sizeof_value * i) 36 37/******************************************************************** 38The default ib_vector_t heap malloc. Uses mem_heap_alloc(). */ 39UNIV_INLINE 40void *ib_heap_malloc(ib_alloc_t *allocator, /* in: allocator */ 41 ulint size) /* in: size in bytes */ 42{ 43 mem_heap_t *heap = (mem_heap_t *)allocator->arg; 44 45 return (mem_heap_alloc(heap, size)); 46} 47 48/******************************************************************** 49The default ib_vector_t heap free. Does nothing. */ 50UNIV_INLINE 51void ib_heap_free(ib_alloc_t *allocator UNIV_UNUSED, /* in: allocator */ 52 void *ptr UNIV_UNUSED) /* in: size in bytes */ 53{ 54 /* We can't free individual elements. */ 55} 56 57/******************************************************************** 58The default ib_vector_t heap resize. Since we can't resize the heap 59we have to copy the elements from the old ptr to the new ptr. 60We always assume new_size >= old_size, so the buffer won't overflow. 61Uses mem_heap_alloc(). */ 62UNIV_INLINE 63void *ib_heap_resize(ib_alloc_t *allocator, /* in: allocator */ 64 void *old_ptr, /* in: pointer to memory */ 65 ulint old_size, /* in: old size in bytes */ 66 ulint new_size) /* in: new size in bytes */ 67{ 68 void *new_ptr; 69 mem_heap_t *heap = (mem_heap_t *)allocator->arg; 70 71 ut_a(new_size >= old_size); 72 new_ptr = mem_heap_alloc(heap, new_size); 73 memcpy(new_ptr, old_ptr, old_size); 74 75 return (new_ptr); 76} 77 78/******************************************************************** 79Create a heap allocator that uses the passed in heap. */ 80UNIV_INLINE 81ib_alloc_t *ib_heap_allocator_create(mem_heap_t *heap) /* in: heap to use */ 82{ 83 ib_alloc_t *heap_alloc; 84 85 heap_alloc = (ib_alloc_t *)mem_heap_alloc(heap, sizeof(*heap_alloc)); 86 87 heap_alloc->arg = heap; 88 heap_alloc->mem_release = ib_heap_free; 89 heap_alloc->mem_malloc = ib_heap_malloc; 90 heap_alloc->mem_resize = ib_heap_resize; 91 92 return (heap_alloc); 93} 94 95/******************************************************************** 96Free a heap allocator. */ 97UNIV_INLINE 98void ib_heap_allocator_free( 99 ib_alloc_t *ib_ut_alloc) /* in: alloc instace to free */ 100{ 101 mem_heap_free((mem_heap_t *)ib_ut_alloc->arg); 102} 103 104/******************************************************************** 105Get number of elements in vector. */ 106UNIV_INLINE 107ulint ib_vector_size( 108 /* out: number of elements in vector*/ 109 const ib_vector_t *vec) /* in: vector */ 110{ 111 return (vec->used); 112} 113 114/** Get n'th element. */ 115UNIV_INLINE 116void *ib_vector_get(ib_vector_t *vec, /*!< in: vector */ 117 ulint n) /*!< in: element index to get */ 118{ 119 ut_a(n < vec->used); 120 121 return ((byte *)vec->data + IB_VEC_OFFSET(vec, n)); 122} 123 124/******************************************************************** 125Const version of the get n'th element. 126@return n'th element */ 127UNIV_INLINE 128const void *ib_vector_get_const(const ib_vector_t *vec, /* in: vector */ 129 ulint n) /* in: element index to get */ 130{ 131 ut_a(n < vec->used); 132 133 return ((byte *)vec->data + IB_VEC_OFFSET(vec, n)); 134} 135/** Get last element. The vector must not be empty. 136 @return last element */ 137UNIV_INLINE 138void *ib_vector_get_last(ib_vector_t *vec) /*!< in: vector */ 139{ 140 ut_a(vec->used > 0); 141 142 return ((byte *)ib_vector_get(vec, vec->used - 1)); 143} 144 145/** Set the n'th element. */ 146UNIV_INLINE 147void ib_vector_set(ib_vector_t *vec, /*!< in/out: vector */ 148 ulint n, /*!< in: element index to set */ 149 void *elem) /*!< in: data element */ 150{ 151 void *slot; 152 153 ut_a(n < vec->used); 154 155 slot = ((byte *)vec->data + IB_VEC_OFFSET(vec, n)); 156 memcpy(slot, elem, vec->sizeof_value); 157} 158 159/******************************************************************** 160Reset the vector size to 0 elements. */ 161UNIV_INLINE 162void ib_vector_reset( 163 /* out: void */ 164 ib_vector_t *vec) /* in: vector */ 165{ 166 vec->used = 0; 167} 168 169/******************************************************************** 170Get the last element of the vector. */ 171UNIV_INLINE 172void *ib_vector_last( 173 /* out: void */ 174 ib_vector_t *vec) /* in: vector */ 175{ 176 ut_a(ib_vector_size(vec) > 0); 177 178 return (ib_vector_get(vec, ib_vector_size(vec) - 1)); 179} 180 181/******************************************************************** 182Get the last element of the vector. */ 183UNIV_INLINE 184const void *ib_vector_last_const( 185 /* out: void */ 186 const ib_vector_t *vec) /* in: vector */ 187{ 188 ut_a(ib_vector_size(vec) > 0); 189 190 return (ib_vector_get_const(vec, ib_vector_size(vec) - 1)); 191} 192 193/** Remove the last element from the vector. 194 @return last vector element */ 195UNIV_INLINE 196void *ib_vector_pop( 197 /* out: pointer to element */ 198 ib_vector_t *vec) /* in: vector */ 199{ 200 void *elem; 201 202 ut_a(vec->used > 0); 203 204 elem = ib_vector_last(vec); 205 --vec->used; 206 207 return (elem); 208} 209 210/******************************************************************** 211Append an element to the vector, if elem != NULL then copy the data 212from elem.*/ 213UNIV_INLINE 214void *ib_vector_push( 215 /* out: pointer to the "new" element */ 216 ib_vector_t *vec, /* in: vector */ 217 const void *elem) /* in: element to add (can be NULL) */ 218{ 219 void *last; 220 221 if (vec->used >= vec->total) { 222 ib_vector_resize(vec); 223 } 224 225 last = (byte *)vec->data + IB_VEC_OFFSET(vec, vec->used); 226 227#ifdef UNIV_DEBUG 228 memset(last, 0, vec->sizeof_value); 229#endif 230 231 if (elem) { 232 memcpy(last, elem, vec->sizeof_value); 233 } 234 235 ++vec->used; 236 237 return (last); 238} 239 240/** Remove an element to the vector 241 @return pointer to the "removed" element */ 242UNIV_INLINE 243void *ib_vector_remove(ib_vector_t *vec, /*!< in: vector */ 244 const void *elem) /*!< in: value to remove */ 245{ 246 void *current = nullptr; 247 void *next; 248 ulint i; 249 ulint old_used_count = vec->used; 250 251 for (i = 0; i < vec->used; i++) { 252 current = ib_vector_get(vec, i); 253 254 if (*(void **)current == elem) { 255 if (i == vec->used - 1) { 256 return (ib_vector_pop(vec)); 257 } 258 259 next = ib_vector_get(vec, i + 1); 260 memmove(current, next, vec->sizeof_value * (vec->used - i - 1)); 261 --vec->used; 262 break; 263 } 264 } 265 266 return ((old_used_count != vec->used) ? current : nullptr); 267} 268 269/******************************************************************** 270Sort the vector elements. */ 271UNIV_INLINE 272void ib_vector_sort( 273 /* out: void */ 274 ib_vector_t *vec, /* in: vector */ 275 ib_compare_t compare) /* in: the comparator to use for sort */ 276{ 277 qsort(vec->data, vec->used, vec->sizeof_value, compare); 278} 279 280/******************************************************************** 281Destroy the vector. Make sure the vector owns the allocator, e.g., 282the heap in the the heap allocator. */ 283UNIV_INLINE 284void ib_vector_free(ib_vector_t *vec) /* in, own: vector */ 285{ 286 /* Currently we only support one type of allocator - heap, 287 when the heap is freed all the elements are freed too. */ 288 289 /* Only the heap allocator uses the arg field. */ 290 ut_ad(vec->allocator->arg != nullptr); 291 292 mem_heap_free((mem_heap_t *)vec->allocator->arg); 293} 294 295/******************************************************************** 296Test whether a vector is empty or not. 297@return true if empty */ 298UNIV_INLINE 299ibool ib_vector_is_empty(const ib_vector_t *vec) /*!< in: vector */ 300{ 301 return (ib_vector_size(vec) == 0); 302} 303