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