46 	struct squat_node *node;
107 static void node_free(struct squat_trie *trie, struct squat_node *node)
112 	if (node->leaf_string_length > 0) {
113 		if (NODE_IS_DYNAMIC_LEAF(node))
114 			i_free(node->children.leaf_string);
115 	} else if (!node->children_not_mapped) {
116 		children = NODE_CHILDREN_NODES(node);
119 			NODE_CHILDREN_ALLOC_SIZE(node->child_count);
120 		for (i = 0; i < node->child_count; i++)
123 		i_free(node->children.data);
335 node_make_sequential(struct squat_trie *trie, struct squat_node *node, int level)
343 	i_assert(node->child_count == 0);
347 	node->want_sequential = FALSE;
348 	node->have_sequential = TRUE;
350 	node->child_count = SEQUENTIAL_COUNT;
351 	node->children.data = i_malloc(alloc_size);
353 	chars = NODE_CHILDREN_CHARS(node);
358 		children = NODE_CHILDREN_NODES(node);
365 node_add_child(struct squat_trie *trie, struct squat_node *node,
368 	unsigned int old_child_count = node->child_count;
373 	i_assert(node->leaf_string_length == 0);
375 	if (node->want_sequential) {
376 		node_make_sequential(trie, node, level);
383 	node->child_count++;
384 	new_size = NODE_CHILDREN_ALLOC_SIZE(node->child_count);
388 		node->children.data = i_malloc(new_size);
394 			node->children.data = i_realloc(node->children.data,
398 		children = NODE_CHILDREN_NODES(node);
399 		old_children = (void *)(NODE_CHILDREN_CHARS(node) +
407 	chars = NODE_CHILDREN_CHARS(node);
409 	chars[node->child_count - 1] = chr;
410 	return node->child_count - 1;
428 node_read_children(struct squat_trie *trie, struct squat_node *node, int level)
438 	i_assert(node->children_not_mapped);
439 	i_assert(!node->have_sequential);
444 	node_offset = node->children.offset;
445 	node->children_not_mapped = FALSE;
446 	node->children.data = NULL;
474 		if (node->have_sequential && child_chars[i] < SEQUENTIAL_COUNT)
477 			child_idx = node_add_child(trie, node, child_chars[i],
479 			children = NODE_CHILDREN_NODES(node);
577 		    struct squat_node *node, const uoff_t *node_offsets)
585 	chars = NODE_CHILDREN_CHARS(node);
586 	children = NODE_CHILDREN_NODES(node);
589 	child_count = node->child_count;
635 	     struct squat_node *node)
637 	if (uid < node->next_uid) {
641 	node->unused_uids += uid - node->next_uid;
642 	node->next_uid = uid + 1;
644 	node->uid_list_idx =
646 					    node->uid_list_idx, uid);
650 node_split_string(struct squat_trie_build_context *ctx, struct squat_node *node)
654 	unsigned int uid, idx, leafstr_len = node->leaf_string_length;
658 	/* make a copy of the leaf string and convert to normal node by
661 	if (!NODE_IS_DYNAMIC_LEAF(node))
662 		memcpy(str, node->children.static_leaf_string, leafstr_len);
664 		memcpy(str, node->children.leaf_string, leafstr_len);
665 		i_free(node->children.leaf_string);
667 	node->leaf_string_length = 0;
669 	/* create a new child node for the rest of the string */
670 	idx = node_add_child(ctx->trie, node, str[0], MAX_FAST_LEVEL);
671 	child = NODE_CHILDREN_NODES(node) + idx;
674 	child->next_uid =  node->next_uid - node->unused_uids;
699 			      struct squat_node *node,
702 	const unsigned char *str = NODE_LEAF_STRING(node);
703 	const unsigned int leafstr_len = node->leaf_string_length;
709 			node_split_string(ctx, node);
718 				node_split_string(ctx, node);
730 	struct squat_node *node = &trie->root;
737 		if (node->children_not_mapped) {
738 			if (unlikely(node_read_children(trie, node, level) < 0))
742 		if (node->leaf_string_length != 0) {
744 			   the node */
745 			if (node_leaf_string_add_or_split(ctx, node, data,
747 				node_add_uid(ctx, uid, node);
752 		node_add_uid(ctx, uid, node);
754 		if (unlikely(uid < node->unused_uids)) {
758 		/* child node's UIDs are relative to ours. so for example if
759 		   we're adding UID 4 and this node now has [2,4] UIDs,
760 		   unused_uids=3 and so the child node will be adding
762 		uid -= node->unused_uids;
768 		if (node->have_sequential) {
769 			i_assert(node->child_count >= SEQUENTIAL_COUNT);
778 		chars = NODE_CHILDREN_CHARS(node);
779 		for (; idx < node->child_count; idx++) {
786 		node = NODE_CHILDREN_NODES(node) + idx;
790 	i_assert(node->leaf_string_length == 0);
793 		idx = node_add_child(trie, node, *data,
795 		node = NODE_CHILDREN_NODES(node) + idx;
797 		node_add_uid(ctx, uid, node);
803 		if (!node->have_sequential) {
804 			/* convert the node into a leaf string */
807 			i_assert(node->children.data == NULL);
808 			node->leaf_string_length = len;
809 			if (!NODE_IS_DYNAMIC_LEAF(node)) {
810 				memcpy(node->children.static_leaf_string,
813 				node->children.leaf_string = i_malloc(len);
814 				memcpy(node->children.leaf_string, data, len);
971 node_drop_unused_children(struct squat_trie *trie, struct squat_node *node)
975 	unsigned int i, j, orig_child_count = node->child_count;
977 	chars = NODE_CHILDREN_CHARS(node);
978 	children_src = NODE_CHILDREN_NODES(node);
985 	node->child_count = j;
989 	   same node. */
990 	children_dest = NODE_CHILDREN_NODES(node);
1000 squat_write_node(struct squat_trie_build_context *ctx, struct squat_node *node,
1010 	i_assert(node->next_uid != 0);
1012 	if (node->children_not_mapped && ctx->compress_nodes) {
1013 		if (node_read_children(trie, node, MAX_FAST_LEVEL) < 0)
1017 	node->have_sequential = FALSE;
1018 	node_drop_unused_children(trie, node);
1020 	child_count = node->child_count;
1022 		i_assert(!node->children_not_mapped ||
1023 			 node->leaf_string_length == 0);
1024 		*node_offset_r = !node->children_not_mapped ? 0 :
1025 			node->children.offset;
1028 	i_assert(!node->children_not_mapped);
1032 	children = NODE_CHILDREN_NODES(node);
1044 	node_write_children(ctx, node, node_offsets);
1077 	ctx->cur.node = &trie->root;
1085 	struct squat_trie_iterate_node *node;
1089 		array_foreach_modifiable(&ctx->parents, node)
1090 			array_free(&node->shifts);
1101 	if (ctx->cur.node->children_not_mapped) {
1102 		if (node_read_children(ctx->trie, ctx->cur.node, 1) < 0) {
1107 	return ctx->cur.node;
1118 	while (ctx->cur.idx == ctx->cur.node->child_count ||
1119 	       ctx->cur.node->uid_list_idx == 0)
1135 	children = NODE_CHILDREN_NODES(ctx->cur.node);
1137 		if (ctx->cur.idx == ctx->cur.node->child_count) {
1138 			/* no more non-empty children in this node */
1143 	ctx->cur.node = &children[ctx->cur.idx-1];
1157 				   struct squat_node *node, bool do_shifts)
1166 		i_assert(node->uid_list_idx != 0 || node->child_count == 0);
1171 	node->unused_uids = 0;
1198 					node->unused_uids += uids[0].seq1;
1200 					node->unused_uids +=
1270 			/* root node - UIDs are only removed, not shifted */
1276 		/* no UIDs left, delete the node's children and mark it
1278 		if (!NODE_IS_DYNAMIC_LEAF(node))
1279 			node_free(trie, node);
1281 		node->child_count = 0;
1282 		node->have_sequential = FALSE;
1283 		node->next_uid = 0;
1286 			node->next_uid = uids[uid_count-1].seq2 + 1;
1288 			node->unused_uids += (node->next_uid - 1) -
1300 	struct squat_node *node;
1305 	node = squat_trie_iterate_first(iter);
1306 	if (node->uid_list_idx == 0)
1318 		i_assert(node->uid_list_idx != 0);
1321 					       node->uid_list_idx,
1327 						   &uid_range, ctx->trie, node,
1329 		node->uid_list_idx =
1331 		i_assert(node->uid_list_idx != 0 || node->next_uid == 0);
1333 		node = squat_trie_iterate_next(iter, &shifts);
1335 	} while (node != NULL);
1346 	struct squat_node *node;
1351 	node = squat_trie_iterate_first(iter);
1352 	if (node->uid_list_idx == 0)
1356 	while (node != NULL) {
1357 		i_assert(node->uid_list_idx != 0);
1358 		if (!UIDLIST_IS_SINGLETON(node->uid_list_idx)) {
1362 					      node->uid_list_idx, &uids) < 0) {
1366 			node->uid_list_idx =
1369 		node = squat_trie_iterate_next(iter, &shifts);
1773 	struct squat_node *node = &trie->root;
1781 		if (node->children_not_mapped) {
1782 			if (node_read_children(trie, node, level) < 0)
1785 		if (node->leaf_string_length != 0) {
1786 			unsigned int len = node->leaf_string_length;
1789 			if (len > sizeof(node->children.static_leaf_string))
1790 				str = node->children.leaf_string;
1792 				str = node->children.static_leaf_string;
1805 		if (node->have_sequential) {
1814 		chars = NODE_CHILDREN_CHARS(node);
1815 		for (; idx < node->child_count; idx++) {
1825 						       node->uid_list_idx,
1830 						 node->uid_list_idx, uids) < 0)
1835 		node = NODE_CHILDREN_NODES(node) + idx;
1838 	if (squat_uidlist_filter(trie->uidlist, node->uid_list_idx, uids) < 0)

Indexes created Tue Jul 24 14:28:13 CEST 2018