Mercurial > projects > hoofbaby

comparison src/impl/hoofbaby/util/array.d @ 0:3425707ddbf6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import (hopefully this mercurial stuff works...)
author fraserofthenight
date Mon, 06 Jul 2009 08:06:28 -0700
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3425707ddbf6
1 /**
2 * Hoofbaby -- http://www.dsource.org/projects/hoofbaby
3 * Copyright (C) 2009 Robert Fraser
4 *
5 * This program is free software; you can redistribute it andor
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 */
15
16 module hoofbaby.util.array;
17
18 import tango.core.BitManip : bsr;
19 import tango.core.Traits : isReferenceType;
20 import tango.core.Memory : GC;
21 import tango.stdc.string : memcpy, memset;
22
23
24 public struct Array(T, size_t START_SIZE = 16, bool doScan = isReferenceType!(T),
25 alias Realloc = GC.realloc, alias Free = GC.free)
26 {
27 T* arr = null;
28 size_t len = 0;
29 size_t cap = 0;
30
31 public void opCatAssign(T v)
32 {
33 len++;
34 if(len >= cap)
35 grow(cap ? cap * 2 : START_SIZE);
36 arr[len - 1] = v;
37 }
38
39 public void opCatAssign(T[] v)
40 {
41 int newlen = len + v.length;
42 if(newlen > cap)
43 {
44 if(newlen < START_SIZE)
45 grow(START_SIZE);
46 else
47 grow(2 << bsr(newlen + 1)); // Next power of 2
48 }
49 memcpy(arr + len, v.ptr, (newlen - len) * T.sizeof);
50 len = newlen;
51 }
52
53 public void opCatAssign(Array!(T) v)
54 {
55 opCatAssign(v.toArray());
56 }
57
58 public T[] toArray()
59 {
60 return arr[0 .. len];
61 }
62
63 public size_t length()
64 {
65 return len;
66 }
67
68 public T opIndex(size_t n)
69 {
70 assert(n < len);
71 return arr[n];
72 }
73
74 public void opIndexAssign(T v, size_t n)
75 {
76 assert(n < len);
77 arr[n] = v;
78 }
79
80 public T[] opSlice()
81 {
82 return toArray();
83 }
84
85 public T[] opSlice(size_t low, size_t high)
86 {
87 assert(low <= high);
88 assert(high < len);
89 return arr[low .. high];
90 }
91
92 public void opSliceAssign(T v)
93 {
94 arr[0 .. len] = v;
95 }
96
97 public void opSliceAssign(T v, size_t low, size_t high)
98 {
99 assert(low <= high);
100 assert(high < len);
101 arr[low .. high] = v;
102 }
103
104 public void opSliceAssign(T[] v, size_t low, size_t high)
105 {
106 assert(low <= high);
107 assert(high < len);
108 assert(v.length == high - low);
109 memcpy(arr + low, v.ptr, v.length * T.sizeof);
110 }
111
112 public void opSliceAssign(Array!(T) v, size_t low, size_t high)
113 {
114 opSliceAssign(v.toArray(), low, high);
115 }
116
117 public bool isEmpty()
118 {
119 return len == 0;
120 }
121
122 public void clear()
123 {
124 len = 0;
125 }
126
127 public void free()
128 {
129 if(arr)
130 {
131 Free(arr);
132 arr = null;
133 }
134 len = 0;
135 }
136
137 public void zero()
138 {
139 if(arr)
140 {
141 memset(arr, 0, cap * T.sizeof);
142 Free(arr);
143 arr = null;
144 }
145 len = 0;
146 }
147
148 public void addNull()
149 {
150 len++;
151 if(len >= cap)
152 grow(cap ? cap * 2 : START_SIZE);
153 }
154
155 public bool contains(T elem)
156 {
157 for(int i = 0; i < len; i++)
158 if(arr[i] == elem)
159 return true;
160 return false;
161 }
162
163 static if(doScan)
164 private static const BlkAttr = 0;
165 else
166 private static const BlkAttr = GC.BlkAttr.NO_SCAN;
167
168 private void grow(size_t sz)
169 {
170 arr = cast(T*) Realloc(arr, sz * T.sizeof, BlkAttr);
171 static if(doScan)
172 {
173 memset(arr + cap, 0, (sz - cap) * T.sizeof);
174 }
175 cap = sz;
176 }
177 }
178
179 public struct Stack(T, size_t START_SIZE = 16, bool doScan = true, bool zeroOnPop = false,
180 alias ArrayType = Array, ArrayArgs...)
181 {
182 private ArrayType!(T, START_SIZE, doScan, ArrayArgs) arr;
183
184 public void pushNull()
185 {
186 arr.addNull();
187 }
188
189 public void push(T v)
190 {
191 arr ~= v;
192 }
193
194 public T pop()
195 {
196 assert(arr.len > 0);
197 T ret = arr.arr[arr.len - 1];
198 static if(zeroOnPop)
199 arr.arr[arr.len - 1] = T.init;
200 arr.len--;
201 return ret;
202 }
203
204 public T peek()
205 {
206 assert(arr.len > 0);
207 return arr.arr[arr.len - 1];
208 }
209
210 public bool isEmpty()
211 {
212 return arr.isEmpty();
213 }
214
215 public void clear()
216 {
217 static if(zeroOnPop)
218 arr.zero();
219 else
220 arr.clear();
221 }
222
223 public bool contains(T elem)
224 {
225 return arr.contains(elem);
226 }
227
228 public T[] toArray()
229 {
230 return arr.toArray();
231 }
232 }