src-worddic/texttrie.c

   1 /*
   2  * DEPRECATED, it is too hard to debug.
   3  * you may use textdict instead
   4  *
   5  * Trie in Text
   6  *
   7  * *issues
   8  *  +correct API
   9  *   -iterator vs callback
  10  *  +robustness
  11  *   -error detection
  12  *   -auto correction
  13  *   -concurrent access
  14  *  +efficiency
  15  *   -lower memory consumption
  16  *   -disk space?
  17  *
  18  * on some file system like jffs2 on linux, writable mmap
  19  * is not allowed, though you can write it.
  20  *
  21  */
  22 /*
  23  * API
  24  *  anthy_trie_open()
  25  *  anthy_trie_close()
  26  *  anthy_trie_add()
  27  *  anthy_trie_find()
  28  *  anthy_trie_delete()
  29  *  anthy_trie_find_next_key()
  30  *  anthy_trie_find_prefix()
  31  *  anthy_trie_print_array()
  32  *
  33  * Copyright (C) 2005-2006 TABATA Yusuke
  34  *
  35  */
  36 /*
  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.
  41
  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.
  46
  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
  50  */
  51 /* open & mmap */
  52 #include <unistd.h>
  53 #include <sys/types.h>
  54 #include <sys/stat.h>
  55 #include <fcntl.h>
  56 /**/
  57 #include <stdlib.h>
  58 #include <stdio.h>
  59 #include <string.h>
  60 #include <ctype.h>
  61 #include <anthy/texttrie.h>
  62 #include <anthy/filemap.h>
  63 #include "dic_main.h"
  64
  65 /* configs */
  66 #define OBJ_LEN 20
  67 #define LINE_LEN 32
  68 #define EXPAND_COUNT 16
  69
  70 /* cell type */
  71 #define TT_SUPER 0
  72 #define TT_UNUSED 1
  73 #define TT_ALLOCED 2
  74 #define TT_NODE 3
  75 #define TT_BODY 4
  76 #define TT_TAIL 5
  77
  78 /* cell structure */
  79 struct cell {
  80   /* (common) type */
  81   int type;
  82   /* union */
  83   union {
  84     /* unused */
  85     int next_unused;
  86     /* super */
  87     struct {
  88       int first_unused;
  89       int root_cell;
  90       int size;
  91       int serial;
  92     } super;
  93     /* node */
  94     struct {
  95       int key;
  96       int next;
  97       int child;
  98       int body;
  99       int parent;
 100     } node;
 101     /* body */
 102     struct {
 103       int owner;
 104       char *obj;
 105     } body;
 106     /* tail */
 107     struct {
 108       char *obj;
 109       int prev;
 110     } tail;
 111   } u;
 112   /* body & tail */
 113   int next_tail;
 114 };
 115
 116 struct text_trie {
 117   /**/
 118   int fatal;
 119   /**/
 120   char *fn;
 121   FILE *wfp;
 122   struct filemapping *mapping;
 123   char *ptr;
 124   /**/
 125   struct cell super;
 126   int valid_super;
 127 };
 128
 129 struct path {
 130   /**/
 131   const char *key_str;
 132   /**/
 133   int max_len;
 134   int *path;
 135   int len;
 136   int cur;
 137 };
 138
 139 static void
 140 print_super_cell(struct cell *c)
 141 {
 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);
 145 }
 146
 147 static void
 148 print_alloced_cell(void)
 149 {
 150   printf("alloc-ed\n");
 151 }
 152
 153 static void
 154 print_node_cell(struct cell *c)
 155 {
 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);
 159   }
 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);
 162 }
 163
 164 static void
 165 print_unused_cell(struct cell *c)
 166 {
 167   printf("unused next_unused=%d\n",
 168          c->u.next_unused);
 169 }
 170
 171 static void
 172 print_body_cell(struct cell *c)
 173 {
 174   printf("body object=(%s), owner=%d, next_tail=%d\n",
 175          c->u.body.obj, c->u.body.owner, c->next_tail);
 176 }
 177
 178 static void
 179 print_tail_cell(struct cell *c)
 180 {
 181   printf("tail object=(%s), prev=%d, next_tail=%d\n",
 182          c->u.tail.obj, c->u.tail.prev, c->next_tail);
 183 }
 184
 185 static void
 186 print_cell(int idx, struct cell *c)
 187 {
 188   if (!c) {
 189     printf("idx =%d(null cell):\n", idx);
 190     return ;
 191   }
 192   printf("idx=%d:", idx);
 193   switch (c->type) {
 194   case TT_SUPER:
 195     print_super_cell(c);
 196     break;
 197   case TT_ALLOCED:
 198     print_alloced_cell();
 199     break;
 200   case TT_NODE:
 201     print_node_cell(c);
 202     break;
 203   case TT_UNUSED:
 204     print_unused_cell(c);
 205     break;
 206   case TT_BODY:
 207     print_body_cell(c);
 208     break;
 209   case TT_TAIL:
 210     print_tail_cell(c);
 211     break;
 212   default:
 213     printf("unknown\n");
 214   }
 215 }
 216
 217 static void
 218 path_setup(struct path *path, const char *key, int len, int *buf)
 219 {
 220   unsigned char *p = (unsigned char *)key;
 221   path->key_str = key;
 222   path->max_len = len;
 223   path->path = buf;
 224   path->len = 0;
 225   path->cur = 0;
 226   /**/
 227   while (*p) {
 228     path->path[path->len] = p[0] * 256 + p[1];
 229     path->len ++;
 230     p++;
 231     if (p[0]) {
 232       p++;
 233     }
 234   }
 235 }
 236
 237 static void
 238 path_copy_to_str(struct path *path, char *str, int buf_len)
 239 {
 240   unsigned char *p = (unsigned char *)str;
 241   int i, o;
 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;
 245     o += 2;
 246   }
 247   p[o] = 0;
 248 }
 249
 250 static int
 251 sput_int(char *buf, int num)
 252 {
 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;
 257   tmp[3] = num&255;
 258   return 4;
 259 }
 260
 261 static char *
 262 sget_int(char *buf, int *num)
 263 {
 264   unsigned int res;
 265   unsigned char *tmp = (unsigned char *)buf;
 266   res = 0;
 267   res += tmp[0] << 24;
 268   res += tmp[1] << 16;
 269   res += tmp[2] << 8;
 270   res += tmp[3];
 271   *num = res;
 272   buf += 4;
 273   return buf;
 274 }
 275
 276 static char *
 277 pass_str(char *buf, const char *str)
 278 {
 279   buf += strlen(str);
 280   return buf;
 281 }
 282
 283 static void
 284 encode_super(struct cell *c, char *buf)
 285 {
 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);
 292 }
 293
 294 static void
 295 encode_node(struct cell *c, char *buf)
 296 {
 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);
 303 }
 304
 305 static void
 306 encode_body(struct cell *c, char *buf)
 307 {
 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\"",
 312           c->u.body.obj);
 313 }
 314
 315 static void
 316 encode_unused(struct cell *c, char *buf)
 317 {
 318   buf += sprintf(buf, "-next=");
 319   buf += sput_int(buf, c->u.next_unused);
 320 }
 321
 322 static void
 323 encode_tail(struct cell *c, char *buf)
 324 {
 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\"",
 329           c->u.tail.obj);
 330 }
 331
 332 static void
 333 encode_unknown(char *buf)
 334 {
 335   sprintf(buf, "?");
 336 }
 337
 338 static void
 339 encode_cell(struct cell *c, char *buf)
 340 {
 341   switch (c->type) {
 342   case TT_SUPER:
 343     encode_super(c, buf);
 344     break;
 345   case TT_NODE:
 346     encode_node(c, buf);
 347     break;
 348   case TT_UNUSED:
 349     encode_unused(c, buf);
 350     break;
 351   case TT_BODY:
 352     encode_body(c, buf);
 353     break;
 354   case TT_TAIL:
 355     encode_tail(c, buf);
 356     break;
 357   default:
 358     encode_unknown(buf);
 359     break;
 360   }
 361 }
 362
 363 static void
 364 write_back_cell(struct text_trie *tt, struct cell *c, int idx)
 365 {
 366   int i;
 367   char buf[LINE_LEN+1];
 368   /* sanity check */
 369   if (((anthy_mmap_size(tt->mapping) / LINE_LEN) < (idx + 1)) ||
 370       idx < 0) {
 371     return ;
 372   }
 373   for (i = 0; i < LINE_LEN; i++) {
 374     buf[i] = ' ';
 375   }
 376   encode_cell(c, buf);
 377   buf[LINE_LEN-1] = '\n';
 378   if (anthy_mmap_is_writable(tt->mapping)) {
 379     memcpy(&tt->ptr[idx*LINE_LEN], buf, LINE_LEN);
 380   } else {
 381     fseek(tt->wfp, idx*LINE_LEN, SEEK_SET);
 382     fwrite(buf, LINE_LEN, 1, tt->wfp);
 383     fflush(tt->wfp);
 384   }
 385 }
 386
 387 static char *
 388 decode_str(char *raw_buf, int off)
 389 {
 390   char *head;
 391   char copy_buf[LINE_LEN + 1];
 392   char *buf;
 393   int i;
 394   /* from off to before last '\n' */
 395   for (i = 0; i < LINE_LEN - off - 1; i++) {
 396     copy_buf[i] = raw_buf[i];
 397   }
 398   copy_buf[i] = 0;
 399   buf = copy_buf;
 400   /* find first double quote */
 401   while (*buf && *buf != '\"') {
 402     buf ++;
 403   }
 404   if (!*buf) {
 405     /* cant find double quote */
 406     return strdup("");
 407   }
 408   buf ++;
 409   head = buf;
 410   /* go to the end of string */
 411   while (*buf) {
 412     buf ++;
 413   }
 414   /* find last double quote */
 415   while (*buf != '\"') {
 416     buf--;
 417   }
 418   *buf = 0;
 419   /**/
 420   return strdup(head);
 421 }
 422
 423 static void
 424 release_cell_str(struct cell *c)
 425 {
 426   if (!c) {
 427     return ;
 428   }
 429   if (c->type == TT_BODY) {
 430     free(c->u.body.obj);
 431   }
 432   if (c->type == TT_TAIL) {
 433     free(c->u.tail.obj);
 434   }
 435 }
 436
 437 static int
 438 decode_super(struct cell *c, char *buf)
 439 {
 440   c->type = TT_SUPER;
 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);
 446   return 0;
 447 }
 448
 449 static int
 450 decode_unuse(struct cell *c, char *buf)
 451 {
 452   c->type = TT_UNUSED;
 453   buf = pass_str(buf, "-next=");
 454   buf = sget_int(buf, &c->u.next_unused);
 455   return 0;
 456 }
 457
 458 static int
 459 decode_node(struct cell *c, char *buf)
 460 {
 461   c->type = TT_NODE;
 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);
 468   return 0;
 469 }
 470
 471 static int
 472 decode_body(struct cell *c, char *buf)
 473 {
 474   c->type = TT_BODY;
 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);
 479   return 0;
 480 }
 481
 482 static int
 483 decode_tail(struct cell *c, char *buf)
 484 {
 485   c->type = TT_TAIL;
 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);
 490   return 0;
 491 }
 492
 493 static int
 494 decode_alloced(struct cell *c)
 495 {
 496   c->type = TT_ALLOCED;
 497   return 0;
 498 }
 499
 500 static struct cell *
 501 decode_nth_cell(struct text_trie *tt, struct cell *c, int nth)
 502 {
 503   int res;
 504   char *buf;
 505   if (nth < 0 ||
 506       (anthy_mmap_size(tt->mapping) / LINE_LEN) <
 507       (nth + 1)) {
 508     return NULL;
 509   }
 510   buf = &tt->ptr[nth*LINE_LEN];
 511
 512   res = -1;
 513   switch (buf[0]) {
 514   case 'S':
 515     res = decode_super(c, buf);
 516     break;
 517   case '-':
 518     res = decode_unuse(c, buf);
 519     break;
 520   case 'N':
 521     res = decode_node(c, buf);
 522     break;
 523   case 'B':
 524     res = decode_body(c, buf);
 525     break;
 526   case 'T':
 527     res = decode_tail(c, buf);
 528     break;
 529   case '?':
 530     res =  decode_alloced(c);
 531     break;
 532   default:
 533     /*printf("decode fail (nth=%d::%s).\n", nth, buf);*/
 534     ;
 535   }
 536   if (res) {
 537     c->type = TT_UNUSED;
 538   }
 539   return c;
 540 }
 541
 542 static struct cell *
 543 decode_nth_node(struct text_trie *tt, struct cell *c, int nth)
 544 {
 545   if (!decode_nth_cell(tt, c, nth)) {
 546     return NULL;
 547   }
 548   if (c->type != TT_NODE) {
 549     return NULL;
 550   }
 551   return c;
 552 }
 553
 554 static int
 555 update_mapping(struct text_trie *tt)
 556 {
 557   if (tt->mapping) {
 558     anthy_munmap(tt->mapping);
 559   }
 560   tt->mapping = anthy_mmap(tt->fn, 1);
 561   if (!tt->mapping) {
 562     /* try to fall back read-only mmap */
 563     tt->mapping = anthy_mmap(tt->fn, 0);
 564   }
 565   if (!tt->mapping) {
 566     tt->ptr = NULL;
 567     return 1;
 568   }
 569   tt->ptr = anthy_mmap_address(tt->mapping);
 570   return 0;
 571 }
 572
 573 static int
 574 expand_file(struct text_trie *tt, int count)
 575 {
 576   char buf[LINE_LEN+1];
 577   int i;
 578   for (i = 0; i < LINE_LEN; i++) {
 579     buf[i] = ' ';
 580   }
 581   buf[LINE_LEN-1] = '\n';
 582   /**/
 583   for (i = 0; i < count; i++) {
 584     int res;
 585     res = fwrite(buf, LINE_LEN, 1, tt->wfp);
 586     if (res != 1) {
 587       return 1;
 588     }
 589     if (fflush(tt->wfp)) {
 590       return 1;
 591     }
 592   }
 593   return 0;
 594 }
 595
 596 static int
 597 set_file_size(struct text_trie *tt, int len)
 598 {
 599   int size = LINE_LEN * len;
 600   int cur_size;
 601   int err = 0;
 602
 603   fseek(tt->wfp, 0, SEEK_END);
 604   cur_size = ftell(tt->wfp);
 605   if (cur_size == size) {
 606     return 0;
 607   }
 608   if (cur_size > size) {
 609     truncate(tt->fn, size);
 610   } else {
 611     err = expand_file(tt, (size - cur_size) / LINE_LEN);
 612     if (!err) {
 613       update_mapping(tt);
 614     } else {
 615       tt->fatal = 1;
 616     }
 617   }
 618
 619   return err;
 620 }
 621
 622 static struct cell *
 623 get_super_cell(struct text_trie *tt)
 624 {
 625   /* cached? */
 626   if (tt->valid_super) {
 627     return &tt->super;
 628   }
 629   /* read */
 630   if (decode_nth_cell(tt, &tt->super, 0)) {
 631     tt->valid_super = 1;
 632     return &tt->super;
 633   }
 634   /* create now */
 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) {
 641     return NULL;
 642   }
 643   write_back_cell(tt, &tt->super, 0);
 644   tt->valid_super = 1;
 645   return &tt->super;
 646 }
 647
 648 /* convenience function */
 649 static int
 650 get_array_size(struct text_trie *a)
 651 {
 652   struct cell *super = get_super_cell(a);
 653   int size = super->u.super.size;
 654   return size;
 655 }
 656
 657 /* convenience function */
 658 static int
 659 get_root_idx(struct text_trie *tt)
 660 {
 661   struct cell *super = get_super_cell(tt);
 662   if (!super) {
 663     return 0;
 664   }
 665   return super->u.super.root_cell;
 666 }
 667
 668 static int
 669 expand_array(struct text_trie *tt, int len)
 670 {
 671   int i;
 672   struct cell *super;
 673   int res;
 674   int size = get_array_size(tt);
 675   if (size >= len) {
 676     return 0;
 677   }
 678   /* expand file */
 679   res = set_file_size(tt, len);
 680   if (res) {
 681     return 1;
 682   }
 683   /* fill unused */
 684   super = get_super_cell(tt);
 685   for (i = super->u.super.size; i < len; i++) {
 686     struct cell ex_cell;
 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;
 691   }
 692   super->u.super.size = len;
 693   write_back_cell(tt, super, 0);
 694   return 0;
 695 }
 696
 697 void
 698 anthy_trie_print_array(struct text_trie *tt)
 699 {
 700   int i;
 701   int size = get_array_size(tt);
 702   print_cell(0, get_super_cell(tt));
 703   for (i = 1; i < size; i++) {
 704     struct cell c;
 705     decode_nth_cell(tt, &c, i);
 706     print_cell(i, &c);
 707     release_cell_str(&c);
 708   }
 709 }
 710
 711 /* get unused cell */
 712 static int
 713 get_unused_index(struct text_trie *tt)
 714 {
 715   struct cell *super;
 716   int unuse;
 717   struct cell new_cell;
 718
 719   super = get_super_cell(tt);
 720   unuse = super->u.super.first_unused;
 721   if (!unuse) {
 722     /* expand array */
 723     expand_array(tt, super->u.super.size + EXPAND_COUNT);
 724     unuse = super->u.super.first_unused;
 725     if (!unuse) {
 726       return 0;
 727     }
 728   }
 729   if (!decode_nth_cell(tt, &new_cell, unuse)) {
 730     tt->fatal = 1;
 731     return 0;
 732   }
 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);
 737   return unuse;
 738 }
 739
 740 static void
 741 free_cell(struct text_trie *tt, int idx)
 742 {
 743   struct cell *super = get_super_cell(tt);
 744   struct cell c;
 745   if (!decode_nth_cell(tt, &c, idx)) {
 746     tt->fatal = 1;
 747   } else {
 748     c.type = TT_UNUSED;
 749     c.u.next_unused = super->u.super.first_unused;
 750     write_back_cell(tt, &c, idx);
 751   }
 752   super->u.super.first_unused = idx;
 753   write_back_cell(tt, super, 0);
 754 }
 755
 756 static void
 757 load_super(struct text_trie *tt)
 758 {
 759   struct cell root, *super;
 760   int root_idx;
 761   super = get_super_cell(tt);
 762   if (!super) {
 763     tt->fatal = 1;
 764     return ;
 765   }
 766   /**/
 767   if (super->u.super.root_cell) {
 768     return ;
 769   }
 770   /**/
 771   root_idx = get_unused_index(tt);
 772   if (root_idx == 0) {
 773     tt->fatal = 1;
 774     return ;
 775   }
 776   root.u.node.key = 0;
 777   root.type = TT_NODE;
 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);
 783   /**/
 784   tt->super.u.super.root_cell = root_idx;
 785   write_back_cell(tt, super, 0);
 786 }
 787
 788 static void
 789 purge_cache(struct text_trie *tt)
 790 {
 791   if (tt) {
 792     tt->valid_super = 0;
 793   }
 794 }
 795
 796 static FILE *
 797 do_fopen(const char *fn, int create)
 798 {
 799   int fd;
 800   if (!create) {
 801     /* check file existance */
 802     FILE *fp;
 803     fp = fopen(fn, "r");
 804     if (!fp) {
 805       return NULL;
 806     }
 807     fclose(fp);
 808   }
 809   fd = open(fn, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR);
 810   if (fd == -1) {
 811     return NULL;
 812   }
 813   return fdopen(fd, "w");
 814 }
 815
 816 static struct text_trie *
 817 alloc_tt(const char *fn, FILE *wfp)
 818 {
 819   struct text_trie *tt;
 820   tt = malloc(sizeof(struct text_trie));
 821   tt->fatal = 0;
 822   tt->wfp = wfp;
 823   tt->valid_super = 0;
 824   tt->fn = strdup(fn);
 825   tt->mapping = NULL;
 826   return tt;
 827 }
 828
 829 static void
 830 clear_file(const char *fn)
 831 {
 832   FILE *fp = fopen(fn, "w");
 833   if (fp) {
 834     fclose(fp);
 835   }
 836 }
 837
 838 static struct text_trie *
 839 trie_open(const char *fn, int create, int do_retry)
 840 {
 841   struct text_trie *tt;
 842   FILE *fp;
 843   /**/
 844   fp = do_fopen(fn, create);
 845   if (!fp) {
 846     return NULL;
 847   }
 848   /**/
 849   tt = alloc_tt(fn, fp);
 850   if (!tt) {
 851     fclose(fp);
 852     return NULL;
 853   }
 854   /**/
 855   update_mapping(tt);
 856   load_super(tt);
 857   /**/
 858   if (tt->fatal) {
 859     anthy_trie_close(tt);
 860     if (!do_retry) {
 861       return NULL;
 862     }
 863     clear_file(fn);
 864     return trie_open(fn, create, 0);
 865   }
 866   /**/
 867   return tt;
 868 }
 869
 870
 871 /* API */
 872 struct text_trie *
 873 anthy_trie_open(const char *fn, int create)
 874 {
 875   struct text_trie *tt;
 876   anthy_priv_dic_lock();
 877   tt = trie_open(fn, create, 1);
 878   anthy_priv_dic_unlock();
 879   purge_cache(tt);
 880   return tt;
 881 }
 882
 883 /* API */
 884 void
 885 anthy_trie_close(struct text_trie *tt)
 886 {
 887   if (!tt) {
 888     return ;
 889   }
 890   fclose(tt->wfp);
 891   anthy_munmap(tt->mapping);
 892   free(tt->fn);
 893   free(tt);
 894 }
 895
 896 /* API */
 897 void
 898 anthy_trie_update_mapping(struct text_trie *tt)
 899 {
 900   if (!tt) {
 901     return ;
 902   }
 903   anthy_priv_dic_lock();
 904   update_mapping(tt);
 905   anthy_priv_dic_unlock();
 906 }
 907
 908 static void
 909 graft_child(struct text_trie *tt, int parent_idx, int new_idx)
 910 {
 911   struct cell parent_cell;
 912   struct cell new_cell;
 913   struct cell cur_youngest_cell;
 914   int cur_idx;
 915   /**/
 916   if (!decode_nth_node(tt, &parent_cell, parent_idx)) {
 917     return ;
 918   }
 919   /**/
 920   if (parent_cell.u.node.child == 0) {
 921     /* 1st child */
 922     parent_cell.u.node.child = new_idx;
 923     write_back_cell(tt, &parent_cell, parent_idx);
 924     return ;
 925   }
 926
 927   if (!decode_nth_node(tt, &cur_youngest_cell, parent_cell.u.node.child)) {
 928     return ;
 929   }
 930   if (!decode_nth_node(tt, &new_cell, new_idx)) {
 931     return ;
 932   }
 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);
 939     return;
 940   }
 941
 942   /* insert some order */
 943   cur_idx = parent_cell.u.node.child;
 944   while (cur_idx) {
 945     int next_idx;
 946     struct cell cur_cell, tmp_cell;
 947     struct cell *next_cell = NULL;
 948     if (!decode_nth_node(tt, &cur_cell, cur_idx)) {
 949       return ;
 950     }
 951     next_idx = cur_cell.u.node.next;
 952     /**/
 953     if (next_idx) {
 954       next_cell = decode_nth_node(tt, &tmp_cell, next_idx);
 955     }
 956     if (!next_cell) {
 957       /* append */
 958       new_cell.u.node.next = 0;
 959       cur_cell.u.node.next = new_idx;
 960       write_back_cell(tt, &cur_cell, cur_idx);
 961       break;
 962     } else {
 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);
 968         break;
 969       }
 970     }
 971     cur_idx = next_idx;
 972   }
 973   write_back_cell(tt, &new_cell, new_idx);
 974 }
 975
 976 static int
 977 find_child(struct text_trie *tt, int parent_idx, int key, int exact)
 978 {
 979   int child_idx;
 980   int prev_key;
 981   struct cell parent_cell;
 982
 983   if (!decode_nth_node(tt, &parent_cell, parent_idx)) {
 984     return 0;
 985   }
 986
 987   /**/
 988   prev_key = 0;
 989   child_idx = parent_cell.u.node.child;
 990
 991   /**/
 992   while (child_idx) {
 993     struct cell child_cell;
 994     int this_key;
 995     /**/
 996     if (!decode_nth_node(tt, &child_cell, child_idx)) {
 997       return 0;
 998     }
 999     this_key = child_cell.u.node.key;
1000     if (this_key <= prev_key) {
1001       return 0;
1002     }
1003     /**/
1004     if (exact && this_key == key) {
1005       return child_idx;
1006     }
1007     if (!exact && (this_key & 0xff00) == (key & 0xff00)) {
1008       return child_idx;
1009     }
1010     child_idx = child_cell.u.node.next;
1011     prev_key = this_key;
1012   }
1013   return 0;
1014 }
1015
1016 static int
1017 trie_search_rec(struct text_trie *tt, struct path *p,
1018                 int parent_idx, int create)
1019 {
1020   int child_idx;
1021   int key = p->path[p->cur];
1022   /* special case */
1023   if (p->cur == p->len) {
1024     return parent_idx;
1025   }
1026   /* scan child */
1027   child_idx = find_child(tt, parent_idx, key, 1);
1028   if (!child_idx) {
1029     struct cell child_cell;
1030     if (!create) {
1031       return 0;
1032     }
1033     /* add child */
1034     child_idx = get_unused_index(tt);
1035     if (!child_idx) {
1036       return 0;
1037     }
1038     if (!decode_nth_cell(tt, &child_cell, child_idx)) {
1039       return 0;
1040     }
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);
1048     /* graft */
1049     graft_child(tt, parent_idx, child_idx);
1050   }
1051   p->cur ++;
1052   key ++;
1053   if (!key) {
1054     return child_idx;
1055   }
1056   return trie_search_rec(tt, p, child_idx, create);
1057 }
1058
1059 static char *
1060 get_str_part(const char *str, int from)
1061 {
1062   char buf[OBJ_LEN+1];
1063   int i;
1064   for (i = 0; i < OBJ_LEN; i++) {
1065     buf[i] = str[from+i];
1066   }
1067   buf[i] = 0;
1068   return strdup(buf);
1069 }
1070
1071 static void
1072 release_body(struct text_trie *tt, int idx)
1073 {
1074   struct cell c;
1075   int tail_idx;
1076   if (!decode_nth_cell(tt, &c, idx) ||
1077       c.type != TT_BODY) {
1078     return ;
1079   }
1080   tail_idx = c.next_tail;
1081   while (tail_idx) {
1082     struct cell tail_cell;
1083     int tmp;
1084     if (!decode_nth_cell(tt, &tail_cell, tail_idx)) {
1085       break;
1086     }
1087     tmp = tail_cell.next_tail;
1088     free_cell(tt, tail_idx);
1089     tail_idx = tmp;
1090   }
1091   free_cell(tt, idx);
1092 }
1093
1094 static void
1095 set_body(struct text_trie *tt, int idx, const char *body_str)
1096 {
1097   int body_idx = get_unused_index(tt);
1098   int len;
1099   int i;
1100   struct cell node_cell;
1101   struct cell body_cell;
1102   struct cell prev_cell;
1103   struct cell tail_cell;
1104   int prev_idx;
1105   /**/
1106   if (!decode_nth_cell(tt, &node_cell, idx)) {
1107     return ;
1108   }
1109   if (node_cell.u.node.body) {
1110     release_body(tt, node_cell.u.node.body);
1111   }
1112   len = strlen(body_str);
1113   /**/
1114   node_cell.u.node.body = body_idx;
1115   write_back_cell(tt, &node_cell, idx);
1116   /**/
1117   if (!decode_nth_cell(tt, &body_cell, body_idx)) {
1118     return ;
1119   }
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);
1126   /**/
1127   if (!decode_nth_cell(tt, &body_cell, body_idx)) {
1128     return ;
1129   }
1130   /**/
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)) {
1136       return ;
1137     }
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);
1146     /**/
1147     prev_idx = tail_idx;
1148     prev_cell = tail_cell;
1149   }
1150   if (i != OBJ_LEN) {
1151     release_cell_str(&tail_cell);
1152   }
1153 }
1154
1155 static int
1156 trie_add(struct text_trie *tt, struct path *p, const char *body)
1157 {
1158   int root_idx = get_root_idx(tt);
1159   int target_idx;
1160   /**/
1161   if (root_idx == 0) {
1162     return -1;
1163   }
1164   target_idx = trie_search_rec(tt, p, root_idx, 1);
1165   if (target_idx) {
1166     set_body(tt, target_idx, body);
1167   }
1168   return 0;
1169 }
1170
1171 /* API */
1172 int
1173 anthy_trie_add(struct text_trie *tt, const char *key, const char *body)
1174 {
1175   int res;
1176   int len;
1177   struct path p;
1178   if (!tt || tt->fatal) {
1179     return -1;
1180   }
1181   len = strlen(key);
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();
1186   purge_cache(tt);
1187   return res;
1188 }
1189
1190 static int
1191 get_object_length(struct text_trie *tt, int body_idx)
1192 {
1193   int len = 0;
1194   int idx = body_idx;
1195   while (idx) {
1196     struct cell c;
1197     if (!decode_nth_cell(tt, &c, idx)) {
1198       return 0;
1199     }
1200     idx = c.next_tail;
1201     len += OBJ_LEN;
1202     release_cell_str(&c);
1203   }
1204   return len;
1205 }
1206
1207 static char *
1208 gather_str(struct text_trie *tt, int body_idx)
1209 {
1210   int idx;
1211   char *buf;
1212   int len;
1213   /* count length */
1214   len = get_object_length(tt, body_idx);
1215   if (len == 0) {
1216     return NULL;
1217   }
1218   /**/
1219   buf = malloc(len + 1);
1220   idx = body_idx;
1221   len = 0;
1222   while (idx) {
1223     struct cell c;
1224     if (!decode_nth_cell(tt, &c, idx)) {
1225       free(buf);
1226       return NULL;
1227     }
1228     if (len == 0) {
1229       sprintf(&buf[len], "%s", c.u.body.obj);
1230     } else {
1231       sprintf(&buf[len], "%s", c.u.tail.obj);
1232     }
1233     idx = c.next_tail;
1234     len += OBJ_LEN;
1235     release_cell_str(&c);
1236   }
1237   return buf;
1238 }
1239
1240 static char *
1241 trie_find(struct text_trie *tt, struct path *p)
1242 {
1243   int root_idx;
1244   int target_idx;
1245   root_idx = get_root_idx(tt);
1246   if (!root_idx) {
1247     return NULL;
1248   }
1249   target_idx = trie_search_rec(tt, p, root_idx, 0);
1250   if (target_idx) {
1251     struct cell target_cell;
1252     int body_idx;
1253     if (!decode_nth_node(tt, &target_cell, target_idx)) {
1254       return NULL;
1255     }
1256     body_idx = target_cell.u.node.body;
1257     if (body_idx) {
1258       return gather_str(tt, body_idx);
1259     }
1260   }
1261   return NULL;
1262 }
1263
1264 /* API */
1265 char *
1266 anthy_trie_find(struct text_trie *tt, char *key)
1267 {
1268   char *res;
1269   struct path p;
1270   int len;
1271   if (!tt || tt->fatal) {
1272     return NULL;
1273   }
1274   len = strlen(key);
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();
1279   purge_cache(tt);
1280   return res;
1281 }
1282
1283 static int
1284 do_find_next_key(struct text_trie *tt, struct path *p,
1285                  int root_idx, int target_idx)
1286 {
1287   struct cell *target_cell, tmp_cell;
1288   int prev_is_up = 0;
1289   target_cell = decode_nth_node(tt, &tmp_cell, target_idx);
1290   /**/
1291   do {
1292     /* one step */
1293     if (!target_cell) {
1294       return -1;
1295     }
1296     if (!prev_is_up && target_cell->u.node.child) {
1297       prev_is_up = 0;
1298       target_idx = target_cell->u.node.child;
1299       p->cur++;
1300     } else if (target_cell->u.node.next) {
1301       prev_is_up = 0;
1302       target_idx = target_cell->u.node.next;
1303     } else if (target_cell->u.node.parent) {
1304       prev_is_up = 1;
1305       target_idx = target_cell->u.node.parent;
1306       p->cur--;
1307     } else {
1308       return -1;
1309     }
1310     target_cell = decode_nth_node(tt, &tmp_cell, target_idx);
1311     if (!target_cell) {
1312       return -1;
1313     }
1314     if (p->cur >= p->max_len) {
1315       continue;
1316     }
1317     if (p->cur == 0) {
1318       return -1;
1319     }
1320     p->path[p->cur-1] = target_cell->u.node.key;
1321     if (!prev_is_up && target_cell->u.node.body) {
1322       return 0;
1323     }
1324   } while (target_idx != root_idx);
1325   return -1;
1326 }
1327
1328 static int
1329 find_partial_key(struct text_trie *tt, struct path *p, int idx)
1330 {
1331   struct cell c;
1332   if (!decode_nth_node(tt, &c, idx)) {
1333     return -1;
1334   }
1335   if (c.type != TT_NODE) {
1336     return -1;
1337   }
1338   p->len ++;
1339   p->path[p->cur] = c.u.node.key;
1340   p->cur ++;
1341   return 0;
1342 }
1343
1344 static int
1345 trie_find_next_key(struct text_trie *tt, struct path *p)
1346 {
1347   int root_idx = get_root_idx(tt);
1348   int target_idx;
1349   int tmp_idx;
1350   /**/
1351   target_idx = trie_search_rec(tt, p, root_idx, 0);
1352   if (target_idx > 0) {
1353     /* easy case */
1354     return do_find_next_key(tt, p, root_idx, target_idx);
1355   }
1356   if ((p->path[p->len-1] & 0xff) != 0) {
1357     /* simply not exist in tree */
1358     return -1;
1359   }
1360   /* special case */
1361   p->len --;
1362   p->cur = 0;
1363   target_idx = trie_search_rec(tt, p, root_idx, 0);
1364   tmp_idx = find_child(tt, target_idx, p->path[p->len], 0);
1365   if (tmp_idx) {
1366     return find_partial_key(tt, p, tmp_idx);
1367   }
1368   return do_find_next_key(tt, p, root_idx, target_idx);
1369 }
1370
1371
1372 /* API */
1373 char *
1374 anthy_trie_find_next_key(struct text_trie *tt, char *buf, int buf_len)
1375 {
1376   int res;
1377   struct path p;
1378   if (!tt || tt->fatal) {
1379     return NULL;
1380   }
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();
1385   purge_cache(tt);
1386   if (res) {
1387     return NULL;
1388   }
1389   path_copy_to_str(&p, buf, buf_len);
1390   return buf;
1391 }
1392
1393 static void
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))
1397 {
1398   int idx = get_root_idx(tt);
1399   int i, len = strlen(str);
1400   for (i = 0; i < len && i < buf_len; i++) {
1401     struct cell c;
1402     idx = find_child(tt, idx, str[i], 1);
1403     if (!idx) {
1404       return ;
1405     }
1406     if (!decode_nth_node(tt, &c, idx)) {
1407       return ;
1408     }
1409     buf[i] = idx;
1410     buf[i+1] = 0;
1411     if (c.u.node.body) {
1412       char *s = gather_str(tt, c.u.node.body);
1413       if (cb) {
1414         cb(buf, s);
1415       }
1416       free(s);
1417     }
1418   }
1419 }
1420
1421 void
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))
1425 {
1426   if (!tt || tt->fatal) {
1427     return ;
1428   }
1429   anthy_priv_dic_lock();
1430   trie_find_prefix(tt, str, buf, buf_len, cb);
1431   anthy_priv_dic_unlock();
1432   purge_cache(tt);
1433 }
1434
1435 static void
1436 disconnect(struct text_trie *tt, int parent_idx, int target_idx)
1437 {
1438   struct cell parent_cell;
1439   struct cell target_cell;
1440
1441   if (!decode_nth_node(tt, &parent_cell, parent_idx) ||
1442       !decode_nth_node(tt, &target_cell, target_idx)) {
1443     return ;
1444   }
1445
1446   if (parent_cell.u.node.child == target_idx) {
1447     /* 1st child */
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);
1455       return ;
1456     }
1457     free_cell(tt, target_idx);
1458   } else {
1459     /* not 1st child */
1460     int child_idx = parent_cell.u.node.child;
1461     while (child_idx) {
1462       struct cell cur;
1463       if (!decode_nth_cell(tt, &cur, child_idx)) {
1464         return ;
1465       }
1466       if (cur.u.node.next == target_idx) {
1467         /**/
1468         cur.u.node.next = target_cell.u.node.next;
1469         write_back_cell(tt, &cur, child_idx);
1470         free_cell(tt, target_idx);
1471         return ;
1472       }
1473       child_idx = cur.u.node.next;
1474     }
1475   }
1476 }
1477
1478 static void
1479 trie_delete(struct text_trie *tt, struct path *p)
1480 {
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);
1485   if (!target_idx) {
1486     return ;
1487   }
1488   if (!decode_nth_node(tt, &target_cell, target_idx)) {
1489     return ;
1490   }
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) {
1495     return ;
1496   }
1497   parent_idx = target_cell.u.node.parent;
1498   disconnect(tt, parent_idx, target_idx);
1499 }
1500
1501 /* API */
1502 void
1503 anthy_trie_delete(struct text_trie *tt, const char *key)
1504 {
1505   struct path p;
1506   int len;
1507   if (!tt || tt->fatal) {
1508     return ;
1509   }
1510   len = strlen(key);
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();
1515   purge_cache(tt);
1516 }