1 /*
2 * IceWM - Simple dynamic array
3 * Copyright (C) 2001 The Authors of IceWM
4 *
5 * Release under terms of the GNU Library General Public License
6 *
7 * 2001/04/14: Mathias Hasselmann <mathias.hasselmann@gmx.net>
8 * - initial version
9 * 2002/07/31: Mathias Hasselmann <mathias.hasselmann@gmx.net>
10 * - major rewrite of the code
11 * - introduced YBaseArray to reduce overhead caused by templates
12 * - introduced YObjectArray for easy memory management
13 * - introduced YStringArray
14 */
15
16 #include "config.h"
17 #include "mstring.h"
18 #include "yarray.h"
19 #include <string.h>
20 #include <stdlib.h>
21 #include <assert.h>
22
YBaseArray(YBaseArray & other)23 YBaseArray::YBaseArray(YBaseArray &other):
24 fElementSize(other.fElementSize),
25 fCapacity(other.fCapacity),
26 fCount(other.fCount),
27 fElements(other.fElements) {
28 other.release();
29 }
30
YBaseArray(const YBaseArray & other)31 YBaseArray::YBaseArray(const YBaseArray& other):
32 fElementSize(other.fElementSize),
33 fCapacity(other.fCount),
34 fCount(other.fCount),
35 fElements(nullptr)
36 {
37 const unsigned size = unsigned(fCount) * fElementSize;
38 if (size) {
39 fElements = new StorageType[size];
40 if (fElements)
41 memcpy(fElements, other.fElements, size);
42 else
43 fCount = fCapacity = 0;
44 }
45 }
46
setCapacity(SizeType nCapacity)47 void YBaseArray::setCapacity(SizeType nCapacity) {
48 if (nCapacity != fCapacity) {
49 const unsigned newSize = unsigned(nCapacity) * fElementSize;
50 StorageType* nElements = new StorageType[newSize];
51 if (nElements == nullptr)
52 return;
53 if (fElements) {
54 if (0 < fCount) {
55 const unsigned oldSize = unsigned(fCount) * fElementSize;
56 memcpy(nElements, fElements, min(newSize, oldSize));
57 }
58 delete[] fElements;
59 }
60 fElements = nElements;
61 fCapacity = nCapacity;
62 fCount = min(fCount, fCapacity);
63 }
64 }
65
append(const void * item)66 void YBaseArray::append(const void *item) {
67 if (fCapacity < fCount + 1) {
68 setCapacity(max(fCapacity * 2, fCount + 1, 4));
69 }
70 if (fCount < fCapacity) {
71 memcpy(getElement(fCount), item, fElementSize);
72 fCount++;
73 }
74 }
75
insert(const SizeType index,const void * item)76 void YBaseArray::insert(const SizeType index, const void *item) {
77 PRECONDITION(index <= fCount);
78
79 const SizeType nCount = max(index, fCount) + 1;
80 const SizeType nCapacity(nCount <= fCapacity ? fCapacity :
81 max(nCount, fCapacity * 2, 4));
82 StorageType* nElements = fElements;
83 if (fCapacity < nCapacity) {
84 const unsigned newSize = unsigned(nCapacity) * fElementSize;
85 nElements = new StorageType[newSize];
86 if (nElements == nullptr)
87 return;
88 const SizeType head = min(index, fCount);
89 if (0 < head)
90 memcpy(nElements, fElements, unsigned(head) * fElementSize);
91 }
92
93 if (index < fCount && fElements)
94 memmove(nElements + unsigned(index + 1) * fElementSize,
95 fElements + unsigned(index) * fElementSize,
96 unsigned(fCount - index) * fElementSize);
97 else if (fCount < index && nElements)
98 memset(nElements + unsigned(fCount) * fElementSize,
99 0, unsigned(index - fCount) * fElementSize);
100
101 if (nElements != fElements) {
102 delete[] fElements;
103 fElements = nElements;
104 fCapacity = nCapacity;
105 }
106
107 memcpy(fElements + unsigned(index) * fElementSize, item, fElementSize);
108 fCount = nCount;
109
110 PRECONDITION(fCount <= fCapacity);
111 PRECONDITION(index < fCount);
112 }
113
extend(const SizeType extendedCount)114 void YBaseArray::extend(const SizeType extendedCount) {
115 if (fCapacity < extendedCount)
116 setCapacity(extendedCount);
117 if (fCount < extendedCount && extendedCount <= fCapacity) {
118 memset(fElements + unsigned(fCount) * fElementSize, 0,
119 unsigned(extendedCount - fCount) * fElementSize);
120 fCount = extendedCount;
121 }
122 }
123
remove(const SizeType index)124 void YBaseArray::remove(const SizeType index) {
125 PRECONDITION(index < getCount());
126 if (0 <= index) {
127 int tail = fCount - index - 1;
128 if (tail > 0) {
129 memmove(getElement(index), getElement(index + 1),
130 unsigned(tail) * fElementSize);
131 fCount--;
132 }
133 else if (tail == 0 && --fCount == 0)
134 clear();
135 }
136 }
137
shrink(const SizeType reducedCount)138 void YBaseArray::shrink(const SizeType reducedCount) {
139 if (reducedCount >= 0 && reducedCount <= fCount)
140 fCount = reducedCount;
141 else { PRECONDITION(false); }
142 }
143
clear()144 void YBaseArray::clear() {
145 if (fElements) {
146 delete[] fElements;
147 release();
148 }
149 }
150
release()151 void YBaseArray::release() {
152 fElements = nullptr;
153 fCapacity = 0;
154 fCount = 0;
155 }
156
swap(YBaseArray & other)157 void YBaseArray::swap(YBaseArray& other) {
158 PRECONDITION(fElementSize == other.fElementSize);
159 ::swap(fCapacity, other.fCapacity);
160 ::swap(fCount, other.fCount);
161 ::swap(fElements, other.fElements);
162 }
163
operator =(const YBaseArray & other)164 void YBaseArray::operator=(const YBaseArray& other) {
165 if (this != &other) {
166 clear();
167 if (other.nonempty()) {
168 setCapacity(other.getCount());
169 memcpy(fElements, other.fElements,
170 unsigned(fCount) * fElementSize);
171 fCount = other.getCount();
172 }
173 }
174 }
175
YStringArray(const YStringArray & other)176 YStringArray::YStringArray(const YStringArray &other) :
177 BaseType(other.getCount())
178 {
179 for (SizeType i = 0; i < other.getCount(); ++i)
180 append(other.getString(i));
181 }
182
YStringArray(const char * cstr[],SizeType num,SizeType cap)183 YStringArray::YStringArray(const char* cstr[], SizeType num, SizeType cap) :
184 BaseType(max(num, cap))
185 {
186 if (cstr) {
187 if (num == npos) {
188 for (SizeType i = 0; cstr[i]; ++i)
189 append(cstr[i]);
190 append(nullptr);
191 }
192 else {
193 for (SizeType i = 0; i < num; ++i)
194 append(cstr[i]);
195 }
196 }
197 }
198
strequal(const char * a,const char * b)199 static bool strequal(const char *a, const char *b) {
200 return a ? b && !strcmp(a, b) : !b;
201 }
202
find(const char * str)203 YStringArray::SizeType YStringArray::find(const char *str) {
204 for (SizeType i = 0; i < getCount(); ++i)
205 if (strequal(getString(i), str)) return i;
206
207 return npos;
208 }
209
remove(const SizeType index)210 void YStringArray::remove(const SizeType index) {
211 if (inrange(index, 0, getCount() - 1)) {
212 delete[] getString(index);
213 YBaseArray::remove(index);
214 }
215 }
216
replace(const SizeType index,const char * str)217 void YStringArray::replace(const SizeType index, const char *str) {
218 if (inrange(index, 0, getCount() - 1)) {
219 const char *copy = newstr(str);
220 ::swap(copy, *getItemPtr(index));
221 delete[] copy;
222 }
223 else if (index == getCount())
224 append(str);
225 }
226
clear()227 void YStringArray::clear() {
228 for (int i = 0; i < getCount(); ++i)
229 delete[] getString(i);
230 YBaseArray::clear();
231 }
232
shrink(int reducedSize)233 void YStringArray::shrink(int reducedSize) {
234 for (int n = getCount(); n > reducedSize; )
235 delete[] getString(--n);
236 BaseType::shrink(reducedSize);
237 }
238
ystring_compare(const void * p1,const void * p2)239 static int ystring_compare(const void *p1, const void *p2) {
240 return strcoll(*(char *const *)p1, *(char *const *)p2);
241 }
242
sort()243 void YStringArray::sort() {
244 if (1 < getCount())
245 qsort(getItemPtr(0), getCount(), sizeof(char *), ystring_compare);
246 }
247
getCArray() const248 char * const *YStringArray::getCArray() const {
249 return (char * const*) begin();
250 }
251
release()252 char **YStringArray::release() {
253 char **strings = (char **) begin();
254 YBaseArray::release();
255 return strings;
256 }
257
mstring_compare(const void * p1,const void * p2)258 static int mstring_compare(const void *p1, const void *p2)
259 {
260 const mstring* s1 = static_cast<const mstring*>(p1);
261 const mstring* s2 = static_cast<const mstring*>(p2);
262 return const_cast<mstring*>(s1)->collate(*const_cast<mstring*>(s2));
263 }
264
sort()265 void MStringArray::sort() {
266 if (1 < getCount())
267 qsort(getItemPtr(0), getCount(), sizeof(mstring), mstring_compare);
268 }
269
testOnce(const char * file,const int line)270 bool testOnce(const char* file, const int line) {
271 static YArray<unsigned long> list;
272 unsigned long hash = strhash(file) * 0x10001 ^ line;
273 return find(list, hash) < 0 ? list.append(hash), true : false;
274 }
275
276 // vim: set sw=4 ts=4 et:
277