1/*****************************************************************************
2
3Copyright (c) 2006, 2016, 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.h
21A vector of pointers to data items
22
23Created 4/6/2006 Osku Salerma
24************************************************************************/
25
26#ifndef IB_VECTOR_H
27#define IB_VECTOR_H
28
29#include "univ.i"
30#include "mem0mem.h"
31
32struct ib_alloc_t;
33struct ib_vector_t;
34
35typedef void* (*ib_mem_alloc_t)(
36 /* out: Pointer to allocated memory */
37 ib_alloc_t* allocator, /* in: Pointer to allocator instance */
38 ulint size); /* in: Number of bytes to allocate */
39
40typedef void (*ib_mem_free_t)(
41 ib_alloc_t* allocator, /* in: Pointer to allocator instance */
42 void* ptr); /* in: Memory to free */
43
44typedef void* (*ib_mem_resize_t)(
45 /* out: Pointer to resized memory */
46 ib_alloc_t* allocator, /* in: Pointer to allocator */
47 void* ptr, /* in: Memory to resize */
48 ulint old_size, /* in: Old memory size in bytes */
49 ulint new_size); /* in: New size in bytes */
50
51typedef int (*ib_compare_t)(const void*, const void*);
52
53/* An automatically resizing vector datatype with the following properties:
54
55 -All memory allocation is done through an allocator, which is responsible for
56freeing it when done with the vector.
57*/
58
59/* This is useful shorthand for elements of type void* */
60#define ib_vector_getp(v, n) (*(void**) ib_vector_get(v, n))
61#define ib_vector_getp_const(v, n) (*(void**) ib_vector_get_const(v, n))
62
63#define ib_vector_allocator(v) (v->allocator)
64
65/********************************************************************
66Create a new vector with the given initial size. */
67ib_vector_t*
68ib_vector_create(
69/*=============*/
70 /* out: vector */
71 ib_alloc_t* alloc, /* in: Allocator */
72 /* in: size of the data item */
73 ulint sizeof_value,
74 ulint size); /* in: initial size */
75
76/********************************************************************
77Destroy the vector. Make sure the vector owns the allocator, e.g.,
78the heap in the the heap allocator. */
79UNIV_INLINE
80void
81ib_vector_free(
82/*===========*/
83 ib_vector_t* vec); /* in/out: vector */
84
85/********************************************************************
86Push a new element to the vector, increasing its size if necessary,
87if elem is not NULL then elem is copied to the vector.*/
88UNIV_INLINE
89void*
90ib_vector_push(
91/*===========*/
92 /* out: pointer the "new" element */
93 ib_vector_t* vec, /* in/out: vector */
94 const void* elem); /* in: data element */
95
96/********************************************************************
97Pop the last element from the vector.*/
98UNIV_INLINE
99void*
100ib_vector_pop(
101/*==========*/
102 /* out: pointer to the "new" element */
103 ib_vector_t* vec); /* in/out: vector */
104
105/*******************************************************************//**
106Remove an element to the vector
107@return pointer to the "removed" element */
108UNIV_INLINE
109void*
110ib_vector_remove(
111/*=============*/
112 ib_vector_t* vec, /*!< in: vector */
113 const void* elem); /*!< in: value to remove */
114
115/********************************************************************
116Get the number of elements in the vector. */
117UNIV_INLINE
118ulint
119ib_vector_size(
120/*===========*/
121 /* out: number of elements in vector */
122 const ib_vector_t* vec); /* in: vector */
123
124/********************************************************************
125Increase the size of the vector. */
126void
127ib_vector_resize(
128/*=============*/
129 /* out: number of elements in vector */
130 ib_vector_t* vec); /* in/out: vector */
131
132/********************************************************************
133Test whether a vector is empty or not.
134@return TRUE if empty */
135UNIV_INLINE
136ibool
137ib_vector_is_empty(
138/*===============*/
139 const ib_vector_t* vec); /*!< in: vector */
140
141/****************************************************************//**
142Get the n'th element.
143@return n'th element */
144UNIV_INLINE
145void*
146ib_vector_get(
147/*==========*/
148 ib_vector_t* vec, /*!< in: vector */
149 ulint n); /*!< in: element index to get */
150
151/********************************************************************
152Const version of the get n'th element.
153@return n'th element */
154UNIV_INLINE
155const void*
156ib_vector_get_const(
157/*================*/
158 const ib_vector_t* vec, /* in: vector */
159 ulint n); /* in: element index to get */
160/****************************************************************//**
161Get last element. The vector must not be empty.
162@return last element */
163UNIV_INLINE
164void*
165ib_vector_get_last(
166/*===============*/
167 ib_vector_t* vec); /*!< in: vector */
168/****************************************************************//**
169Set the n'th element. */
170UNIV_INLINE
171void
172ib_vector_set(
173/*==========*/
174 ib_vector_t* vec, /*!< in/out: vector */
175 ulint n, /*!< in: element index to set */
176 void* elem); /*!< in: data element */
177
178/********************************************************************
179Reset the vector size to 0 elements. */
180UNIV_INLINE
181void
182ib_vector_reset(
183/*============*/
184 ib_vector_t* vec); /* in/out: vector */
185
186/********************************************************************
187Get the last element of the vector. */
188UNIV_INLINE
189void*
190ib_vector_last(
191/*===========*/
192 /* out: pointer to last element */
193 ib_vector_t* vec); /* in/out: vector */
194
195/********************************************************************
196Get the last element of the vector. */
197UNIV_INLINE
198const void*
199ib_vector_last_const(
200/*=================*/
201 /* out: pointer to last element */
202 const ib_vector_t* vec); /* in: vector */
203
204/********************************************************************
205Sort the vector elements. */
206UNIV_INLINE
207void
208ib_vector_sort(
209/*===========*/
210 ib_vector_t* vec, /* in/out: vector */
211 ib_compare_t compare); /* in: the comparator to use for sort */
212
213/********************************************************************
214The default ib_vector_t heap free. Does nothing. */
215UNIV_INLINE
216void
217ib_heap_free(
218/*=========*/
219 ib_alloc_t* allocator, /* in: allocator */
220 void* ptr); /* in: size in bytes */
221
222/********************************************************************
223The default ib_vector_t heap malloc. Uses mem_heap_alloc(). */
224UNIV_INLINE
225void*
226ib_heap_malloc(
227/*===========*/
228 /* out: pointer to allocated memory */
229 ib_alloc_t* allocator, /* in: allocator */
230 ulint size); /* in: size in bytes */
231
232/********************************************************************
233The default ib_vector_t heap resize. Since we can't resize the heap
234we have to copy the elements from the old ptr to the new ptr.
235Uses mem_heap_alloc(). */
236UNIV_INLINE
237void*
238ib_heap_resize(
239/*===========*/
240 /* out: pointer to reallocated
241 memory */
242 ib_alloc_t* allocator, /* in: allocator */
243 void* old_ptr, /* in: pointer to memory */
244 ulint old_size, /* in: old size in bytes */
245 ulint new_size); /* in: new size in bytes */
246
247/********************************************************************
248Create a heap allocator that uses the passed in heap. */
249UNIV_INLINE
250ib_alloc_t*
251ib_heap_allocator_create(
252/*=====================*/
253 /* out: heap allocator instance */
254 mem_heap_t* heap); /* in: heap to use */
255
256/********************************************************************
257Free a heap allocator. */
258UNIV_INLINE
259void
260ib_heap_allocator_free(
261/*===================*/
262 ib_alloc_t* ib_ut_alloc); /* in: alloc instace to free */
263
264/* Allocator used by ib_vector_t. */
265struct ib_alloc_t {
266 ib_mem_alloc_t mem_malloc; /* For allocating memory */
267 ib_mem_free_t mem_release; /* For freeing memory */
268 ib_mem_resize_t mem_resize; /* For resizing memory */
269 void* arg; /* Currently if not NULL then it
270 points to the heap instance */
271};
272
273/* See comment at beginning of file. */
274struct ib_vector_t {
275 ib_alloc_t* allocator; /* Allocator, because one size
276 doesn't fit all */
277 void* data; /* data elements */
278 ulint used; /* number of elements currently used */
279 ulint total; /* number of elements allocated */
280 /* Size of a data item */
281 ulint sizeof_value;
282};
283
284#include "ut0vec.ic"
285
286#endif /* IB_VECTOR_H */
287