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