sux 0.12.3

A pure Rust implementation of succinct and compressed data structures
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

/**
 * This code is released under the
 * Apache License Version 2.0 http://www.apache.org/licenses/.
 *
 * (c) Daniel Lemire, http://lemire.me/en/
 */

#ifndef MEMUTIL_H_
#define MEMUTIL_H_

#include "common.h"

namespace FastPFor {

template<class T, size_t alignment>
T * moveToBoundary(T * inbyte) {
    return reinterpret_cast<T *> ((reinterpret_cast<uintptr_t> (inbyte)
            + (alignment - 1)) & ~(alignment - 1));
}

// use this when calling STL object if you want
// their memory to be aligned on cache lines
template<class T, size_t alignment>
class AlignedSTLAllocator {
public:
    // type definitions
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    // rebind allocator to type U
    template<class U>
    struct rebind {
        typedef AlignedSTLAllocator<U, alignment> other;
    };

    pointer address(reference value) const {
        return &value;
    }
    const_pointer address(const_reference value) const {
        return &value;
    }

    /* constructors and destructor
     * - nothing to do because the allocator has no state
     */
    AlignedSTLAllocator() {
    }
    AlignedSTLAllocator(const AlignedSTLAllocator& ) {
    }
    ~AlignedSTLAllocator() {
    }

    // return maximum number of elements that can be allocated
    size_type max_size() const throw () {
        return std::numeric_limits<std::size_t>::max() / sizeof(T);
    }

    /*
     *  allocate but don't initialize num elements of type T
     *
     *  This implementation is potentially unsafe on some compilers.
     */
    pointer allocate(size_type num, const void* = 0) {
        /**
         * The nasty trick here is to make the position of the actual pointer
         * within the newly allocated memory. The alternative is to use
         * some kind of data structure like a hash table, which might be slow.
         */
        size_t * buffer = reinterpret_cast<size_t *> (::operator new(
                sizeof(uintptr_t) + (num + alignment) * sizeof(T)));
        size_t * answer = moveToBoundary<size_t, alignment> (buffer + 1);
        *(answer - 1) = reinterpret_cast<uintptr_t> (answer) - reinterpret_cast<uintptr_t> (buffer);
        return reinterpret_cast<pointer> (answer);
    }

    void construct(pointer p, const T& value) {
    // initialize memory with placement new
          new  (p) T(value);
    }

    // destroy elements of initialized storage p
    void destroy(pointer p) {
        p->~T();
    }

    // deallocate storage p of deleted elements
    void deallocate(pointer p, size_type /*num*/) {
        const size_t * assize_t = reinterpret_cast<size_t *> (p);
        const size_t offset = assize_t[-1];
        ::operator delete(reinterpret_cast<pointer>(reinterpret_cast<uintptr_t> (p) - offset));
    }
};

// for our purposes, we don't want to distinguish between allocators.
template <class T1, size_t t, class T2>
 bool operator== (const AlignedSTLAllocator<T1,t>&,
                  const T2&) throw() {
     return true;
 }

template <class T1, size_t t, class T2>
 bool operator!= (const AlignedSTLAllocator<T1,t>&,
                  const T2&) throw() {
     return false;
 }
// typical cache line
typedef  AlignedSTLAllocator<uint32_t, 64> cacheallocator;

} // namespace FastPFor

#endif /* MEMUTIL_H_ */