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