lbug 0.16.1

An in-process property graph database management system built for query speed and scalability
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#include "function/string/functions/find_function.h"

#include <cstring>

using namespace lbug::common;

namespace lbug {
namespace function {

template<class UNSIGNED>
int64_t Find::unalignedNeedleSizeFind(const uint8_t* haystack, uint32_t haystackLen,
    const uint8_t* needle, uint32_t needleLen, uint32_t firstMatchCharOffset) {
    if (needleLen > haystackLen) {
        return -1;
    }
    // We perform unsigned integer comparisons to check for equality of the entire needle in a
    // single comparison. This implementation is inspired by the memmem implementation of
    // freebsd.
    UNSIGNED needleEntry = 0;
    UNSIGNED haystackEntry = 0;
    const UNSIGNED start = (sizeof(UNSIGNED) * 8) - 8;
    const UNSIGNED shift = (sizeof(UNSIGNED) - needleLen) * 8;
    for (auto i = 0u; i < needleLen; i++) {
        needleEntry |= UNSIGNED(needle[i]) << UNSIGNED(start - i * 8);
        haystackEntry |= UNSIGNED(haystack[i]) << UNSIGNED(start - i * 8);
    }
    for (auto offset = needleLen; offset < haystackLen; offset++) {
        if (haystackEntry == needleEntry) {
            return firstMatchCharOffset + offset - needleLen;
        }
        // We adjust the haystack entry by
        // (1) removing the left-most character (shift by 8)
        // (2) adding the next character (bitwise or, with potential shift)
        // this shift is only necessary if the needle size is not aligned with the unsigned
        // integer size (e.g. needle size 3, unsigned integer size 4, we need to shift by 1).
        haystackEntry = (haystackEntry << 8) | ((UNSIGNED(haystack[offset])) << shift);
    }
    if (haystackEntry == needleEntry) {
        return firstMatchCharOffset + haystackLen - needleLen;
    }
    return -1;
}

template<class UNSIGNED>
int64_t Find::alignedNeedleSizeFind(const uint8_t* haystack, uint32_t haystackLen,
    const uint8_t* needle, uint32_t firstMatchCharOffset) {
    if (sizeof(UNSIGNED) > haystackLen) {
        return -1;
    }
    auto needleVal = *((UNSIGNED*)needle);
    for (auto offset = 0u; offset <= haystackLen - sizeof(UNSIGNED); offset++) {
        auto haystackVal = *((UNSIGNED*)(haystack + offset));
        if (needleVal == haystackVal) {
            return firstMatchCharOffset + offset;
        }
    }
    return -1;
}

int64_t Find::genericFind(const uint8_t* haystack, uint32_t haystackLen, const uint8_t* needle,
    uint32_t needLen, uint32_t firstMatchCharOffset) {
    if (needLen > haystackLen) {
        return -1;
    }
    // This implementation is inspired by Raphael Javaux's faststrstr
    // (https://github.com/RaphaelJ/fast_strstr) generic contains; note that we can't use strstr
    // because we don't have null-terminated strings anymore we keep track of a shifting window
    // sum of all characters with window size equal to needle_size this shifting sum is used to
    // avoid calling into memcmp; we only need to call into memcmp when the window sum is equal
    // to the needle sum when that happens, the characters are potentially the same and we call
    // into memcmp to check if they are.
    auto sumsDiff = 0u;
    for (auto i = 0u; i < needLen; i++) {
        sumsDiff += haystack[i];
        sumsDiff -= needle[i];
    }
    auto offset = 0u;
    while (true) {
        if (sumsDiff == 0 && haystack[offset] == needle[0]) {
            if (memcmp(haystack + offset, needle, needLen) == 0) {
                return firstMatchCharOffset + offset;
            }
        }
        if (offset >= haystackLen - needLen) {
            return -1;
        }
        sumsDiff -= haystack[offset];
        sumsDiff += haystack[offset + needLen];
        offset++;
    }
}

// Returns the position of the first occurrence of needle in the haystack. If haystack doesn't
// contain needle, it returns -1.
int64_t Find::find(const uint8_t* haystack, uint32_t haystackLen, const uint8_t* needle,
    uint32_t needleLen) {
    auto firstMatchCharPos = (uint8_t*)memchr(haystack, needle[0], haystackLen);
    if (firstMatchCharPos == nullptr) {
        return -1;
    }
    auto firstMatchCharOffset = firstMatchCharPos - haystack;
    auto numCharsToMatch = haystackLen - firstMatchCharOffset;
    switch (needleLen) {
    case 1:
        return firstMatchCharOffset;
    case 2:
        return alignedNeedleSizeFind<uint16_t>(firstMatchCharPos, numCharsToMatch, needle,
            firstMatchCharOffset);
    case 3:
        return unalignedNeedleSizeFind<uint32_t>(firstMatchCharPos, numCharsToMatch, needle, 3,
            firstMatchCharOffset);
    case 4:
        return alignedNeedleSizeFind<uint32_t>(firstMatchCharPos, numCharsToMatch, needle,
            firstMatchCharOffset);
    case 5:
    case 6:
    case 7:
        return unalignedNeedleSizeFind<uint64_t>(firstMatchCharPos, numCharsToMatch, needle,
            needleLen, firstMatchCharOffset);
    case 8:
        return alignedNeedleSizeFind<uint64_t>(firstMatchCharPos, numCharsToMatch, needle,
            firstMatchCharOffset);
    default:
        return genericFind(firstMatchCharPos, numCharsToMatch, needle, needleLen,
            firstMatchCharOffset);
    }
}

} // namespace function
} // namespace lbug