1 /** 2 * Immutable hash set. 3 * Copyright: © 2014 Economic Modeling Specialists, Intl. 4 * Authors: Brian Schott 5 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 6 */ 7 8 module containers.immutablehashset; 9 10 /** 11 * The immutable hash set is useful for constructing a read-only collection that 12 * supports quickly determining if an element is present. 13 * 14 * Because the set does not support inserting, it only takes up as much memory 15 * as is necessary to contain the elements provided at construction. 16 */ 17 struct ImmutableHashSet(T, alias hashFunction) 18 { 19 /// 20 @disable this(); 21 /// 22 @disable this(this); 23 24 /** 25 * Constructs an immutable hash set from the given values. The values must 26 * not have any duplicates. 27 */ 28 this(const T[] values) immutable 29 in 30 { 31 import std.algorithm : sort, uniq; 32 import std.array : array; 33 assert (values.dup.sort().uniq().array().length == values.length); 34 } 35 body 36 { 37 empty = values.length == 0; 38 length = values.length; 39 if (empty) 40 return; 41 immutable float a = (cast(float) values.length) / .75f; 42 size_t bucketCount = 1; 43 while (bucketCount <= cast(size_t) a) 44 bucketCount <<= 1; 45 Node[][] mutableBuckets = cast(Node[][]) Mallocator.it.allocate((Node[]).sizeof * bucketCount); 46 Node[] mutableNodes = cast(Node[]) Mallocator.it.allocate(Node.sizeof * values.length); 47 48 size_t[] lengths = cast(size_t[]) Mallocator.it.allocate(size_t.sizeof * bucketCount); 49 lengths[] = 0; 50 scope(exit) Mallocator.it.deallocate(lengths); 51 52 size_t[] indexes = cast(size_t[]) Mallocator.it.allocate(size_t.sizeof * values.length); 53 scope(exit) Mallocator.it.deallocate(indexes); 54 55 size_t[] hashes = cast(size_t[]) Mallocator.it.allocate(size_t.sizeof * values.length); 56 scope(exit) Mallocator.it.deallocate(hashes); 57 58 foreach (i, ref value; values) 59 { 60 hashes[i] = hashFunction(value); 61 indexes[i] = hashes[i] & (mutableBuckets.length - 1); 62 lengths[indexes[i]]++; 63 } 64 65 size_t j = 0; 66 foreach (i, l; lengths) 67 { 68 mutableBuckets[i] = mutableNodes[j .. j + l]; 69 j += l; 70 } 71 72 lengths[] = 0; 73 foreach (i; 0 .. values.length) 74 { 75 immutable l = lengths[indexes[i]]; 76 static if (hasMember!(Node, "hash")) 77 mutableBuckets[indexes[i]][l].hash = hashes[i]; 78 mutableBuckets[indexes[i]][l].value = values[i]; 79 lengths[indexes[i]]++; 80 } 81 buckets = cast(immutable) mutableBuckets; 82 nodes = cast(immutable) mutableNodes; 83 static if (shouldAddGCRange!T) 84 { 85 GC.addRange(buckets.ptr, buckets.length * (Node[]).sizeof); 86 foreach (ref b; buckets) 87 GC.addRange(b.ptr, b.length * Node.sizeof); 88 GC.addRange(nodes.ptr, nodes.length * Node.sizeof); 89 } 90 } 91 92 ~this() 93 { 94 static if (shouldAddGCRange!T) 95 { 96 GC.removeRange(buckets.ptr); 97 foreach (ref b; buckets) 98 GC.removeRange(b.ptr); 99 GC.removeRange(nodes.ptr); 100 } 101 Mallocator.it.deallocate(cast(void[]) buckets); 102 Mallocator.it.deallocate(cast(void[]) nodes); 103 } 104 105 /** 106 * Returns: A GC-allocated array containing the contents of this set. 107 */ 108 immutable(T)[] opSlice() immutable @safe 109 { 110 if (empty) 111 return []; 112 T[] values = new T[](nodes.length); 113 foreach (i, ref v; values) 114 { 115 v = nodes[i].value; 116 } 117 return values; 118 } 119 120 /** 121 * Returns: true if this set contains the given value. 122 */ 123 bool contains(T value) immutable 124 { 125 if (empty) 126 return false; 127 immutable size_t hash = hashFunction(value); 128 immutable size_t index = hash & (buckets.length - 1); 129 if (buckets[index].length == 0) 130 return false; 131 foreach (ref node; buckets[index]) 132 { 133 static if (hasMember!(Node, "hash")) 134 if (hash != node.hash) 135 continue; 136 if (node.value != value) 137 continue; 138 return true; 139 } 140 return false; 141 } 142 143 /** 144 * The number of items in the set. 145 */ 146 size_t length; 147 148 /** 149 * True if the set is empty. 150 */ 151 bool empty; 152 153 private: 154 155 import std.allocator : Mallocator; 156 import std.traits : isBasicType, hasMember; 157 import containers.internal.node : shouldAddGCRange; 158 import core.memory : GC; 159 160 static struct Node 161 { 162 T value; 163 static if (!isBasicType!T) 164 size_t hash; 165 } 166 167 Node[][] buckets; 168 Node[] nodes; 169 } 170 171 /// 172 unittest 173 { 174 auto ihs1 = immutable ImmutableHashSet!(int, a => a)([1, 3, 5, 19, 31, 40, 17]); 175 assert (ihs1.contains(1)); 176 assert (ihs1.contains(3)); 177 assert (ihs1.contains(5)); 178 assert (ihs1.contains(19)); 179 assert (ihs1.contains(31)); 180 assert (ihs1.contains(40)); 181 assert (ihs1.contains(17)); 182 assert (!ihs1.contains(100)); 183 assert (ihs1[].length == 7); 184 185 auto ihs2 = immutable ImmutableHashSet!(int, a => a)([]); 186 assert (ihs2.length == 0); 187 assert (ihs2.empty); 188 assert (ihs2[].length == 0); 189 assert (!ihs2.contains(42)); 190 }