SimdSet

Set implementation that is well suited for small sets and simple items.

Uses SSE instructions to compare multiple elements simultaneously, but has linear time complexity.

Note: Only works on x86_64. Does NOT add GC ranges. Do not store pointers in this container unless they are also stored somewhere else.

struct SimdSet(T, Allocator = Mallocator)
version(D_InlineAsm_X86_64)
struct SimdSet (
T
Allocator = Mallocator
) if (
T.sizeof == 1 ||
T.sizeof == 2
||
T.sizeof == 4
||
T.sizeof == 8
) {
this(this);
this();
this(Allocator allocator);
~this();
bool contains(T item);
bool insert(T item);
bool remove(T item);
auto opSlice();
size_t length();
}
struct SimdSet(T)

Constructors

this this(): No default construction if an allocator must be provided.
this this(Allocator allocator): Use the given allocator for allocations.

Destructor

~this ~this(): Undocumented in source.

Postblit

this(this) this(this): Undocumented in source.

Members

Functions

contains bool contains(T item)
insert bool insert(T item): Inserts the given item into the set.
length size_t length()
opSlice auto opSlice(): Slice operator
remove bool remove(T item): Removes the given item from the set.

Examples

1 import std.string : format;
2 
3 void testSimdSet(T)()
4 {
5 	SimdSet!T set;
6 	assert(set.insert(1));
7 	assert(set.length == 1);
8 	assert(set.contains(1));
9 	assert(!set.insert(1));
10 	set.insert(0);
11 	set.insert(20);
12 	assert(set.contains(1));
13 	assert(set.contains(0));
14 	assert(!set.contains(10));
15 	assert(!set.contains(50));
16 	assert(set.contains(20));
17 	foreach (T i; 28 .. 127)
18 		set.insert(i);
19 	foreach (T i; 28 .. 127)
20 		assert(set.contains(i), "%d".format(i));
21 	foreach (T i; 28 .. 127)
22 		assert(set.remove(i));
23 	assert(set.length == 3, "%d".format(set.length));
24 	assert(set.contains(0));
25 	assert(set.contains(1));
26 	assert(set.contains(20));
27 	assert(!set.contains(28));
28 }
29 
30 testSimdSet!ubyte();
31 testSimdSet!ushort();
32 testSimdSet!uint();
33 testSimdSet!ulong();
34 testSimdSet!byte();
35 testSimdSet!short();
36 testSimdSet!int();
37 testSimdSet!long();