2 * DEPRECATED, it is too hard to debug.
3 * you may use textdict instead
9 * -iterator vs callback
15 * -lower memory consumption
18 * on some file system like jffs2 on linux, writable mmap
19 * is not allowed, though you can write it.
29 * anthy_trie_find_next_key()
30 * anthy_trie_find_prefix()
31 * anthy_trie_print_array()
33 * Copyright (C) 2005-2006 TABATA Yusuke
37 This library is free software; you can redistribute it and/or
38 modify it under the terms of the GNU Lesser General Public
39 License as published by the Free Software Foundation; either
40 version 2 of the License, or (at your option) any later version.
42 This library is distributed in the hope that it will be useful,
43 but WITHOUT ANY WARRANTY; without even the implied warranty of
44 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
45 Lesser General Public License for more details.
47 You should have received a copy of the GNU Lesser General Public
48 License along with this library; if not, write to the Free Software
49 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
53 #include <sys/types.h>
61 #include <anthy/texttrie.h>
62 #include <anthy/filemap.h>
68 #define EXPAND_COUNT 16
122 struct filemapping *mapping;
140 print_super_cell(struct cell *c)
142 printf("super first_unused=%d, root_cell=%d, size=%d, serial=%d\n",
143 c->u.super.first_unused, c->u.super.root_cell,
144 c->u.super.size, c->u.super.serial);
148 print_alloced_cell(void)
150 printf("alloc-ed\n");
154 print_node_cell(struct cell *c)
156 printf("node key=%d", c->u.node.key);
157 if (c->u.node.key > 0 && isprint(c->u.node.key)) {
158 printf("(%c)", c->u.node.key);
160 printf(" parent=%d next=%d child=%d body=%d\n",
161 c->u.node.parent, c->u.node.next, c->u.node.child, c->u.node.body);
165 print_unused_cell(struct cell *c)
167 printf("unused next_unused=%d\n",
172 print_body_cell(struct cell *c)
174 printf("body object=(%s), owner=%d, next_tail=%d\n",
175 c->u.body.obj, c->u.body.owner, c->next_tail);
179 print_tail_cell(struct cell *c)
181 printf("tail object=(%s), prev=%d, next_tail=%d\n",
182 c->u.tail.obj, c->u.tail.prev, c->next_tail);
186 print_cell(int idx, struct cell *c)
189 printf("idx =%d(null cell):\n", idx);
192 printf("idx=%d:", idx);
198 print_alloced_cell();
204 print_unused_cell(c);
218 path_setup(struct path *path, const char *key, int len, int *buf)
220 unsigned char *p = (unsigned char *)key;
228 path->path[path->len] = p[0] * 256 + p[1];
238 path_copy_to_str(struct path *path, char *str, int buf_len)
240 unsigned char *p = (unsigned char *)str;
242 for (i = 0, o = 0; i < path->cur && o < buf_len - 2; i++) {
243 p[o] = (path->path[i]>>8)&255;
244 p[o+1] = path->path[i]&255;
251 sput_int(char *buf, int num)
253 unsigned char *tmp = (unsigned char *)buf;
254 tmp[0] = (num>>24)&255;
255 tmp[1] = (num>>16)&255;
256 tmp[2] = (num>>8)&255;
262 sget_int(char *buf, int *num)
265 unsigned char *tmp = (unsigned char *)buf;
277 pass_str(char *buf, const char *str)
284 encode_super(struct cell *c, char *buf)
286 buf += sprintf(buf, "S ");
287 buf += sput_int(buf, c->u.super.size);
288 buf += sput_int(buf, c->u.super.root_cell);
289 buf += sput_int(buf, c->u.super.first_unused);
290 buf += sput_int(buf, c->u.super.serial);
291 buf += sput_int(buf, LINE_LEN);
295 encode_node(struct cell *c, char *buf)
297 buf += sprintf(buf, "N ");
298 buf += sput_int(buf, c->u.node.key);
299 buf += sput_int(buf, c->u.node.parent);
300 buf += sput_int(buf, c->u.node.next);
301 buf += sput_int(buf, c->u.node.child);
302 buf += sput_int(buf, c->u.node.body);
306 encode_body(struct cell *c, char *buf)
308 buf += sprintf(buf, "B");
309 buf += sput_int(buf, c->next_tail);
310 buf += sput_int(buf, c->u.body.owner);
311 sprintf(buf, "\"%s\"",
316 encode_unused(struct cell *c, char *buf)
318 buf += sprintf(buf, "-next=");
319 buf += sput_int(buf, c->u.next_unused);
323 encode_tail(struct cell *c, char *buf)
325 buf += sprintf(buf, "T");
326 buf += sput_int(buf, c->u.tail.prev);
327 buf += sput_int(buf, c->next_tail);
328 sprintf(buf, "\"%s\"",
333 encode_unknown(char *buf)
339 encode_cell(struct cell *c, char *buf)
343 encode_super(c, buf);
349 encode_unused(c, buf);
364 write_back_cell(struct text_trie *tt, struct cell *c, int idx)
367 char buf[LINE_LEN+1];
369 if (((anthy_mmap_size(tt->mapping) / LINE_LEN) < (idx + 1)) ||
373 for (i = 0; i < LINE_LEN; i++) {
377 buf[LINE_LEN-1] = '\n';
378 if (anthy_mmap_is_writable(tt->mapping)) {
379 memcpy(&tt->ptr[idx*LINE_LEN], buf, LINE_LEN);
381 fseek(tt->wfp, idx*LINE_LEN, SEEK_SET);
382 fwrite(buf, LINE_LEN, 1, tt->wfp);
388 decode_str(char *raw_buf, int off)
391 char copy_buf[LINE_LEN + 1];
394 /* from off to before last '\n' */
395 for (i = 0; i < LINE_LEN - off - 1; i++) {
396 copy_buf[i] = raw_buf[i];
400 /* find first double quote */
401 while (*buf && *buf != '\"') {
405 /* cant find double quote */
410 /* go to the end of string */
414 /* find last double quote */
415 while (*buf != '\"') {
424 release_cell_str(struct cell *c)
429 if (c->type == TT_BODY) {
432 if (c->type == TT_TAIL) {
438 decode_super(struct cell *c, char *buf)
441 buf = pass_str(buf, "S ");
442 buf = sget_int(buf, &c->u.super.size);
443 buf = sget_int(buf, &c->u.super.root_cell);
444 buf = sget_int(buf, &c->u.super.first_unused);
445 buf = sget_int(buf, &c->u.super.serial);
450 decode_unuse(struct cell *c, char *buf)
453 buf = pass_str(buf, "-next=");
454 buf = sget_int(buf, &c->u.next_unused);
459 decode_node(struct cell *c, char *buf)
462 buf = pass_str(buf, "N ");
463 buf = sget_int(buf, &c->u.node.key);
464 buf = sget_int(buf, &c->u.node.parent);
465 buf = sget_int(buf, &c->u.node.next);
466 buf = sget_int(buf, &c->u.node.child);
467 buf = sget_int(buf, &c->u.node.body);
472 decode_body(struct cell *c, char *buf)
475 buf = pass_str(buf, "B");
476 buf = sget_int(buf, &c->next_tail);
477 buf = sget_int(buf, &c->u.body.owner);
478 c->u.body.obj = decode_str(buf, 9);
483 decode_tail(struct cell *c, char *buf)
486 buf = pass_str(buf, "T");
487 buf = sget_int(buf, &c->u.tail.prev);
488 buf = sget_int(buf, &c->next_tail);
489 c->u.tail.obj = decode_str(buf, 9);
494 decode_alloced(struct cell *c)
496 c->type = TT_ALLOCED;
501 decode_nth_cell(struct text_trie *tt, struct cell *c, int nth)
506 (anthy_mmap_size(tt->mapping) / LINE_LEN) <
510 buf = &tt->ptr[nth*LINE_LEN];
515 res = decode_super(c, buf);
518 res = decode_unuse(c, buf);
521 res = decode_node(c, buf);
524 res = decode_body(c, buf);
527 res = decode_tail(c, buf);
530 res = decode_alloced(c);
533 /*printf("decode fail (nth=%d::%s).\n", nth, buf);*/
543 decode_nth_node(struct text_trie *tt, struct cell *c, int nth)
545 if (!decode_nth_cell(tt, c, nth)) {
548 if (c->type != TT_NODE) {
555 update_mapping(struct text_trie *tt)
558 anthy_munmap(tt->mapping);
560 tt->mapping = anthy_mmap(tt->fn, 1);
562 /* try to fall back read-only mmap */
563 tt->mapping = anthy_mmap(tt->fn, 0);
569 tt->ptr = anthy_mmap_address(tt->mapping);
574 expand_file(struct text_trie *tt, int count)
576 char buf[LINE_LEN+1];
578 for (i = 0; i < LINE_LEN; i++) {
581 buf[LINE_LEN-1] = '\n';
583 for (i = 0; i < count; i++) {
585 res = fwrite(buf, LINE_LEN, 1, tt->wfp);
589 if (fflush(tt->wfp)) {
597 set_file_size(struct text_trie *tt, int len)
599 int size = LINE_LEN * len;
603 fseek(tt->wfp, 0, SEEK_END);
604 cur_size = ftell(tt->wfp);
605 if (cur_size == size) {
608 if (cur_size > size) {
609 truncate(tt->fn, size);
611 err = expand_file(tt, (size - cur_size) / LINE_LEN);
623 get_super_cell(struct text_trie *tt)
626 if (tt->valid_super) {
630 if (decode_nth_cell(tt, &tt->super, 0)) {
635 tt->super.type = TT_SUPER;
636 tt->super.u.super.first_unused = 0;
637 tt->super.u.super.root_cell = 0;
638 tt->super.u.super.size = 1;
639 tt->super.u.super.serial = 1;
640 if (set_file_size(tt, 1) != 0) {
643 write_back_cell(tt, &tt->super, 0);
648 /* convenience function */
650 get_array_size(struct text_trie *a)
652 struct cell *super = get_super_cell(a);
653 int size = super->u.super.size;
657 /* convenience function */
659 get_root_idx(struct text_trie *tt)
661 struct cell *super = get_super_cell(tt);
665 return super->u.super.root_cell;
669 expand_array(struct text_trie *tt, int len)
674 int size = get_array_size(tt);
679 res = set_file_size(tt, len);
684 super = get_super_cell(tt);
685 for (i = super->u.super.size; i < len; i++) {
687 ex_cell.type = TT_UNUSED;
688 ex_cell.u.next_unused = super->u.super.first_unused;
689 write_back_cell(tt, &ex_cell, i);
690 super->u.super.first_unused = i;
692 super->u.super.size = len;
693 write_back_cell(tt, super, 0);
698 anthy_trie_print_array(struct text_trie *tt)
701 int size = get_array_size(tt);
702 print_cell(0, get_super_cell(tt));
703 for (i = 1; i < size; i++) {
705 decode_nth_cell(tt, &c, i);
707 release_cell_str(&c);
711 /* get unused cell */
713 get_unused_index(struct text_trie *tt)
717 struct cell new_cell;
719 super = get_super_cell(tt);
720 unuse = super->u.super.first_unused;
723 expand_array(tt, super->u.super.size + EXPAND_COUNT);
724 unuse = super->u.super.first_unused;
729 if (!decode_nth_cell(tt, &new_cell, unuse)) {
733 super->u.super.first_unused = new_cell.u.next_unused;
734 new_cell.type = TT_ALLOCED;
735 write_back_cell(tt, &new_cell, unuse);
736 write_back_cell(tt, super, 0);
741 free_cell(struct text_trie *tt, int idx)
743 struct cell *super = get_super_cell(tt);
745 if (!decode_nth_cell(tt, &c, idx)) {
749 c.u.next_unused = super->u.super.first_unused;
750 write_back_cell(tt, &c, idx);
752 super->u.super.first_unused = idx;
753 write_back_cell(tt, super, 0);
757 load_super(struct text_trie *tt)
759 struct cell root, *super;
761 super = get_super_cell(tt);
767 if (super->u.super.root_cell) {
771 root_idx = get_unused_index(tt);
778 root.u.node.parent = 0;
779 root.u.node.next = 0;
780 root.u.node.child = 0;
781 root.u.node.body = 0;
782 write_back_cell(tt, &root, root_idx);
784 tt->super.u.super.root_cell = root_idx;
785 write_back_cell(tt, super, 0);
789 purge_cache(struct text_trie *tt)
797 do_fopen(const char *fn, int create)
801 /* check file existance */
809 fd = open(fn, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR);
813 return fdopen(fd, "w");
816 static struct text_trie *
817 alloc_tt(const char *fn, FILE *wfp)
819 struct text_trie *tt;
820 tt = malloc(sizeof(struct text_trie));
830 clear_file(const char *fn)
832 FILE *fp = fopen(fn, "w");
838 static struct text_trie *
839 trie_open(const char *fn, int create, int do_retry)
841 struct text_trie *tt;
844 fp = do_fopen(fn, create);
849 tt = alloc_tt(fn, fp);
859 anthy_trie_close(tt);
864 return trie_open(fn, create, 0);
873 anthy_trie_open(const char *fn, int create)
875 struct text_trie *tt;
876 anthy_priv_dic_lock();
877 tt = trie_open(fn, create, 1);
878 anthy_priv_dic_unlock();
885 anthy_trie_close(struct text_trie *tt)
891 anthy_munmap(tt->mapping);
898 anthy_trie_update_mapping(struct text_trie *tt)
903 anthy_priv_dic_lock();
905 anthy_priv_dic_unlock();
909 graft_child(struct text_trie *tt, int parent_idx, int new_idx)
911 struct cell parent_cell;
912 struct cell new_cell;
913 struct cell cur_youngest_cell;
916 if (!decode_nth_node(tt, &parent_cell, parent_idx)) {
920 if (parent_cell.u.node.child == 0) {
922 parent_cell.u.node.child = new_idx;
923 write_back_cell(tt, &parent_cell, parent_idx);
927 if (!decode_nth_node(tt, &cur_youngest_cell, parent_cell.u.node.child)) {
930 if (!decode_nth_node(tt, &new_cell, new_idx)) {
933 if (new_cell.u.node.key < cur_youngest_cell.u.node.key) {
934 /* newly added younger child */
935 new_cell.u.node.next = parent_cell.u.node.child;
936 parent_cell.u.node.child = new_idx;
937 write_back_cell(tt, &new_cell, new_idx);
938 write_back_cell(tt, &parent_cell, parent_idx);
942 /* insert some order */
943 cur_idx = parent_cell.u.node.child;
946 struct cell cur_cell, tmp_cell;
947 struct cell *next_cell = NULL;
948 if (!decode_nth_node(tt, &cur_cell, cur_idx)) {
951 next_idx = cur_cell.u.node.next;
954 next_cell = decode_nth_node(tt, &tmp_cell, next_idx);
958 new_cell.u.node.next = 0;
959 cur_cell.u.node.next = new_idx;
960 write_back_cell(tt, &cur_cell, cur_idx);
963 if (cur_cell.u.node.key < new_cell.u.node.key &&
964 new_cell.u.node.key < next_cell->u.node.key) {
965 cur_cell.u.node.next = new_idx;
966 new_cell.u.node.next = next_idx;
967 write_back_cell(tt, &cur_cell, cur_idx);
973 write_back_cell(tt, &new_cell, new_idx);
977 find_child(struct text_trie *tt, int parent_idx, int key, int exact)
981 struct cell parent_cell;
983 if (!decode_nth_node(tt, &parent_cell, parent_idx)) {
989 child_idx = parent_cell.u.node.child;
993 struct cell child_cell;
996 if (!decode_nth_node(tt, &child_cell, child_idx)) {
999 this_key = child_cell.u.node.key;
1000 if (this_key <= prev_key) {
1004 if (exact && this_key == key) {
1007 if (!exact && (this_key & 0xff00) == (key & 0xff00)) {
1010 child_idx = child_cell.u.node.next;
1011 prev_key = this_key;
1017 trie_search_rec(struct text_trie *tt, struct path *p,
1018 int parent_idx, int create)
1021 int key = p->path[p->cur];
1023 if (p->cur == p->len) {
1027 child_idx = find_child(tt, parent_idx, key, 1);
1029 struct cell child_cell;
1034 child_idx = get_unused_index(tt);
1038 if (!decode_nth_cell(tt, &child_cell, child_idx)) {
1041 child_cell.type = TT_NODE;
1042 child_cell.u.node.parent = parent_idx;
1043 child_cell.u.node.key = key;
1044 child_cell.u.node.next = 0;
1045 child_cell.u.node.child = 0;
1046 child_cell.u.node.body = 0;
1047 write_back_cell(tt, &child_cell, child_idx);
1049 graft_child(tt, parent_idx, child_idx);
1056 return trie_search_rec(tt, p, child_idx, create);
1060 get_str_part(const char *str, int from)
1062 char buf[OBJ_LEN+1];
1064 for (i = 0; i < OBJ_LEN; i++) {
1065 buf[i] = str[from+i];
1072 release_body(struct text_trie *tt, int idx)
1076 if (!decode_nth_cell(tt, &c, idx) ||
1077 c.type != TT_BODY) {
1080 tail_idx = c.next_tail;
1082 struct cell tail_cell;
1084 if (!decode_nth_cell(tt, &tail_cell, tail_idx)) {
1087 tmp = tail_cell.next_tail;
1088 free_cell(tt, tail_idx);
1095 set_body(struct text_trie *tt, int idx, const char *body_str)
1097 int body_idx = get_unused_index(tt);
1100 struct cell node_cell;
1101 struct cell body_cell;
1102 struct cell prev_cell;
1103 struct cell tail_cell;
1106 if (!decode_nth_cell(tt, &node_cell, idx)) {
1109 if (node_cell.u.node.body) {
1110 release_body(tt, node_cell.u.node.body);
1112 len = strlen(body_str);
1114 node_cell.u.node.body = body_idx;
1115 write_back_cell(tt, &node_cell, idx);
1117 if (!decode_nth_cell(tt, &body_cell, body_idx)) {
1120 body_cell.type = TT_BODY;
1121 body_cell.u.body.obj = get_str_part(body_str, 0);
1122 body_cell.u.body.owner = idx;
1123 body_cell.next_tail = 0;
1124 write_back_cell(tt, &body_cell, body_idx);
1125 release_cell_str(&body_cell);
1127 if (!decode_nth_cell(tt, &body_cell, body_idx)) {
1131 prev_idx = body_idx;
1132 prev_cell = body_cell;
1133 for (i = OBJ_LEN; i < len; i += OBJ_LEN) {
1134 int tail_idx = get_unused_index(tt);
1135 if (!decode_nth_cell(tt, &tail_cell, tail_idx)) {
1138 tail_cell.type = TT_TAIL;
1139 tail_cell.u.tail.obj = get_str_part(body_str, i);
1140 tail_cell.u.tail.prev = prev_idx;
1141 tail_cell.next_tail = 0;
1142 prev_cell.next_tail = tail_idx;
1143 write_back_cell(tt, &tail_cell, tail_idx);
1144 write_back_cell(tt, &prev_cell, prev_idx);
1145 release_cell_str(&prev_cell);
1147 prev_idx = tail_idx;
1148 prev_cell = tail_cell;
1151 release_cell_str(&tail_cell);
1156 trie_add(struct text_trie *tt, struct path *p, const char *body)
1158 int root_idx = get_root_idx(tt);
1161 if (root_idx == 0) {
1164 target_idx = trie_search_rec(tt, p, root_idx, 1);
1166 set_body(tt, target_idx, body);
1173 anthy_trie_add(struct text_trie *tt, const char *key, const char *body)
1178 if (!tt || tt->fatal) {
1182 path_setup(&p, key, len, alloca(sizeof(int)*len));
1183 anthy_priv_dic_lock();
1184 res = trie_add(tt, &p, body);
1185 anthy_priv_dic_unlock();
1191 get_object_length(struct text_trie *tt, int body_idx)
1197 if (!decode_nth_cell(tt, &c, idx)) {
1202 release_cell_str(&c);
1208 gather_str(struct text_trie *tt, int body_idx)
1214 len = get_object_length(tt, body_idx);
1219 buf = malloc(len + 1);
1224 if (!decode_nth_cell(tt, &c, idx)) {
1229 sprintf(&buf[len], "%s", c.u.body.obj);
1231 sprintf(&buf[len], "%s", c.u.tail.obj);
1235 release_cell_str(&c);
1241 trie_find(struct text_trie *tt, struct path *p)
1245 root_idx = get_root_idx(tt);
1249 target_idx = trie_search_rec(tt, p, root_idx, 0);
1251 struct cell target_cell;
1253 if (!decode_nth_node(tt, &target_cell, target_idx)) {
1256 body_idx = target_cell.u.node.body;
1258 return gather_str(tt, body_idx);
1266 anthy_trie_find(struct text_trie *tt, char *key)
1271 if (!tt || tt->fatal) {
1275 path_setup(&p, key, len, alloca(sizeof(int)*len));
1276 anthy_priv_dic_lock();
1277 res = trie_find(tt, &p);
1278 anthy_priv_dic_unlock();
1284 do_find_next_key(struct text_trie *tt, struct path *p,
1285 int root_idx, int target_idx)
1287 struct cell *target_cell, tmp_cell;
1289 target_cell = decode_nth_node(tt, &tmp_cell, target_idx);
1296 if (!prev_is_up && target_cell->u.node.child) {
1298 target_idx = target_cell->u.node.child;
1300 } else if (target_cell->u.node.next) {
1302 target_idx = target_cell->u.node.next;
1303 } else if (target_cell->u.node.parent) {
1305 target_idx = target_cell->u.node.parent;
1310 target_cell = decode_nth_node(tt, &tmp_cell, target_idx);
1314 if (p->cur >= p->max_len) {
1320 p->path[p->cur-1] = target_cell->u.node.key;
1321 if (!prev_is_up && target_cell->u.node.body) {
1324 } while (target_idx != root_idx);
1329 find_partial_key(struct text_trie *tt, struct path *p, int idx)
1332 if (!decode_nth_node(tt, &c, idx)) {
1335 if (c.type != TT_NODE) {
1339 p->path[p->cur] = c.u.node.key;
1345 trie_find_next_key(struct text_trie *tt, struct path *p)
1347 int root_idx = get_root_idx(tt);
1351 target_idx = trie_search_rec(tt, p, root_idx, 0);
1352 if (target_idx > 0) {
1354 return do_find_next_key(tt, p, root_idx, target_idx);
1356 if ((p->path[p->len-1] & 0xff) != 0) {
1357 /* simply not exist in tree */
1363 target_idx = trie_search_rec(tt, p, root_idx, 0);
1364 tmp_idx = find_child(tt, target_idx, p->path[p->len], 0);
1366 return find_partial_key(tt, p, tmp_idx);
1368 return do_find_next_key(tt, p, root_idx, target_idx);
1374 anthy_trie_find_next_key(struct text_trie *tt, char *buf, int buf_len)
1378 if (!tt || tt->fatal) {
1381 path_setup(&p, buf, buf_len, alloca(sizeof(int)*buf_len));
1382 anthy_priv_dic_lock();
1383 res = trie_find_next_key(tt, &p);
1384 anthy_priv_dic_unlock();
1389 path_copy_to_str(&p, buf, buf_len);
1394 trie_find_prefix(struct text_trie *tt, const char *str,
1395 char *buf, int buf_len,
1396 int (*cb)(const char *key, const char *str))
1398 int idx = get_root_idx(tt);
1399 int i, len = strlen(str);
1400 for (i = 0; i < len && i < buf_len; i++) {
1402 idx = find_child(tt, idx, str[i], 1);
1406 if (!decode_nth_node(tt, &c, idx)) {
1411 if (c.u.node.body) {
1412 char *s = gather_str(tt, c.u.node.body);
1422 anthy_trie_find_prefix(struct text_trie *tt, const char *str,
1423 char *buf, int buf_len,
1424 int (*cb)(const char *key, const char *str))
1426 if (!tt || tt->fatal) {
1429 anthy_priv_dic_lock();
1430 trie_find_prefix(tt, str, buf, buf_len, cb);
1431 anthy_priv_dic_unlock();
1436 disconnect(struct text_trie *tt, int parent_idx, int target_idx)
1438 struct cell parent_cell;
1439 struct cell target_cell;
1441 if (!decode_nth_node(tt, &parent_cell, parent_idx) ||
1442 !decode_nth_node(tt, &target_cell, target_idx)) {
1446 if (parent_cell.u.node.child == target_idx) {
1448 parent_cell.u.node.child = target_cell.u.node.next;
1449 write_back_cell(tt, &parent_cell, parent_idx);
1450 if (!target_cell.u.node.next &&
1451 !parent_cell.u.node.body) {
1452 /* only child and parent does not have body, so traverse upward */
1453 disconnect(tt, parent_cell.u.node.parent, parent_idx);
1454 free_cell(tt, target_idx);
1457 free_cell(tt, target_idx);
1460 int child_idx = parent_cell.u.node.child;
1463 if (!decode_nth_cell(tt, &cur, child_idx)) {
1466 if (cur.u.node.next == target_idx) {
1468 cur.u.node.next = target_cell.u.node.next;
1469 write_back_cell(tt, &cur, child_idx);
1470 free_cell(tt, target_idx);
1473 child_idx = cur.u.node.next;
1479 trie_delete(struct text_trie *tt, struct path *p)
1481 struct cell target_cell;
1482 int root_idx = get_root_idx(tt);
1483 int target_idx, parent_idx;
1484 target_idx = trie_search_rec(tt, p, root_idx, 0);
1488 if (!decode_nth_node(tt, &target_cell, target_idx)) {
1491 release_body(tt, target_cell.u.node.body);
1492 target_cell.u.node.body = 0;
1493 write_back_cell(tt, &target_cell, target_idx);
1494 if (target_cell.u.node.child) {
1497 parent_idx = target_cell.u.node.parent;
1498 disconnect(tt, parent_idx, target_idx);
1503 anthy_trie_delete(struct text_trie *tt, const char *key)
1507 if (!tt || tt->fatal) {
1511 path_setup(&p, key, len, alloca(sizeof(int)*len));
1512 anthy_priv_dic_lock();
1513 trie_delete(tt, &p);
1514 anthy_priv_dic_unlock();