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