Welcome to little lamb

Code » limb » master » tree

[master] / src / liblimb / cdbmake.h / cdbmaker_sa_finish.c 

 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
/* This file is part of limb                           https://lila.oss/limb
 * Copyright (C) 2023 Olivier Brunel                          jjk@jjacky.com */
/* SPDX-License-Identifier: GPL-2.0-only */
#include <errno.h>
#include <limb/cdbmake.h>
#include <limb/u32.h>
#include "cdbmake.h"

int
cdbmaker_sa_finish(cdbmaker_sa *m)
{
    u32 count[256] = { 0 };
    u32 start[256];
    unsigned int size = 1;
    unsigned int n = genalloc_len(diu32, &m->hplist);
    unsigned int i;
    diu32 *hp = genalloc_s(diu32, &m->hplist);

    for (i = 0; i < n; ++i)
        ++count[hp[i].left & 255];

    u32 u = 0;
    for (i = 0; i < 256; ++i)
        start[i] = u += count[i];
    for (i = 0; i < 256; ++i) {
        u = count[i] << 1;
        if (u > size)
            size = u;
    }

    size += n;
    u = 0xffffffffUL;
    u /= sizeof(diu32);
    if (size > u)
        return (errno = ENOMEM, 0);

    diu32 split[size];
    i = n;
    while (i--)
        split[--start[hp[i].left & 255]] = hp[i];
    genalloc_free(diu32, &m->hplist);
    hp = split + n;

    for (i = 0; i < 256; ++i) {
        u32 k = count[i];
        u32 len = k << 1;
        diu32 *p = split + start[i];

        u32_pack(m->sa.s + (i << 3), m->sa.len);
        u32_pack(m->sa.s + (i << 3) + 4, len);

        for (u32 j = 0; j < len; ++j)
            hp[j].left = hp[j].right = 0;
        for (u32 j = 0; j < k; ++j) {
            u32 where = (p->left >> 8) % len;
            while (hp[where].right)
                if (++where == len)
                    where = 0;
            hp[where] = *p++;
        }

        for (u32 j = 0; j < len; ++j) {
            if (!stralloc_readyplus(&m->sa, 8))
                return 0;
            u32_pack(m->sa.s + m->sa.len, hp[j].left);
            m->sa.len += 4;
            u32_pack(m->sa.s + m->sa.len, hp[j].right);
            m->sa.len += 4;
        }
    }

    return 1;
}