aboutsummaryrefslogtreecommitdiffstats
path: root/util/memory/segmented_string_pool.h
blob: a40aa408f5182fe5153ecd41d65c5cb178470399 (plain) (blame)
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#pragma once

#include <util/system/align.h>
#include <util/system/yassert.h>
#include <util/system/defaults.h>
#include <util/generic/noncopyable.h>
#include <util/generic/vector.h>
#include <util/generic/strbuf.h>

#include <memory>
#include <cstdio>
#include <cstdlib>

/*
 * Non-reallocated storage for the objects of POD type
 */
template <class T, class Alloc = std::allocator<T>>
class segmented_pool: TNonCopyable {
protected:
    Alloc seg_allocator;
    struct seg_inf {
        T* data;        // allocated chunk
        size_t _size;   // size of allocated chunk in sizeof(T)-units
        size_t freepos; // offset to free chunk's memory in bytes
        seg_inf()
            : data(nullptr)
            , _size(0)
            , freepos(0)
        {
        }
        seg_inf(T* d, size_t sz)
            : data(d)
            , _size(sz)
            , freepos(0)
        {
        }
    };
    using seg_container = TVector<seg_inf>;
    using seg_iterator = typename seg_container::iterator;
    using seg_const_iterator = typename seg_container::const_iterator;
    const size_t segment_size; // default size of a memory chunk in sizeof(T)-units
    size_t last_free;          // size of free memory in chunk in sizeof(T)-units
    size_t last_ins_size;      // size of memory used in chunk by the last append() in bytes
    seg_container segs;        // array of memory chunks
    seg_iterator curseg;       // a segment for the current insertion
    const char* Name;          // for debug memory usage
protected:
    void check_capacity(size_t len) {
        if (Y_UNLIKELY(!last_free || len > last_free)) {
            if (curseg != segs.end() && curseg->freepos > 0)
                ++curseg;
            last_free = (len > segment_size ? len : segment_size);
            if (curseg == segs.end() || curseg->_size < last_free) {
                segs.push_back(seg_inf(seg_allocator.allocate(last_free), last_free));
                if (Y_UNLIKELY(Name))
                    printf("Pool \"%s\" was increased by %" PRISZT " bytes to %" PRISZT " Mb.\n", Name, last_free * sizeof(T), capacity() / 0x100000);
                curseg = segs.end() - 1;
            }
            Y_ASSERT(curseg->freepos == 0);
            Y_ASSERT(curseg->_size >= last_free);
        }
    }

public:
    explicit segmented_pool(size_t segsz, const char* name = nullptr)
        : segment_size(segsz)
        , last_free(0)
        , last_ins_size(0)
        , Name(name)
    {
        curseg = segs.begin();
    }
    ~segmented_pool() {
        clear();
    }
    /* src - array of objects, len - count of elements in array */
    T* append(const T* src, size_t len) {
        check_capacity(len);
        ui8* rv = (ui8*)curseg->data + curseg->freepos;
        last_ins_size = sizeof(T) * len;
        if (src)
            memcpy(rv, src, last_ins_size);
        curseg->freepos += last_ins_size, last_free -= len;
        return (T*)rv;
    }
    T* append() {
        T* obj = get_raw();
        new (obj) T();
        return obj;
    }
    T* get_raw() { // append(0, 1)
        check_capacity(1);
        ui8* rv = (ui8*)curseg->data + curseg->freepos;
        last_ins_size = sizeof(T);
        curseg->freepos += last_ins_size, last_free -= 1;
        return (T*)rv;
    }
    size_t get_segment_size() const {
        return segment_size;
    }
    bool contains(const T* ptr) const {
        for (seg_const_iterator i = segs.begin(), ie = segs.end(); i != ie; ++i)
            if ((char*)ptr >= (char*)i->data && (char*)ptr < (char*)i->data + i->freepos)
                return true;
        return false;
    }
    size_t size() const {
        size_t r = 0;
        for (seg_const_iterator i = segs.begin(); i != segs.end(); ++i)
            r += i->freepos;
        return r;
    }
    size_t capacity() const {
        return segs.size() * segment_size * sizeof(T);
    }
    void restart() {
        if (curseg != segs.end())
            ++curseg;
        for (seg_iterator i = segs.begin(); i != curseg; ++i)
            i->freepos = 0;
        curseg = segs.begin();
        last_free = 0;
        last_ins_size = 0;
    }
    void clear() {
        for (seg_iterator i = segs.begin(); i != segs.end(); ++i)
            seg_allocator.deallocate(i->data, i->_size);
        segs.clear();
        curseg = segs.begin();
        last_free = 0;
        last_ins_size = 0;
    }
    void undo_last_append() {
        Y_ASSERT(curseg != segs.end()); // do not use before append()
        if (last_ins_size) {
            Y_ASSERT(last_ins_size <= curseg->freepos);
            curseg->freepos -= last_ins_size;
            last_free += last_ins_size / sizeof(T);
            last_ins_size = 0;
        }
    }
    void alloc_first_seg() {
        Y_ASSERT(capacity() == 0);
        check_capacity(segment_size);
        Y_ASSERT(capacity() == segment_size * sizeof(T));
    }
};

class segmented_string_pool: public segmented_pool<char> {
private:
    using _Base = segmented_pool<char>;

public:
    segmented_string_pool()
        : segmented_string_pool(1024 * 1024)
    {
    }

    explicit segmented_string_pool(size_t segsz)
        : _Base(segsz)
    {
    }
    char* append(const char* src) {
        Y_ASSERT(src);
        return _Base::append(src, strlen(src) + 1);
    }
    char* append(const char* src, size_t len) {
        char* rv = _Base::append(nullptr, len + 1);
        if (src)
            memcpy(rv, src, len);
        rv[len] = 0;
        return rv;
    }
    char* Append(const TStringBuf s) {
        return append(s.data(), s.size());
    }
    void align_4() {
        size_t t = (curseg->freepos + 3) & ~3;
        last_free -= t - curseg->freepos;
        curseg->freepos = t;
    }
    char* Allocate(size_t len) {
        return append(nullptr, len);
    }
};

template <typename T, typename C>
inline T* pool_push(segmented_pool<C>& pool, const T* v) {
    static_assert(sizeof(C) == 1, "only char type supported");
    size_t len = SizeOf(v);
    C* buf = pool.append(nullptr, AlignUp(len));
    memcpy(buf, v, len);
    return (T*)buf;
}