Lines Matching defs:trie
14 #include "squat-trie-private.h"
34 struct squat_trie *trie;
52 struct squat_trie *trie;
58 static int squat_trie_map(struct squat_trie *trie, bool building);
60 void squat_trie_delete(struct squat_trie *trie)
62 i_unlink_if_exists(trie->path);
63 squat_uidlist_delete(trie->uidlist);
66 static void squat_trie_set_corrupted(struct squat_trie *trie)
68 trie->corrupted = TRUE;
69 i_error("Corrupted file %s", trie->path);
70 squat_trie_delete(trie);
73 static void squat_trie_normalize_map_build(struct squat_trie *trie)
79 memset(trie->default_normalize_map, 0,
80 sizeof(trie->default_normalize_map));
87 trie->default_normalize_map[chr-'A'+'a'] = j;
88 trie->default_normalize_map[chr] = j++;
93 trie->default_normalize_map[i] = j++;
99 trie->default_normalize_map[chr-'A'+'a'] = chr;
100 trie->default_normalize_map[chr] = chr;
103 trie->default_normalize_map[i] = i_toupper(i);
107 static void node_free(struct squat_trie *trie, struct squat_node *node)
118 trie->node_alloc_size -=
121 node_free(trie, &children[i]);
132 struct squat_trie *trie;
134 trie = i_new(struct squat_trie, 1);
135 trie->path = i_strdup(path);
136 trie->uidlist = squat_uidlist_init(trie);
137 trie->fd = -1;
138 trie->lock_method = lock_method;
139 trie->uidvalidity = uidvalidity;
140 trie->flags = flags;
141 trie->create_mode = mode;
142 trie->create_gid = gid;
143 squat_trie_normalize_map_build(trie);
145 trie->dotlock_set.use_excl_lock =
147 trie->dotlock_set.nfs_flush = (flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0;
148 trie->dotlock_set.timeout = SQUAT_TRIE_LOCK_TIMEOUT;
149 trie->dotlock_set.stale_timeout = SQUAT_TRIE_DOTLOCK_STALE_TIMEOUT;
150 trie->default_partial_len = DEFAULT_PARTIAL_LEN;
151 trie->default_full_len = DEFAULT_FULL_LEN;
152 return trie;
155 static void squat_trie_close_fd(struct squat_trie *trie)
157 trie->data = NULL;
158 trie->data_size = 0;
160 if (trie->mmap_size != 0) {
161 if (munmap(trie->mmap_base, trie->mmap_size) < 0)
162 i_error("munmap(%s) failed: %m", trie->path);
163 trie->mmap_base = NULL;
164 trie->mmap_size = 0;
166 i_close_fd_path(&trie->fd, trie->path);
169 static void squat_trie_close(struct squat_trie *trie)
171 trie->corrupted = FALSE;
172 node_free(trie, &trie->root);
173 i_zero(&trie->root);
174 i_zero(&trie->hdr);
176 squat_trie_close_fd(trie);
177 if (trie->file_cache != NULL)
178 file_cache_free(&trie->file_cache);
179 trie->locked_file_size = 0;
184 struct squat_trie *trie = *_trie;
187 squat_trie_close(trie);
188 squat_uidlist_deinit(trie->uidlist);
189 i_free(trie->path);
190 i_free(trie);
193 void squat_trie_set_partial_len(struct squat_trie *trie, unsigned int len)
195 trie->default_partial_len = len;
198 void squat_trie_set_full_len(struct squat_trie *trie, unsigned int len)
200 trie->default_full_len = len;
203 static void squat_trie_header_init(struct squat_trie *trie)
205 i_zero(&trie->hdr);
206 trie->hdr.version = SQUAT_TRIE_VERSION;
207 trie->hdr.indexid = time(NULL);
208 trie->hdr.uidvalidity = trie->uidvalidity;
209 trie->hdr.partial_len = trie->default_partial_len;
210 trie->hdr.full_len = trie->default_full_len;
212 i_assert(sizeof(trie->hdr.normalize_map) ==
213 sizeof(trie->default_normalize_map));
214 memcpy(trie->hdr.normalize_map, trie->default_normalize_map,
215 sizeof(trie->hdr.normalize_map));
218 static int squat_trie_open_fd(struct squat_trie *trie)
220 trie->fd = open(trie->path, O_RDWR);
221 if (trie->fd == -1) {
223 squat_trie_header_init(trie);
226 i_error("open(%s) failed: %m", trie->path);
229 if (trie->file_cache != NULL)
230 file_cache_set_fd(trie->file_cache, trie->fd);
234 int squat_trie_open(struct squat_trie *trie)
236 squat_trie_close(trie);
238 if (squat_trie_open_fd(trie) < 0)
240 return squat_trie_map(trie, FALSE);
243 static int squat_trie_is_file_stale(struct squat_trie *trie)
247 if ((trie->flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0)
248 nfs_flush_file_handle_cache(trie->path);
249 if (nfs_safe_stat(trie->path, &st) < 0) {
253 i_error("stat(%s) failed: %m", trie->path);
256 if (fstat(trie->fd, &st2) < 0) {
259 i_error("fstat(%s) failed: %m", trie->path);
262 trie->locked_file_size = st2.st_size;
265 i_assert(trie->locked_file_size >= trie->data_size);
271 int squat_trie_refresh(struct squat_trie *trie)
275 ret = squat_trie_is_file_stale(trie);
277 ret = squat_trie_open(trie);
281 static int squat_trie_lock(struct squat_trie *trie, int lock_type,
287 i_assert(trie->fd != -1);
293 if (trie->lock_method != FILE_LOCK_METHOD_DOTLOCK) {
294 ret = file_wait_lock(trie->fd, trie->path, lock_type,
295 trie->lock_method,
299 ret = file_dotlock_create(&trie->dotlock_set,
300 trie->path, 0, dotlock_r);
303 i_error("squat trie %s: Locking timed out", trie->path);
309 /* if the trie has been compressed, we need to reopen the
311 ret = squat_trie_is_file_stale(trie);
322 squat_trie_close(trie);
323 if (squat_trie_open_fd(trie) < 0)
325 if (trie->fd == -1)
329 if ((trie->flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0)
330 nfs_flush_read_cache_locked(trie->path, trie->fd);
335 node_make_sequential(struct squat_trie *trie, struct squat_node *node, int level)
345 trie->node_alloc_size += alloc_size;
365 node_add_child(struct squat_trie *trie, struct squat_node *node,
376 node_make_sequential(trie, node, level);
389 trie->node_alloc_size += new_size;
393 trie->node_alloc_size += new_size - old_size;
414 trie_file_cache_read(struct squat_trie *trie, size_t offset, size_t size)
416 if (trie->file_cache == NULL)
419 if (file_cache_read(trie->file_cache, offset, size) < 0) {
420 i_error("read(%s) failed: %m", trie->path);
423 trie->data = file_cache_get_map(trie->file_cache, &trie->data_size);
428 node_read_children(struct squat_trie *trie, struct squat_node *node, int level)
440 i_assert(trie->unmapped_child_count > 0);
441 i_assert(trie->data_size <= trie->locked_file_size);
443 trie->unmapped_child_count--;
448 if (trie_file_cache_read(trie, node_offset, TRIE_READAHEAD_SIZE) < 0)
450 if (unlikely(node_offset >= trie->data_size)) {
451 squat_trie_set_corrupted(trie);
455 data = CONST_PTR_OFFSET(trie->data, node_offset);
456 end = CONST_PTR_OFFSET(trie->data, trie->data_size);
458 if (unlikely(node_offset + child_count >= trie->data_size)) {
459 squat_trie_set_corrupted(trie);
477 child_idx = node_add_child(trie, node, child_chars[i],
496 if (base_offset >= trie->locked_file_size) {
497 squat_trie_set_corrupted(trie);
500 trie->unmapped_child_count++;
509 squat_trie_set_corrupted(trie);
540 if (trie->file_cache != NULL) {
546 (const char *)trie->data;
549 if (trie_file_cache_read(trie, offset,
552 data = CONST_PTR_OFFSET(trie->data, offset);
553 end = CONST_PTR_OFFSET(trie->data,
554 trie->data_size);
555 child_chars = CONST_PTR_OFFSET(trie->data,
560 squat_trie_set_corrupted(trie);
569 squat_trie_set_corrupted(trie);
670 idx = node_add_child(ctx->trie, node, str[0], MAX_FAST_LEVEL);
729 struct squat_trie *trie = ctx->trie;
730 struct squat_node *node = &trie->root;
738 if (unlikely(node_read_children(trie, node, level) < 0))
755 squat_trie_set_corrupted(trie);
793 idx = node_add_child(trie, node, *data,
826 struct squat_trie *trie = ctx->trie;
829 if (trie->hdr.full_len <= trie->hdr.partial_len)
834 I_MIN(size, trie->hdr.full_len)) < 0)
841 I_MIN(trie->hdr.partial_len, size-i)) < 0)
852 struct squat_trie *trie = ctx->trie;
860 if (trie->hdr.full_len <= trie->hdr.partial_len)
865 for (j = 0; j < trie->hdr.full_len && bytelen < size; j++)
876 for (j = 0; j < trie->hdr.partial_len && i+bytelen < size; j++)
887 squat_data_normalize(struct squat_trie *trie, const unsigned char *data,
904 dest[i] = trie->hdr.normalize_map[data[i]];
915 struct squat_trie *trie = ctx->trie;
925 data = squat_data_normalize(trie, input, size);
971 node_drop_unused_children(struct squat_trie *trie, struct squat_node *node)
995 node_free(trie, &children_src[i]);
1003 struct squat_trie *trie = ctx->trie;
1013 if (node_read_children(trie, node, MAX_FAST_LEVEL) < 0)
1018 node_drop_unused_children(trie, node);
1030 trie->hdr.node_count++;
1050 struct squat_trie *trie = ctx->trie;
1054 if (ctx->trie->root.next_uid == 0)
1058 ret = squat_write_node(ctx, &ctx->trie->root, &node_offset, 0);
1063 trie->hdr.root_offset = node_offset;
1064 trie->hdr.root_unused_uids = trie->root.unused_uids;
1065 trie->hdr.root_next_uid = trie->root.next_uid;
1066 trie->hdr.root_uidlist_idx = trie->root.uid_list_idx;
1071 squat_trie_iterate_init(struct squat_trie *trie)
1076 ctx->trie = trie;
1077 ctx->cur.node = &trie->root;
1078 i_array_init(&ctx->parents, trie->hdr.partial_len*2);
1102 if (node_read_children(ctx->trie, ctx->cur.node, 1) < 0) {
1156 struct squat_trie *trie,
1279 node_free(trie, node);
1320 if (squat_uidlist_get_seqrange(ctx->trie->uidlist,
1327 &uid_range, ctx->trie, node,
1361 if (squat_uidlist_get(ctx->trie->uidlist,
1390 ctx->trie->hdr.indexid =
1391 I_MAX((unsigned int)now, ctx->trie->hdr.indexid + 1);
1393 iter = squat_trie_iterate_init(ctx->trie);
1403 /* lock the trie before we rename uidlist */
1405 if (squat_trie_lock(ctx->trie, F_WRLCK,
1411 static bool squat_trie_check_header(struct squat_trie *trie)
1413 if (trie->hdr.version != SQUAT_TRIE_VERSION ||
1414 trie->hdr.uidvalidity != trie->uidvalidity)
1417 if (trie->hdr.partial_len > trie->hdr.full_len) {
1418 i_error("Corrupted %s: partial len > full len", trie->path);
1421 if (trie->hdr.full_len == 0) {
1422 i_error("Corrupted %s: full len=0", trie->path);
1428 static int squat_trie_map_header(struct squat_trie *trie)
1432 if (trie->locked_file_size == 0) {
1434 squat_trie_header_init(trie);
1437 i_assert(trie->fd != -1);
1439 if ((trie->flags & SQUAT_INDEX_FLAG_MMAP_DISABLE) != 0) {
1440 ret = pread_full(trie->fd, &trie->hdr, sizeof(trie->hdr), 0);
1443 i_error("pread(%s) failed: %m", trie->path);
1446 i_error("Corrupted %s: File too small", trie->path);
1449 trie->data = NULL;
1450 trie->data_size = 0;
1452 if (trie->locked_file_size < sizeof(trie->hdr)) {
1453 i_error("Corrupted %s: File too small", trie->path);
1456 if (trie->mmap_size != 0) {
1457 if (munmap(trie->mmap_base, trie->mmap_size) < 0)
1458 i_error("munmap(%s) failed: %m", trie->path);
1461 trie->mmap_size = trie->locked_file_size;
1462 trie->mmap_base = mmap(NULL, trie->mmap_size,
1464 MAP_SHARED, trie->fd, 0);
1465 if (trie->mmap_base == MAP_FAILED) {
1466 trie->data = trie->mmap_base = NULL;
1467 trie->data_size = trie->mmap_size = 0;
1468 i_error("mmap(%s) failed: %m", trie->path);
1471 memcpy(&trie->hdr, trie->mmap_base, sizeof(trie->hdr));
1472 trie->data = trie->mmap_base;
1473 trie->data_size = trie->mmap_size;
1476 return squat_trie_check_header(trie) ? 1 : 0;
1479 static int squat_trie_map(struct squat_trie *trie, bool building)
1486 if (trie->fd != -1) {
1487 if (squat_trie_lock(trie, F_RDLCK, &file_lock, &dotlock) <= 0)
1489 if ((trie->flags & SQUAT_INDEX_FLAG_MMAP_DISABLE) != 0 &&
1490 trie->file_cache == NULL)
1491 trie->file_cache = file_cache_new_path(trie->fd, trie->path);
1494 ret = squat_trie_map_header(trie);
1500 squat_trie_delete(trie);
1501 squat_trie_close(trie);
1502 squat_trie_header_init(trie);
1504 changed = trie->root.children.offset != trie->hdr.root_offset;
1506 if (changed || trie->hdr.root_offset == 0) {
1507 node_free(trie, &trie->root);
1508 i_zero(&trie->root);
1509 trie->root.want_sequential = TRUE;
1510 trie->root.unused_uids = trie->hdr.root_unused_uids;
1511 trie->root.next_uid = trie->hdr.root_next_uid;
1512 trie->root.uid_list_idx = trie->hdr.root_uidlist_idx;
1513 trie->root.children.offset = trie->hdr.root_offset;
1515 if (trie->hdr.root_offset == 0) {
1516 trie->unmapped_child_count = 0;
1517 trie->root.children_not_mapped = FALSE;
1519 trie->unmapped_child_count = 1;
1520 trie->root.children_not_mapped = TRUE;
1526 ret = squat_uidlist_refresh(trie->uidlist);
1536 return trie->hdr.root_offset == 0 || !changed ? 0 :
1537 node_read_children(trie, &trie->root, 1);
1540 int squat_trie_create_fd(struct squat_trie *trie, const char *path, int flags)
1546 fd = open(path, O_RDWR | O_CREAT | flags, trie->create_mode);
1552 if (trie->create_gid != (gid_t)-1) {
1553 if (fchown(fd, (uid_t)-1, trie->create_gid) < 0) {
1555 path, (long)trie->create_gid);
1563 int squat_trie_build_init(struct squat_trie *trie,
1569 if (trie->fd == -1) {
1570 trie->fd = squat_trie_create_fd(trie, trie->path, 0);
1571 if (trie->fd == -1)
1574 if (trie->file_cache != NULL)
1575 file_cache_set_fd(trie->file_cache, trie->fd);
1576 i_assert(trie->locked_file_size == 0);
1580 if (squat_uidlist_build_init(trie->uidlist, &uidlist_build_ctx) < 0)
1583 if (squat_trie_map(trie, TRUE) < 0) {
1589 ctx->trie = trie;
1591 ctx->first_uid = trie->root.next_uid;
1602 if (squat_trie_lock(ctx->trie, F_WRLCK,
1610 struct squat_trie *trie = ctx->trie;
1616 if ((trie->hdr.used_file_size > sizeof(trie->hdr) &&
1617 trie->unmapped_child_count < trie->hdr.node_count/4) || 1) {
1621 path = t_strconcat(trie->path, ".tmp", NULL);
1622 fd = squat_trie_create_fd(trie, path, O_TRUNC);
1626 if (trie->lock_method != FILE_LOCK_METHOD_DOTLOCK) {
1628 trie->lock_method,
1643 o_stream_nsend(output, &trie->hdr, sizeof(trie->hdr));
1646 path = trie->path;
1648 trie->hdr.used_file_size == sizeof(trie->hdr);
1650 if (trie->hdr.used_file_size == 0) {
1655 output = o_stream_create_fd(trie->fd, 0);
1658 if (trie->hdr.used_file_size != 0)
1659 (void)o_stream_seek(output, trie->hdr.used_file_size);
1661 o_stream_nsend(output, &trie->hdr, sizeof(trie->hdr));
1672 if (trie->corrupted)
1677 trie->hdr.used_file_size = output->offset;
1679 o_stream_nsend(output, &trie->hdr, sizeof(trie->hdr));
1694 /* recreating the trie file */
1699 } else if (rename(path, trie->path) < 0) {
1700 i_error("rename(%s, %s) failed: %m", path, trie->path);
1708 squat_trie_close_fd(trie);
1709 trie->fd = fd;
1710 trie->locked_file_size = trie->hdr.used_file_size;
1711 if (trie->file_cache != NULL)
1712 file_cache_set_fd(trie->file_cache, trie->fd);
1729 compress = (ctx->trie->root.next_uid - ctx->first_uid) > 10;
1731 /* keep trie locked while header is being written and when files are
1732 being renamed, so that while trie is read locked, uidlist can't
1758 int squat_trie_get_last_uid(struct squat_trie *trie, uint32_t *last_uid_r)
1760 if (trie->fd == -1) {
1761 if (squat_trie_open(trie) < 0)
1765 *last_uid_r = I_MAX((trie->root.next_uid+1)/2, 1) - 1;
1770 squat_trie_lookup_data(struct squat_trie *trie, const unsigned char *data,
1773 struct squat_node *node = &trie->root;
1782 if (node_read_children(trie, node, level) < 0)
1824 if (squat_uidlist_get_seqrange(trie->uidlist,
1829 if (squat_uidlist_filter(trie->uidlist,
1838 if (squat_uidlist_filter(trie->uidlist, node->uid_list_idx, uids) < 0)
1888 struct squat_trie *trie;
1901 const unsigned int partial_len = ctx->trie->hdr.partial_len;
1915 ret = squat_trie_lookup_data(ctx->trie, data + i, bytelen,
1938 static void squat_trie_add_unknown(struct squat_trie *trie,
1945 last_uid = I_MAX((trie->root.next_uid+1)/2, 1) - 1;
1959 squat_trie_lookup_real(struct squat_trie *trie, const char *str,
1975 ctx.trie = trie;
1990 data = squat_data_normalize(trie, (const unsigned char *)str,
2009 if (str_charlen <= trie->hdr.partial_len ||
2010 trie->hdr.full_len > trie->hdr.partial_len) {
2011 ret = squat_trie_lookup_data(trie, data, str_bytelen,
2021 if (str_charlen <= trie->hdr.partial_len ||
2022 trie->hdr.partial_len == 0) {
2040 ret = squat_uidlist_get_seqrange(trie->uidlist,
2041 trie->root.uid_list_idx,
2050 ret = squat_uidlist_get_seqrange(trie->uidlist,
2051 trie->root.uid_list_idx,
2060 squat_trie_add_unknown(trie, maybe_uids);
2066 int squat_trie_lookup(struct squat_trie *trie, const char *str,
2074 ret = squat_trie_lookup_real(trie, str, type,
2080 struct squat_uidlist *squat_trie_get_uidlist(struct squat_trie *trie)
2082 return trie->uidlist;
2085 size_t squat_trie_mem_used(struct squat_trie *trie, unsigned int *count_r)
2087 *count_r = trie->hdr.node_count;
2088 return trie->node_alloc_size;