24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include "lib.h"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include "array.h"

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen#include "str.h"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include "read-full.h"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include "istream.h"

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen#include "ostream.h"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include "unichar.h"

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen#include "nfs-workarounds.h"

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen#include "file-cache.h"

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen#include "seq-range-array.h"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include "squat-uidlist.h"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include "squat-trie-private.h"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#include <stdio.h>

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen#include <unistd.h>

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen#include <sys/mman.h>

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen#define DEFAULT_NORMALIZE_MAP_CHARS \

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen "EOTIRSACDNLMVUGPHBFWYXKJQZ0123456789@.-+#$%_&"

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#define DEFAULT_PARTIAL_LEN 4

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#define DEFAULT_FULL_LEN 4

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#define MAX_FAST_LEVEL 3

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#define SEQUENTIAL_COUNT 46

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#define TRIE_BYTES_LEFT(n) \

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen ((n) * SQUAT_PACK_MAX_SIZE)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#define TRIE_READAHEAD_SIZE \

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen I_MAX(4096, 1 + 256 + TRIE_BYTES_LEFT(256))

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstruct squat_trie_build_context {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct squat_trie *trie;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct ostream *output;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_uidlist_build_context *uidlist_build_ctx;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct file_lock *file_lock;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct dotlock *dotlock;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen uint32_t first_uid;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen bool compress_nodes:1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen};

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainenstruct squat_trie_iterate_node {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct squat_node *node;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen ARRAY_TYPE(seq_range) shifts;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned int idx;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen};

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstruct squat_trie_iterate_context {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct squat_trie *trie;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct squat_trie_iterate_node cur;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen ARRAY(struct squat_trie_iterate_node) parents;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen bool failed;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen};

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic int squat_trie_map(struct squat_trie *trie, bool building);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenvoid squat_trie_delete(struct squat_trie *trie)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen{

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_unlink_if_exists(trie->path);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen squat_uidlist_delete(trie->uidlist);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen}

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainenstatic void squat_trie_set_corrupted(struct squat_trie *trie)

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen{

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen trie->corrupted = TRUE;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen i_error("Corrupted file %s", trie->path);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen squat_trie_delete(trie);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen}

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic void squat_trie_normalize_map_build(struct squat_trie *trie)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen{

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen static unsigned char valid_chars[] =

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen DEFAULT_NORMALIZE_MAP_CHARS;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int i, j;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen memset(trie->default_normalize_map, 0,

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen sizeof(trie->default_normalize_map));

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#if 1

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 0, j = 1; i < sizeof(valid_chars)-1; i++) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned char chr = valid_chars[i];

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (chr >= 'A' && chr <= 'Z')

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->default_normalize_map[chr-'A'+'a'] = j;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->default_normalize_map[chr] = j++;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen }

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_assert(j <= SEQUENTIAL_COUNT);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 128; i < 256; i++)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->default_normalize_map[i] = j++;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen#else

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 0; i < sizeof(valid_chars)-1; i++) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned char chr = valid_chars[i];

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (chr >= 'A' && chr <= 'Z')

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->default_normalize_map[chr-'A'+'a'] = chr;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->default_normalize_map[chr] = chr;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen for (i = 128; i < 256; i++)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->default_normalize_map[i] = i_toupper(i);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen#endif

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic void node_free(struct squat_trie *trie, struct squat_node *node)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct squat_node *children;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int i;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (node->leaf_string_length > 0) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (NODE_IS_DYNAMIC_LEAF(node))

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_free(node->children.leaf_string);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else if (!node->children_not_mapped) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen children = NODE_CHILDREN_NODES(node);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->node_alloc_size -=

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen NODE_CHILDREN_ALLOC_SIZE(node->child_count);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 0; i < node->child_count; i++)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node_free(trie, &children[i]);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_free(node->children.data);

7a24bdc1a5e2d5368c2569b4852192f2bdb5a31fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

7a24bdc1a5e2d5368c2569b4852192f2bdb5a31fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstruct squat_trie *

7a24bdc1a5e2d5368c2569b4852192f2bdb5a31fTimo Sirainensquat_trie_init(const char *path, uint32_t uidvalidity,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen enum file_lock_method lock_method, enum squat_index_flags flags,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen mode_t mode, gid_t gid)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen struct squat_trie *trie;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie = i_new(struct squat_trie, 1);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->path = i_strdup(path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->uidlist = squat_uidlist_init(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->fd = -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->lock_method = lock_method;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->uidvalidity = uidvalidity;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->flags = flags;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->create_mode = mode;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->create_gid = gid;

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen squat_trie_normalize_map_build(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->dotlock_set.use_excl_lock =

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen (flags & SQUAT_INDEX_FLAG_DOTLOCK_USE_EXCL) != 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->dotlock_set.nfs_flush = (flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->dotlock_set.timeout = SQUAT_TRIE_LOCK_TIMEOUT;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->dotlock_set.stale_timeout = SQUAT_TRIE_DOTLOCK_STALE_TIMEOUT;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->default_partial_len = DEFAULT_PARTIAL_LEN;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->default_full_len = DEFAULT_FULL_LEN;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return trie;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic void squat_trie_close_fd(struct squat_trie *trie)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->data = NULL;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->data_size = 0;

7e209b78ca757294dbbc15604c88673b3a6b0c39Timo Sirainen

7e209b78ca757294dbbc15604c88673b3a6b0c39Timo Sirainen if (trie->mmap_size != 0) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (munmap(trie->mmap_base, trie->mmap_size) < 0)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_error("munmap(%s) failed: %m", trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->mmap_base = NULL;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->mmap_size = 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (trie->fd != -1) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (close(trie->fd) < 0)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_error("close(%s) failed: %m", trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->fd = -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainenstatic void squat_trie_close(struct squat_trie *trie)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen trie->corrupted = FALSE;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen node_free(trie, &trie->root);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen memset(&trie->root, 0, sizeof(trie->root));

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen memset(&trie->hdr, 0, sizeof(trie->hdr));

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen squat_trie_close_fd(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (trie->file_cache != NULL)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen file_cache_free(&trie->file_cache);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->locked_file_size = 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainenvoid squat_trie_deinit(struct squat_trie **_trie)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen struct squat_trie *trie = *_trie;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen *_trie = NULL;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen squat_trie_close(trie);

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen squat_uidlist_deinit(trie->uidlist);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_free(trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_free(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainenvoid squat_trie_set_partial_len(struct squat_trie *trie, unsigned int len)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->default_partial_len = len;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenvoid squat_trie_set_full_len(struct squat_trie *trie, unsigned int len)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->default_full_len = len;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic void squat_trie_header_init(struct squat_trie *trie)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen memset(&trie->hdr, 0, sizeof(trie->hdr));

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->hdr.version = SQUAT_TRIE_VERSION;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->hdr.indexid = time(NULL);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->hdr.uidvalidity = trie->uidvalidity;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->hdr.partial_len = trie->default_partial_len;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->hdr.full_len = trie->default_full_len;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_assert(sizeof(trie->hdr.normalize_map) ==

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen sizeof(trie->default_normalize_map));

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen memcpy(trie->hdr.normalize_map, trie->default_normalize_map,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen sizeof(trie->hdr.normalize_map));

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainenstatic int squat_trie_open_fd(struct squat_trie *trie)

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen{

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen trie->fd = open(trie->path, O_RDWR);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (trie->fd == -1) {

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen if (errno == ENOENT) {

939a0d82523538b2de38a02bc9f790a67b7ebf47Timo Sirainen squat_trie_header_init(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_error("open(%s) failed: %m", trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (trie->file_cache != NULL)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen file_cache_set_fd(trie->file_cache, trie->fd);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenint squat_trie_open(struct squat_trie *trie)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen squat_trie_close(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (squat_trie_open_fd(trie) < 0)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return squat_trie_map(trie, FALSE);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic int squat_trie_is_file_stale(struct squat_trie *trie)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen struct stat st, st2;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if ((trie->flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen nfs_flush_file_handle_cache(trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (nfs_safe_stat(trie->path, &st) < 0) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (errno == ENOENT)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return 1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_error("stat(%s) failed: %m", trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (fstat(trie->fd, &st2) < 0) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (errno == ESTALE)

7e209b78ca757294dbbc15604c88673b3a6b0c39Timo Sirainen return 1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_error("fstat(%s) failed: %m", trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->locked_file_size = st2.st_size;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (st.st_ino == st2.st_ino && CMP_DEV_T(st.st_dev, st2.st_dev)) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_assert(trie->locked_file_size >= trie->data_size);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return 1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenint squat_trie_refresh(struct squat_trie *trie)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen int ret;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen ret = squat_trie_is_file_stale(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (ret > 0)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen ret = squat_trie_open(trie);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return ret;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic int squat_trie_lock(struct squat_trie *trie, int lock_type,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen struct file_lock **file_lock_r,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen struct dotlock **dotlock_r)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen int ret;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_assert(trie->fd != -1);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen *file_lock_r = NULL;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen *dotlock_r = NULL;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen for (;;) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (trie->lock_method != FILE_LOCK_METHOD_DOTLOCK) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen ret = file_wait_lock(trie->fd, trie->path, lock_type,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->lock_method,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen SQUAT_TRIE_LOCK_TIMEOUT,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen file_lock_r);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen } else {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen ret = file_dotlock_create(&trie->dotlock_set,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen trie->path, 0, dotlock_r);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (ret == 0) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_error("squat trie %s: Locking timed out", trie->path);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (ret < 0)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return -1;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* if the trie has been compressed, we need to reopen the

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen ret = squat_trie_is_file_stale(trie);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (ret == 0)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen break;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (*file_lock_r != NULL)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen file_unlock(file_lock_r);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen else

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen file_dotlock_delete(dotlock_r);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (ret < 0)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return -1;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen squat_trie_close(trie);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (squat_trie_open_fd(trie) < 0)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return -1;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (trie->fd == -1)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return 0;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen }

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if ((trie->flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen nfs_flush_read_cache_locked(trie->path, trie->fd);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return 1;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen}

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic void

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainennode_make_squential(struct squat_trie *trie, struct squat_node *node, int level)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen{

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen const unsigned int alloc_size =

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen NODE_CHILDREN_ALLOC_SIZE(SEQUENTIAL_COUNT);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct squat_node *children;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned char *chars;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned int i;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_assert(node->child_count == 0);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->node_alloc_size += alloc_size;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->want_sequential = FALSE;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->have_sequential = TRUE;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->child_count = SEQUENTIAL_COUNT;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->children.data = i_malloc(alloc_size);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen chars = NODE_CHILDREN_CHARS(node);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 0; i < SEQUENTIAL_COUNT; i++)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen chars[i] = i;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (level < MAX_FAST_LEVEL) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen children = NODE_CHILDREN_NODES(node);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 0; i < SEQUENTIAL_COUNT; i++)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen children[i].want_sequential = TRUE;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen }

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen}

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic unsigned int

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainennode_add_child(struct squat_trie *trie, struct squat_node *node,

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned char chr, int level)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen{

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned int old_child_count = node->child_count;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen struct squat_node *children, *old_children;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned char *chars;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen size_t old_size, new_size;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_assert(node->leaf_string_length == 0);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (node->want_sequential) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node_make_squential(trie, node, level);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (chr < SEQUENTIAL_COUNT)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return chr;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen old_child_count = SEQUENTIAL_COUNT;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen }

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->child_count++;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen new_size = NODE_CHILDREN_ALLOC_SIZE(node->child_count);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (old_child_count == 0) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* first child */

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->children.data = i_malloc(new_size);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->node_alloc_size += new_size;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen } else {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen old_size = NODE_CHILDREN_ALLOC_SIZE(old_child_count);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (old_size != new_size) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->node_alloc_size += new_size - old_size;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->children.data = i_realloc(node->children.data,

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen old_size, new_size);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen children = NODE_CHILDREN_NODES(node);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen old_children = (void *)(NODE_CHILDREN_CHARS(node) +

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen MEM_ALIGN(old_child_count));

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (children != old_children) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen memmove(children, old_children,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen old_child_count * sizeof(struct squat_node));

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen chars = NODE_CHILDREN_CHARS(node);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_assert(chars != NULL);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen chars[node->child_count - 1] = chr;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return node->child_count - 1;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen}

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainenstatic int

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainentrie_file_cache_read(struct squat_trie *trie, size_t offset, size_t size)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen{

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (trie->file_cache == NULL)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return 0;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (file_cache_read(trie->file_cache, offset, size) < 0) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_error("read(%s) failed: %m", trie->path);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return -1;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen }

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen trie->data = file_cache_get_map(trie->file_cache, &trie->data_size);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return 0;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic int

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainennode_read_children(struct squat_trie *trie, struct squat_node *node, int level)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen const uint8_t *data, *end;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen const unsigned char *child_chars;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen struct squat_node *child, *children = NULL;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen uoff_t node_offset;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen unsigned int i, child_idx, child_count;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen uoff_t base_offset;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen uint32_t num;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(node->children_not_mapped);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_assert(!node->have_sequential);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_assert(trie->unmapped_child_count > 0);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen i_assert(trie->data_size <= trie->locked_file_size);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->unmapped_child_count--;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node_offset = node->children.offset;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->children_not_mapped = FALSE;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen node->children.data = NULL;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen if (trie_file_cache_read(trie, node_offset, TRIE_READAHEAD_SIZE) < 0)

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return -1;

db0735f9b388c5bcfb781b1b25015e898d63d953Timo Sirainen if (unlikely(node_offset >= trie->data_size)) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen squat_trie_set_corrupted(trie);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen data = CONST_PTR_OFFSET(trie->data, node_offset);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen end = CONST_PTR_OFFSET(trie->data, trie->data_size);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_count = *data++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (unlikely(node_offset + child_count >= trie->data_size)) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen squat_trie_set_corrupted(trie);

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (child_count == 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen child_chars = data;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen data += child_count;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* get child offsets */

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen base_offset = node_offset;

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen for (i = 0; i < child_count; i++) {

24e5e4526d8f5cbc056ab97fd0d154d0936d7a5eTimo Sirainen /* we always start with !have_sequential, so at i=0 this

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (node->have_sequential && child_chars[i] < SEQUENTIAL_COUNT)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_idx = child_chars[i];

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen else {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_idx = node_add_child(trie, node, child_chars[i],

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen level);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen children = NODE_CHILDREN_NODES(node);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(children != NULL);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child = &children[child_idx];

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* 1) child offset */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen num = squat_unpack_num(&data, end);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (num == 0) {

e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainen /* no children */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if ((num & 1) != 0) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen base_offset += num >> 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen base_offset -= num >> 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (base_offset >= trie->locked_file_size) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen squat_trie_set_corrupted(trie);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->unmapped_child_count++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child->children_not_mapped = TRUE;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child->children.offset = base_offset;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* 2) uidlist */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child->uid_list_idx = squat_unpack_num(&data, end);

e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainen if (child->uid_list_idx == 0) {

e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainen /* we don't write nodes with empty uidlists */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen squat_trie_set_corrupted(trie);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (!UIDLIST_IS_SINGLETON(child->uid_list_idx)) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* 3) next uid */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child->next_uid = squat_unpack_num(&data, end) + 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else {

e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainen uint32_t idx = child->uid_list_idx;

e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen child->next_uid = 1 +

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen squat_uidlist_singleton_last_uid(idx);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* 4) unused uids + leaf string flag */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen num = squat_unpack_num(&data, end);

fb7dd075cf883e5e7defbc0c8fb8326e30bdccdeTimo Sirainen child->unused_uids = num >> 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if ((num & 1) != 0) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* leaf string */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int len;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned char *dest;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen /* 5) leaf string length */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen len = child->leaf_string_length =

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen squat_unpack_num(&data, end) + 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (!NODE_IS_DYNAMIC_LEAF(child))

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen dest = child->children.static_leaf_string;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen else {

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen dest = child->children.leaf_string =

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_malloc(len);

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (trie->file_cache != NULL) {

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen /* the string may be long -

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen size_t offset, size;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen offset = (const char *)data -

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen (const char *)trie->data;

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen size = len + TRIE_BYTES_LEFT(child_count - i);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (trie_file_cache_read(trie, offset,

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen size) < 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen data = CONST_PTR_OFFSET(trie->data, offset);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen end = CONST_PTR_OFFSET(trie->data,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->data_size);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_chars = CONST_PTR_OFFSET(trie->data,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node_offset + 1);

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen }

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen if ((size_t)(end - data) < len) {

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen squat_trie_set_corrupted(trie);

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen return -1;

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen memcpy(dest, data, len);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen data += len;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (unlikely(data == end)) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* we should never get this far */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen squat_trie_set_corrupted(trie);

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen return -1;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen

e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainenstatic void

e3736b5d480878031c386ac55d201fcf08e68766Timo Sirainennode_write_children(struct squat_trie_build_context *ctx,

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen struct squat_node *node, const uoff_t *node_offsets)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_node *children;

d516e6848ecfbc7381abe9414fd8011fdf9d8c95Timo Sirainen const unsigned char *chars;

a21823d90cee6a18aeab0378637472c7e3fbbab2Timo Sirainen uint8_t child_count, buf[SQUAT_PACK_MAX_SIZE * 5], *bufp;

d516e6848ecfbc7381abe9414fd8011fdf9d8c95Timo Sirainen uoff_t base_offset;

d516e6848ecfbc7381abe9414fd8011fdf9d8c95Timo Sirainen unsigned int i;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen chars = NODE_CHILDREN_CHARS(node);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen children = NODE_CHILDREN_NODES(node);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen base_offset = ctx->output->offset;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child_count = node->child_count;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen o_stream_nsend(ctx->output, &child_count, 1);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen o_stream_nsend(ctx->output, chars, child_count);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen for (i = 0; i < child_count; i++) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen bufp = buf;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* 1) child offset */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen if (node_offsets[i] == 0)

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen *bufp++ = 0;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen else if (node_offsets[i] >= base_offset) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen squat_pack_num(&bufp,

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen ((node_offsets[i] - base_offset) << 1) | 1);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen base_offset = node_offsets[i];

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen } else {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen squat_pack_num(&bufp,

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen (base_offset - node_offsets[i]) << 1);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen base_offset = node_offsets[i];

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* 2) uidlist */

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen squat_pack_num(&bufp, children[i].uid_list_idx);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (!UIDLIST_IS_SINGLETON(children[i].uid_list_idx)) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* 3) next uid */

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen squat_pack_num(&bufp, children[i].next_uid - 1);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (children[i].leaf_string_length == 0) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* 4a) unused uids */

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen squat_pack_num(&bufp, children[i].unused_uids << 1);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen o_stream_nsend(ctx->output, buf, bufp - buf);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen } else {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen i_assert(node_offsets[i] == 0);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* 4b) unused uids + flag */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen squat_pack_num(&bufp, (children[i].unused_uids << 1) | 1);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* 5) leaf string length */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen squat_pack_num(&bufp, children[i].leaf_string_length - 1);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen o_stream_nsend(ctx->output, buf, bufp - buf);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen o_stream_nsend(ctx->output,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen NODE_LEAF_STRING(&children[i]),

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen children[i].leaf_string_length);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen}

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainenstatic inline void

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainennode_add_uid(struct squat_trie_build_context *ctx, uint32_t uid,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen struct squat_node *node)

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen{

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen if (uid < node->next_uid) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* duplicate */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen return;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen node->unused_uids += uid - node->next_uid;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen node->next_uid = uid + 1;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen node->uid_list_idx =

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen squat_uidlist_build_add_uid(ctx->uidlist_build_ctx,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen node->uid_list_idx, uid);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen}

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainenstatic void

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainennode_split_string(struct squat_trie_build_context *ctx, struct squat_node *node)

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen{

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen struct squat_node *child;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen unsigned char *str;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen unsigned int uid, idx, leafstr_len = node->leaf_string_length;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen i_assert(leafstr_len > 0);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* make a copy of the leaf string and convert to normal node by

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen str = t_malloc_no0(leafstr_len);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen if (!NODE_IS_DYNAMIC_LEAF(node))

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen memcpy(str, node->children.static_leaf_string, leafstr_len);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen else {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen memcpy(str, node->children.leaf_string, leafstr_len);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen i_free(node->children.leaf_string);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen node->leaf_string_length = 0;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* create a new child node for the rest of the string */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen idx = node_add_child(ctx->trie, node, str[0], MAX_FAST_LEVEL);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child = NODE_CHILDREN_NODES(node) + idx;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* update uidlist to contain all of parent's UIDs */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child->next_uid = node->next_uid - node->unused_uids;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen for (uid = 0; uid < child->next_uid; uid++) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child->uid_list_idx =

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen squat_uidlist_build_add_uid(ctx->uidlist_build_ctx,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child->uid_list_idx, uid);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen i_assert(!child->have_sequential && child->children.data == NULL);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen if (leafstr_len > 1) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* make the child a leaf string */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen leafstr_len--;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child->leaf_string_length = leafstr_len;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen if (!NODE_IS_DYNAMIC_LEAF(child)) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen memcpy(child->children.static_leaf_string,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen str + 1, leafstr_len);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen } else {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child->children.leaf_string = i_malloc(leafstr_len);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen memcpy(child->children.leaf_string,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen str + 1, leafstr_len);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen}

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainenstatic bool

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainennode_leaf_string_add_or_split(struct squat_trie_build_context *ctx,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen struct squat_node *node,

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen const unsigned char *data, unsigned int data_len)

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen{

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen const unsigned char *str = NODE_LEAF_STRING(node);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen const unsigned int leafstr_len = node->leaf_string_length;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen unsigned int i;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen if (data_len != leafstr_len) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen /* different lengths, can't match */

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen T_BEGIN {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen node_split_string(ctx, node);

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen } T_END;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen return FALSE;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen }

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen for (i = 0; i < data_len; i++) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen if (data[i] != str[i]) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* non-match */

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen T_BEGIN {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen node_split_string(ctx, node);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen } T_END;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen return FALSE;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen return TRUE;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen}

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainenstatic int squat_build_add(struct squat_trie_build_context *ctx, uint32_t uid,

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen const unsigned char *data, unsigned int size)

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen{

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen struct squat_trie *trie = ctx->trie;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen struct squat_node *node = &trie->root;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen const unsigned char *end = data + size;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen unsigned char *chars;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen unsigned int idx;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen int level = 0;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen for (;;) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (node->children_not_mapped) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (unlikely(node_read_children(trie, node, level) < 0))

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen return -1;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (node->leaf_string_length != 0) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* the whole string must match or we need to split

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (node_leaf_string_add_or_split(ctx, node, data,

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen end - data)) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen node_add_uid(ctx, uid, node);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen return 0;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen node_add_uid(ctx, uid, node);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (unlikely(uid < node->unused_uids)) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen squat_trie_set_corrupted(trie);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen return -1;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* child node's UIDs are relative to ours. so for example if

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen uid -= node->unused_uids;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (data == end)

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen return 0;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen level++;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (node->have_sequential) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen i_assert(node->child_count >= SEQUENTIAL_COUNT);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (*data < SEQUENTIAL_COUNT) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen idx = *data;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen goto found;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen idx = SEQUENTIAL_COUNT;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen } else {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen idx = 0;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen chars = NODE_CHILDREN_CHARS(node);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen for (; idx < node->child_count; idx++) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (chars[idx] == *data)

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen goto found;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen }

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen break;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen found:

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen data++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node = NODE_CHILDREN_NODES(node) + idx;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* create new children */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(node->leaf_string_length == 0);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen for (;;) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen idx = node_add_child(trie, node, *data,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen size - (end - data) + 1);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node = NODE_CHILDREN_NODES(node) + idx;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen node_add_uid(ctx, uid, node);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen uid = 0;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (++data == end)

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen break;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (!node->have_sequential) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* convert the node into a leaf string */

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen unsigned int len = end - data;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(node->children.data == NULL);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->leaf_string_length = len;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (!NODE_IS_DYNAMIC_LEAF(node)) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen memcpy(node->children.static_leaf_string,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen data, len);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->children.leaf_string = i_malloc(len);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen memcpy(node->children.leaf_string, data, len);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen break;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic int

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_build_word_bytes(struct squat_trie_build_context *ctx, uint32_t uid,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen const unsigned char *data, unsigned int size)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie *trie = ctx->trie;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen unsigned int i;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (trie->hdr.full_len <= trie->hdr.partial_len)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen else {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* the first word is longer than others */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (squat_build_add(ctx, uid, data,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen I_MIN(size, trie->hdr.full_len)) < 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i = 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen for (; i < size; i++) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (squat_build_add(ctx, uid, data + i,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen I_MIN(trie->hdr.partial_len, size-i)) < 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic int

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_build_word(struct squat_trie_build_context *ctx, uint32_t uid,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen const unsigned char *data, const uint8_t *char_lengths,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int size)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie *trie = ctx->trie;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int i, j, bytelen;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (char_lengths == NULL) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* optimization path: all characters are bytes */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return squat_build_word_bytes(ctx, uid, data, size);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (trie->hdr.full_len <= trie->hdr.partial_len)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen else {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* the first word is longer than others */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen bytelen = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen for (j = 0; j < trie->hdr.full_len && bytelen < size; j++)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen bytelen += char_lengths[bytelen];

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(bytelen <= size);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (squat_build_add(ctx, uid, data, bytelen) < 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i = char_lengths[0];

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

41955c400476941fa274f18b106a5922866fd780Timo Sirainen

41955c400476941fa274f18b106a5922866fd780Timo Sirainen for (; i < size; i += char_lengths[i]) {

41955c400476941fa274f18b106a5922866fd780Timo Sirainen bytelen = 0;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen for (j = 0; j < trie->hdr.partial_len && i+bytelen < size; j++)

41955c400476941fa274f18b106a5922866fd780Timo Sirainen bytelen += char_lengths[i + bytelen];

41955c400476941fa274f18b106a5922866fd780Timo Sirainen i_assert(i + bytelen <= size);

41955c400476941fa274f18b106a5922866fd780Timo Sirainen

41955c400476941fa274f18b106a5922866fd780Timo Sirainen if (squat_build_add(ctx, uid, data + i, bytelen) < 0)

41955c400476941fa274f18b106a5922866fd780Timo Sirainen return -1;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen }

41955c400476941fa274f18b106a5922866fd780Timo Sirainen return 0;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen}

41955c400476941fa274f18b106a5922866fd780Timo Sirainen

41955c400476941fa274f18b106a5922866fd780Timo Sirainenstatic unsigned char *

41955c400476941fa274f18b106a5922866fd780Timo Sirainensquat_data_normalize(struct squat_trie *trie, const unsigned char *data,

41955c400476941fa274f18b106a5922866fd780Timo Sirainen unsigned int size)

41955c400476941fa274f18b106a5922866fd780Timo Sirainen{

41955c400476941fa274f18b106a5922866fd780Timo Sirainen static const unsigned char replacement_utf8[] = { 0xef, 0xbf, 0xbd };

41955c400476941fa274f18b106a5922866fd780Timo Sirainen unsigned char *dest;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen unsigned int i;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen

41955c400476941fa274f18b106a5922866fd780Timo Sirainen dest = t_malloc_no0(size);

41955c400476941fa274f18b106a5922866fd780Timo Sirainen for (i = 0; i < size; i++) {

41955c400476941fa274f18b106a5922866fd780Timo Sirainen if (data[i] == replacement_utf8[0] && i + 2 < size &&

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen data[i+1] == replacement_utf8[1] &&

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen data[i+2] == replacement_utf8[2]) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* Don't index replacement character */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen dest[i++] = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen dest[i++] = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen dest[i] = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen dest[i] = trie->hdr.normalize_map[data[i]];

41955c400476941fa274f18b106a5922866fd780Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return dest;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic int

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_trie_build_more_real(struct squat_trie_build_context *ctx,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uint32_t uid, enum squat_index_type type,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen const unsigned char *input, unsigned int size)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie *trie = ctx->trie;

41955c400476941fa274f18b106a5922866fd780Timo Sirainen const unsigned char *data;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uint8_t *char_lengths;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int i, start = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen bool multibyte_chars = FALSE;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen int ret = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uid = uid * 2 + (type == SQUAT_INDEX_TYPE_HEADER ? 1 : 0);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen char_lengths = t_malloc_no0(size);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen data = squat_data_normalize(trie, input, size);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen for (i = 0; i < size; i++) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen char_lengths[i] = uni_utf8_char_bytes(input[i]);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (char_lengths[i] != 1)

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen multibyte_chars = TRUE;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (data[i] != '\0')

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen continue;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen while (start < i && data[start] == '\0')

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen start++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (i != start) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (squat_build_word(ctx, uid, data + start,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen !multibyte_chars ? NULL :

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen char_lengths + start,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i - start) < 0) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ret = -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen start = i;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen break;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen start = i + 1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen while (start < i && data[start] == '\0')

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen start++;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (i != start) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (squat_build_word(ctx, uid, data + start,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen !multibyte_chars ? NULL :

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen char_lengths + start, i - start) < 0)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen ret = -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return ret;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenint squat_trie_build_more(struct squat_trie_build_context *ctx,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen uint32_t uid, enum squat_index_type type,

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen const unsigned char *input, unsigned int size)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen int ret = 0;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (size != 0) T_BEGIN {

5b486fdbf2077a994337dc8bd4477ec51d5daf4eTimo Sirainen ret = squat_trie_build_more_real(ctx, uid, type, input, size);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen } T_END;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen return ret;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic void

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainennode_drop_unused_children(struct squat_trie *trie, struct squat_node *node)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen{

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen unsigned char *chars;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen struct squat_node *children_src, *children_dest;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen unsigned int i, j, orig_child_count = node->child_count;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen chars = NODE_CHILDREN_CHARS(node);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen children_src = NODE_CHILDREN_NODES(node);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* move chars */

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen for (i = j = 0; i < orig_child_count; i++) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (children_src[i].next_uid != 0)

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen chars[j++] = chars[i];

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->child_count = j;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* move children. note that children_dest may point to different

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen children_dest = NODE_CHILDREN_NODES(node);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen for (i = j = 0; i < orig_child_count; i++) {

3c097377e865689723c8737537886b01a5ebd3d9Timo Sirainen if (children_src[i].next_uid != 0)

3c097377e865689723c8737537886b01a5ebd3d9Timo Sirainen children_dest[j++] = children_src[i];

3c097377e865689723c8737537886b01a5ebd3d9Timo Sirainen else

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node_free(trie, &children_src[i]);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainenstatic int

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainensquat_write_node(struct squat_trie_build_context *ctx, struct squat_node *node,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uoff_t *node_offset_r, int level)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie *trie = ctx->trie;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_node *children;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int i;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uoff_t *node_offsets;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen uint8_t child_count;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen int ret;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_assert(node->next_uid != 0);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (node->children_not_mapped && ctx->compress_nodes) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (node_read_children(trie, node, MAX_FAST_LEVEL) < 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen }

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen node->have_sequential = FALSE;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen node_drop_unused_children(trie, node);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen child_count = node->child_count;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen if (child_count == 0) {

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen i_assert(!node->children_not_mapped ||

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->leaf_string_length == 0);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen *node_offset_r = !node->children_not_mapped ? 0 :

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->children.offset;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(!node->children_not_mapped);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->hdr.node_count++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen children = NODE_CHILDREN_NODES(node);

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen node_offsets = t_new(uoff_t, child_count);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen for (i = 0; i < child_count; i++) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen T_BEGIN {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ret = squat_write_node(ctx, &children[i],

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen &node_offsets[i], level + 1);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } T_END;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (ret < 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen *node_offset_r = ctx->output->offset;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node_write_children(ctx, node, node_offsets);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic int squat_write_nodes(struct squat_trie_build_context *ctx)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie *trie = ctx->trie;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uoff_t node_offset;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen int ret;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (ctx->trie->root.next_uid == 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen T_BEGIN {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ret = squat_write_node(ctx, &ctx->trie->root, &node_offset, 0);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } T_END;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (ret < 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return -1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->hdr.root_offset = node_offset;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->hdr.root_unused_uids = trie->root.unused_uids;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->hdr.root_next_uid = trie->root.next_uid;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen trie->hdr.root_uidlist_idx = trie->root.uid_list_idx;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic struct squat_trie_iterate_context *

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_trie_iterate_init(struct squat_trie *trie)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie_iterate_context *ctx;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ctx = i_new(struct squat_trie_iterate_context, 1);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ctx->trie = trie;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ctx->cur.node = &trie->root;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_array_init(&ctx->parents, trie->hdr.partial_len*2);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return ctx;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic int

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_trie_iterate_deinit(struct squat_trie_iterate_context *ctx)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie_iterate_node *node;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen int ret = ctx->failed ? -1 : 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (array_is_created(&ctx->cur.shifts)) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen array_foreach_modifiable(&ctx->parents, node)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen array_free(&node->shifts);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen array_free(&ctx->cur.shifts);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen array_free(&ctx->parents);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_free(ctx);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return ret;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic struct squat_node *

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_trie_iterate_first(struct squat_trie_iterate_context *ctx)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (ctx->cur.node->children_not_mapped) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (node_read_children(ctx->trie, ctx->cur.node, 1) < 0) {

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen ctx->failed = TRUE;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return NULL;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return ctx->cur.node;

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen}

3b49aee9ced3b0370a3be396aca53acd5f21418cTimo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic struct squat_node *

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_trie_iterate_next(struct squat_trie_iterate_context *ctx,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ARRAY_TYPE(seq_range) *shifts_r)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

2b9fd042e701cfe7d79c4294a5ab401d6ec9ce18Timo Sirainen struct squat_trie_iterate_node *iter_nodes;

2b9fd042e701cfe7d79c4294a5ab401d6ec9ce18Timo Sirainen struct squat_node *children;

2b9fd042e701cfe7d79c4294a5ab401d6ec9ce18Timo Sirainen unsigned int count, shift_count = 0;

2b9fd042e701cfe7d79c4294a5ab401d6ec9ce18Timo Sirainen

2b9fd042e701cfe7d79c4294a5ab401d6ec9ce18Timo Sirainen while (ctx->cur.idx == ctx->cur.node->child_count ||

2b9fd042e701cfe7d79c4294a5ab401d6ec9ce18Timo Sirainen ctx->cur.node->uid_list_idx == 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen iter_nodes = array_get_modifiable(&ctx->parents, &count);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (count == 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return NULL;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (array_is_created(&ctx->cur.shifts))

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen array_free(&ctx->cur.shifts);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ctx->cur = iter_nodes[count-1];

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen array_delete(&ctx->parents, count-1, 1);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen *shifts_r = ctx->cur.shifts;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (array_is_created(&ctx->cur.shifts))

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift_count = array_count(&ctx->cur.shifts);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen children = NODE_CHILDREN_NODES(ctx->cur.node);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen while (children[ctx->cur.idx++].uid_list_idx == 0) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (ctx->cur.idx == ctx->cur.node->child_count) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* no more non-empty children in this node */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return squat_trie_iterate_next(ctx, shifts_r);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen array_append(&ctx->parents, &ctx->cur, 1);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ctx->cur.node = &children[ctx->cur.idx-1];

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ctx->cur.idx = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (shift_count != 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_array_init(&ctx->cur.shifts, shift_count);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen else

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen memset(&ctx->cur.shifts, 0, sizeof(ctx->cur.shifts));

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return squat_trie_iterate_first(ctx);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen}

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainenstatic void

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainensquat_uidlist_update_expunged_uids(const ARRAY_TYPE(seq_range) *shifts_arr,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ARRAY_TYPE(seq_range) *child_shifts,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen ARRAY_TYPE(seq_range) *uids_arr,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_trie *trie,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct squat_node *node, bool do_shifts)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen{

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen const struct seq_range *shifts;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen struct seq_range *uids, shift;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int i, uid_idx, uid_count, shift_count;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uint32_t child_shift_seq1, child_shift_count, seq_high;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen unsigned int shift_sum = 0, child_sum = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (!array_is_created(shifts_arr)) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(node->uid_list_idx != 0 || node->child_count == 0);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen return;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* we'll recalculate this */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->unused_uids = 0;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids = array_get_modifiable(uids_arr, &uid_count);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shifts = array_get(shifts_arr, &shift_count);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen for (i = 0, uid_idx = 0, seq_high = 0;; ) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* skip UID ranges until we skip/overlap shifts */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen while (uid_idx < uid_count &&

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen (i == shift_count ||

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen I_MAX(shifts[i].seq1, seq_high) > uids[uid_idx].seq2))

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(uids[uid_idx].seq1 >= shift_sum);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids[uid_idx].seq1 -= shift_sum;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids[uid_idx].seq2 -= shift_sum;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_sum += uids[uid_idx].seq2 -

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids[uid_idx].seq1 + 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (uid_idx > 0 &&

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids[uid_idx-1].seq2 >= uids[uid_idx].seq1 - 1) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* we can merge this and the previous range */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i_assert(uids[uid_idx-1].seq2 ==

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids[uid_idx].seq1 - 1);

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen uids[uid_idx-1].seq2 = uids[uid_idx].seq2;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen array_delete(uids_arr, uid_idx, 1);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids = array_get_modifiable(uids_arr,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen &uid_count);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (uid_idx == 0)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen node->unused_uids += uids[0].seq1;

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen else {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen node->unused_uids +=

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uids[uid_idx].seq1 -

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen uids[uid_idx-1].seq2 - 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen uid_idx++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (uid_idx == uid_count)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen break;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift.seq1 = I_MAX(shifts[i].seq1, seq_high);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift.seq2 = shifts[i].seq2;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (shift.seq2 < uids[uid_idx].seq1) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* shift is entirely before UID range */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift_sum += shift.seq2 - shift.seq1 + 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen } else {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* handle shifts before UID range */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (shift.seq1 < uids[uid_idx].seq1) {

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift_sum += uids[uid_idx].seq1 - shift.seq1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift.seq1 = uids[uid_idx].seq1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen }

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* update child shifts */

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_shift_seq1 = child_sum +

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift.seq1 - uids[uid_idx].seq1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_shift_count =

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen I_MIN(shift.seq2, uids[uid_idx].seq2) -

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen shift.seq1 + 1;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen seq_range_array_add_range(child_shifts,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_shift_seq1,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_shift_seq1 +

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_shift_count - 1);

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen child_sum += child_shift_count;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen /* if the shifts continue after the UID range,

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen if (shift.seq2 <= uids[uid_idx].seq2)

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen i++;

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen else

dee43975a70bcdb9dc83d34d6a2b177d37bb7194Timo Sirainen seq_high = uids[uid_idx].seq2 + 1;

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen

4ece61edd7c266a4b8f3b290a7f0a3cb3d13ca0fTimo Sirainen /* update UIDs - no matter where within the UID range

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen if (uids[uid_idx].seq1 +

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen child_shift_count > uids[uid_idx].seq2) {

905457e0982fc15930d90e174f271dc69f9afcf9Timo Sirainen /* removed completely */