1 // util/array.h -- Dynamically sized arrays
3 // This software is copyright (c) 2007 Scott Wood <scott@buserror.net>.
5 // This software is provided 'as-is', without any express or implied warranty.
6 // In no event will the authors or contributors be held liable for any damages
7 // arising from the use of this software.
9 // Permission is hereby granted to everyone, free of charge, to use, copy,
10 // modify, prepare derivative works of, publish, distribute, perform,
11 // sublicense, and/or sell copies of the Software, provided that the above
12 // copyright notice and disclaimer of warranty be included in all copies or
13 // substantial portions of this software.
32 static const NullArray nullarray = {};
34 template<typename T, typename Alloc = ::System::RunTime::ORBMM> struct MutableArray {
38 bool valid_index(size_t index)
40 return index >= 0 && index < count;
43 T &operator[](size_t index)
45 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
46 if (!valid_index(index))
47 throw ArrayException();
59 MutableArray(NullArray na)
65 MutableArray(T *PTR, size_t COUNT)
71 MutableArray &slice_nocheck(size_t first, size_t newcount)
74 ret.ptr = ptr + first;
79 MutableArray &slice_nocheck(size_t first)
82 ret.ptr = ptr + first;
83 ret.count = count - first;
87 MutableArray &slice(size_t first, size_t count)
89 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
90 if (!valid_index(first) || !valid_index(first + count - 1))
91 throw ArrayException();
94 return slice_nocheck(first, count);
97 MutableArray &slice(size_t first)
99 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
100 if (!valid_index(first))
101 throw ArrayException();
104 return slice_nocheck(first);
109 MutableArray new_arr;
110 new_arr.ptr = new(Alloc()) T[count];
111 new_arr.count = count;
112 memcpy(new_arr.ptr, ptr, count);
117 template<typename T, typename Alloc = ::System::RunTime::ORBMM>
118 struct GrowableArray : public MutableArray<T, Alloc> {
119 using MutableArray<T, Alloc>::ptr;
120 using MutableArray<T, Alloc>::count;
128 GrowableArray(NullArray na) : MutableArray<T, Alloc>(na)
133 GrowableArray(T *PTR, size_t COUNT) : MutableArray<T, Alloc>(PTR, COUNT)
138 GrowableArray(T *PTR, size_t COUNT, size_t BUFSIZE) :
139 MutableArray<T, Alloc>(PTR, COUNT)
144 GrowableArray(MutableArray<T, Alloc> &ma) : MutableArray<T, Alloc>(ma)
149 // FIXME: use realloc
150 void grow(size_t newsize)
152 if (newsize <= bufsize)
156 T *newptr = new(Alloc()) T[newsize];
158 memcpy(newptr, ptr, count * sizeof(T));
159 memset(newptr + count, 0, (newsize - count) * sizeof(T));
162 ll_smp_membar_store_after_store();
164 ll_smp_membar_any_after_store();
166 Alloc::release(oldptr);
169 T *grow_by(size_t len, size_t max = ULONG_MAX)
171 size_t oldcount = count;
173 if (count + len < count)
174 throw ArrayException();
176 if (count + len > max)
177 throw ArrayException();
179 if (count + len > bufsize)
180 grow(ll_get_order_round_up(count + len));
182 return ptr + oldcount;
185 // align must be power-of-two
186 void align_to(size_t align, size_t max = ULONG_MAX)
188 size_t newcount = (count + align - 1) & ~(align - 1);
190 if (newcount < count)
191 throw ArrayException();
194 throw ArrayException();
196 if (newcount > bufsize)
197 grow(ll_get_order_round_up(newcount));
200 // Caller must sync against all writers.
201 void append(T *newptr, size_t len, size_t max = ULONG_MAX)
203 memcpy(ptr + grow_by(len, max), newptr, len * sizeof(T));
208 template<typename T, typename Alloc = ::System::RunTime::ORBMM> struct Array {
212 bool valid_index(size_t index)
214 return index >= 0 && index < count;
217 const T &operator[](size_t index)
219 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
220 if (!valid_index(index))
221 throw ArrayException();
239 Array(const T *PTR, size_t COUNT)
245 Array(MutableArray<T, Alloc> ma)
251 MutableArray<T, Alloc> constcast()
253 MutableArray<T, Alloc> ma;
254 ma.ptr = const_cast<T>(ptr);
259 Array &slice_nocheck(size_t first, size_t newcount)
262 ret.ptr = ptr + first;
263 ret.count = newcount;
267 Array &slice_nocheck(size_t first)
270 ret.ptr = ptr + first;
271 ret.count = count - first;
275 Array &slice(size_t first, size_t count)
277 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
278 if (!valid_index(first) || !valid_index(first + count - 1))
279 throw ArrayException();
282 return slice_nocheck(first, count);
285 Array &slice(size_t first)
287 #ifndef POLINTOS_NO_ARRAY_BOUNDS_CHECK
288 if (!valid_index(first))
289 throw ArrayException();
292 return slice_nocheck(first);
295 MutableArray<T, Alloc> copy()
297 MutableArray<T, Alloc> new_arr;
298 new_arr.ptr = new(Alloc()) T[count];
299 new_arr.count = count;
300 memcpy(new_arr.ptr, ptr, count);
305 template<typename Alloc>
306 static inline Array<uint8_t, Alloc>
307 countarray(const char *ptr)
309 Array<uint8_t, Alloc> ret;
310 ret.ptr = reinterpret_cast<const uint8_t *>(ptr);
311 ret.count = strlen(ptr);
315 template<typename Alloc>
316 static inline MutableArray<uint8_t, Alloc>
317 countarray(char *ptr)
319 MutableArray<uint8_t, Alloc> ret;
320 ret.ptr = reinterpret_cast<uint8_t *>(ptr);
321 ret.count = strlen(ptr);
326 using namespace Arrays;