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