Line data Source code
1 : /*
2 : * Copyright (c) 2013, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : /** \file
29 : * Dynamic array based on segments of exponential growing size.
30 : *
31 : * This array is able to grow dynamically upon request, without any reallocation.
32 : *
33 : * This is very similar at ::tommy_array, but it allows to store elements of any
34 : * size and not just pointers.
35 : *
36 : * Note that in this case tommy_arrayof_ref() returns a pointer to the element,
37 : * that should be used for getting and setting elements in the array,
38 : * as generic getter and setter are not available.
39 : */
40 :
41 : #ifndef __TOMMYARRAYOF_H
42 : #define __TOMMYARRAYOF_H
43 :
44 : #include "tommytypes.h"
45 :
46 : #include <assert.h> /* for assert */
47 :
48 : /******************************************************************************/
49 : /* array */
50 :
51 : /**
52 : * Initial and minimal size of the array expressed as a power of 2.
53 : * The initial size is 2^TOMMY_ARRAYOF_BIT.
54 : */
55 : #define TOMMY_ARRAYOF_BIT 6
56 :
57 : /**
58 : * Array container type.
59 : * \note Don't use internal fields directly, but access the container only using functions.
60 : */
61 : typedef struct tommy_arrayof_struct {
62 : void* bucket[TOMMY_SIZE_BIT]; /**< Dynamic array of buckets. */
63 : tommy_size_t element_size; /**< Size of the stored element in bytes. */
64 : tommy_size_t bucket_max; /**< Number of buckets. */
65 : tommy_size_t count; /**< Number of initialized elements in the array. */
66 : tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
67 : } tommy_arrayof;
68 :
69 : /**
70 : * Initializes the array.
71 : * \param element_size Size in byte of the element to store in the array.
72 : */
73 : void tommy_arrayof_init(tommy_arrayof* array, tommy_size_t element_size);
74 :
75 : /**
76 : * Deinitializes the array.
77 : */
78 : void tommy_arrayof_done(tommy_arrayof* array);
79 :
80 : /**
81 : * Grows the size up to the specified value.
82 : * All the new elements in the array are initialized with the 0 value.
83 : */
84 : void tommy_arrayof_grow(tommy_arrayof* array, tommy_size_t size);
85 :
86 : /**
87 : * Gets a reference of the element at the specified position.
88 : * You must be sure that space for this position is already
89 : * allocated calling tommy_arrayof_grow().
90 : */
91 150000000 : tommy_inline void* tommy_arrayof_ref(tommy_arrayof* array, tommy_size_t pos)
92 : {
93 : unsigned char* ptr;
94 : tommy_uint_t bsr;
95 :
96 150000000 : assert(pos < array->count);
97 :
98 : /* get the highest bit set, in case of all 0, return 0 */
99 150000000 : bsr = tommy_ilog2(pos | 1);
100 :
101 150000000 : ptr = tommy_cast(unsigned char*, array->bucket[bsr]);
102 :
103 150000000 : return ptr + pos * array->element_size;
104 : }
105 :
106 : /**
107 : * Gets the initialized size of the array.
108 : */
109 : tommy_inline tommy_size_t tommy_arrayof_size(tommy_arrayof* array)
110 : {
111 : return array->count;
112 : }
113 :
114 : /**
115 : * Gets the size of allocated memory.
116 : */
117 : tommy_size_t tommy_arrayof_memory_usage(tommy_arrayof* array);
118 :
119 : #endif
120 :
|
