Mercurial > dovecot > original-hg > dovecot-1.2

comparison src/plugins/fts-squat/squat-trie.c @ 7197:bb9304dee6d4 HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
uidlist renumbering: changed iteration code to iterate children first. This will be needed for handling expunges.
author Timo Sirainen <tss@iki.fi>
date Sun, 27 Jan 2008 11:49:35 +0200
parents d9b87e3ce6c8
children f5f77a3ae203
comparison
equal deleted inserted replaced
7196:4f1527e3d61b 7197:bb9304dee6d4
997 trie->hdr.root_uidlist_idx = trie->root.uid_list_idx; 997 trie->hdr.root_uidlist_idx = trie->root.uid_list_idx;
998 return 0; 998 return 0;
999 } 999 }
1000 1000
1001 static struct squat_trie_iterate_context * 1001 static struct squat_trie_iterate_context *
1002 squat_trie_iterate_uidlist_init(struct squat_trie *trie) 1002 squat_trie_iterate_init(struct squat_trie *trie)
1003 { 1003 {
1004 struct squat_trie_iterate_context *ctx; 1004 struct squat_trie_iterate_context *ctx;
1005 1005
1006 ctx = i_new(struct squat_trie_iterate_context, 1); 1006 ctx = i_new(struct squat_trie_iterate_context, 1);
1007 ctx->trie = trie; 1007 ctx->trie = trie;
1009 i_array_init(&ctx->parents, trie->hdr.partial_len*2); 1009 i_array_init(&ctx->parents, trie->hdr.partial_len*2);
1010 return ctx; 1010 return ctx;
1011 } 1011 }
1012 1012
1013 static int 1013 static int
1014 squat_trie_iterate_uidlist_deinit(struct squat_trie_iterate_context *ctx) 1014 squat_trie_iterate_deinit(struct squat_trie_iterate_context *ctx)
1015 { 1015 {
1016 int ret = ctx->failed ? -1 : 0; 1016 int ret = ctx->failed ? -1 : 0;
1017 1017
1018 array_free(&ctx->parents); 1018 array_free(&ctx->parents);
1019 i_free(ctx); 1019 i_free(ctx);
1020 return ret; 1020 return ret;
1021 } 1021 }
1022 1022
1023 static struct squat_node * 1023 static struct squat_node *
1024 squat_trie_iterate_uidlist_first(struct squat_trie_iterate_context *ctx) 1024 squat_trie_iterate_first(struct squat_trie_iterate_context *ctx)
1025 { 1025 {
1026 struct squat_node *node = ctx->cur.node; 1026 if (ctx->cur.node->children_not_mapped) {
1027 int level; 1027 if (node_read_children(ctx->trie, ctx->cur.node, 1) < 0) {
1028
1029 if (UIDLIST_IS_SINGLETON(node->uid_list_idx)) {
1030 /* no uidlists */
1031 i_assert(node == &ctx->trie->root);
1032 return NULL;
1033 }
1034
1035 if (node->children_not_mapped) {
1036 level = array_count(&ctx->parents);
1037
1038 if (node_read_children(ctx->trie, node, level) < 0) {
1039 ctx->failed = TRUE; 1028 ctx->failed = TRUE;
1040 return NULL; 1029 return NULL;
1041 } 1030 }
1042 } 1031 }
1043 return node; 1032 return ctx->cur.node;
1044 } 1033 }
1045 1034
1046 static struct squat_node * 1035 static struct squat_node *
1047 squat_trie_iterate_uidlist_next(struct squat_trie_iterate_context *ctx) 1036 squat_trie_iterate_next(struct squat_trie_iterate_context *ctx)
1048 { 1037 {
1049 struct squat_trie_iterate_node *iter_nodes; 1038 struct squat_trie_iterate_node *iter_nodes;
1050 struct squat_node *node = ctx->cur.node;
1051 struct squat_node *children; 1039 struct squat_node *children;
1052 unsigned int count; 1040 unsigned int count;
1053 1041
1054 /* return our children first */ 1042 while (ctx->cur.idx == ctx->cur.node->child_count) {
1055 children = NODE_CHILDREN_NODES(node);
1056 for (; ctx->cur.idx < node->child_count; ctx->cur.idx++) {
1057 if (!UIDLIST_IS_SINGLETON(children[ctx->cur.idx].uid_list_idx))
1058 return &children[ctx->cur.idx++];
1059 }
1060
1061 ctx->cur.idx = 0;
1062 for (;;) {
1063 /* next start iterating our childrens' children */
1064 while (ctx->cur.idx < node->child_count) {
1065 uint32_t list_idx =
1066 children[ctx->cur.idx++].uid_list_idx;
1067
1068 if (UIDLIST_IS_SINGLETON(list_idx))
1069 continue;
1070
1071 array_append(&ctx->parents, &ctx->cur, 1);
1072 ctx->cur.node = &children[ctx->cur.idx-1];
1073 ctx->cur.idx = 0;
1074 if (squat_trie_iterate_uidlist_first(ctx) == NULL)
1075 return NULL;
1076 return squat_trie_iterate_uidlist_next(ctx);
1077 }
1078
1079 /* no more children. go to next sibling's children */
1080 iter_nodes = array_get_modifiable(&ctx->parents, &count); 1043 iter_nodes = array_get_modifiable(&ctx->parents, &count);
1081 if (count == 0) 1044 if (count == 0)
1082 return NULL; 1045 return NULL;
1083
1084 ctx->cur = iter_nodes[count-1]; 1046 ctx->cur = iter_nodes[count-1];
1085 array_delete(&ctx->parents, count-1, 1); 1047 array_delete(&ctx->parents, count-1, 1);
1086 1048 }
1087 node = ctx->cur.node; 1049
1088 children = NODE_CHILDREN_NODES(node); 1050 ctx->cur.idx++;
1089 } 1051 array_append(&ctx->parents, &ctx->cur, 1);
1052 children = NODE_CHILDREN_NODES(ctx->cur.node);
1053 ctx->cur.node = &children[ctx->cur.idx-1];
1054 ctx->cur.idx = 0;
1055 return ctx->cur.node;
1090 } 1056 }
1091 1057
1092 static int 1058 static int
1093 squat_trie_renumber_uidlists(struct squat_trie_build_context *ctx, 1059 squat_trie_renumber_uidlists(struct squat_trie_build_context *ctx,
1094 bool compress) 1060 bool compress)
1109 now = time(NULL); 1075 now = time(NULL);
1110 ctx->trie->hdr.indexid = 1076 ctx->trie->hdr.indexid =
1111 I_MAX((unsigned int)now, ctx->trie->hdr.indexid + 1); 1077 I_MAX((unsigned int)now, ctx->trie->hdr.indexid + 1);
1112 1078
1113 i_array_init(&uids, 1024); 1079 i_array_init(&uids, 1024);
1114 iter = squat_trie_iterate_uidlist_init(ctx->trie); 1080 iter = squat_trie_iterate_init(ctx->trie);
1115 node = squat_trie_iterate_uidlist_first(iter); 1081 node = squat_trie_iterate_first(iter);
1116 new_uid_list_idx = 0x100; 1082 new_uid_list_idx = 0x100;
1117 while (node != NULL) { 1083 while (node != NULL) {
1118 array_clear(&uids); 1084 if (!UIDLIST_IS_SINGLETON(node->uid_list_idx)) {
1119 if (squat_uidlist_get(ctx->trie->uidlist, node->uid_list_idx, 1085 array_clear(&uids);
1120 &uids) < 0) { 1086 if (squat_uidlist_get(ctx->trie->uidlist,
1121 ret = -1; 1087 node->uid_list_idx, &uids) < 0) {
1122 break; 1088 ret = -1;
1123 } 1089 break;
1124 max_count = I_MAX(max_count, array_count(&uids)); 1090 }
1125 squat_uidlist_rebuild_next(rebuild_ctx, &uids); 1091 max_count = I_MAX(max_count, array_count(&uids));
1126 node->uid_list_idx = new_uid_list_idx << 1; 1092 squat_uidlist_rebuild_next(rebuild_ctx, &uids);
1127 new_uid_list_idx++; 1093 node->uid_list_idx = new_uid_list_idx << 1;
1128 1094 new_uid_list_idx++;
1129 node = squat_trie_iterate_uidlist_next(iter); 1095 }
1130 } 1096 node = squat_trie_iterate_next(iter);
1131 squat_trie_iterate_uidlist_deinit(iter); 1097 }
1098 squat_trie_iterate_deinit(iter);
1132 array_free(&uids); 1099 array_free(&uids);
1133 1100
1134 /* lock the trie before we rename uidlist */ 1101 /* lock the trie before we rename uidlist */
1135 if (squat_trie_lock(ctx->trie, F_WRLCK, &ctx->file_lock) <= 0) 1102 if (squat_trie_lock(ctx->trie, F_WRLCK, &ctx->file_lock) <= 0)
1136 ret = -1; 1103 ret = -1;