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
|
/*
* Copyright (c) 2013, 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 blocks of fixed size.
*
* This array is able to grow dynamically upon request, without any reallocation.
*
* The grow operation involves an allocation of a new array block, without reallocating
* the already used memory, and then not increasing the heap fragmentation,
* and minimize the space occupation.
* This also implies that the address of the stored elements never change.
*
* Allocated blocks are always of the same fixed size of 4 Ki pointers.
*/
#ifndef __TOMMYARRAYBLK_H
#define __TOMMYARRAYBLK_H
#include "tommytypes.h"
#include "tommyarray.h"
#include <assert.h> /* for assert */
/******************************************************************************/
/* array */
/**
* Elements for each block.
*/
#define TOMMY_ARRAYBLK_SIZE (4 * 1024)
/**
* Array container type.
* \note Don't use internal fields directly, but access the container only using functions.
*/
typedef struct tommy_arrayblk_struct {
tommy_array block; /**< Array of blocks. */
tommy_count_t count; /**< Number of initialized elements in the array. */
} tommy_arrayblk;
/**
* Initializes the array.
*/
void tommy_arrayblk_init(tommy_arrayblk* array);
/**
* Deinitializes the array.
*/
void tommy_arrayblk_done(tommy_arrayblk* array);
/**
* Grows the size up to the specified value.
* All the new elements in the array are initialized with the 0 value.
*/
void tommy_arrayblk_grow(tommy_arrayblk* 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_arrayblk_grow().
*/
tommy_inline void** tommy_arrayblk_ref(tommy_arrayblk* array, tommy_count_t pos)
{
void** ptr;
assert(pos < array->count);
ptr = tommy_cast(void**, tommy_array_get(&array->block, pos / TOMMY_ARRAYBLK_SIZE));
return &ptr[pos % TOMMY_ARRAYBLK_SIZE];
}
/**
* Sets the element at the specified position.
* You must be sure that space for this position is already
* allocated calling tommy_arrayblk_grow().
*/
tommy_inline void tommy_arrayblk_set(tommy_arrayblk* array, tommy_count_t pos, void* element)
{
*tommy_arrayblk_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_arrayblk_grow().
*/
tommy_inline void* tommy_arrayblk_get(tommy_arrayblk* array, tommy_count_t pos)
{
return *tommy_arrayblk_ref(array, pos);
}
/**
* Grows and inserts a new element at the end of the array.
*/
tommy_inline void tommy_arrayblk_insert(tommy_arrayblk* array, void* element)
{
tommy_count_t pos = array->count;
tommy_arrayblk_grow(array, pos + 1);
tommy_arrayblk_set(array, pos, element);
}
/**
* Gets the initialized size of the array.
*/
tommy_inline tommy_count_t tommy_arrayblk_size(tommy_arrayblk* array)
{
return array->count;
}
/**
* Gets the size of allocated memory.
*/
tommy_size_t tommy_arrayblk_memory_usage(tommy_arrayblk* array);
#endif
|
