libd.algorithm.search source code

1 module libd.algorithm.search;
2 import  libd.algorithm, libd.util.cpuid;
3 
4 const INDEX_NOT_FOUND = size_t.max; // Since our only target is x86_64, we can account for the fact it's literally impossible for a memory address to be this value.
5 
6 @nogc nothrow:
7 
8 // Using NASM because D's inline ASM, and even core.simd, don't support things like vpbroadcastb, so....
9 @trusted
10 private extern(C) ulong indexOfByteAvx2(const(ubyte)* haystack, ulong haystackSize, ubyte* needle, ulong* remainingChars);
11 @("indexOfByteAvx2")
12 unittest
13 {
14     if(cpuidHasAvx2)
15     {
16         size_t remainingChars;
17         ubyte needle = ' ';
18         assert(indexOfByteAvx2(null, 0, &needle, &remainingChars) == INDEX_NOT_FOUND);
19         assert(indexOfByteAvx2(cast(const ubyte*)"                                ".ptr, 32, &needle, &remainingChars) == 0);
20         assert(indexOfByteAvx2(cast(const ubyte*)"0123                            ".ptr, 32, &needle, &remainingChars) == 4);
21 
22         remainingChars = 33;
23         needle = '_';
24         assert(indexOfByteAvx2(cast(const ubyte*)"0123                            _".ptr, 33, &needle, &remainingChars) == INDEX_NOT_FOUND);
25         assert(remainingChars == 1);
26 
27         assert(indexOfByteAvx2(cast(const ubyte*)"0123                            _123                            ".ptr, 64, &needle, &remainingChars) == 32);
28         needle = '6';
29         assert(indexOfByteAvx2(cast(const ubyte*)"0123                            _126                            ".ptr, 64, &needle, &remainingChars) == 35);
30     }
31 }
32 
33 @trusted
34 size_t indexOfAscii(scope const bcstring haystack, char asciiChar)
35 {
36     assert((asciiChar & 0b1000_0000) == 0, "This function does not support searching for UTF chars.");
37 
38     size_t remainingChars = haystack.length;
39 
40     if(cpuidHasAvx2 && remainingChars >= 32)
41     {
42         const result = indexOfByteAvx2(cast(const ubyte*)haystack.ptr, haystack.length, cast(ubyte*)&asciiChar, &remainingChars);
43         if(result != INDEX_NOT_FOUND)
44             return result;
45     }
46 
47     for(size_t i = haystack.length-remainingChars; i < haystack.length; i++)
48     {
49         if(haystack[i] == asciiChar)
50             return i;
51     }
52 
53     return INDEX_NOT_FOUND;
54 }
55 ///
56 @("indexOfAscii")
57 unittest
58 {
59     assert("0123456789".indexOfAscii('0') == 0);
60     assert("0123456789".indexOfAscii('9') == 9);
61     assert("0123456789".indexOfAscii('4') == 4);
62 
63     assert("The quick brown fox jumped over the lazy dog.".indexOfAscii('d') == 25);
64     assert("The quick brown fox jumped over the lazy dog.".indexOfAscii('z') == 38);
65 }
66 
67 size_t indexOf(alias Comparator, HaystackT, NeedleT)(const auto ref HaystackT haystack, const auto ref NeedleT needle)
68 if(canForeachOrProvidesRange!HaystackT)
69 {
70     import libd.meta : ElementType;
71 
72     static if(!canForeach!HaystackT)
73         auto range = haystack.range;
74     else
75         alias range = haystack;
76 
77     static immutable IMPL = q{
78         if(value == needle)
79             return index;
80         index++;
81     };
82 
83     size_t index;
84     static if(!is(ElementType!range == struct) || __traits(isPOD, ElementType!range))
85     {
86         foreach(value; range)
87             mixin(IMPL);
88     }
89     else
90     {
91         foreach(ref value; range)
92             mixin(IMPL);
93     }
94 
95     return INDEX_NOT_FOUND;
96 }
97 ///
98 @("indexOf")
99 unittest
100 {
101     import libd.datastructures..string, libd.datastructures.array;
102 
103     Array!char arr;
104     arr.put("0123456789");
105 
106     assert("0123456789".indexOf('0') == 0);
107     assert(String("0123456789").indexOf('9') == 9);
108     assert(arr.indexOf('4') == 4);
109 
110     assert("The quick brown fox jumped over the lazy dog.".indexOf('d') == 25);
111     assert("The quick brown fox jumped over the lazy dog.".indexOf('z') == 38);
112 }
113 
114 size_t indexOf(HaystackT, NeedleT, alias Comparator = (a,b) => a == b)(const auto ref HaystackT haystack, const auto ref NeedleT needle)
115 {
116     return indexOf!Comparator(haystack, needle);
117 }