Debian Codegraph @

Source/Utilities/Container/CQtManagedRestrictedModificationListData.cpp

raw
1 /*
2 * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
3 *
4 * This file is part of the reasoning system Konclude.
5 * For details and support, see <http://konclude.com/>.
6 *
7 * Konclude is free software: you can redistribute it and/or modify
8 * it under the terms of version 3 of the GNU Lesser General Public
9 * License (LGPLv3) as published by the Free Software Foundation.
10 *
11 * Konclude is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU (Lesser) General Public License for more details.
15 *
16 * You should have received a copy of the GNU (Lesser) General Public
17 * License along with Konclude. If not, see <http://www.gnu.org/licenses/>.
18 *
19 * This file incorporates work covered by the following copyright and
20 * permission notice (to be compatible with LGPLv2.1,
21 * this code is available/released under GPLv3,
22 * see https://www.gnu.org/licenses/gpl-faq.html#AllCompatibility):
23 *
24 *
25 * Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
26 * Contact: http://www.qt-project.org/legal
27 *
28 * This file is part of the QtCore module of the Qt Toolkit.
29 *
30 * $QT_BEGIN_LICENSE:LGPL$
31 * Commercial License Usage
32 * Licensees holding valid commercial Qt licenses may use this file in
33 * accordance with the commercial license agreement provided with the
34 * Software or, alternatively, in accordance with the terms contained in
35 * a written agreement between you and Digia. For licensing terms and
36 * conditions see http://qt.digia.com/licensing. For further information
37 * use the contact form at http://qt.digia.com/contact-us.
38 *
39 * GNU Lesser General Public License Usage
40 * Alternatively, this file may be used under the terms of the GNU Lesser
41 * General Public License version 2.1 as published by the Free Software
42 * Foundation and appearing in the file LICENSE.LGPL included in the
43 * packaging of this file. Please review the following information to
44 * ensure the GNU Lesser General Public License version 2.1 requirements
45 * will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
46 *
47 * In addition, as a special exception, Digia gives you certain additional
48 * rights. These rights are described in the Digia Qt LGPL Exception
49 * version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
50 *
51 * GNU General Public License Usage
52 * Alternatively, this file may be used under the terms of the GNU
53 * General Public License version 3.0 as published by the Free Software
54 * Foundation and appearing in the file LICENSE.GPL included in the
55 * packaging of this file. Please review the following information to
56 * ensure the GNU General Public License version 3.0 requirements will be
57 * met: http://www.gnu.org/copyleft/gpl.html.
58 *
59 *
60 * $QT_END_LICENSE$
61 *
62 *
63 */
64
65 #include "CQtManagedRestrictedModificationListData.h"
66
67
68 namespace Konclude {
69
70 namespace Utilities {
71
72 namespace Container {
73
74
75 #ifdef KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_LIST_CONTAINER
76
77
78
79 CQtManagedRestrictedModificationListData::Data CQtManagedRestrictedModificationListData::shared_null = { nullptr, 0, 0, 0, true, { 0 } };
80
81
82
83 int cAllocMore(int alloc, int extra)
84 {
85 if (alloc == 0 && extra == 0)
86 return 0;
87 const int page = 1 << 12;
88 int nalloc;
89 alloc += extra;
90 if (alloc < 1<<6) {
91 nalloc = (1<<3) + ((alloc >>3) << 3);
92 } else {
93 // don't do anything if the loop will overflow signed int.
94 if (alloc >= INT_MAX/2)
95 return INT_MAX;
96 nalloc = (alloc < page) ? 1 << 3 : page;
97 while (nalloc < alloc) {
98 if (nalloc <= 0)
99 return INT_MAX;
100 nalloc *= 2;
101 }
102 }
103 return nalloc - extra;
104 }
105
106
107 static int grow(int size, CMemoryAllocationManager* memMan)
108 {
109 // dear compiler: don't optimize me out.
110 //if (!memMan) {
111 volatile int x = cAllocMore(size * sizeof(void *), CQtManagedRestrictedModificationListData::DataHeaderSize) / sizeof(void *);
112 return x;
113 /*} else {
114 return memMan->getOptimizedMoreAllocationSize(size * sizeof(void *)+ CQtManagedRestrictedModificationListData::DataHeaderSize) / sizeof(void *);
115 }*/
116 }
117
118 /*!
119 * Detaches the CQtManagedRestrictedModificationListData by allocating new memory for a list which will be bigger
120 * than the copied one and is expected to grow further.
121 * *idx is the desired insertion point and is clamped to the actual size of the list.
122 * num is the number of new elements to insert at the insertion point.
123 * Returns the old (shared) data, it is up to the caller to deref() and free().
124 * For the new data node_copy needs to be called.
125 *
126 * \internal
127 */
128 CQtManagedRestrictedModificationListData::Data *CQtManagedRestrictedModificationListData::detach_grow(int *idx, int num, CMemoryAllocationManager* memMan, CQtManagedRestrictedModificationListBase* listBase)
129 {
130 Data *x = d;
131 int l = x->end - x->begin;
132 int nl = l + num;
133 int alloc = grow(nl,memMan);
134 Data* t = static_cast<Data *>(CMemoryAllocator::allocateMemory(memMan,DataHeaderSize + alloc * sizeof(void *)));
135 Q_CHECK_PTR(t);
136
137 //t->ref = 1;
138 t->refList = listBase;
139 t->sharable = true;
140 t->alloc = alloc;
141 // The space reservation algorithm's optimization is biased towards appending:
142 // Something which looks like an append will put the data at the beginning,
143 // while something which looks like a prepend will put it in the middle
144 // instead of at the end. That's based on the assumption that prepending
145 // is uncommon and even an initial prepend will eventually be followed by
146 // at least some appends.
147 int bg;
148 if (*idx < 0) {
149 *idx = 0;
150 bg = (alloc - nl) >> 1;
151 } else if (*idx > l) {
152 *idx = l;
153 bg = 0;
154 } else if (*idx < (l >> 1)) {
155 bg = (alloc - nl) >> 1;
156 } else {
157 bg = 0;
158 }
159 t->begin = bg;
160 t->end = bg + nl;
161 d = t;
162
163 return x;
164 }
165
166
167 /*!
168 * Detaches the CQtManagedRestrictedModificationListData by allocating new memory for a list which possibly
169 * has a different size than the copied one.
170 * Returns the old (shared) data, it is up to the caller to deref() and free()
171 * For the new data node_copy needs to be called.
172 *
173 * \internal
174 */
175 CQtManagedRestrictedModificationListData::Data *CQtManagedRestrictedModificationListData::detach(int alloc, CMemoryAllocationManager* memMan, CQtManagedRestrictedModificationListBase* listBase)
176 {
177 Data *x = d;
178 Data* t = nullptr;
179 //t = static_cast<Data *>(qMalloc(DataHeaderSize + alloc * sizeof(void *)));
180 t = static_cast<Data *>(CMemoryAllocator::allocateMemory(memMan,DataHeaderSize + alloc * sizeof(void *)));
181 Q_CHECK_PTR(t);
182
183 //t->ref = 1;
184 t->refList = listBase;
185 t->sharable = true;
186 t->alloc = alloc;
187 if (!alloc) {
188 t->begin = 0;
189 t->end = 0;
190 } else {
191 t->begin = x->begin;
192 t->end = x->end;
193 }
194 d = t;
195
196 return x;
197 }
198
199
200 // ensures that enough space is available to append n elements
201 void **CQtManagedRestrictedModificationListData::append(int n, CMemoryAllocationManager* memMan)
202 {
203 //Q_ASSERT(d->ref == 1);
204 int e = d->end;
205 if (e + n > d->alloc) {
206 int b = d->begin;
207 if (b - n >= 2 * d->alloc / 3) {
208 // we have enough space. Just not at the end -> move it.
209 e -= b;
210 ::memcpy(d->array, d->array + b, e * sizeof(void *));
211 d->begin = 0;
212 } else {
213 realloc(grow(d->alloc + n,memMan),memMan);
214 }
215 }
216 d->end = e + n;
217 return d->array + e;
218 }
219
220 // ensures that enough space is available to append one element
221 void **CQtManagedRestrictedModificationListData::append(CMemoryAllocationManager* memMan)
222 {
223 return append(1,memMan);
224 }
225
226 // ensures that enough space is available to append the list
227 void **CQtManagedRestrictedModificationListData::append2(const CQtManagedRestrictedModificationListData& l, CMemoryAllocationManager* memMan)
228 {
229 return append(l.d->end - l.d->begin,memMan);
230 }
231
232 void **CQtManagedRestrictedModificationListData::append(const CQtManagedRestrictedModificationListData& l, CMemoryAllocationManager* memMan)
233 {
234 //Q_ASSERT(d->ref == 1);
235 int e = d->end;
236 int n = l.d->end - l.d->begin;
237 if (n) {
238 if (e + n > d->alloc)
239 realloc(grow(e + n,memMan),memMan);
240 ::memcpy(d->array + d->end, l.d->array + l.d->begin, n*sizeof(void*));
241 d->end += n;
242 }
243 return d->array + e;
244 }
245
246
247 void **CQtManagedRestrictedModificationListData::prepend(CMemoryAllocationManager* memMan)
248 {
249 //Q_ASSERT(d->ref == 1);
250 if (d->begin == 0) {
251 if (d->end >= d->alloc / 3)
252 realloc(grow(d->alloc + 1,memMan),memMan);
253
254 if (d->end < d->alloc / 3)
255 d->begin = d->alloc - 2 * d->end;
256 else
257 d->begin = d->alloc - d->end;
258
259 ::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));
260 d->end += d->begin;
261 }
262 return d->array + --d->begin;
263 }
264
265 void **CQtManagedRestrictedModificationListData::insert(int i, CMemoryAllocationManager* memMan)
266 {
267 //Q_ASSERT(d->ref == 1);
268 if (i <= 0)
269 return prepend(memMan);
270 int size = d->end - d->begin;
271 if (i >= size)
272 return append(memMan);
273
274 bool leftward = false;
275
276 if (d->begin == 0) {
277 if (d->end == d->alloc) {
278 // If the array is full, we expand it and move some items rightward
279 realloc(grow(d->alloc + 1,memMan),memMan);
280 } else {
281 // If there is free space at the end of the array, we move some items rightward
282 }
283 } else {
284 if (d->end == d->alloc) {
285 // If there is free space at the beginning of the array, we move some items leftward
286 leftward = true;
287 } else {
288 // If there is free space at both ends, we move as few items as possible
289 leftward = (i < size - i);
290 }
291 }
292
293 if (leftward) {
294 --d->begin;
295 ::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));
296 } else {
297 ::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,
298 (size - i) * sizeof(void *));
299 ++d->end;
300 }
301 return d->array + d->begin + i;
302 }
303
304 void CQtManagedRestrictedModificationListData::remove(int i)
305 {
306 //Q_ASSERT(d->ref == 1);
307 i += d->begin;
308 if (i - d->begin < d->end - i) {
309 if (int offset = i - d->begin)
310 ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
311 d->begin++;
312 } else {
313 if (int offset = d->end - i - 1)
314 ::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));
315 d->end--;
316 }
317 }
318
319 void CQtManagedRestrictedModificationListData::remove(int i, int n)
320 {
321 //Q_ASSERT(d->ref == 1);
322 i += d->begin;
323 int middle = i + n/2;
324 if (middle - d->begin < d->end - middle) {
325 ::memmove(d->array + d->begin + n, d->array + d->begin,
326 (i - d->begin) * sizeof(void*));
327 d->begin += n;
328 } else {
329 ::memmove(d->array + i, d->array + i + n,
330 (d->end - i - n) * sizeof(void*));
331 d->end -= n;
332 }
333 }
334
335 void CQtManagedRestrictedModificationListData::move(int from, int to)
336 {
337 //Q_ASSERT(d->ref == 1);
338 if (from == to)
339 return;
340
341 from += d->begin;
342 to += d->begin;
343 void *t = d->array[from];
344
345 if (from < to) {
346 if (d->end == d->alloc || 3 * (to - from) < 2 * (d->end - d->begin)) {
347 ::memmove(d->array + from, d->array + from + 1, (to - from) * sizeof(void *));
348 } else {
349 // optimization
350 if (int offset = from - d->begin)
351 ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
352 if (int offset = d->end - (to + 1))
353 ::memmove(d->array + to + 2, d->array + to + 1, offset * sizeof(void *));
354 ++d->begin;
355 ++d->end;
356 ++to;
357 }
358 } else {
359 if (d->begin == 0 || 3 * (from - to) < 2 * (d->end - d->begin)) {
360 ::memmove(d->array + to + 1, d->array + to, (from - to) * sizeof(void *));
361 } else {
362 // optimization
363 if (int offset = to - d->begin)
364 ::memmove(d->array + d->begin - 1, d->array + d->begin, offset * sizeof(void *));
365 if (int offset = d->end - (from + 1))
366 ::memmove(d->array + from, d->array + from + 1, offset * sizeof(void *));
367 --d->begin;
368 --d->end;
369 --to;
370 }
371 }
372 d->array[to] = t;
373 }
374
375 void **CQtManagedRestrictedModificationListData::erase(void **xi)
376 {
377 //Q_ASSERT(d->ref == 1);
378 int i = xi - (d->array + d->begin);
379 remove(i);
380 return d->array + d->begin + i;
381 }
382
383 void CQtManagedRestrictedModificationListData::realloc(int alloc, CMemoryAllocationManager* memMan)
384 {
385 //Q_ASSERT(d->ref == 1);
386 //Data *x = static_cast<Data *>(qRealloc(d, DataHeaderSize + alloc * sizeof(void *)));
387 Data *x = nullptr;
388 x = static_cast<Data *>(CMemoryAllocator::reallocateMemory(d,memMan, DataHeaderSize + d->alloc * sizeof(void *), DataHeaderSize + alloc * sizeof(void *)));
389 Q_CHECK_PTR(x);
390
391 d = x;
392 d->alloc = alloc;
393 if (!alloc)
394 d->begin = d->end = 0;
395 }
396
397
398 #endif // KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_LIST_CONTAINER
399
400
401 }; // end namespace Container
402
403 }; // end namespace Utilities
404
405 }; // end namespace Konclude
406