← Back to branch summary

~tapaal-ltl/verifypn/scc-optimise

« back to all changes in this revision

Viewing changes to PetriEngine/Structures/ptrie.h

  • Committer: srba.jiri at gmail
  • Date: 2020-09-11 14:23:39 UTC
  • mfrom: (213.1.151 interval_tar)
  • Revision ID: srba.jiri@gmail.com-20200911142339-bq9328s1gppw24uj
merged in lp:~verifypn-maintainers/verifypn/interval_tar doing 
- Implements TAR w/o z3, but using a simple integer inference engine for Hoare logic.
 - Replaces LP-Solve with GLPK, reduces computation-time and memory overhead
 - Implements new global properties, translated into CTL formulae.

Show diffs side-by-side

added added

removed removed

Lines of Context:
PetriEngine/Structures/ptrie.h
1
 
/* VerifyPN - TAPAAL Petri Net Engine
2
 
 * Copyright (C) 2016  Peter Gjøl Jensen <root@petergjoel.dk>
3
 
 * 
4
 
 * This program is free software: you can redistribute it and/or modify
5
 
 * it under the terms of the GNU General Public License as published by
6
 
 * the Free Software Foundation, either version 3 of the License, or
7
 
 * (at your option) any later version.
8
 
 * 
9
 
 * This program is distributed in the hope that it will be useful,
10
 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
 
 * GNU General Public License for more details.
13
 
 * 
14
 
 * You should have received a copy of the GNU General Public License
15
 
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
16
 
 */
17
 
 
18
 
/* 
19
 
 * File:   ptrie.h
20
 
 * Author: Peter G. Jensen
21
 
 *
22
 
 * Created on 10 June 2015, 18:44
23
 
 */
24
 
 
25
 
#ifndef PTRIE_H
26
 
#define PTRIE_H
27
 
 
28
 
#include <stdint.h>
29
 
#include <assert.h>
30
 
#include <limits>
31
 
#include <stack>
32
 
#include <string.h>
33
 
#include <functional>
34
 
 
35
 
#include "binarywrapper.h"
36
 
#include "linked_bucket.h"
37
 
 
38
 
 
39
 
 
40
 
// direct 2lvl indexing in chunks of ~ 2^32
41
 
// takes up ~ 512k (256k on 32bit) for the index.
42
 
// when to keep data in bucket or send to heap - just make sure bucket does not overflow
43
 
 
44
 
namespace ptrie {
45
 
    typedef uint32_t uint;
46
 
    typedef unsigned char uchar;
47
 
 
48
 
    template<typename D, typename N>
49
 
    struct ptrie_el_t {
50
 
        N node;
51
 
        D data;
52
 
        uchar path;
53
 
    };
54
 
 
55
 
    template<typename N>
56
 
    struct ptrie_el_t<void, N> {
57
 
        N node;
58
 
        uchar path;
59
 
    } __attribute__((packed));
60
 
    typedef std::pair<bool, size_t> returntype_t;
61
 
 
62
 
    struct base_t {
63
 
        uchar _path;
64
 
        uchar _type;
65
 
    } __attribute__((packed));
66
 
 
67
 
 
68
 
#define PTRIETPL uint16_t HEAPBOUND, uint16_t SPLITBOUND, size_t ALLOCSIZE, typename T, typename I
69
 
    
70
 
    template<
71
 
    uint16_t HEAPBOUND = 17,
72
 
    uint16_t SPLITBOUND = 129,
73
 
    size_t ALLOCSIZE = (1024 * 64),
74
 
    typename T = void,
75
 
    typename I = size_t
76
 
    >
77
 
    class set {
78
 
    protected:
79
 
 
80
 
        struct fwdnode_t;
81
 
        struct node_t;
82
 
 
83
 
        static_assert(HEAPBOUND * (sizeof(fwdnode_t)/sizeof(size_t)) < std::numeric_limits<uint16_t>::max(),
84
 
                "HEAPBOUND * (sizeof(fwdnode_t)/sizeof(fwdnode_t)) should be less than 2^16");
85
 
 
86
 
        static_assert(SPLITBOUND < sizeof(fwdnode_t),
87
 
                "SPLITBOUND should be less than sizeof(fwdnode_t)");
88
 
 
89
 
        static_assert(SPLITBOUND > 3,
90
 
                "SPLITBOUND MUST BE LARGER THAN 3");
91
 
 
92
 
        static_assert(HEAPBOUND > sizeof(size_t),
93
 
                "HEAPBOUND MUST BE LARGER THAN sizeof(size_t)");
94
 
    protected:
95
 
 
96
 
        typedef ptrie_el_t<T, I> entry_t;
97
 
 
98
 
        struct bucket_t {
99
 
 
100
 
            bucket_t() {
101
 
            }
102
 
            uchar _data;
103
 
 
104
 
            static inline size_t overhead(size_t count, bool hasent) {
105
 
                if (hasent)
106
 
                    return count * (sizeof (uint16_t) + sizeof (I));
107
 
                else
108
 
                    return count * (sizeof (uint16_t));
109
 
            }
110
 
 
111
 
            inline I* entries(uint16_t count, bool hasent) {
112
 
                if (hasent) return (I*) (data(0, hasent) + (count * (sizeof (uint16_t))));
113
 
                else return NULL;
114
 
            }
115
 
 
116
 
            inline uchar* data(uint16_t count, bool hasent) {
117
 
                return ((uchar*) (&_data)) + overhead(count, hasent);
118
 
            }
119
 
 
120
 
            inline uint16_t& first(uint16_t count = 0, uint16_t index = 0) {
121
 
                return ((uint16_t*) &_data)[index];
122
 
            }
123
 
 
124
 
        } __attribute__((packed));
125
 
 
126
 
        // nodes in the tree
127
 
 
128
 
        struct node_t : public base_t {
129
 
            uint16_t _totsize = 0;
130
 
            uint16_t _count = 0; // bucket-counts
131
 
            bucket_t* _data = NULL; // back-pointers to data-array up to date
132
 
        } __attribute__((packed));
133
 
 
134
 
        struct fwdnode_t : public base_t {
135
 
            base_t* _children[256];
136
 
            fwdnode_t* _parent;
137
 
 
138
 
            base_t*& operator[](size_t i) {
139
 
                return _children[i];
140
 
            }
141
 
        } __attribute__((packed));
142
 
 
143
 
        linked_bucket_t<entry_t, ALLOCSIZE>* _entries = NULL;
144
 
 
145
 
        fwdnode_t* _root;
146
 
    protected:
147
 
        node_t* new_node();
148
 
        fwdnode_t* new_fwd();
149
 
 
150
 
        base_t* fast_forward(const binarywrapper_t& encoding, fwdnode_t** tree_pos, uint& byte);
151
 
        bool bucket_search(const binarywrapper_t& encoding, node_t* node, uint& b_index, uint byte);
152
 
 
153
 
        bool best_match(const binarywrapper_t& encoding, fwdnode_t** tree_pos, base_t** node, uint& byte, uint& b_index);
154
 
 
155
 
        void split_node(node_t* node, fwdnode_t* jumppar, node_t* locked, size_t bsize, size_t byte);
156
 
 
157
 
        void split_fwd(node_t* node, fwdnode_t* jumppar, node_t* locked, size_t bsize, size_t byte);
158
 
 
159
 
        static inline uint16_t bytes(const uint16_t d) {
160
 
            if (d >= HEAPBOUND) return sizeof (uchar*);
161
 
            else return d;
162
 
        }
163
 
 
164
 
        void init();
165
 
 
166
 
        void erase(fwdnode_t* parent, node_t* node, size_t bucketid, int byte);
167
 
        bool merge_down(fwdnode_t* parent, node_t* node, int byte);
168
 
        void inject_byte(node_t* node, uchar topush, size_t totsize, std::function<uint16_t(size_t)> sizes);
169
 
 
170
 
 
171
 
    public:
172
 
        set();
173
 
        ~set();
174
 
 
175
 
        returntype_t insert(binarywrapper_t wrapper);
176
 
        returntype_t insert(const uchar* data, size_t length);
177
 
        returntype_t exists(binarywrapper_t wrapper);
178
 
        returntype_t exists(const uchar* data, size_t length);
179
 
        bool         erase (binarywrapper_t wrapper);
180
 
        bool         erase (const uchar* data, size_t length);
181
 
 
182
 
 
183
 
    };
184
 
 
185
 
    template<PTRIETPL>
186
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::~set() {
187
 
        std::stack<fwdnode_t*> stack;
188
 
        stack.push(_root);
189
 
        while(!stack.empty())
190
 
        {
191
 
            fwdnode_t* next = stack.top();
192
 
            stack.pop();
193
 
            for(size_t i = 0; i < 256; ++i)
194
 
            {
195
 
                base_t* child = next->_children[i];
196
 
                if(child != next)
197
 
                {
198
 
                    if(i > 0 && child == next->_children[i-1]) continue;
199
 
                    if(child->_type == 255)
200
 
                    {
201
 
                        stack.push((fwdnode_t*)child);
202
 
                    }
203
 
                    else
204
 
                    {
205
 
                        node_t* node = (node_t*) child;
206
 
                        // TODO: we should delete data here also!
207
 
                        free(node->_data);
208
 
                        delete node;
209
 
                    }
210
 
                }
211
 
            }
212
 
            delete next;
213
 
        }
214
 
       delete _entries;
215
 
    }
216
 
 
217
 
    template<PTRIETPL>
218
 
    void set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::init()
219
 
    {
220
 
        delete _entries;
221
 
        if(_entries != NULL)
222
 
        {
223
 
            _entries = new linked_bucket_t<entry_t, ALLOCSIZE>(1);
224
 
        }
225
 
 
226
 
        _root = new_fwd();
227
 
        _root->_parent = NULL;
228
 
        _root->_type = 255;
229
 
        _root->_path = 0;
230
 
 
231
 
        size_t i = 0;
232
 
        for (; i < 256; ++i) (*_root)[i] = _root;
233
 
    }
234
 
 
235
 
    template<PTRIETPL>
236
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::set()
237
 
    {
238
 
        init();
239
 
    }
240
 
 
241
 
    template<PTRIETPL>
242
 
    typename set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::node_t*
243
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::new_node() {
244
 
        return new node_t;
245
 
    }
246
 
 
247
 
    template<PTRIETPL>
248
 
    typename set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::fwdnode_t*
249
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::new_fwd() {
250
 
        return new fwdnode_t;
251
 
    }
252
 
 
253
 
    template<PTRIETPL>
254
 
    base_t*
255
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::fast_forward(const binarywrapper_t& encoding, fwdnode_t** tree_pos, uint& byte) {
256
 
        fwdnode_t* t_pos = *tree_pos;
257
 
 
258
 
        uint16_t s = encoding.size(); // TODO remove minus to
259
 
        uchar* sc = (uchar*) & s;
260
 
 
261
 
        do {
262
 
            *tree_pos = t_pos;
263
 
 
264
 
            base_t* next;
265
 
            if (byte >= 2) next = (*t_pos)[encoding[byte - 2]];
266
 
            else next = (*t_pos)[sc[1 - byte]];
267
 
 
268
 
            assert(next != NULL);
269
 
            if(next == t_pos)
270
 
            {
271
 
              return t_pos;
272
 
            } else
273
 
            if (next->_type != 255) {
274
 
                return (node_t*) next;
275
 
            } else {
276
 
                t_pos = static_cast<fwdnode_t*> (next);
277
 
                ++byte;
278
 
            }
279
 
        } while (true);
280
 
        assert(false);
281
 
    }
282
 
 
283
 
    template<PTRIETPL>
284
 
    bool set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::bucket_search(const binarywrapper_t& encoding, node_t* node, uint& b_index, uint byte) {
285
 
        // run through the stored data in the bucket, looking for matches
286
 
        // start by creating an encoding that "points" to the "unmatched"
287
 
        // part of the encoding. Notice, this is a shallow copy, no actual
288
 
        // heap-allocation happens!
289
 
        const bool hasent = _entries != NULL;
290
 
        bool found = false;
291
 
 
292
 
        uint16_t encsize;
293
 
        if (encoding.size() > byte) {
294
 
            encsize = byte > 0 ? encoding.size() - byte : encoding.size();
295
 
        } else {
296
 
            encsize = 0;
297
 
        }
298
 
        const uchar* raw = encoding.const_raw() + byte;
299
 
        uint16_t first;
300
 
        uchar* tf = (uchar*) & first;
301
 
        if (byte <= 1) {
302
 
            first = encoding.size();
303
 
            if (byte == 1) {
304
 
                first <<= 8;
305
 
                tf[0] = encoding[0];
306
 
            }
307
 
        } else {
308
 
            tf[1] = encoding[-2 + byte];
309
 
            tf[0] = encoding[-2 + byte + 1];
310
 
        }
311
 
 
312
 
        bucket_t* bucket = node->_data;
313
 
        if (node->_count > 0) {
314
 
            size_t offset = 0;
315
 
            b_index = 0;
316
 
            uint16_t bs = 0;
317
 
            uchar* bsc = (uchar*) & bs;
318
 
            uint16_t f;
319
 
            uchar* fc = (uchar*) & f;
320
 
            for (; b_index < node->_count; ++b_index) {
321
 
                f = bucket->first(node->_count, b_index);
322
 
                if (f >= first) break;
323
 
                if (byte > 1) bs = encsize;
324
 
                else if (byte == 1) {
325
 
                    bs = encoding.size();
326
 
                    bsc[0] = fc[1];
327
 
                    bs -= 1;
328
 
 
329
 
                    //                    bs = bucket->bytes(b_index);
330
 
                } else // if byte == 0
331
 
                {
332
 
                    bsc[0] = fc[0];
333
 
                    bsc[1] = fc[1];
334
 
                    //                    bs = bucket->bytes(b_index);
335
 
                }
336
 
 
337
 
                //                assert(bytes(bs) == bucket->bytes(b_index));
338
 
                offset += bytes(bs);
339
 
            }
340
 
 
341
 
            if (b_index >= node->_count ||
342
 
                    bucket->first(node->_count, b_index) > first) return false;
343
 
 
344
 
            uchar* data = bucket->data(node->_count, hasent);
345
 
            for (; b_index < node->_count; ++b_index) {
346
 
 
347
 
                size_t b = 0;
348
 
 
349
 
                if (bucket->first(node->_count, b_index) > first) break;
350
 
                // first is 2 bytes, which is size of counter, the first part of the tree
351
 
                // if we reach here, things have same size
352
 
 
353
 
                if (encsize < HEAPBOUND) {
354
 
                    for (; b < encsize; ++b) {
355
 
                        if (data[offset + b] != raw[b]) break;
356
 
                    }
357
 
                    if (b == encsize) {
358
 
                        found = true;
359
 
                        break;
360
 
                    } else {
361
 
                        assert(raw[b] != data[offset + b]);
362
 
                        if (raw[b] < data[offset + b]) {
363
 
                            found = false;
364
 
                            break;
365
 
                        }
366
 
                        // else continue search
367
 
                    }
368
 
                } else {
369
 
                    uchar* ptr = *((uchar**) (&data[offset]));
370
 
                    int cmp = memcmp(ptr, raw, encsize);
371
 
                    if (cmp > 0) {
372
 
                        found = false;
373
 
                        break;
374
 
                    }
375
 
 
376
 
                    if (cmp == 0) {
377
 
                        found = true;
378
 
                        break;
379
 
                    }
380
 
                }
381
 
                offset += bytes(encsize);
382
 
            }
383
 
        } else {
384
 
            b_index = 0;
385
 
        }
386
 
        return found;
387
 
    }
388
 
 
389
 
    template<PTRIETPL>
390
 
    bool set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::best_match(const binarywrapper_t& encoding, fwdnode_t** tree_pos, base_t** node,
391
 
            uint& byte, uint& b_index) {
392
 
        // run through tree as long as there are branches covering some of 
393
 
        // the encoding
394
 
        *node = fast_forward(encoding, tree_pos, byte);
395
 
        if((size_t)*node != (size_t)*tree_pos) {
396
 
            return bucket_search(encoding, (node_t*)*node, b_index, byte);
397
 
        } else
398
 
        {
399
 
            return false;
400
 
        }
401
 
    }
402
 
 
403
 
 
404
 
    template<PTRIETPL>
405
 
    void set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::split_fwd(node_t* node, fwdnode_t* jumppar, node_t* locked, size_t bsize, size_t byte) {
406
 
 
407
 
        const uint16_t bucketsize = node->_count;
408
 
        if(bucketsize < (sizeof(fwdnode_t) / sizeof(size_t))) return;
409
 
        const bool hasent = _entries != NULL;
410
 
        node_t lown;
411
 
        fwdnode_t* fwd_n = new_fwd();
412
 
 
413
 
        //        std::cerr << "SplitFWD " << (locked ? locked : node) << " OP : " << jumppar << " NP : " << fwd_n  << " LOW : " << low_n << std::endl;
414
 
 
415
 
        fwd_n->_parent = jumppar;
416
 
        fwd_n->_type = 255;
417
 
        fwd_n->_path = node->_path;
418
 
 
419
 
        lown._path = 0;
420
 
        node->_path = binarywrapper_t::_masks[0];
421
 
        lown._type = 1;
422
 
        node->_type = 1;
423
 
 
424
 
 
425
 
        for (size_t i = 0; i < 256; ++i) (*fwd_n)[i] = (locked == NULL ? node : locked);
426
 
 
427
 
        (*jumppar)[fwd_n->_path] = fwd_n;
428
 
 
429
 
        lown._data = NULL;
430
 
 
431
 
        int lcnt = 0;
432
 
        int hcnt = 0;
433
 
        int lsize = 0;
434
 
        int hsize = 0;
435
 
        int bcnt = 0;
436
 
        bucket_t* bucket = node->_data;
437
 
        // get sizes
438
 
        uint16_t lengths[sizeof(fwdnode_t)/sizeof(size_t)];
439
 
        for (int i = 0; i < bucketsize; ++i) {
440
 
 
441
 
            lengths[i] = bsize;
442
 
            if (byte < 2) {
443
 
                uchar* f = (uchar*)&(bucket->first(bucketsize, i));
444
 
                uchar* d = (uchar*)&(lengths[i]);
445
 
                if (byte != 0) {
446
 
                    lengths[i] += 1;
447
 
                    d[0] = f[1];
448
 
                    lengths[i] -= 1;
449
 
                } else {
450
 
                    d[0] = f[0];
451
 
                    d[1] = f[1];
452
 
                }
453
 
            }
454
 
            //            assert(lengths[i] == bucket->length(i));
455
 
 
456
 
            if ((bucket->first(bucketsize, i) & binarywrapper_t::_masks[0]) == 0) {
457
 
                ++lcnt;
458
 
                if (lengths[i] < (HEAPBOUND + 1)) {
459
 
                    if (lengths[i] > 1) {
460
 
                        lsize += lengths[i] - 1;
461
 
                    }
462
 
                    // otherwise new size = 0
463
 
                } else {
464
 
                    lsize += bytes(lengths[i]);
465
 
                }
466
 
            } else {
467
 
                ++hcnt;
468
 
                if (lengths[i] < (HEAPBOUND + 1)) {
469
 
                    hsize += lengths[i] - 1;
470
 
                } else {
471
 
                    hsize += bytes(lengths[i]);
472
 
                }
473
 
            }
474
 
            bcnt += bytes(lengths[i]);
475
 
        }
476
 
 
477
 
        //if(bucketsize > 0)free(node->_data);
478
 
 
479
 
        // allocate new buckets
480
 
        node->_totsize = hsize > 0 ? hsize : 0;
481
 
        node->_count = hcnt;
482
 
        if (hcnt == 0) node->_data = NULL;
483
 
        else node->_data = (bucket_t*) malloc(node->_totsize + 
484
 
                bucket_t::overhead(node->_count, hasent));
485
 
 
486
 
        lown._totsize = lsize > 0 ? lsize : 0;
487
 
        lown._count = lcnt;
488
 
        if (lcnt == 0) lown._data = NULL;
489
 
        else lown._data = (bucket_t*) malloc(lown._totsize +
490
 
                bucket_t::overhead(lown._count, hasent));
491
 
 
492
 
        // copy values
493
 
        int lbcnt = 0;
494
 
        int hbcnt = 0;
495
 
        bcnt = 0;
496
 
#define LLENGTH(x) lengths[x] - 1
497
 
        for (int i = 0; i < bucketsize; ++i) {
498
 
            if (i < lown._count) {
499
 
                lown._data->first(lown._count, i) = (bucket->first(bucketsize, i) << 8);
500
 
                if (lengths[i] > 0) {
501
 
                    //                    lown._data->length(i) = LLENGTH(i);
502
 
                    uchar* dest = &(lown._data->data(lown._count, hasent)[lbcnt]);
503
 
                    if (LLENGTH(i) >= HEAPBOUND) {
504
 
                        uchar* data = (uchar*) malloc(LLENGTH(i));
505
 
                        memcpy(dest, &data, sizeof (uchar*));
506
 
                        dest = data;
507
 
                        //                        std::cout << "DATA FOR " << i << " in " << low_n << " IN " << (void*)dest << std::endl;
508
 
                    }
509
 
 
510
 
                    uchar* src;
511
 
                    if (lengths[i] >= HEAPBOUND) {
512
 
                        src = *((uchar**)&(bucket->data(bucketsize, hasent)[bcnt]));
513
 
                    } else {
514
 
                        src = &(bucket->data(bucketsize, hasent)[bcnt]);
515
 
                    }
516
 
 
517
 
                    uchar* f = (uchar*)&(lown._data->first(lown._count, i));
518
 
                    f[0] = src[0];
519
 
 
520
 
                    memcpy(dest,
521
 
                            &(src[1]),
522
 
                            LLENGTH(i));
523
 
 
524
 
                    if (lengths[i] >= HEAPBOUND) {
525
 
#ifndef NDEBUG
526
 
                        if (LLENGTH(i) >= HEAPBOUND) {
527
 
                            uchar* tmp = *((uchar**)&(lown._data->data(lown._count, hasent)[lbcnt]));
528
 
                            assert(tmp == dest);
529
 
                            assert(memcmp(tmp, &(src[1]), LLENGTH(i)) == 0);
530
 
                        }
531
 
#endif
532
 
                        free(src);
533
 
                    }
534
 
 
535
 
                    lbcnt += bytes(LLENGTH(i));
536
 
                }
537
 
 
538
 
                //                std::cout << bucket->first(bucketsize, i) << std::endl;
539
 
                //                std::cout << i << " NFIRST " << lown._data->first(lown._count, i) << std::endl;
540
 
 
541
 
                //                assert(lown._data->length(i) == 0 && lengths[i] <= 1 ||
542
 
                //                        lengths[i] - 1 == lown._data->length(i));
543
 
            } else {
544
 
                int j = i - lown._count;
545
 
                node->_data->first(node->_count, j) = (bucket->first(bucketsize, i) << 8);
546
 
                //                node->_data->length(j) = lengths[i] - 1;
547
 
                if (lengths[i] > 0) {
548
 
                    uchar* dest = &(node->_data->data(node->_count, hasent)[hbcnt]);
549
 
                    if (LLENGTH(i) >= HEAPBOUND) {
550
 
                        uchar* data = (uchar*) malloc(LLENGTH(i));
551
 
                        memcpy(dest, &data, sizeof (uchar*));
552
 
                        dest = data;
553
 
                        //                    std::cout << "DATA FOR " << j << " in " << node << " IN " << (void*)dest << std::endl;
554
 
                    }
555
 
 
556
 
                    uchar* src;
557
 
                    if (lengths[i] < HEAPBOUND) {
558
 
                        src = &(bucket->data(bucketsize, hasent)[bcnt]);
559
 
                    } else {
560
 
                        src = *((uchar**)&(bucket->data(bucketsize, hasent)[bcnt]));
561
 
                    }
562
 
 
563
 
                    uchar* f = (uchar*) & node->_data->first(node->_count, j);
564
 
 
565
 
                    f[0] = src[0];
566
 
 
567
 
                    memcpy(dest,
568
 
                            &(src[1]),
569
 
                            LLENGTH(i));
570
 
 
571
 
                    if (lengths[i] >= HEAPBOUND) {
572
 
#ifndef NDEBUG
573
 
                        if (LLENGTH(i) >= HEAPBOUND) {
574
 
                            uchar* tmp = *((uchar**)&(node->_data->data(node->_count, hasent)[hbcnt]));
575
 
                            assert(tmp == dest);
576
 
                            assert(memcmp(tmp, &(src[1]), LLENGTH(i)) == 0);
577
 
                        }
578
 
#endif
579
 
                        free(src);
580
 
                    }
581
 
                }
582
 
 
583
 
                hbcnt += bytes(LLENGTH(i));
584
 
                assert(LLENGTH(i) == lengths[i] - 1);
585
 
                //                std::cout << bucket->first(bucketsize, i) << std::endl;
586
 
                //                std::cout << i << " NFIRST " << node->_data->first(node->_count, j) << std::endl;
587
 
 
588
 
            }
589
 
 
590
 
            bcnt += bytes(lengths[i]);
591
 
 
592
 
        }
593
 
 
594
 
        if (hasent) {
595
 
            I* ents = bucket->entries(bucketsize, true);
596
 
            for (size_t i = 0; i < bucketsize; ++i) {
597
 
                entry_t& ent = _entries->operator[](ents[i]);
598
 
                ent.node = (size_t)fwd_n;
599
 
                ent.path = (bucket->first(bucketsize, i));
600
 
            }
601
 
        }
602
 
 
603
 
        if (lcnt == 0) {
604
 
            if (hasent)
605
 
                memcpy(node->_data->entries(bucketsize, true), bucket->entries(bucketsize, true), bucketsize * sizeof (I));
606
 
            free(bucket);
607
 
            //            std::cout << "SPLIT ALL HIGH" << std::endl;
608
 
            lown._data = NULL;
609
 
            for (size_t i = 0; i < 128; ++i) (*fwd_n)[i] = fwd_n;
610
 
            split_node(node, fwd_n, locked, bsize > 0 ? bsize - 1 : 0, byte + 1);
611
 
        }
612
 
        else if (hcnt == 0) {
613
 
            if (hasent)
614
 
                memcpy(lown._data->entries(bucketsize, true), bucket->entries(bucketsize, true), bucketsize * sizeof (I));
615
 
            for (size_t i = 128; i < 256; ++i) (*fwd_n)[i] = fwd_n;
616
 
            free(bucket);
617
 
            //            std::cout << "SPLIT ALL LOW" << std::endl;
618
 
            node->_data = lown._data;
619
 
            node->_path = lown._path;
620
 
            node->_count = lown._count;
621
 
            node->_totsize = lown._totsize;
622
 
            node->_type = lown._type;
623
 
            split_node(node, fwd_n, locked, bsize > 0 ? bsize - 1 : 0, byte + 1);
624
 
        } else {
625
 
            node_t* low_n = new_node();
626
 
            low_n->_data = lown._data;
627
 
            low_n->_totsize = lown._totsize;
628
 
            low_n->_count = lown._count;
629
 
            low_n->_path = lown._path;
630
 
            low_n->_type = lown._type;
631
 
            for (size_t i = 0; i < 128; ++i) (*fwd_n)[i] = low_n;
632
 
            if (hasent) {
633
 
                // We are stopping splitting here, so correct entries if needed
634
 
                I* ents = bucket->entries(bucketsize, true);
635
 
 
636
 
                for (size_t i = 0; i < bucketsize; ++i) {
637
 
                    if (i < lown._count) lown._data->entries(lown._count, true)[i] = ents[i];
638
 
                    else node->_data->entries(node->_count, true)[i - lown._count] = ents[i];
639
 
                }
640
 
            }
641
 
            free(bucket);
642
 
            if(lown._count >= SPLITBOUND && lown._count >= node->_count)
643
 
            {
644
 
                split_node(low_n, fwd_n, NULL, bsize > 0 ? bsize - 1 : 0, byte + 1);
645
 
            }
646
 
            if(node->_count >= SPLITBOUND)
647
 
            {
648
 
                 split_node(node, fwd_n, locked, bsize > 0 ? bsize - 1 : 0, byte + 1);
649
 
            }
650
 
            //            std::cout << "SPLIT Moving LOW " << lown._count << " TO " << low_n << std::endl;
651
 
            //            std::cout << "SPLIT Moving HIGH " << node->_count << " TO " << node << std::endl;
652
 
 
653
 
        }
654
 
    }
655
 
 
656
 
    template<PTRIETPL>
657
 
    void set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::split_node(node_t* node, fwdnode_t* jumppar, node_t* locked, size_t bsize, size_t byte) {
658
 
 
659
 
        assert(bsize != std::numeric_limits<size_t>::max());
660
 
        if (node->_type == 8) // new fwd node!
661
 
        {
662
 
            //stuff
663
 
            split_fwd(node, jumppar, locked, bsize, byte);
664
 
            return;
665
 
        }
666
 
 
667
 
        const uint16_t bucketsize = node->_count;
668
 
 
669
 
        node_t hnode;
670
 
        //        std::cerr << "Split " << (locked ? locked : node) << " high : " << h_node << std::endl;
671
 
 
672
 
        hnode._type = node->_type + 1;
673
 
        assert(hnode._type <= 8);
674
 
        assert(node->_type <= 8);
675
 
 
676
 
        //assert(n_node->_lck == 0);
677
 
        assert((node->_path & binarywrapper_t::_masks[node->_type]) == 0);
678
 
        hnode._path = node->_path | binarywrapper_t::_masks[node->_type];
679
 
 
680
 
        // because we are only really shifting around bits when enc_pos % 8 = 0
681
 
        // then we need to find out which bit of the first 8 we are
682
 
        // splitting on in the "remainder"
683
 
        const uint r_pos = node->_type;
684
 
        assert(r_pos < 8);
685
 
 
686
 
        // Copy over the data to the new buckets
687
 
 
688
 
        int lcnt = 0;
689
 
        int hcnt = bucketsize;
690
 
        int lsize = 0;
691
 
 
692
 
#ifndef NDEBUG
693
 
        bool high = false;
694
 
#endif
695
 
 
696
 
        for (size_t i = 0; i < bucketsize; i++) {
697
 
 
698
 
            uchar* f = (uchar*) & node->_data->first(bucketsize, i);
699
 
            if ((f[1] & binarywrapper_t::_masks[r_pos]) > 0) {
700
 
#ifndef NDEBUG
701
 
                high = true;
702
 
#else
703
 
                break;
704
 
#endif
705
 
            } else {
706
 
                assert(!high);
707
 
                ++lcnt;
708
 
                --hcnt;
709
 
                uint16_t fc;
710
 
                if (byte < 2) {
711
 
                    uchar* fcc = (uchar*) & fc;
712
 
                    if (byte == 0) {
713
 
                        fcc[0] = f[0];
714
 
                        fcc[1] = f[1];
715
 
                    } else {
716
 
                        fc = (bsize + byte);
717
 
                        fcc[0] = f[1];
718
 
                        fc -= byte;
719
 
                    }
720
 
                } else {
721
 
                    fc = bsize;
722
 
                }
723
 
                //                assert(bytes(fc) == node->_data->bytes(i));
724
 
                lsize += bytes(fc);
725
 
            }
726
 
        }
727
 
 
728
 
        bucket_t* old = node->_data;
729
 
        // copy over values
730
 
        hnode._count = hcnt;
731
 
        hnode._totsize = node->_totsize - lsize;
732
 
        node->_count = lcnt;
733
 
        node->_totsize = lsize;
734
 
 
735
 
        if(byte >= 2)
736
 
        {
737
 
            assert(hnode._totsize == bytes(bsize) * hnode._count);
738
 
            assert(node->_totsize == bytes(bsize) * node->_count);
739
 
        }
740
 
 
741
 
        size_t dist = (hnode._path - node->_path);
742
 
        assert(dist > 0);
743
 
 
744
 
        node->_type += 1;
745
 
 
746
 
        const bool hasent = _entries != NULL;
747
 
 
748
 
        if (node->_count == 0) // only high node has data
749
 
        {
750
 
            //            std::cout << "ALL HIGH" << std::endl;
751
 
            for(size_t i = node->_path; i < hnode._path; ++i)
752
 
            {
753
 
                assert(jumppar->_children[i] == node);
754
 
                jumppar->_children[i] = jumppar;
755
 
            }
756
 
 
757
 
            node->_path = hnode._path;
758
 
            node->_count = hnode._count;
759
 
            node->_data = old;
760
 
            node->_totsize = hnode._totsize;
761
 
            node->_type = hnode._type;
762
 
 
763
 
 
764
 
            split_node(node, jumppar, locked, bsize, byte);
765
 
        }
766
 
        else if (hnode._count == 0) // only low node has data
767
 
        {
768
 
            //            std::cout << "ALL LOW" << std::endl;
769
 
            for(size_t i = hnode._path; i < hnode._path + dist; ++i)
770
 
            {
771
 
                assert(jumppar->_children[i] == node);
772
 
                jumppar->_children[i] = jumppar;
773
 
            }
774
 
 
775
 
            node->_data = old;
776
 
            split_node(node, jumppar, locked, bsize, byte);
777
 
        } else {
778
 
            node_t* h_node = new_node();
779
 
            h_node->_count = hnode._count;
780
 
            h_node->_type = hnode._type;
781
 
            h_node->_path = hnode._path;
782
 
            h_node->_totsize = hnode._totsize;
783
 
            h_node->_data = hnode._data;
784
 
 
785
 
            for(size_t i = hnode._path; i < hnode._path + dist; ++i)
786
 
            {
787
 
                assert(jumppar->_children[i] == node);
788
 
                jumppar->_children[i] = h_node;
789
 
            }
790
 
 
791
 
            //            std::cout << "Moving LOW " << node->_count << " TO " << node << std::endl;
792
 
            //            std::cout << "Moving HIGH " << h_node->_count << " TO " << h_node << std::endl;
793
 
            h_node->_data = (bucket_t*) malloc(h_node->_totsize + 
794
 
                    bucket_t::overhead(h_node->_count, hasent));
795
 
            node->_data = (bucket_t*) malloc(node->_totsize + 
796
 
                    bucket_t::overhead(node->_count, hasent));
797
 
 
798
 
            // copy firsts
799
 
            memcpy(&node->_data->first(node->_count), &(old->first(bucketsize)), sizeof (uint16_t) * node->_count);
800
 
            memcpy(&h_node->_data->first(h_node->_count), &(old->first(bucketsize, node->_count)), sizeof (uint16_t) * h_node->_count);
801
 
 
802
 
            // copy data
803
 
            memcpy(node->_data->data(node->_count, hasent), old->data(bucketsize, hasent), node->_totsize);
804
 
            memcpy(h_node->_data->data(h_node->_count, hasent), &(old->data(bucketsize, hasent)[node->_totsize]), h_node->_totsize);
805
 
 
806
 
            if (hasent) {
807
 
                I* ents = old->entries(bucketsize, true);
808
 
 
809
 
                for (size_t i = 0; i < bucketsize; ++i) {
810
 
                    if (i < node->_count) node->_data->entries(node->_count, true)[i] = ents[i];
811
 
                    else h_node->_data->entries(h_node->_count, true)[i - node->_count] = ents[i];
812
 
                }
813
 
            }
814
 
 
815
 
            free(old);
816
 
            if(node->_count >= SPLITBOUND && node->_count >= h_node->_count)
817
 
            {
818
 
                split_node(node, jumppar, locked, bsize, byte);
819
 
            }
820
 
            if(h_node->_count >= SPLITBOUND)
821
 
            {
822
 
                split_node(h_node, jumppar, NULL, bsize, byte);
823
 
            }
824
 
        }
825
 
    }
826
 
 
827
 
    template<PTRIETPL>
828
 
    std::pair<bool, size_t>
829
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::exists(const uchar* data, size_t length) {
830
 
        assert(length <= 65536);
831
 
        binarywrapper_t encoding((uchar*) data, length * 8);
832
 
        //        memcpy(encoding.raw()+2, data, length);
833
 
        //        length += 2;
834
 
        //        memcpy(encoding.raw(), &length, 2);
835
 
 
836
 
        uint b_index = 0;
837
 
 
838
 
        fwdnode_t* fwd = _root;
839
 
        base_t* base = NULL;
840
 
        uint byte = 0;
841
 
 
842
 
        b_index = 0;
843
 
        bool res = best_match(encoding, &fwd, &base, byte, b_index);
844
 
        returntype_t ret = returntype_t(res, std::numeric_limits<size_t>::max());
845
 
        if((size_t)fwd != (size_t)base) {
846
 
            node_t* node = (node_t*)base;
847
 
            if (_entries != NULL && res) {
848
 
                ret.second = node->_data->entries(node->_count, true)[b_index];
849
 
            }
850
 
        }
851
 
        return ret;
852
 
    }
853
 
 
854
 
    template<PTRIETPL>
855
 
    returntype_t
856
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::insert(const uchar* data, size_t length) {
857
 
        assert(length <= 65536);
858
 
        binarywrapper_t e2((uchar*) data, length * 8);
859
 
        const bool hasent = _entries != NULL;
860
 
        //        binarywrapper_t encoding(length*8+16);
861
 
        //        memcpy(encoding.raw()+2, data, length);
862
 
        //        length += 2;
863
 
        //        memcpy(encoding.raw(), &length, 2);
864
 
 
865
 
        uint b_index = 0;
866
 
 
867
 
        fwdnode_t* fwd = _root;
868
 
        node_t* node = NULL;
869
 
        base_t* base = NULL;
870
 
        uint byte = 0;
871
 
 
872
 
        bool res = best_match(e2, &fwd, &base, byte, b_index);
873
 
        if (res) { // We are not inserting duplicates, semantics of PTrie is a set.
874
 
            returntype_t ret(false, 0);
875
 
            if (hasent) {
876
 
                node = (node_t*)base;
877
 
                ret = returntype_t(false, node->_data->entries(node->_count, true)[b_index]);
878
 
            }
879
 
            return ret;
880
 
        }
881
 
 
882
 
        if((size_t)base == (size_t)fwd)
883
 
        {
884
 
            node = new_node();
885
 
            node->_count = 0;
886
 
            node->_data = NULL;
887
 
            node->_type = 0;
888
 
            node->_path = 0;
889
 
            assert(node);
890
 
 
891
 
            size_t s = e2.size();
892
 
            uchar* sc = (uchar*) & s;
893
 
            uchar b = (byte < 2 ? sc[1 - byte] : e2[byte-2]);
894
 
 
895
 
            uchar min = b;
896
 
            uchar max = b;
897
 
            int bit = 8;
898
 
            bool stop = false;
899
 
            do {
900
 
                --bit;
901
 
 
902
 
                min = min & (~binarywrapper_t::_masks[bit]);
903
 
                max |= binarywrapper_t::_masks[bit];
904
 
                for (int i = min; i <= max ; ++i) {
905
 
                    if(fwd->_children[i] != fwd)
906
 
                    {
907
 
                        max = (max & ~binarywrapper_t::_masks[bit]) | (binarywrapper_t::_masks[bit] & b);
908
 
                        min = min | (binarywrapper_t::_masks[bit] & b);
909
 
                        bit += 1;
910
 
                        stop = true;
911
 
                        break;
912
 
                    }
913
 
                }
914
 
            } while(bit > 0 && !stop);
915
 
 
916
 
            for (size_t i = min; i <= max; ++i) (*fwd)[i] = node;
917
 
            node->_path = min;
918
 
            node->_type = bit;
919
 
        } else
920
 
        {
921
 
            node = (node_t*)base;
922
 
        }
923
 
 
924
 
 
925
 
        // shallow copy
926
 
        binarywrapper_t nenc(e2.const_raw(),
927
 
                (e2.size() - byte)*8,
928
 
                byte * 8,
929
 
                e2.size() * 8);
930
 
 
931
 
//                std::cout << "COULD NOT FIND of size " << e2.size() << std::endl;
932
 
//                e2.print(std::cout);
933
 
//                std::cout << "Inserted into " << node << std::endl;
934
 
 
935
 
        // make a new bucket, add new entry, copy over old data
936
 
 
937
 
        uint nbucketcount = node->_count + 1;
938
 
        uint nitemsize = nenc.size();
939
 
        bool copyval = true;
940
 
        if (nitemsize >= HEAPBOUND) {
941
 
            copyval = false;
942
 
            nitemsize = sizeof (uchar*);
943
 
        }
944
 
 
945
 
        uint nbucketsize = node->_totsize + nitemsize;
946
 
 
947
 
        bucket_t* nbucket = (bucket_t*) malloc(nbucketsize + 
948
 
                bucket_t::overhead(nbucketcount, hasent));
949
 
 
950
 
        // copy over old "firsts"
951
 
        memcpy(&nbucket->first(nbucketcount), &(node->_data->first(node->_count)), b_index * sizeof (uint16_t));
952
 
        memcpy(&(nbucket->first(nbucketcount, b_index + 1)), &(node->_data->first(node->_count, b_index)),
953
 
                (node->_count - b_index) * sizeof (uint16_t));
954
 
 
955
 
        uchar* f = (uchar*) & nbucket->first(nbucketcount, b_index);
956
 
        if (byte >= 2) {
957
 
            f[1] = e2[-2 + byte];
958
 
            f[0] = e2[-2 + byte + 1];
959
 
        } else {
960
 
            nbucket->first(nbucketcount, b_index) = e2.size();
961
 
            if (byte == 1) {
962
 
                nbucket->first(nbucketcount, b_index) <<= 8;
963
 
                f[0] = e2[0];
964
 
            }
965
 
        }
966
 
 
967
 
        size_t entry = 0;
968
 
        if (hasent) {
969
 
            // copy over entries
970
 
            memcpy(nbucket->entries(nbucketcount, true), node->_data->entries(node->_count, true), b_index * sizeof (I));
971
 
            memcpy(&(nbucket->entries(nbucketcount, true)[b_index + 1]), &(node->_data->entries(node->_count, true)[b_index]),
972
 
                    (node->_count - b_index) * sizeof (I));
973
 
 
974
 
            entry = nbucket->entries(nbucketcount, true)[b_index] = _entries->next(0);
975
 
            entry_t& ent = _entries->operator[](entry);
976
 
            ent.node = (size_t)fwd;
977
 
            ent.path = (nbucket->first(nbucketcount, b_index) >> 8);
978
 
        }
979
 
 
980
 
 
981
 
 
982
 
        uint tmpsize = 0;
983
 
        if (byte >= 2) tmpsize = b_index * bytes(nenc.size());
984
 
        else {
985
 
            uint16_t o = e2.size();
986
 
            for (size_t i = 0; i < b_index; ++i) {
987
 
 
988
 
                uint16_t f = node->_data->first(nbucketcount - 1, i);
989
 
                uchar* fc = (uchar*) & f;
990
 
                uchar* oc = (uchar*) & o;
991
 
                if (byte != 0) {
992
 
                    f >>= 8;
993
 
                    fc[1] = oc[1];
994
 
                    f -= 1;
995
 
                }
996
 
                tmpsize += bytes(f);
997
 
                //                assert(bytes(f) == nbucket->bytes(i));
998
 
            }
999
 
        }
1000
 
        // copy over old data
1001
 
        memcpy(nbucket->data(nbucketcount, hasent),
1002
 
                node->_data->data(node->_count, hasent), tmpsize);
1003
 
 
1004
 
        memcpy(&(nbucket->data(nbucketcount, hasent)[tmpsize + nitemsize]),
1005
 
                &(node->_data->data(node->_count, hasent)[tmpsize]), (node->_totsize - tmpsize));
1006
 
 
1007
 
        // copy over new data
1008
 
        if (copyval) {
1009
 
            memcpy(&(nbucket->data(nbucketcount, hasent)[tmpsize]),
1010
 
                    nenc.const_raw(), nenc.size());
1011
 
        } else {
1012
 
            // alloc space
1013
 
            uchar* data = (uchar*) malloc(nenc.size());
1014
 
 
1015
 
            // copy data to heap
1016
 
            memcpy(data, nenc.const_raw(), nenc.size());
1017
 
 
1018
 
            // copy pointer in
1019
 
            memcpy(&(nbucket->data(nbucketcount, hasent)[tmpsize]),
1020
 
                    &data, sizeof (uchar*));
1021
 
        }
1022
 
 
1023
 
        // if needed, split the node 
1024
 
 
1025
 
        free(node->_data);
1026
 
        node->_data = nbucket;
1027
 
        node->_count = nbucketcount;
1028
 
        node->_totsize = nbucketsize;
1029
 
 
1030
 
        //        std::cout << " FIRST " << tmp._data->first(nbucketcount, b_index) << std::endl;
1031
 
        //        std::cout << "NODE " << node << " SIZE : " << nbucketsize << std::endl;
1032
 
        if (node->_count >= SPLITBOUND) {
1033
 
            // copy over data to we can work while readers finish
1034
 
            // we have to wait for readers to finish for 
1035
 
            // tree extension
1036
 
            split_node(node, fwd, node, nenc.size(), byte);
1037
 
        }
1038
 
 
1039
 
#ifndef NDEBUG        
1040
 
        for (int i = byte - 1; i >= 2; --i) {
1041
 
            assert(fwd != NULL);
1042
 
            assert(e2[-2 + i] == fwd->_path);
1043
 
            assert(fwd->_parent == NULL || fwd->_parent->_children[fwd->_path] == fwd);
1044
 
            fwd = fwd->_parent;
1045
 
 
1046
 
        }
1047
 
        auto r = exists(data, length);
1048
 
        if (!r.first) {
1049
 
 
1050
 
            r = exists(data, length);
1051
 
            assert(false);
1052
 
        }
1053
 
#endif
1054
 
        return returntype_t(true, entry);
1055
 
    }
1056
 
 
1057
 
    template<PTRIETPL>
1058
 
    returntype_t
1059
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::insert(binarywrapper_t wrapper) {
1060
 
        return insert(wrapper.raw(), wrapper.size());
1061
 
    }
1062
 
 
1063
 
    template<PTRIETPL>
1064
 
    returntype_t
1065
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::exists(binarywrapper_t wrapper) {
1066
 
        return exists(wrapper.raw(), wrapper.size());
1067
 
    }
1068
 
 
1069
 
    
1070
 
        template<PTRIETPL>
1071
 
    void
1072
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::inject_byte(node_t* node, uchar topush, size_t totsize, std::function<uint16_t(size_t)> _sizes)
1073
 
    {
1074
 
        const bool hasent = _entries != NULL;
1075
 
        bucket_t *nbucket = node->_data;
1076
 
        if(totsize > 0) {
1077
 
            nbucket = (bucket_t *) malloc(totsize +
1078
 
                                          bucket_t::overhead(node->_count,
1079
 
                                                             hasent));
1080
 
        }
1081
 
 
1082
 
        size_t dcnt = 0;
1083
 
        size_t ocnt = 0;
1084
 
        for(size_t i = 0; i < node->_count; ++i)
1085
 
        {
1086
 
            auto const size = _sizes(i);
1087
 
            uchar* f = (uchar*)&nbucket->first(node->_count, i);
1088
 
            nbucket->first(node->_count, i) = node->_data->first(node->_count, i);
1089
 
            uchar push = f[0];
1090
 
            f[0] = f[1];
1091
 
            f[1] = topush;
1092
 
            // in some cases we need to expand to heap here!
1093
 
            if(size > 0)
1094
 
            {
1095
 
                if(size < HEAPBOUND)
1096
 
                {
1097
 
                    nbucket->data(node->_count, hasent)[dcnt] = push;
1098
 
                    dcnt += 1;
1099
 
                }
1100
 
                if(size < HEAPBOUND && size > 1)
1101
 
                {
1102
 
                    memcpy(&(nbucket->data(node->_count, hasent)[dcnt]),
1103
 
                               &(node->_data->data(node->_count, hasent)[ocnt]),
1104
 
                                       size - 1);
1105
 
                    ocnt += size - 1;
1106
 
                    dcnt += size - 1;
1107
 
                }
1108
 
                else if(size >= HEAPBOUND)
1109
 
                {
1110
 
                    uchar* src = NULL;
1111
 
                    uchar* dest = (uchar*)malloc(size);
1112
 
                    memcpy(&(nbucket->data(node->_count, hasent)[dcnt]), &dest, sizeof(size_t));
1113
 
                    ++dest;
1114
 
                    dcnt += sizeof(size_t);
1115
 
                    if(size == HEAPBOUND)
1116
 
                    {
1117
 
                        src = &(node->_data->data(node->_count, hasent)[ocnt]);
1118
 
                        memcpy(dest, src, size - 1);
1119
 
                        ocnt += size - 1;
1120
 
                    }
1121
 
                    else
1122
 
                    {
1123
 
                        assert(size > HEAPBOUND);
1124
 
                        // allready on heap, but we need to expand it
1125
 
                        src = *(uchar**)&(node->_data->data(node->_count, hasent)[ocnt]);
1126
 
                        memcpy(dest, src, size - 1);
1127
 
                        ocnt += sizeof(size_t);
1128
 
                    }
1129
 
                    --dest;
1130
 
                    dest[0] = push;
1131
 
                }
1132
 
            }
1133
 
            // also, handle entries here!
1134
 
        }
1135
 
 
1136
 
        assert(ocnt == node->_totsize);
1137
 
        assert(totsize == dcnt);
1138
 
 
1139
 
        if(nbucket != node->_data) free(node->_data);
1140
 
 
1141
 
        node->_data = nbucket;
1142
 
    }
1143
 
 
1144
 
 
1145
 
    template<PTRIETPL>
1146
 
    bool
1147
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::merge_down(fwdnode_t* parent, node_t* node, int on_heap)
1148
 
    {
1149
 
        const bool hasent = _entries != NULL;
1150
 
        if(node->_type == 0)
1151
 
        {
1152
 
            if(node->_count < SPLITBOUND/3) return true;
1153
 
            if(node->_count == 0)
1154
 
            {
1155
 
                for(size_t i = 0; i < 256; ++i) parent->_children[i] = parent;
1156
 
                delete node;
1157
 
                do {
1158
 
                    if (parent != this->_root) {
1159
 
                        // we can remove fwd and go back one level
1160
 
                        parent->_parent->_children[parent->_path] = parent->_parent;
1161
 
                        ++on_heap;
1162
 
                        fwdnode_t* next = parent->_parent;
1163
 
                        delete parent;
1164
 
                        parent = next;
1165
 
                        base_t* other = parent;
1166
 
                        for(size_t i = 0; i < 256; ++i)
1167
 
                        {
1168
 
                            if(parent->_children[i] != parent && other != parent->_children[i])
1169
 
                            {
1170
 
                                if(other != parent)
1171
 
                                {
1172
 
                                    other = NULL;
1173
 
                                    break;
1174
 
                                }
1175
 
                                else
1176
 
                                {
1177
 
                                    other = parent->_children[i];
1178
 
                                }
1179
 
                            }
1180
 
                        }
1181
 
 
1182
 
                        if(other == NULL)
1183
 
                        {
1184
 
                            return true;
1185
 
                        }
1186
 
                        else if(other->_type != 255)
1187
 
                        {
1188
 
                            node = (node_t*)other;
1189
 
                            return merge_down(parent, node, on_heap);
1190
 
                        }
1191
 
                        else if(other != parent)
1192
 
                        {
1193
 
                            assert(other->_type == 255);
1194
 
                            return true;
1195
 
                        }
1196
 
 
1197
 
                    } else {
1198
 
                        return true;
1199
 
                    }
1200
 
                } while(true);
1201
 
            }
1202
 
            else if(parent != this->_root)
1203
 
            {
1204
 
                // we need to re-add path to items here.
1205
 
                if(parent->_parent == this->_root) {
1206
 
                    // something
1207
 
                    uint16_t sizes[256];
1208
 
                    size_t totsize = 0;
1209
 
                    for(size_t i = 0; i < node->_count; ++i)
1210
 
                    {
1211
 
                        uint16_t t = 0;
1212
 
                        uchar* tc = (uchar*)&t;
1213
 
                        uchar* fc = (uchar*)&node->_data->first(node->_count, i);
1214
 
                        tc[0] = fc[1];
1215
 
                        tc[1] = parent->_path;
1216
 
                        sizes[i] = t;
1217
 
                        totsize += bytes(sizes[i]);
1218
 
                    }
1219
 
 
1220
 
                    inject_byte(node, parent->_path, totsize, [&sizes](size_t i )
1221
 
                    {
1222
 
                        return sizes[i];
1223
 
                    });
1224
 
 
1225
 
                    node->_path = parent->_path;
1226
 
                    parent->_parent->_children[node->_path] = node;
1227
 
                    node->_type = 8;
1228
 
                    node->_totsize = totsize;
1229
 
                    fwdnode_t* next = parent->_parent;
1230
 
                    delete parent;
1231
 
                    return merge_down(next, node, on_heap + 1);
1232
 
                }
1233
 
                else
1234
 
                {
1235
 
                    assert(node->_count > 0);
1236
 
                    if(on_heap == std::numeric_limits<int>::min())
1237
 
                    {
1238
 
                        int depth = 0;
1239
 
                        uint16_t length = 0;
1240
 
                        uchar* l = (uchar*)&length;
1241
 
                        fwdnode_t* tmp = parent;
1242
 
 
1243
 
                        while(tmp != this->_root)
1244
 
                        {
1245
 
                            l[0] = l[1];
1246
 
                            l[1] = tmp->_path;
1247
 
                            tmp = tmp->_parent;
1248
 
                            ++depth;
1249
 
                        }
1250
 
                        assert(length + 1 >= depth);
1251
 
                        on_heap = length;
1252
 
                        on_heap -= depth;
1253
 
                    }
1254
 
 
1255
 
                    on_heap += 1;
1256
 
                    // first copy in path to firsts.
1257
 
 
1258
 
                    assert(on_heap >= 0);
1259
 
                    node->_path = parent->_path;
1260
 
                    parent->_parent->_children[node->_path] = node;
1261
 
                    fwdnode_t* next = parent->_parent;
1262
 
                    delete parent;
1263
 
                    parent = next;
1264
 
                    node->_type = 8;
1265
 
 
1266
 
                    if(on_heap == 0)
1267
 
                    {
1268
 
                        for(size_t i = 0; i < node->_count; ++i)
1269
 
                        {
1270
 
                            uchar* f = (uchar*)&node->_data->first(node->_count, i);
1271
 
                            f[0] = f[1];
1272
 
                            f[1] = node->_path;
1273
 
                        }
1274
 
                    }
1275
 
                    else if(on_heap > 0)
1276
 
                    {
1277
 
                        size_t nbucketsize = 0;
1278
 
                        if(on_heap >= HEAPBOUND)
1279
 
                        {
1280
 
                            nbucketsize = node->_count * sizeof(size_t);
1281
 
                        }
1282
 
                        else//if(on_heap < HEAPBOUND)
1283
 
                        {
1284
 
                            assert(on_heap >= 0);
1285
 
                            nbucketsize = on_heap * node->_count;
1286
 
                        }
1287
 
 
1288
 
                        inject_byte(node, node->_path, nbucketsize, [on_heap](size_t)
1289
 
                        {
1290
 
                            return on_heap;
1291
 
                        });
1292
 
 
1293
 
                        node->_totsize = nbucketsize;
1294
 
                    }
1295
 
                    return merge_down(next, node, on_heap + 1);
1296
 
                }
1297
 
            }
1298
 
            if(parent != this->_root)
1299
 
            {
1300
 
                assert(node->_count > 0);
1301
 
                return merge_down(parent->_parent, node, on_heap);
1302
 
            }
1303
 
        }
1304
 
        else
1305
 
        {
1306
 
            if(node->_count > SPLITBOUND / 3) return true;
1307
 
            uchar path = node->_path;
1308
 
            base_t* child;
1309
 
            if(path & binarywrapper_t::_masks[node->_type - 1])
1310
 
            {
1311
 
                child = parent->_children[
1312
 
                         path & ~binarywrapper_t::_masks[node->_type - 1]];
1313
 
            }
1314
 
            else
1315
 
            {
1316
 
                child = parent->_children[
1317
 
                        path | binarywrapper_t::_masks[node->_type - 1]];
1318
 
            }
1319
 
 
1320
 
            assert(node != child);
1321
 
 
1322
 
            if(child->_type != node->_type && child->_type != 255)
1323
 
            {
1324
 
                // The other node is not ready for merging yet.
1325
 
                assert(child->_type > node->_type);
1326
 
                return false;
1327
 
            }
1328
 
            else
1329
 
            {
1330
 
 
1331
 
                if(child->_type != 255) {
1332
 
                    node_t *other = (node_t *) child;
1333
 
 
1334
 
                    const uint nbucketcount = node->_count + other->_count;
1335
 
                    const uint nbucketsize = node->_totsize + other->_totsize;
1336
 
 
1337
 
                    if (nbucketcount >= SPLITBOUND)
1338
 
                        return false;
1339
 
 
1340
 
                    bucket_t *nbucket = (bucket_t *) malloc(nbucketsize +
1341
 
                                                            bucket_t::overhead(nbucketcount, hasent));
1342
 
                    node_t *first = node;
1343
 
                    node_t *second = other;
1344
 
                    if (path & binarywrapper_t::_masks[node->_type - 1]) {
1345
 
                        std::swap(first, second);
1346
 
                    }
1347
 
 
1348
 
                    memcpy(&nbucket->first(nbucketcount),
1349
 
                           &(first->_data->first(first->_count)),
1350
 
                           first->_count * sizeof(uint16_t));
1351
 
 
1352
 
                    memcpy(&(nbucket->first(nbucketcount, first->_count)),
1353
 
                           &(second->_data->first(second->_count)),
1354
 
                           second->_count * sizeof(uint16_t));
1355
 
 
1356
 
                    if (hasent) {
1357
 
                        // copy over entries
1358
 
                        memcpy(nbucket->entries(nbucketcount, true),
1359
 
                               first->_data->entries(first->_count, true),
1360
 
                               first->_count * sizeof(I));
1361
 
                        memcpy(&(nbucket->entries(nbucketcount, true)[first->_count]),
1362
 
                               second->_data->entries(second->_count, true),
1363
 
                               second->_count * sizeof(I));
1364
 
 
1365
 
                    }
1366
 
 
1367
 
                    // copy over old data
1368
 
                    if (nbucketsize > 0) {
1369
 
                        memcpy(nbucket->data(nbucketcount, hasent),
1370
 
                               first->_data->data(first->_count, hasent), first->_totsize);
1371
 
 
1372
 
                        memcpy(&(nbucket->data(nbucketcount, hasent)[first->_totsize]),
1373
 
                               second->_data->data(second->_count, hasent), second->_totsize);
1374
 
 
1375
 
                    }
1376
 
                    free(node->_data);
1377
 
                    node->_data = nbucket;
1378
 
                    node->_totsize = nbucketsize;
1379
 
                    node->_count = nbucketcount;
1380
 
                }
1381
 
                uchar from = node->_path & ~binarywrapper_t::_masks[node->_type - 1];
1382
 
                uchar to = from;
1383
 
                for(size_t i = node->_type - 1; i < 8; ++i) {
1384
 
                    to = to | binarywrapper_t::_masks[i];
1385
 
                }
1386
 
 
1387
 
                if(child->_type == 255)
1388
 
                {
1389
 
                    if(child != parent) return true;
1390
 
                    for(size_t i = from; i <= to; ++i)
1391
 
                    {
1392
 
                        if( parent->_children[i] != child &&
1393
 
                            parent->_children[i] != node)
1394
 
                            return  true;
1395
 
                    }
1396
 
                }
1397
 
 
1398
 
                node->_type -= 1;
1399
 
                node->_path = from;
1400
 
 
1401
 
                for(size_t i = from; i <= to; ++i)
1402
 
                {
1403
 
                    assert(parent->_children[i] == child ||
1404
 
                       parent->_children[i] == node);
1405
 
                    parent->_children[i] = node;
1406
 
                }
1407
 
                return merge_down(parent, node, on_heap);
1408
 
            }
1409
 
        }
1410
 
        return true;
1411
 
    }
1412
 
 
1413
 
    template<PTRIETPL>
1414
 
    void
1415
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::erase(fwdnode_t* parent, node_t* node, size_t bindex, int on_heap)
1416
 
    {
1417
 
        const bool hasent = _entries != NULL;
1418
 
 
1419
 
        // first find size and amount before
1420
 
        uint16_t size = 0;
1421
 
        uint16_t before = 0;
1422
 
        if (parent == this->_root)
1423
 
        {
1424
 
            for(size_t i = 0; i < bindex; ++i)
1425
 
            {
1426
 
               before += bytes(node->_data->first(node->_count, i));
1427
 
            }
1428
 
            size = node->_data->first(node->_count, bindex);
1429
 
        }
1430
 
        else if(parent->_parent == this->_root) {
1431
 
             for(size_t i = 0; i <= bindex; ++i)
1432
 
             {
1433
 
                 uint16_t t = 0;
1434
 
                 uchar* tc = (uchar*)&t;
1435
 
                 uchar* fc = (uchar*)&node->_data->first(node->_count, i);
1436
 
                 tc[0] = fc[1];
1437
 
                 tc[1] = parent->_path;
1438
 
                 --t;
1439
 
                 if(i == bindex) size = t;
1440
 
                 else before += bytes(t);
1441
 
             }
1442
 
        } else {
1443
 
            assert(on_heap != std::numeric_limits<int>::min());
1444
 
            size = on_heap > 0 ? on_heap : 0;
1445
 
            before = size * bindex;
1446
 
        }
1447
 
 
1448
 
        // got sizes, now we can remove data if we point to anything
1449
 
        if(size >= HEAPBOUND)
1450
 
        {
1451
 
            before = sizeof(size_t)*bindex;
1452
 
            uchar* src = *((uchar**)&(node->_data->data(node->_count, hasent)[before]));
1453
 
            free(src);
1454
 
            size = sizeof(size_t);
1455
 
        }
1456
 
 
1457
 
        uint nbucketcount = node->_count - 1;
1458
 
        if(nbucketcount > 0) {
1459
 
            uint nbucketsize = node->_totsize - size;
1460
 
 
1461
 
            bucket_t *nbucket = (bucket_t *) malloc(nbucketsize +
1462
 
                                                    bucket_t::overhead(nbucketcount, hasent));
1463
 
 
1464
 
            // copy over old "firsts", [0,bindex) to [0,bindex) then (bindex,node->_count) to [bindex, nbucketcount)
1465
 
            memcpy(&nbucket->first(nbucketcount),
1466
 
                   &(node->_data->first(node->_count)),
1467
 
                   bindex * sizeof(uint16_t));
1468
 
 
1469
 
            memcpy(&(nbucket->first(nbucketcount, bindex)),
1470
 
                       &(node->_data->first(node->_count, bindex + 1)),
1471
 
                       (nbucketcount - bindex) * sizeof(uint16_t));
1472
 
 
1473
 
            if (hasent) {
1474
 
                // copy over entries
1475
 
                memcpy(nbucket->entries(nbucketcount, true),
1476
 
                       node->_data->entries(node->_count, true),
1477
 
                       bindex * sizeof(I));
1478
 
                memcpy(&(nbucket->entries(nbucketcount, true)[bindex]),
1479
 
                       &(node->_data->entries(node->_count, true)[bindex + 1]),
1480
 
                       (nbucketcount - bindex) * sizeof(I));
1481
 
 
1482
 
                // copy back entries here in _entries!
1483
 
                // TODO fixme!
1484
 
            }
1485
 
 
1486
 
            // copy over old data
1487
 
            if (nbucketsize > 0) {
1488
 
                memcpy(nbucket->data(nbucketcount, hasent),
1489
 
                       node->_data->data(node->_count, hasent), before);
1490
 
                assert(nbucketsize >= before);
1491
 
                memcpy(&(nbucket->data(nbucketcount, hasent)[before]),
1492
 
                       &(node->_data->data(node->_count, hasent)[before + size]),
1493
 
                       (nbucketsize - before));
1494
 
 
1495
 
            }
1496
 
            free(node->_data);
1497
 
            node->_data = nbucket;
1498
 
            node->_count = nbucketcount;
1499
 
            node->_totsize -= size;
1500
 
 
1501
 
        }
1502
 
        else
1503
 
        {
1504
 
            free(node->_data);
1505
 
            node->_data = NULL;
1506
 
            node->_count = 0;
1507
 
            node->_totsize = 0;
1508
 
        }
1509
 
 
1510
 
        merge_down(parent, node, on_heap);
1511
 
    }
1512
 
 
1513
 
    template<PTRIETPL>
1514
 
    bool
1515
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::erase(binarywrapper_t encoding)
1516
 
    {
1517
 
        assert(encoding.size() <= 65536);
1518
 
        uint b_index = 0;
1519
 
 
1520
 
        fwdnode_t* fwd = this->_root;
1521
 
        base_t* base = NULL;
1522
 
        uint byte = 0;
1523
 
 
1524
 
        b_index = 0;
1525
 
        bool res = this->best_match(encoding, &fwd, &base, byte, b_index);
1526
 
        if(!res || (size_t)fwd == (size_t)base)
1527
 
        {
1528
 
            assert(!this->exists(encoding).first);
1529
 
            return false;
1530
 
        }
1531
 
        else
1532
 
        {
1533
 
            int onheap = encoding.size();
1534
 
            onheap -= byte;
1535
 
            erase(fwd, (node_t *) base, b_index, onheap);
1536
 
            assert(!this->exists(encoding).first);
1537
 
            return true;
1538
 
        }
1539
 
    }
1540
 
 
1541
 
    template<PTRIETPL>
1542
 
    bool
1543
 
    set<HEAPBOUND, SPLITBOUND, ALLOCSIZE, T, I>::erase(const uchar *data, size_t length)
1544
 
    {
1545
 
        binarywrapper_t b((uchar*)data, length*8);
1546
 
        return erase(b);
1547
 
    }
1548
 
 
1549
 
 
1550
 
}
1551
 
 
1552
 
 
1553
 
 
1554
 
#endif /* PTRIE_H */