BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file grow_array.h
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
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 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29  
30 // Preprocessor inputs:
31 // GROWARRAY_NAME - prefix of of functions to define
32 // GROWARRAY_OBJECT_TYPE - type of structure where array and capacity sizes are
33 // GROWARRAY_ARRAY_MEMBER - array member
34 // GROWARRAY_CAPACITY_MEMBER - capacity member
35 // GROWARRAY_MAX_CAPACITY - max value of capacity member
36  
37 #include <limits.h>
38 #include <string.h>
39 #include <stddef.h>
40  
41 #include <misc/debug.h>
42 #include <misc/balloc.h>
43 #include <misc/merge.h>
44  
45 #define GrowArrayObject GROWARRAY_OBJECT_TYPE
46 #define GrowArray_Init MERGE(GROWARRAY_NAME, _Init)
47 #define GrowArray_InitEmpty MERGE(GROWARRAY_NAME, _InitEmpty)
48 #define GrowArray_Free MERGE(GROWARRAY_NAME, _Free)
49 #define GrowArray_DoubleUp MERGE(GROWARRAY_NAME, _DoubleUp)
50 #define GrowArray_DoubleUpLimit MERGE(GROWARRAY_NAME, _DoubleUpLimit)
51  
52 static int GrowArray_Init (GrowArrayObject *o, size_t capacity) WARN_UNUSED;
53 static void GrowArray_InitEmpty (GrowArrayObject *o);
54 static void GrowArray_Free (GrowArrayObject *o);
55 static int GrowArray_DoubleUp (GrowArrayObject *o) WARN_UNUSED;
56 static int GrowArray_DoubleUpLimit (GrowArrayObject *o, size_t limit) WARN_UNUSED;
57  
58 static int GrowArray_Init (GrowArrayObject *o, size_t capacity)
59 {
60 if (capacity > GROWARRAY_MAX_CAPACITY) {
61 return 0;
62 }
63  
64 if (capacity == 0) {
65 o->GROWARRAY_ARRAY_MEMBER = NULL;
66 } else {
67 if (!(o->GROWARRAY_ARRAY_MEMBER = BAllocArray(capacity, sizeof(o->GROWARRAY_ARRAY_MEMBER[0])))) {
68 return 0;
69 }
70 }
71  
72 o->GROWARRAY_CAPACITY_MEMBER = capacity;
73  
74 return 1;
75 }
76  
77 static void GrowArray_InitEmpty (GrowArrayObject *o)
78 {
79 o->GROWARRAY_ARRAY_MEMBER = NULL;
80 o->GROWARRAY_CAPACITY_MEMBER = 0;
81 }
82  
83 static void GrowArray_Free (GrowArrayObject *o)
84 {
85 if (o->GROWARRAY_ARRAY_MEMBER) {
86 BFree(o->GROWARRAY_ARRAY_MEMBER);
87 }
88 }
89  
90 static int GrowArray_DoubleUp (GrowArrayObject *o)
91 {
92 return GrowArray_DoubleUpLimit(o, SIZE_MAX);
93 }
94  
95 static int GrowArray_DoubleUpLimit (GrowArrayObject *o, size_t limit)
96 {
97 if (o->GROWARRAY_CAPACITY_MEMBER > SIZE_MAX / 2 || o->GROWARRAY_CAPACITY_MEMBER > GROWARRAY_MAX_CAPACITY / 2) {
98 return 0;
99 }
100  
101 size_t newcap = 2 * o->GROWARRAY_CAPACITY_MEMBER;
102 if (newcap == 0) {
103 newcap = 1;
104 }
105  
106 if (newcap > limit) {
107 newcap = limit;
108 if (newcap == o->GROWARRAY_CAPACITY_MEMBER) {
109 return 0;
110 }
111 }
112  
113 void *newarr = BAllocArray(newcap, sizeof(o->GROWARRAY_ARRAY_MEMBER[0]));
114 if (!newarr) {
115 return 0;
116 }
117  
118 memcpy(newarr, o->GROWARRAY_ARRAY_MEMBER, o->GROWARRAY_CAPACITY_MEMBER * sizeof(o->GROWARRAY_ARRAY_MEMBER[0]));
119  
120 BFree(o->GROWARRAY_ARRAY_MEMBER);
121  
122 o->GROWARRAY_ARRAY_MEMBER = newarr;
123 o->GROWARRAY_CAPACITY_MEMBER = newcap;
124  
125 return 1;
126 }
127  
128 #undef GROWARRAY_NAME
129 #undef GROWARRAY_OBJECT_TYPE
130 #undef GROWARRAY_ARRAY_MEMBER
131 #undef GROWARRAY_CAPACITY_MEMBER
132 #undef GROWARRAY_MAX_CAPACITY
133  
134 #undef GrowArrayObject
135 #undef GrowArray_Init
136 #undef GrowArray_InitEmpty
137 #undef GrowArray_Free
138 #undef GrowArray_DoubleUp
139 #undef GrowArray_DoubleUpLimit