1/*****************************************************************************
2
3Copyright (c) 2006, 2019, 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, version 2.0, as published by the
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for 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 St, Fifth Floor, Boston, MA 02110-1301  USA
24
25*****************************************************************************/
26
27/** @file include/ut0vec.ic
28 A vector of pointers to data items
29
30 Created 4/6/2006 Osku Salerma
31 ************************************************************************/
32
33#include "ut0new.h"
34
35#define IB_VEC_OFFSET(v, i) (vec->sizeof_value * i)
36
37/********************************************************************
38The default ib_vector_t heap malloc. Uses mem_heap_alloc(). */
39UNIV_INLINE
40void *ib_heap_malloc(ib_alloc_t *allocator, /* in: allocator */
41                     ulint size)            /* in: size in bytes */
42{
43  mem_heap_t *heap = (mem_heap_t *)allocator->arg;
44
45  return (mem_heap_alloc(heap, size));
46}
47
48/********************************************************************
49The default ib_vector_t heap free. Does nothing. */
50UNIV_INLINE
51void ib_heap_free(ib_alloc_t *allocator UNIV_UNUSED, /* in: allocator */
52                  void *ptr UNIV_UNUSED)             /* in: size in bytes */
53{
54  /* We can't free individual elements. */
55}
56
57/********************************************************************
58The default ib_vector_t heap resize. Since we can't resize the heap
59we have to copy the elements from the old ptr to the new ptr.
60We always assume new_size >= old_size, so the buffer won't overflow.
61Uses mem_heap_alloc(). */
62UNIV_INLINE
63void *ib_heap_resize(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 *ib_heap_allocator_create(mem_heap_t *heap) /* in: heap to use */
82{
83  ib_alloc_t *heap_alloc;
84
85  heap_alloc = (ib_alloc_t *)mem_heap_alloc(heap, sizeof(*heap_alloc));
86
87  heap_alloc->arg = heap;
88  heap_alloc->mem_release = ib_heap_free;
89  heap_alloc->mem_malloc = ib_heap_malloc;
90  heap_alloc->mem_resize = ib_heap_resize;
91
92  return (heap_alloc);
93}
94
95/********************************************************************
96Free a heap allocator. */
97UNIV_INLINE
98void ib_heap_allocator_free(
99    ib_alloc_t *ib_ut_alloc) /* in: alloc instace to free */
100{
101  mem_heap_free((mem_heap_t *)ib_ut_alloc->arg);
102}
103
104/********************************************************************
105Get number of elements in vector. */
106UNIV_INLINE
107ulint ib_vector_size(
108    /* out: number of elements in vector*/
109    const ib_vector_t *vec) /* in: vector */
110{
111  return (vec->used);
112}
113
114/** Get n'th element. */
115UNIV_INLINE
116void *ib_vector_get(ib_vector_t *vec, /*!< in: vector */
117                    ulint n)          /*!< in: element index to get */
118{
119  ut_a(n < vec->used);
120
121  return ((byte *)vec->data + IB_VEC_OFFSET(vec, n));
122}
123
124/********************************************************************
125Const version of the get n'th element.
126@return n'th element */
127UNIV_INLINE
128const void *ib_vector_get_const(const ib_vector_t *vec, /* in: vector */
129                                ulint n) /* in: element index to get */
130{
131  ut_a(n < vec->used);
132
133  return ((byte *)vec->data + IB_VEC_OFFSET(vec, n));
134}
135/** Get last element. The vector must not be empty.
136 @return last element */
137UNIV_INLINE
138void *ib_vector_get_last(ib_vector_t *vec) /*!< in: vector */
139{
140  ut_a(vec->used > 0);
141
142  return ((byte *)ib_vector_get(vec, vec->used - 1));
143}
144
145/** Set the n'th element. */
146UNIV_INLINE
147void ib_vector_set(ib_vector_t *vec, /*!< in/out: vector */
148                   ulint n,          /*!< in: element index to set */
149                   void *elem)       /*!< in: data element */
150{
151  void *slot;
152
153  ut_a(n < vec->used);
154
155  slot = ((byte *)vec->data + IB_VEC_OFFSET(vec, n));
156  memcpy(slot, elem, vec->sizeof_value);
157}
158
159/********************************************************************
160Reset the vector size to 0 elements. */
161UNIV_INLINE
162void ib_vector_reset(
163    /* out: void */
164    ib_vector_t *vec) /* in: vector */
165{
166  vec->used = 0;
167}
168
169/********************************************************************
170Get the last element of the vector. */
171UNIV_INLINE
172void *ib_vector_last(
173    /* out: void */
174    ib_vector_t *vec) /* in: vector */
175{
176  ut_a(ib_vector_size(vec) > 0);
177
178  return (ib_vector_get(vec, ib_vector_size(vec) - 1));
179}
180
181/********************************************************************
182Get the last element of the vector. */
183UNIV_INLINE
184const void *ib_vector_last_const(
185    /* out: void */
186    const ib_vector_t *vec) /* in: vector */
187{
188  ut_a(ib_vector_size(vec) > 0);
189
190  return (ib_vector_get_const(vec, ib_vector_size(vec) - 1));
191}
192
193/** Remove the last element from the vector.
194 @return last vector element */
195UNIV_INLINE
196void *ib_vector_pop(
197    /* out: pointer to element */
198    ib_vector_t *vec) /* in: vector */
199{
200  void *elem;
201
202  ut_a(vec->used > 0);
203
204  elem = ib_vector_last(vec);
205  --vec->used;
206
207  return (elem);
208}
209
210/********************************************************************
211Append an element to the vector, if elem != NULL then copy the data
212from elem.*/
213UNIV_INLINE
214void *ib_vector_push(
215    /* out: pointer to the "new" element */
216    ib_vector_t *vec, /* in: vector */
217    const void *elem) /* in: element to add (can be NULL) */
218{
219  void *last;
220
221  if (vec->used >= vec->total) {
222    ib_vector_resize(vec);
223  }
224
225  last = (byte *)vec->data + IB_VEC_OFFSET(vec, vec->used);
226
227#ifdef UNIV_DEBUG
228  memset(last, 0, vec->sizeof_value);
229#endif
230
231  if (elem) {
232    memcpy(last, elem, vec->sizeof_value);
233  }
234
235  ++vec->used;
236
237  return (last);
238}
239
240/** Remove an element to the vector
241 @return pointer to the "removed" element */
242UNIV_INLINE
243void *ib_vector_remove(ib_vector_t *vec, /*!< in: vector */
244                       const void *elem) /*!< in: value to remove */
245{
246  void *current = nullptr;
247  void *next;
248  ulint i;
249  ulint old_used_count = vec->used;
250
251  for (i = 0; i < vec->used; i++) {
252    current = ib_vector_get(vec, i);
253
254    if (*(void **)current == elem) {
255      if (i == vec->used - 1) {
256        return (ib_vector_pop(vec));
257      }
258
259      next = ib_vector_get(vec, i + 1);
260      memmove(current, next, vec->sizeof_value * (vec->used - i - 1));
261      --vec->used;
262      break;
263    }
264  }
265
266  return ((old_used_count != vec->used) ? current : nullptr);
267}
268
269/********************************************************************
270Sort the vector elements. */
271UNIV_INLINE
272void ib_vector_sort(
273    /* out: void */
274    ib_vector_t *vec,     /* in: vector */
275    ib_compare_t compare) /* in: the comparator to use for sort */
276{
277  qsort(vec->data, vec->used, vec->sizeof_value, compare);
278}
279
280/********************************************************************
281Destroy the vector. Make sure the vector owns the allocator, e.g.,
282the heap in the the heap allocator. */
283UNIV_INLINE
284void ib_vector_free(ib_vector_t *vec) /* in, own: vector */
285{
286  /* Currently we only support one type of allocator - heap,
287  when the heap is freed all the elements are freed too. */
288
289  /* Only the heap allocator uses the arg field. */
290  ut_ad(vec->allocator->arg != nullptr);
291
292  mem_heap_free((mem_heap_t *)vec->allocator->arg);
293}
294
295/********************************************************************
296Test whether a vector is empty or not.
297@return true if empty */
298UNIV_INLINE
299ibool ib_vector_is_empty(const ib_vector_t *vec) /*!< in: vector */
300{
301  return (ib_vector_size(vec) == 0);
302}
303