1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
/*
* Copyright (c) 2011, Andrea Mazzoleni. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/** \file
* Dynamic array based on segments of exponential growing size.
*
* This array is able to grow dynamically upon request, without any reallocation.
*
* The grow operation involves an allocation of a new array segment, without reallocating
* the already used memory, and then not increasing the heap fragmentation.
* This also implies that the address of the stored elements never change.
*
* Allocated segments grow in size exponentially.
*/
#ifndef __TOMMYARRAY_H
#define __TOMMYARRAY_H
#include "tommytypes.h"
#include <assert.h> /* for assert */
/******************************************************************************/
/* array */
/**
* Initial and minimal size of the array expressed as a power of 2.
* The initial size is 2^TOMMY_ARRAY_BIT.
*/
#define TOMMY_ARRAY_BIT 6
/** \internal
* Max number of elements as a power of 2.
*/
#define TOMMY_ARRAY_BIT_MAX 32
/**
* Array container type.
* \note Don't use internal fields directly, but access the container only using functions.
*/
typedef struct tommy_array_struct {
void** bucket[TOMMY_ARRAY_BIT_MAX]; /**< Dynamic array of buckets. */
tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
tommy_count_t bucket_max; /**< Number of buckets. */
tommy_count_t count; /**< Number of initialized elements in the array. */
} tommy_array;
/**
* Initializes the array.
*/
void tommy_array_init(tommy_array* array);
/**
* Deinitializes the array.
*/
void tommy_array_done(tommy_array* array);
/**
* Grows the size up to the specified value.
* All the new elements in the array are initialized with the 0 value.
*/
void tommy_array_grow(tommy_array* array, tommy_count_t size);
/**
* Gets a reference of the element at the specified position.
* You must be sure that space for this position is already
* allocated calling tommy_array_grow().
*/
tommy_inline void** tommy_array_ref(tommy_array* array, tommy_count_t pos)
{
tommy_uint_t bsr;
assert(pos < array->count);
/* get the highest bit set, in case of all 0, return 0 */
bsr = tommy_ilog2_u32(pos | 1);
return &array->bucket[bsr][pos];
}
/**
* Sets the element at the specified position.
* You must be sure that space for this position is already
* allocated calling tommy_array_grow().
*/
tommy_inline void tommy_array_set(tommy_array* array, tommy_count_t pos, void* element)
{
*tommy_array_ref(array, pos) = element;
}
/**
* Gets the element at the specified position.
* You must be sure that space for this position is already
* allocated calling tommy_array_grow().
*/
tommy_inline void* tommy_array_get(tommy_array* array, tommy_count_t pos)
{
return *tommy_array_ref(array, pos);
}
/**
* Grows and inserts a new element at the end of the array.
*/
tommy_inline void tommy_array_insert(tommy_array* array, void* element)
{
tommy_count_t pos = array->count;
tommy_array_grow(array, pos + 1);
tommy_array_set(array, pos, element);
}
/**
* Gets the initialized size of the array.
*/
tommy_inline tommy_count_t tommy_array_size(tommy_array* array)
{
return array->count;
}
/**
* Gets the size of allocated memory.
*/
tommy_size_t tommy_array_memory_usage(tommy_array* array);
#endif
|
