1/***************************************************************************** 2 3Copyright (c) 2006, 2009, Oracle and/or its affiliates. All Rights Reserved. 4 5This program is free software; you can redistribute it and/or modify 6it under the terms of the GNU General Public License, version 2.0, 7as published by the Free Software Foundation. 8 9This program is also distributed with certain software (including 10but not limited to OpenSSL) that is licensed under separate terms, 11as designated in a particular file or component or in included license 12documentation. The authors of MySQL hereby grant you an additional 13permission to link the program and your derivative works with the 14separately licensed software that they have included with MySQL. 15 16This program is distributed in the hope that it will be useful, 17but WITHOUT ANY WARRANTY; without even the implied warranty of 18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19GNU General Public License, version 2.0, for 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 Street, Suite 500, Boston, MA 02110-1335 USA 24 25*****************************************************************************/ 26 27/*******************************************************************//** 28@file include/ut0vec.ic 29A vector of pointers to data items 30 31Created 4/6/2006 Osku Salerma 32************************************************************************/ 33 34#define IB_VEC_OFFSET(v, i) (vec->sizeof_value * i) 35 36/******************************************************************** 37The default ib_vector_t heap malloc. Uses mem_heap_alloc(). */ 38UNIV_INLINE 39void* 40ib_heap_malloc( 41/*===========*/ 42 ib_alloc_t* allocator, /* in: allocator */ 43 ulint size) /* in: size in bytes */ 44{ 45 mem_heap_t* heap = (mem_heap_t*) allocator->arg; 46 47 return(mem_heap_alloc(heap, size)); 48} 49 50/******************************************************************** 51The default ib_vector_t heap free. Does nothing. */ 52UNIV_INLINE 53void 54ib_heap_free( 55/*=========*/ 56 ib_alloc_t* allocator UNIV_UNUSED, /* in: allocator */ 57 void* ptr UNIV_UNUSED) /* in: size in bytes */ 58{ 59 /* We can't free individual elements. */ 60} 61 62/******************************************************************** 63The default ib_vector_t heap resize. Since we can't resize the heap 64we have to copy the elements from the old ptr to the new ptr. 65Uses mem_heap_alloc(). */ 66UNIV_INLINE 67void* 68ib_heap_resize( 69/*===========*/ 70 ib_alloc_t* allocator, /* in: allocator */ 71 void* old_ptr, /* in: pointer to memory */ 72 ulint old_size, /* in: old size in bytes */ 73 ulint new_size) /* in: new size in bytes */ 74{ 75 void* new_ptr; 76 mem_heap_t* heap = (mem_heap_t*) allocator->arg; 77 78 new_ptr = mem_heap_alloc(heap, new_size); 79 memcpy(new_ptr, old_ptr, old_size); 80 81 return(new_ptr); 82} 83 84/******************************************************************** 85Create a heap allocator that uses the passed in heap. */ 86UNIV_INLINE 87ib_alloc_t* 88ib_heap_allocator_create( 89/*=====================*/ 90 mem_heap_t* heap) /* in: heap to use */ 91{ 92 ib_alloc_t* heap_alloc; 93 94 heap_alloc = (ib_alloc_t*) mem_heap_alloc(heap, sizeof(*heap_alloc)); 95 96 heap_alloc->arg = heap; 97 heap_alloc->mem_release = ib_heap_free; 98 heap_alloc->mem_malloc = ib_heap_malloc; 99 heap_alloc->mem_resize = ib_heap_resize; 100 101 return(heap_alloc); 102} 103 104/******************************************************************** 105Free a heap allocator. */ 106UNIV_INLINE 107void 108ib_heap_allocator_free( 109/*===================*/ 110 ib_alloc_t* ib_ut_alloc) /* in: alloc instace to free */ 111{ 112 mem_heap_free((mem_heap_t*) ib_ut_alloc->arg); 113} 114 115/******************************************************************** 116Wrapper around ut_malloc(). */ 117UNIV_INLINE 118void* 119ib_ut_malloc( 120/*=========*/ 121 ib_alloc_t* allocator UNIV_UNUSED, /* in: allocator */ 122 ulint size) /* in: size in bytes */ 123{ 124 return(ut_malloc(size)); 125} 126 127/******************************************************************** 128Wrapper around ut_free(). */ 129UNIV_INLINE 130void 131ib_ut_free( 132/*=======*/ 133 ib_alloc_t* allocator UNIV_UNUSED, /* in: allocator */ 134 void* ptr) /* in: size in bytes */ 135{ 136 ut_free(ptr); 137} 138 139/******************************************************************** 140Wrapper aroung ut_realloc(). */ 141UNIV_INLINE 142void* 143ib_ut_resize( 144/*=========*/ 145 ib_alloc_t* allocator UNIV_UNUSED, /* in: allocator */ 146 void* old_ptr, /* in: pointer to memory */ 147 ulint old_size UNIV_UNUSED,/* in: old size in bytes */ 148 ulint new_size) /* in: new size in bytes */ 149{ 150 return(ut_realloc(old_ptr, new_size)); 151} 152 153/******************************************************************** 154Create a ut allocator. */ 155UNIV_INLINE 156ib_alloc_t* 157ib_ut_allocator_create(void) 158/*========================*/ 159{ 160 ib_alloc_t* ib_ut_alloc; 161 162 ib_ut_alloc = (ib_alloc_t*) ut_malloc(sizeof(*ib_ut_alloc)); 163 164 ib_ut_alloc->arg = NULL; 165 ib_ut_alloc->mem_release = ib_ut_free; 166 ib_ut_alloc->mem_malloc = ib_ut_malloc; 167 ib_ut_alloc->mem_resize = ib_ut_resize; 168 169 return(ib_ut_alloc); 170} 171 172/******************************************************************** 173Free a ut allocator. */ 174UNIV_INLINE 175void 176ib_ut_allocator_free( 177/*=================*/ 178 ib_alloc_t* ib_ut_alloc) /* in: alloc instace to free */ 179{ 180 ut_free(ib_ut_alloc); 181} 182 183/******************************************************************** 184Get number of elements in vector. */ 185UNIV_INLINE 186ulint 187ib_vector_size( 188/*===========*/ 189 /* out: number of elements in vector*/ 190 const ib_vector_t* vec) /* in: vector */ 191{ 192 return(vec->used); 193} 194 195/****************************************************************//** 196Get n'th element. */ 197UNIV_INLINE 198void* 199ib_vector_get( 200/*==========*/ 201 ib_vector_t* vec, /*!< in: vector */ 202 ulint n) /*!< in: element index to get */ 203{ 204 ut_a(n < vec->used); 205 206 return((byte*) vec->data + IB_VEC_OFFSET(vec, n)); 207} 208 209/******************************************************************** 210Const version of the get n'th element. 211@return n'th element */ 212UNIV_INLINE 213const void* 214ib_vector_get_const( 215/*================*/ 216 const ib_vector_t* vec, /* in: vector */ 217 ulint n) /* in: element index to get */ 218{ 219 ut_a(n < vec->used); 220 221 return((byte*) vec->data + IB_VEC_OFFSET(vec, n)); 222} 223/****************************************************************//** 224Get last element. The vector must not be empty. 225@return last element */ 226UNIV_INLINE 227void* 228ib_vector_get_last( 229/*===============*/ 230 ib_vector_t* vec) /*!< in: vector */ 231{ 232 ut_a(vec->used > 0); 233 234 return((byte*) ib_vector_get(vec, vec->used - 1)); 235} 236 237/****************************************************************//** 238Set the n'th element. */ 239UNIV_INLINE 240void 241ib_vector_set( 242/*==========*/ 243 ib_vector_t* vec, /*!< in/out: vector */ 244 ulint n, /*!< in: element index to set */ 245 void* elem) /*!< in: data element */ 246{ 247 void* slot; 248 249 ut_a(n < vec->used); 250 251 slot = ((byte*) vec->data + IB_VEC_OFFSET(vec, n)); 252 memcpy(slot, elem, vec->sizeof_value); 253} 254 255/******************************************************************** 256Reset the vector size to 0 elements. */ 257UNIV_INLINE 258void 259ib_vector_reset( 260/*============*/ 261 /* out: void */ 262 ib_vector_t* vec) /* in: vector */ 263{ 264 vec->used = 0; 265} 266 267/******************************************************************** 268Get the last element of the vector. */ 269UNIV_INLINE 270void* 271ib_vector_last( 272/*===========*/ 273 /* out: void */ 274 ib_vector_t* vec) /* in: vector */ 275{ 276 ut_a(ib_vector_size(vec) > 0); 277 278 return(ib_vector_get(vec, ib_vector_size(vec) - 1)); 279} 280 281/******************************************************************** 282Get the last element of the vector. */ 283UNIV_INLINE 284const void* 285ib_vector_last_const( 286/*=================*/ 287 /* out: void */ 288 const ib_vector_t* vec) /* in: vector */ 289{ 290 ut_a(ib_vector_size(vec) > 0); 291 292 return(ib_vector_get_const(vec, ib_vector_size(vec) - 1)); 293} 294 295/****************************************************************//** 296Remove the last element from the vector. 297@return last vector element */ 298UNIV_INLINE 299void* 300ib_vector_pop( 301/*==========*/ 302 /* out: pointer to element */ 303 ib_vector_t* vec) /* in: vector */ 304{ 305 void* elem; 306 307 ut_a(vec->used > 0); 308 309 elem = ib_vector_last(vec); 310 --vec->used; 311 312 return(elem); 313} 314 315/******************************************************************** 316Append an element to the vector, if elem != NULL then copy the data 317from elem.*/ 318UNIV_INLINE 319void* 320ib_vector_push( 321/*===========*/ 322 /* out: pointer to the "new" element */ 323 ib_vector_t* vec, /* in: vector */ 324 const void* elem) /* in: element to add (can be NULL) */ 325{ 326 void* last; 327 328 if (vec->used >= vec->total) { 329 ib_vector_resize(vec); 330 } 331 332 last = (byte*) vec->data + IB_VEC_OFFSET(vec, vec->used); 333 334#ifdef UNIV_DEBUG 335 memset(last, 0, vec->sizeof_value); 336#endif 337 338 if (elem) { 339 memcpy(last, elem, vec->sizeof_value); 340 } 341 342 ++vec->used; 343 344 return(last); 345} 346 347/*******************************************************************//** 348Remove an element to the vector 349@return pointer to the "removed" element */ 350UNIV_INLINE 351void* 352ib_vector_remove( 353/*=============*/ 354 ib_vector_t* vec, /*!< in: vector */ 355 const void* elem) /*!< in: value to remove */ 356{ 357 void* current = NULL; 358 void* next; 359 ulint i; 360 ulint old_used_count = vec->used; 361 362 for (i = 0; i < vec->used; i++) { 363 current = ib_vector_get(vec, i); 364 365 if (*(void**) current == elem) { 366 if (i == vec->used - 1) { 367 return(ib_vector_pop(vec)); 368 } 369 370 next = ib_vector_get(vec, i + 1); 371 memmove(current, next, vec->sizeof_value 372 * (vec->used - i - 1)); 373 --vec->used; 374 break; 375 } 376 } 377 378 return((old_used_count != vec->used) ? current : NULL); 379} 380 381/******************************************************************** 382Sort the vector elements. */ 383UNIV_INLINE 384void 385ib_vector_sort( 386/*===========*/ 387 /* out: void */ 388 ib_vector_t* vec, /* in: vector */ 389 ib_compare_t compare)/* in: the comparator to use for sort */ 390{ 391 qsort(vec->data, vec->used, vec->sizeof_value, compare); 392} 393 394/******************************************************************** 395Destroy the vector. Make sure the vector owns the allocator, e.g., 396the heap in the the heap allocator. */ 397UNIV_INLINE 398void 399ib_vector_free( 400/*===========*/ 401 ib_vector_t* vec) /* in, own: vector */ 402{ 403 /* Currently we only support two types of allocators, heap 404 and ut_malloc(), when the heap is freed all the elements are 405 freed too. With ut allocator, we need to free the elements, 406 the vector instance and the allocator separately. */ 407 408 /* Only the heap allocator uses the arg field. */ 409 if (vec->allocator->arg) { 410 mem_heap_free((mem_heap_t*) vec->allocator->arg); 411 } else { 412 ib_alloc_t* allocator; 413 414 allocator = vec->allocator; 415 416 allocator->mem_release(allocator, vec->data); 417 allocator->mem_release(allocator, vec); 418 419 ib_ut_allocator_free(allocator); 420 } 421} 422 423/******************************************************************** 424Test whether a vector is empty or not. 425@return TRUE if empty */ 426UNIV_INLINE 427ibool 428ib_vector_is_empty( 429/*===============*/ 430 const ib_vector_t* vec) /*!< in: vector */ 431{ 432 return(ib_vector_size(vec) == 0); 433} 434