1 /*******************************************************************************
2 3 Template for a struct implementing a single bucket in a set (see
4 ocean.util.container.map.model.BucketSet). A bucket contains a set of
5 elements which can be added to, removed from and searched.
6 7 Each element in a bucket has a unique key with which it can be identified.
8 The elements' key type is templated, but defaults to hash_t. A bucket can
9 only contain one element with a given key - if a duplicate is added it will
10 replace the original. The elements in the bucket are stored as a linked
11 list, for easy removal and insertion.
12 13 Note that the bucket does not own its elements, these must be managed from
14 the outside in a pool. The bucket itself simply keeps a pointer to the first
15 element which it contains.
16 17 Two element structs exist in this module, one for a basic bucket element,
18 and one for a bucket element which contains a value in addition to a key.
19 20 Usage:
21 See ocean.util.container.map.model.BucketSet,
22 ocean.util.container.map.HashMap & ocean.util.container.map.HashSet
23 24 Copyright:
25 Copyright (c) 2009-2016 dunnhumby Germany GmbH.
26 All rights reserved.
27 28 License:
29 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
30 Alternatively, this file may be distributed under the terms of the Tango
31 3-Clause BSD License (see LICENSE_BSD.txt for details).
32 33 *******************************************************************************/34 35 moduleocean.util.container.map.model.Bucket;
36 37 38 importocean.meta.traits.Basic;
39 40 /*******************************************************************************
41 42 Template to be mixed in to a bucket element. Contains the shared core
43 members of a bucket element.
44 45 This template mixin is used so that we can use structs for the bucket
46 elements rather than classes, thus avoiding the memory overhead of class
47 instances. In the case of bucket elements, which could exist in quantities
48 of many thousands, this is significant.
49 50 Using structs instead of classes means that we can't use an interface or
51 base class, and the Bucket struct (below) has to simply assume that the
52 Element struct has certain members. As it's purely internal, we can live
53 with this.
54 55 Params:
56 V = value size (.sizeof of the value type), may be 0 to store no value
57 K = key type
58 59 *******************************************************************************/60 61 publicstructBucket ( size_tV, K = hash_t )
62 {
63 /**************************************************************************
64 65 Bucket element type
66 67 **************************************************************************/68 69 structElement70 {
71 /**********************************************************************
72 73 Element value, may be a dummy of zero size if no value is stored.
74 75 !!! WARNING !!!
76 77 Is extremely important that this "val" is at the top of the struct,
78 otherwise the struct can get into alignment issues that can cause
79 the GC to miss the pointers in the data.
80 81 **********************************************************************/82 83 publicaliasubyte[V] Val;
84 85 union86 {
87 publicValval;
88 89 /**********************************************************************
90 91 Mark this memory as potentially containing pointers and align size of data
92 to next multiple of (void*).sizeof.
93 94 **********************************************************************/95 privatevoid*[(V + (void*).sizeof - 1) / (void*).sizeof] _void;
96 }
97 98 /**********************************************************************
99 100 Make sure val is properly aligned.
101 102 See http://www.digitalmars.com/d/1.0/attribute.html#align
103 104 **********************************************************************/105 106 staticassert(val.offsetof == 0);
107 108 /**********************************************************************
109 110 Key = bucket element key type
111 112 **********************************************************************/113 114 publicaliasKKey;
115 116 /**********************************************************************
117 118 Element key
119 120 **********************************************************************/121 122 publicKeykey;
123 124 /**********************************************************************
125 126 Make sure key is properly aligned.
127 128 **********************************************************************/129 130 staticassert(key.offsetof % size_t.sizeof == 0);
131 132 /**********************************************************************
133 134 Next and previous element. For the first/last bucket element
135 next/prev is null, respectively.
136 137 **********************************************************************/138 139 packageElement* next = null;
140 141 debug (HostingArrayMapBucket) privateBucket!(V, K)* bucket;
142 }
143 144 /**************************************************************************
145 146 First bucket element
147 148 **************************************************************************/149 150 packageElement* first = null;
151 152 /**************************************************************************
153 154 Tells whether there is at least one element in this bucket.
155 156 Returns:
157 false if the bucket is empty or true otherwise.
158 159 **************************************************************************/160 161 publicboolhas_element ( )
162 {
163 returnthis.first !isnull;
164 }
165 166 /**************************************************************************
167 168 Looks up the element whose key equals key.
169 170 Params:
171 key = element key
172 173 Returns:
174 the element whose key equals key or null if not found.
175 176 **************************************************************************/177 178 publicElement* find ( inElement.Keykey )
179 out (element)
180 {
181 debug (HostingArrayMapBucket) if (element)
182 {
183 assert (element.bucket, "bucket not set in found element");
184 assert (element.bucketis &this,
185 "element found is not from this bucket");
186 }
187 }
188 do189 {
190 for (Element* element = this.first; element; element = element.next)
191 {
192 if (element.key == key)
193 {
194 returnelement;
195 }
196 }
197 198 returnnull;
199 }
200 201 202 /**************************************************************************
203 204 Adds a bucket element with key as key.
205 206 The element is inserted as the first bucket element.
207 208 Params:
209 key = key for the new element
210 new_element = expression returning a new element, evaluated exactly
211 once, if the key to be added does not already exist in the
212 bucket
213 214 Returns:
215 pointer to inserted element
216 217 Out:
218 The returned pointer is never null.
219 220 **************************************************************************/221 222 publicElement* add ( Element.Keykey, lazyElement* new_element )
223 out (element)
224 {
225 assert (element !isnull);
226 }
227 do228 {
229 Element* element = this.find(key);
230 231 if (!element)
232 {
233 element = this.add(new_element);
234 235 staticif (isArrayType!(K) == ArrayKind.Static)
236 {
237 element.key[] = key;
238 }
239 else240 {
241 element.key = key;
242 }
243 }
244 245 returnelement;
246 }
247 248 249 /**************************************************************************
250 251 Adds an element to the bucket.
252 253 The element is inserted as the first bucket element.
254 255 Params:
256 element = element to add
257 258 Returns:
259 element
260 261 **************************************************************************/262 263 publicElement* add ( Element* element )
264 in265 {
266 debug (HostingArrayMapBucket) element.bucket = &this;
267 }
268 out269 {
270 debug (HostingArrayMapBucket)
271 {
272 // Check for cyclic links using 2 pointers, one which traverse273 // twice as fast as the first one274 autoptr1 = this.first;
275 autoptr2 = ptr1;
276 277 // Find meeting point278 while(ptr2 !isnull)
279 {
280 ptr1 = ptr1.next;
281 if (ptr2.next == null)
282 break; // We reached end of the list, no loop283 else284 ptr2 = ptr2.next.next;
285 286 assert(ptr1 !isptr2, "Cyclic linked-list found");
287 }
288 }
289 }
290 do291 {
292 element.next = this.first;
293 this.first = element;
294 295 returnelement;
296 }
297 298 /**************************************************************************
299 300 Looks up the element corresponding to key in this bucket and removes it,
301 if found.
302 303 The removed element must be recycled by the owner of the bucket.
304 305 Params:
306 key = key of the element to remove
307 308 Returns:
309 removed element or null if not found.
310 311 **************************************************************************/312 313 publicElement* remove ( Kkey )
314 out (removed)
315 {
316 if (removed !isnull)
317 {
318 assert (removed.nextisnull, "remove: forgot to clear removed.next");
319 320 debug (HostingArrayMapBucket) if (removed)
321 {
322 assert (removed.bucketis &this,
323 "element to remove is not from this bucket");
324 325 removed.bucket = null;
326 }
327 }
328 }
329 do330 {
331 if (this.first !isnull)
332 {
333 if (this.first.key == key)
334 {
335 Element* removed = this.first;
336 337 this.first = this.first.next;
338 removed.next = null;
339 340 returnremoved;
341 }
342 else343 {
344 Element* element = this.first.next;
345 346 for (Element* prev = this.first; element;)
347 {
348 if (element.key == key)
349 {
350 Element* removed = element;
351 352 prev.next = element.next;
353 removed.next = null;
354 355 returnremoved;
356 }
357 else358 {
359 prev = element;
360 element = element.next;
361 }
362 }
363 }
364 }
365 366 returnnull;
367 }
368 }
369 370 version (none):
371 372 /**
373 Order the provided members to minimize size while preserving alignment.
374 Returns a declaration to be mixed in.
375 376 Example:
377 ---
378 struct Banner {
379 mixin(alignForSize!(byte[6], double)(["name", "height"]));
380 }
381 ---
382 383 Alignment is not always optimal for 80-bit reals, nor for structs declared
384 as align(1).
385 */386 char[] alignForSize(E...)(string[] names...)
387 {
388 // Sort all of the members by .alignof.389 // BUG: Alignment is not always optimal for align(1) structs390 // or 80-bit reals or 64-bit primitives on x86.391 // TRICK: Use the fact that .alignof is always a power of 2,392 // and maximum 16 on extant systems. Thus, we can perform393 // a very limited radix sort.394 // Contains the members with .alignof = 64,32,16,8,4,2,1395 396 assert(E.length == names.length,
397 "alignForSize: There should be as many member names as the types");
398 399 char[][7] declaration = ["", "", "", "", "", "", ""];
400 401 foreach (i, T; E) {
402 autoa = T.alignof;
403 autok = a>=64? 0 : a>=32? 1 : a>=16? 2 : a>=8? 3 : a>=4? 4 : a>=2? 5 : 6;
404 declaration[k] ~= T.stringof ~ " " ~ names[i] ~ ";\n";
405 }
406 407 autos = "";
408 foreach (decl; declaration)
409 s ~= decl;
410 returns;
411 }
412 413 unittest {
414 staticimmutablex = alignForSize!(int[], char[3], short, double[5])("x", "y","z", "w");
415 structFoo{ intx; }
416 staticimmutabley = alignForSize!(ubyte, Foo, cdouble)("x", "y","z");
417 418 staticif(size_t.sizeof == uint.sizeof)
419 {
420 staticimmutablepassNormalX = x == "double[5u] w;\nint[] x;\nshort z;\nchar[3u] y;\n";
421 staticimmutablepassNormalY = y == "cdouble z;\nFoo y;\nubyte x;\n";
422 423 staticimmutablepassAbnormalX = x == "int[] x;\ndouble[5u] w;\nshort z;\nchar[3u] y;\n";
424 staticimmutablepassAbnormalY = y == "Foo y;\ncdouble z;\nubyte x;\n";
425 // ^ blame http://d.puremagic.com/issues/show_bug.cgi?id=231426 427 staticassert(passNormalX || double.alignof <= (int[]).alignof && passAbnormalX);
428 staticassert(passNormalY || double.alignof <= int.alignof && passAbnormalY);
429 }
430 else431 {
432 staticassert(x == "int[] x;\ndouble[5LU] w;\nshort z;\nchar[3LU] y;\n");
433 staticassert(y == "cdouble z;\nFoo y;\nubyte x;\n");
434 }
435 }