1 /***************************************************************************** 2 3 Copyright (c) 2006, 2009, Oracle and/or its affiliates. All Rights Reserved. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License, version 2.0, 7 as published by the Free Software Foundation. 8 9 This program is also distributed with certain software (including 10 but not limited to OpenSSL) that is licensed under separate terms, 11 as designated in a particular file or component or in included license 12 documentation. The authors of MySQL hereby grant you an additional 13 permission to link the program and your derivative works with the 14 separately licensed software that they have included with MySQL. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License, version 2.0, for more details. 20 21 You should have received a copy of the GNU General Public License along with 22 this program; if not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA 24 25 *****************************************************************************/ 26 27 /*******************************************************************//** 28 @file include/ut0vec.h 29 A vector of pointers to data items 30 31 Created 4/6/2006 Osku Salerma 32 ************************************************************************/ 33 34 #ifndef IB_VECTOR_H 35 #define IB_VECTOR_H 36 37 #include "univ.i" 38 #include "mem0mem.h" 39 40 struct ib_alloc_t; 41 struct ib_vector_t; 42 43 typedef void* (*ib_mem_alloc_t)( 44 /* out: Pointer to allocated memory */ 45 ib_alloc_t* allocator, /* in: Pointer to allocator instance */ 46 ulint size); /* in: Number of bytes to allocate */ 47 48 typedef void (*ib_mem_free_t)( 49 ib_alloc_t* allocator, /* in: Pointer to allocator instance */ 50 void* ptr); /* in: Memory to free */ 51 52 typedef void* (*ib_mem_resize_t)( 53 /* out: Pointer to resized memory */ 54 ib_alloc_t* allocator, /* in: Pointer to allocator */ 55 void* ptr, /* in: Memory to resize */ 56 ulint old_size, /* in: Old memory size in bytes */ 57 ulint new_size); /* in: New size in bytes */ 58 59 typedef int (*ib_compare_t)(const void*, const void*); 60 61 /* An automatically resizing vector datatype with the following properties: 62 63 -All memory allocation is done through an allocator, which is responsible for 64 freeing it when done with the vector. 65 */ 66 67 /* This is useful shorthand for elements of type void* */ 68 #define ib_vector_getp(v, n) (*(void**) ib_vector_get(v, n)) 69 #define ib_vector_getp_const(v, n) (*(void**) ib_vector_get_const(v, n)) 70 71 #define ib_vector_allocator(v) (v->allocator) 72 73 /******************************************************************** 74 Create a new vector with the given initial size. */ 75 UNIV_INTERN 76 ib_vector_t* 77 ib_vector_create( 78 /*=============*/ 79 /* out: vector */ 80 ib_alloc_t* alloc, /* in: Allocator */ 81 /* in: size of the data item */ 82 ulint sizeof_value, 83 ulint size); /* in: initial size */ 84 85 /******************************************************************** 86 Destroy the vector. Make sure the vector owns the allocator, e.g., 87 the heap in the the heap allocator. */ 88 UNIV_INLINE 89 void 90 ib_vector_free( 91 /*===========*/ 92 ib_vector_t* vec); /* in/out: vector */ 93 94 /******************************************************************** 95 Push a new element to the vector, increasing its size if necessary, 96 if elem is not NULL then elem is copied to the vector.*/ 97 UNIV_INLINE 98 void* 99 ib_vector_push( 100 /*===========*/ 101 /* out: pointer the "new" element */ 102 ib_vector_t* vec, /* in/out: vector */ 103 const void* elem); /* in: data element */ 104 105 /******************************************************************** 106 Pop the last element from the vector.*/ 107 UNIV_INLINE 108 void* 109 ib_vector_pop( 110 /*==========*/ 111 /* out: pointer to the "new" element */ 112 ib_vector_t* vec); /* in/out: vector */ 113 114 /*******************************************************************//** 115 Remove an element to the vector 116 @return pointer to the "removed" element */ 117 UNIV_INLINE 118 void* 119 ib_vector_remove( 120 /*=============*/ 121 ib_vector_t* vec, /*!< in: vector */ 122 const void* elem); /*!< in: value to remove */ 123 124 /******************************************************************** 125 Get the number of elements in the vector. */ 126 UNIV_INLINE 127 ulint 128 ib_vector_size( 129 /*===========*/ 130 /* out: number of elements in vector */ 131 const ib_vector_t* vec); /* in: vector */ 132 133 /******************************************************************** 134 Increase the size of the vector. */ 135 UNIV_INTERN 136 void 137 ib_vector_resize( 138 /*=============*/ 139 /* out: number of elements in vector */ 140 ib_vector_t* vec); /* in/out: vector */ 141 142 /******************************************************************** 143 Test whether a vector is empty or not. 144 @return TRUE if empty */ 145 UNIV_INLINE 146 ibool 147 ib_vector_is_empty( 148 /*===============*/ 149 const ib_vector_t* vec); /*!< in: vector */ 150 151 /****************************************************************//** 152 Get the n'th element. 153 @return n'th element */ 154 UNIV_INLINE 155 void* 156 ib_vector_get( 157 /*==========*/ 158 ib_vector_t* vec, /*!< in: vector */ 159 ulint n); /*!< in: element index to get */ 160 161 /******************************************************************** 162 Const version of the get n'th element. 163 @return n'th element */ 164 UNIV_INLINE 165 const void* 166 ib_vector_get_const( 167 /*================*/ 168 const ib_vector_t* vec, /* in: vector */ 169 ulint n); /* in: element index to get */ 170 /****************************************************************//** 171 Get last element. The vector must not be empty. 172 @return last element */ 173 UNIV_INLINE 174 void* 175 ib_vector_get_last( 176 /*===============*/ 177 ib_vector_t* vec); /*!< in: vector */ 178 /****************************************************************//** 179 Set the n'th element. */ 180 UNIV_INLINE 181 void 182 ib_vector_set( 183 /*==========*/ 184 ib_vector_t* vec, /*!< in/out: vector */ 185 ulint n, /*!< in: element index to set */ 186 void* elem); /*!< in: data element */ 187 188 /******************************************************************** 189 Reset the vector size to 0 elements. */ 190 UNIV_INLINE 191 void 192 ib_vector_reset( 193 /*============*/ 194 ib_vector_t* vec); /* in/out: vector */ 195 196 /******************************************************************** 197 Get the last element of the vector. */ 198 UNIV_INLINE 199 void* 200 ib_vector_last( 201 /*===========*/ 202 /* out: pointer to last element */ 203 ib_vector_t* vec); /* in/out: vector */ 204 205 /******************************************************************** 206 Get the last element of the vector. */ 207 UNIV_INLINE 208 const void* 209 ib_vector_last_const( 210 /*=================*/ 211 /* out: pointer to last element */ 212 const ib_vector_t* vec); /* in: vector */ 213 214 /******************************************************************** 215 Sort the vector elements. */ 216 UNIV_INLINE 217 void 218 ib_vector_sort( 219 /*===========*/ 220 ib_vector_t* vec, /* in/out: vector */ 221 ib_compare_t compare); /* in: the comparator to use for sort */ 222 223 /******************************************************************** 224 The default ib_vector_t heap free. Does nothing. */ 225 UNIV_INLINE 226 void 227 ib_heap_free( 228 /*=========*/ 229 ib_alloc_t* allocator, /* in: allocator */ 230 void* ptr); /* in: size in bytes */ 231 232 /******************************************************************** 233 The default ib_vector_t heap malloc. Uses mem_heap_alloc(). */ 234 UNIV_INLINE 235 void* 236 ib_heap_malloc( 237 /*===========*/ 238 /* out: pointer to allocated memory */ 239 ib_alloc_t* allocator, /* in: allocator */ 240 ulint size); /* in: size in bytes */ 241 242 /******************************************************************** 243 The default ib_vector_t heap resize. Since we can't resize the heap 244 we have to copy the elements from the old ptr to the new ptr. 245 Uses mem_heap_alloc(). */ 246 UNIV_INLINE 247 void* 248 ib_heap_resize( 249 /*===========*/ 250 /* out: pointer to reallocated 251 memory */ 252 ib_alloc_t* allocator, /* in: allocator */ 253 void* old_ptr, /* in: pointer to memory */ 254 ulint old_size, /* in: old size in bytes */ 255 ulint new_size); /* in: new size in bytes */ 256 257 /******************************************************************** 258 Create a heap allocator that uses the passed in heap. */ 259 UNIV_INLINE 260 ib_alloc_t* 261 ib_heap_allocator_create( 262 /*=====================*/ 263 /* out: heap allocator instance */ 264 mem_heap_t* heap); /* in: heap to use */ 265 266 /******************************************************************** 267 Free a heap allocator. */ 268 UNIV_INLINE 269 void 270 ib_heap_allocator_free( 271 /*===================*/ 272 ib_alloc_t* ib_ut_alloc); /* in: alloc instace to free */ 273 274 /******************************************************************** 275 Wrapper for ut_free(). */ 276 UNIV_INLINE 277 void 278 ib_ut_free( 279 /*=======*/ 280 ib_alloc_t* allocator, /* in: allocator */ 281 void* ptr); /* in: size in bytes */ 282 283 /******************************************************************** 284 Wrapper for ut_malloc(). */ 285 UNIV_INLINE 286 void* 287 ib_ut_malloc( 288 /*=========*/ 289 /* out: pointer to allocated memory */ 290 ib_alloc_t* allocator, /* in: allocator */ 291 ulint size); /* in: size in bytes */ 292 293 /******************************************************************** 294 Wrapper for ut_realloc(). */ 295 UNIV_INLINE 296 void* 297 ib_ut_resize( 298 /*=========*/ 299 /* out: pointer to reallocated 300 memory */ 301 ib_alloc_t* allocator, /* in: allocator */ 302 void* old_ptr, /* in: pointer to memory */ 303 ulint old_size, /* in: old size in bytes */ 304 ulint new_size); /* in: new size in bytes */ 305 306 /******************************************************************** 307 Create a heap allocator that uses the passed in heap. */ 308 UNIV_INLINE 309 ib_alloc_t* 310 ib_ut_allocator_create(void); 311 /*=========================*/ 312 313 /******************************************************************** 314 Create a heap allocator that uses the passed in heap. */ 315 UNIV_INLINE 316 void 317 ib_ut_allocator_free( 318 /*=================*/ 319 ib_alloc_t* ib_ut_alloc); /* in: alloc instace to free */ 320 321 /* Allocator used by ib_vector_t. */ 322 struct ib_alloc_t { 323 ib_mem_alloc_t mem_malloc; /* For allocating memory */ 324 ib_mem_free_t mem_release; /* For freeing memory */ 325 ib_mem_resize_t mem_resize; /* For resizing memory */ 326 void* arg; /* Currently if not NULL then it 327 points to the heap instance */ 328 }; 329 330 /* See comment at beginning of file. */ 331 struct ib_vector_t { 332 ib_alloc_t* allocator; /* Allocator, because one size 333 doesn't fit all */ 334 void* data; /* data elements */ 335 ulint used; /* number of elements currently used */ 336 ulint total; /* number of elements allocated */ 337 /* Size of a data item */ 338 ulint sizeof_value; 339 }; 340 341 #ifndef UNIV_NONINL 342 #include "ut0vec.ic" 343 #endif 344 345 #endif /* IB_VECTOR_H */ 346