git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/tokyocabinet/tcutil.c

   1 /*************************************************************************************************
   2  * The utility API of Tokyo Cabinet
   3  *                                                      Copyright (C) 2006-2008 Mikio Hirabayashi
   4  * This file is part of Tokyo Cabinet.
   5  * Tokyo Cabinet is free software; you can redistribute it and/or modify it under the terms of
   6  * the GNU Lesser General Public License as published by the Free Software Foundation; either
   7  * version 2.1 of the License or any later version.  Tokyo Cabinet is distributed in the hope
   8  * that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  10  * License for more details.
  11  * You should have received a copy of the GNU Lesser General Public License along with Tokyo
  12  * Cabinet; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
  13  * Boston, MA 02111-1307 USA.
  14  *************************************************************************************************/
  15
  16
  17 #include "tcutil.h"
  18 #include "myconf.h"
  19
  20
  21 /*************************************************************************************************
  22  * basic utilities
  23  *************************************************************************************************/
  24
  25
  26 /* String containing the version information. */
  27 const char *tcversion = _TC_VERSION;
  28
  29
  30 /* Call back function for handling a fatal error. */
  31 void (*tcfatalfunc)(const char *message) = NULL;
  32
  33
  34 /* Allocate a region on memory. */
  35 void *tcmalloc(size_t size){
  36   assert(size > 0 && size < INT_MAX);
  37   char *p = malloc(size);
  38   if(!p) tcmyfatal("out of memory");
  39   return p;
  40 }
  41
  42
  43 /* Allocate a nullified region on memory. */
  44 void *tccalloc(size_t nmemb, size_t size){
  45   assert(nmemb > 0 && size < INT_MAX && size > 0 && size < INT_MAX);
  46   char *p = calloc(nmemb, size);
  47   if(!p) tcmyfatal("out of memory");
  48   return p;
  49 }
  50
  51
  52 /* Re-allocate a region on memory. */
  53 void *tcrealloc(void *ptr, size_t size){
  54   assert(size >= 0 && size < INT_MAX);
  55   char *p = realloc(ptr, size);
  56   if(!p) tcmyfatal("out of memory");
  57   return p;
  58 }
  59
  60
  61 /* Duplicate a region on memory. */
  62 void *tcmemdup(const void *ptr, size_t size){
  63   assert(ptr && size >= 0);
  64   char *p;
  65   TCMALLOC(p, size + 1);
  66   memcpy(p, ptr, size);
  67   p[size] = '\0';
  68   return p;
  69 }
  70
  71
  72 /* Duplicate a string on memory. */
  73 char *tcstrdup(const void *str){
  74   assert(str);
  75   int size = strlen(str);
  76   char *p;
  77   TCMALLOC(p, size + 1);
  78   memcpy(p, str, size);
  79   p[size] = '\0';
  80   return p;
  81 }
  82
  83
  84 /* Free a region on memory. */
  85 void tcfree(void *ptr){
  86   free(ptr);
  87 }
  88
  89
  90
  91 /*************************************************************************************************
  92  * extensible string
  93  *************************************************************************************************/
  94
  95
  96 #define TCXSTRUNIT     12                // allocation unit size of an extensible string
  97
  98
  99 /* private function prototypes */
 100 static void tcvxstrprintf(TCXSTR *xstr, const char *format, va_list ap);
 101
 102
 103 /* Create an extensible string object. */
 104 TCXSTR *tcxstrnew(void){
 105   TCXSTR *xstr;
 106   TCMALLOC(xstr, sizeof(*xstr));
 107   TCMALLOC(xstr->ptr, TCXSTRUNIT);
 108   xstr->size = 0;
 109   xstr->asize = TCXSTRUNIT;
 110   xstr->ptr[0] = '\0';
 111   return xstr;
 112 }
 113
 114
 115 /* Create an extensible string object from a character string. */
 116 TCXSTR *tcxstrnew2(const char *str){
 117   assert(str);
 118   TCXSTR *xstr;
 119   TCMALLOC(xstr, sizeof(*xstr));
 120   int size = strlen(str);
 121   int asize = tclmax(size + 1, TCXSTRUNIT);
 122   TCMALLOC(xstr->ptr, asize);
 123   xstr->size = size;
 124   xstr->asize = asize;
 125   memcpy(xstr->ptr, str, size + 1);
 126   return xstr;
 127 }
 128
 129
 130 /* Create an extensible string object with the initial allocation size. */
 131 TCXSTR *tcxstrnew3(int asiz){
 132   assert(asiz >= 0);
 133   asiz = tclmax(asiz, TCXSTRUNIT);
 134   TCXSTR *xstr;
 135   TCMALLOC(xstr, sizeof(*xstr));
 136   TCMALLOC(xstr->ptr, asiz);
 137   xstr->size = 0;
 138   xstr->asize = asiz;
 139   xstr->ptr[0] = '\0';
 140   return xstr;
 141 }
 142
 143
 144 /* Copy an extensible string object. */
 145 TCXSTR *tcxstrdup(const TCXSTR *xstr){
 146   assert(xstr);
 147   TCXSTR *nxstr;
 148   TCMALLOC(nxstr, sizeof(*nxstr));
 149   int asize = tclmax(xstr->size + 1, TCXSTRUNIT);
 150   TCMALLOC(nxstr->ptr, asize);
 151   nxstr->size = xstr->size;
 152   nxstr->asize = asize;
 153   memcpy(nxstr->ptr, xstr->ptr, xstr->size + 1);
 154   return nxstr;
 155 }
 156
 157
 158 /* Delete an extensible string object. */
 159 void tcxstrdel(TCXSTR *xstr){
 160   assert(xstr);
 161   free(xstr->ptr);
 162   free(xstr);
 163 }
 164
 165
 166 /* Concatenate a region to the end of an extensible string object. */
 167 void tcxstrcat(TCXSTR *xstr, const void *ptr, int size){
 168   assert(xstr && ptr && size >= 0);
 169   int nsize = xstr->size + size + 1;
 170   if(xstr->asize < nsize){
 171     while(xstr->asize < nsize){
 172       xstr->asize *= 2;
 173       if(xstr->asize < nsize) xstr->asize = nsize;
 174     }
 175     TCREALLOC(xstr->ptr, xstr->ptr, xstr->asize);
 176   }
 177   memcpy(xstr->ptr + xstr->size, ptr, size);
 178   xstr->size += size;
 179   xstr->ptr[xstr->size] = '\0';
 180 }
 181
 182
 183 /* Concatenate a character string to the end of an extensible string object. */
 184 void tcxstrcat2(TCXSTR *xstr, const char *str){
 185   assert(xstr && str);
 186   int size = strlen(str);
 187   int nsize = xstr->size + size + 1;
 188   if(xstr->asize < nsize){
 189     while(xstr->asize < nsize){
 190       xstr->asize *= 2;
 191       if(xstr->asize < nsize) xstr->asize = nsize;
 192     }
 193     TCREALLOC(xstr->ptr, xstr->ptr, xstr->asize);
 194   }
 195   memcpy(xstr->ptr + xstr->size, str, size + 1);
 196   xstr->size += size;
 197 }
 198
 199
 200 /* Get the pointer of the region of an extensible string object. */
 201 const void *tcxstrptr(const TCXSTR *xstr){
 202   assert(xstr);
 203   return xstr->ptr;
 204 }
 205
 206
 207 /* Get the size of the region of an extensible string object. */
 208 int tcxstrsize(const TCXSTR *xstr){
 209   assert(xstr);
 210   return xstr->size;
 211 }
 212
 213
 214 /* Clear an extensible string object. */
 215 void tcxstrclear(TCXSTR *xstr){
 216   assert(xstr);
 217   xstr->size = 0;
 218   xstr->ptr[0] = '\0';
 219 }
 220
 221
 222 /* Convert an extensible string object into a usual allocated region. */
 223 void *tcxstrtomalloc(TCXSTR *xstr){
 224   assert(xstr);
 225   char *ptr;
 226   ptr = xstr->ptr;
 227   free(xstr);
 228   return ptr;
 229 }
 230
 231
 232 /* Create an extensible string object from an allocated region. */
 233 TCXSTR *tcxstrfrommalloc(void *ptr, int size){
 234   TCXSTR *xstr;
 235   TCMALLOC(xstr, sizeof(*xstr));
 236   TCREALLOC(xstr->ptr, ptr, size + 1);
 237   xstr->ptr[size] = '\0';
 238   xstr->size = size;
 239   xstr->asize = size;
 240   return xstr;
 241 }
 242
 243
 244 /* Perform formatted output into an extensible string object. */
 245 void tcxstrprintf(TCXSTR *xstr, const char *format, ...){
 246   assert(xstr && format);
 247   va_list ap;
 248   va_start(ap, format);
 249   tcvxstrprintf(xstr, format, ap);
 250   va_end(ap);
 251 }
 252
 253
 254 /* Allocate a formatted string on memory. */
 255 char *tcsprintf(const char *format, ...){
 256   assert(format);
 257   TCXSTR *xstr = tcxstrnew();
 258   va_list ap;
 259   va_start(ap, format);
 260   tcvxstrprintf(xstr, format, ap);
 261   va_end(ap);
 262   return tcxstrtomalloc(xstr);
 263 }
 264
 265
 266 /* Perform formatted output into an extensible string object. */
 267 static void tcvxstrprintf(TCXSTR *xstr, const char *format, va_list ap){
 268   assert(xstr && format);
 269   while(*format != '\0'){
 270     if(*format == '%'){
 271       char cbuf[TCNUMBUFSIZ];
 272       cbuf[0] = '%';
 273       int cblen = 1;
 274       int lnum = 0;
 275       format++;
 276       while(strchr("0123456789 .+-hlLz", *format) && *format != '\0' &&
 277             cblen < TCNUMBUFSIZ - 1){
 278         if(*format == 'l' || *format == 'L') lnum++;
 279         cbuf[cblen++] = *(format++);
 280       }
 281       cbuf[cblen++] = *format;
 282       cbuf[cblen] = '\0';
 283       int tlen;
 284       char *tmp, tbuf[TCNUMBUFSIZ*2];
 285       switch(*format){
 286       case 's':
 287         tmp = va_arg(ap, char *);
 288         if(!tmp) tmp = "(null)";
 289         tcxstrcat2(xstr, tmp);
 290         break;
 291       case 'd':
 292         if(lnum >= 2){
 293           tlen = sprintf(tbuf, cbuf, va_arg(ap, long long));
 294         } else if(lnum >= 1){
 295           tlen = sprintf(tbuf, cbuf, va_arg(ap, long));
 296         } else {
 297           tlen = sprintf(tbuf, cbuf, va_arg(ap, int));
 298         }
 299         TCXSTRCAT(xstr, tbuf, tlen);
 300         break;
 301       case 'o': case 'u': case 'x': case 'X': case 'c':
 302         if(lnum >= 2){
 303           tlen = sprintf(tbuf, cbuf, va_arg(ap, unsigned long long));
 304         } else if(lnum >= 1){
 305           tlen = sprintf(tbuf, cbuf, va_arg(ap, unsigned long));
 306         } else {
 307           tlen = sprintf(tbuf, cbuf, va_arg(ap, unsigned int));
 308         }
 309         TCXSTRCAT(xstr, tbuf, tlen);
 310         break;
 311       case 'e': case 'E': case 'f': case 'g': case 'G':
 312         if(lnum >= 1){
 313           tlen = sprintf(tbuf, cbuf, va_arg(ap, long double));
 314         } else {
 315           tlen = sprintf(tbuf, cbuf, va_arg(ap, double));
 316         }
 317         TCXSTRCAT(xstr, tbuf, tlen);
 318         break;
 319       case '@':
 320         tmp = va_arg(ap, char *);
 321         if(!tmp) tmp = "(null)";
 322         while(*tmp){
 323           switch(*tmp){
 324           case '&': TCXSTRCAT(xstr, "&amp;", 5); break;
 325           case '<': TCXSTRCAT(xstr, "&lt;", 4); break;
 326           case '>': TCXSTRCAT(xstr, "&gt;", 4); break;
 327           case '"': TCXSTRCAT(xstr, "&quot;", 6); break;
 328           default:
 329             if(!((*tmp >= 0 && *tmp <= 0x8) || (*tmp >= 0x0e && *tmp <= 0x1f)))
 330               TCXSTRCAT(xstr, tmp, 1);
 331             break;
 332           }
 333           tmp++;
 334         }
 335         break;
 336       case '?':
 337         tmp = va_arg(ap, char *);
 338         if(!tmp) tmp = "(null)";
 339         while(*tmp){
 340           unsigned char c = *(unsigned char *)tmp;
 341           if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
 342              (c >= '0' && c <= '9') || (c != '\0' && strchr("_-.", c))){
 343             TCXSTRCAT(xstr, tmp, 1);
 344           } else {
 345             tlen = sprintf(tbuf, "%%%02X", c);
 346             TCXSTRCAT(xstr, tbuf, tlen);
 347           }
 348           tmp++;
 349         }
 350         break;
 351       case '%':
 352         TCXSTRCAT(xstr, "%", 1);
 353         break;
 354       }
 355     } else {
 356       TCXSTRCAT(xstr, format, 1);
 357     }
 358     format++;
 359   }
 360 }
 361
 362
 363
 364 /*************************************************************************************************
 365  * array list
 366  *************************************************************************************************/
 367
 368
 369 #define TCLISTUNIT     64                // allocation unit number of a list handle
 370
 371
 372 /* private function prototypes */
 373 static int tclistelemcmp(const void *a, const void *b);
 374 static int tclistelemcmpci(const void *a, const void *b);
 375
 376
 377 /* Create a list object. */
 378 TCLIST *tclistnew(void){
 379   TCLIST *list;
 380   TCMALLOC(list, sizeof(*list));
 381   list->anum = TCLISTUNIT;
 382   TCMALLOC(list->array, sizeof(list->array[0]) * list->anum);
 383   list->start = 0;
 384   list->num = 0;
 385   return list;
 386 }
 387
 388
 389 /* Create a list object. */
 390 TCLIST *tclistnew2(int anum){
 391   TCLIST *list;
 392   TCMALLOC(list, sizeof(*list));
 393   if(anum < 1) anum = 1;
 394   list->anum = anum;
 395   TCMALLOC(list->array, sizeof(list->array[0]) * list->anum);
 396   list->start = 0;
 397   list->num = 0;
 398   return list;
 399 }
 400
 401
 402 /* Copy a list object. */
 403 TCLIST *tclistdup(const TCLIST *list){
 404   assert(list);
 405   int num = list->num;
 406   if(num < 1) tclistnew();
 407   const TCLISTDATUM *array = list->array + list->start;
 408   TCLIST *nlist;
 409   TCMALLOC(nlist, sizeof(*nlist));
 410   TCLISTDATUM *narray;
 411   TCMALLOC(narray, sizeof(list->array[0]) * tclmax(num, 1));
 412   for(int i = 0; i < num; i++){
 413     int size = array[i].size;
 414     TCMALLOC(narray[i].ptr, tclmax(size + 1, TCXSTRUNIT));
 415     memcpy(narray[i].ptr, array[i].ptr, size + 1);
 416     narray[i].size = array[i].size;
 417   }
 418   nlist->anum = num;
 419   nlist->array = narray;
 420   nlist->start = 0;
 421   nlist->num = num;
 422   return nlist;
 423 }
 424
 425
 426 /* Delete a list object. */
 427 void tclistdel(TCLIST *list){
 428   assert(list);
 429   TCLISTDATUM *array = list->array;
 430   int end = list->start + list->num;
 431   for(int i = list->start; i < end; i++){
 432     free(array[i].ptr);
 433   }
 434   free(list->array);
 435   free(list);
 436 }
 437
 438
 439 /* Get the number of elements of a list object. */
 440 int tclistnum(const TCLIST *list){
 441   assert(list);
 442   return list->num;
 443 }
 444
 445
 446 /* Get the pointer to the region of an element of a list object. */
 447 const void *tclistval(const TCLIST *list, int index, int *sp){
 448   assert(list && index >= 0 && sp);
 449   if(index >= list->num) return NULL;
 450   index += list->start;
 451   *sp = list->array[index].size;
 452   return list->array[index].ptr;
 453 }
 454
 455
 456 /* Get the string of an element of a list object. */
 457 const char *tclistval2(const TCLIST *list, int index){
 458   assert(list && index >= 0);
 459   if(index >= list->num) return NULL;
 460   index += list->start;
 461   return list->array[index].ptr;
 462 }
 463
 464
 465 /* Add an element at the end of a list object. */
 466 void tclistpush(TCLIST *list, const void *ptr, int size){
 467   assert(list && ptr && size >= 0);
 468   int index = list->start + list->num;
 469   if(index >= list->anum){
 470     list->anum += list->num + 1;
 471     TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
 472   }
 473   TCLISTDATUM *array = list->array;
 474   TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
 475   memcpy(array[index].ptr, ptr, size);
 476   array[index].ptr[size] = '\0';
 477   array[index].size = size;
 478   list->num++;
 479 }
 480
 481
 482 /* Add a string element at the end of a list object. */
 483 void tclistpush2(TCLIST *list, const char *str){
 484   assert(list && str);
 485   int index = list->start + list->num;
 486   if(index >= list->anum){
 487     list->anum += list->num + 1;
 488     TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
 489   }
 490   int size = strlen(str);
 491   TCLISTDATUM *array = list->array;
 492   TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
 493   memcpy(array[index].ptr, str, size + 1);
 494   array[index].size = size;
 495   list->num++;
 496 }
 497
 498
 499 /* Add an allocated element at the end of a list object. */
 500 void tclistpushmalloc(TCLIST *list, void *ptr, int size){
 501   assert(list && ptr && size >= 0);
 502   int index = list->start + list->num;
 503   if(index >= list->anum){
 504     list->anum += list->num + 1;
 505     TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
 506   }
 507   TCLISTDATUM *array = list->array;
 508   TCREALLOC(array[index].ptr, ptr, size + 1);
 509   array[index].ptr[size] = '\0';
 510   array[index].size = size;
 511   list->num++;
 512 }
 513
 514
 515 /* Remove an element of the end of a list object. */
 516 void *tclistpop(TCLIST *list, int *sp){
 517   assert(list && sp);
 518   if(list->num < 1) return NULL;
 519   int index = list->start + list->num - 1;
 520   list->num--;
 521   *sp = list->array[index].size;
 522   return list->array[index].ptr;
 523 }
 524
 525
 526 /* Remove a string element of the end of a list object. */
 527 char *tclistpop2(TCLIST *list){
 528   assert(list);
 529   if(list->num < 1) return NULL;
 530   int index = list->start + list->num - 1;
 531   list->num--;
 532   return list->array[index].ptr;
 533 }
 534
 535
 536 /* Add an element at the top of a list object. */
 537 void tclistunshift(TCLIST *list, const void *ptr, int size){
 538   assert(list && ptr && size >= 0);
 539   if(list->start < 1){
 540     if(list->start + list->num >= list->anum){
 541       list->anum += list->num + 1;
 542       TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
 543     }
 544     list->start = list->anum - list->num;
 545     memmove(list->array + list->start, list->array, list->num * sizeof(list->array[0]));
 546   }
 547   int index = list->start - 1;
 548   TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
 549   memcpy(list->array[index].ptr, ptr, size);
 550   list->array[index].ptr[size] = '\0';
 551   list->array[index].size = size;
 552   list->start--;
 553   list->num++;
 554 }
 555
 556
 557 /* Add a string element at the top of a list object. */
 558 void tclistunshift2(TCLIST *list, const char *str){
 559   assert(list && str);
 560   if(list->start < 1){
 561     if(list->start + list->num >= list->anum){
 562       list->anum += list->num + 1;
 563       TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
 564     }
 565     list->start = list->anum - list->num;
 566     memmove(list->array + list->start, list->array, list->num * sizeof(list->array[0]));
 567   }
 568   int index = list->start - 1;
 569   int size = strlen(str);
 570   TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
 571   memcpy(list->array[index].ptr, str, size + 1);
 572   list->array[index].size = size;
 573   list->start--;
 574   list->num++;
 575 }
 576
 577
 578 /* Remove an element of the top of a list object. */
 579 void *tclistshift(TCLIST *list, int *sp){
 580   assert(list && sp);
 581   if(list->num < 1) return NULL;
 582   int index = list->start;
 583   list->start++;
 584   list->num--;
 585   *sp = list->array[index].size;
 586   void *rv = list->array[index].ptr;
 587   if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
 588     memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
 589     list->start = 0;
 590   }
 591   return rv;
 592 }
 593
 594
 595 /* Remove a string element of the top of a list object. */
 596 char *tclistshift2(TCLIST *list){
 597   assert(list);
 598   if(list->num < 1) return NULL;
 599   int index = list->start;
 600   list->start++;
 601   list->num--;
 602   void *rv = list->array[index].ptr;
 603   if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
 604     memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
 605     list->start = 0;
 606   }
 607   return rv;
 608 }
 609
 610
 611 /* Add an element at the specified location of a list object. */
 612 void tclistinsert(TCLIST *list, int index, const void *ptr, int size){
 613   assert(list && index >= 0 && ptr && size >= 0);
 614   if(index > list->num) return;
 615   index += list->start;
 616   if(list->start + list->num >= list->anum){
 617     list->anum += list->num + 1;
 618     TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
 619   }
 620   memmove(list->array + index + 1, list->array + index,
 621           sizeof(list->array[0]) * (list->start + list->num - index));
 622   TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
 623   memcpy(list->array[index].ptr, ptr, size);
 624   list->array[index].ptr[size] = '\0';
 625   list->array[index].size = size;
 626   list->num++;
 627 }
 628
 629
 630 /* Add a string element at the specified location of a list object. */
 631 void tclistinsert2(TCLIST *list, int index, const char *str){
 632   assert(list && index >= 0 && str);
 633   if(index > list->num) return;
 634   index += list->start;
 635   if(list->start + list->num >= list->anum){
 636     list->anum += list->num + 1;
 637     TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
 638   }
 639   memmove(list->array + index + 1, list->array + index,
 640           sizeof(list->array[0]) * (list->start + list->num - index));
 641   int size = strlen(str);
 642   TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
 643   memcpy(list->array[index].ptr, str, size);
 644   list->array[index].ptr[size] = '\0';
 645   list->array[index].size = size;
 646   list->num++;
 647 }
 648
 649
 650 /* Remove an element at the specified location of a list object. */
 651 void *tclistremove(TCLIST *list, int index, int *sp){
 652   assert(list && index >= 0 && sp);
 653   if(index >= list->num) return NULL;
 654   index += list->start;
 655   char *ptr = list->array[index].ptr;
 656   *sp = list->array[index].size;
 657   list->num--;
 658   memmove(list->array + index, list->array + index + 1,
 659           sizeof(list->array[0]) * (list->start + list->num - index));
 660   return ptr;
 661 }
 662
 663
 664 /* Remove a string element at the specified location of a list object. */
 665 char *tclistremove2(TCLIST *list, int index){
 666   assert(list && index >= 0);
 667   if(index >= list->num) return NULL;
 668   index += list->start;
 669   char *ptr = list->array[index].ptr;
 670   list->num--;
 671   memmove(list->array + index, list->array + index + 1,
 672           sizeof(list->array[0]) * (list->start + list->num - index));
 673   return ptr;
 674 }
 675
 676
 677 /* Overwrite an element at the specified location of a list object. */
 678 void tclistover(TCLIST *list, int index, const void *ptr, int size){
 679   assert(list && index >= 0 && ptr && size >= 0);
 680   if(index >= list->num) return;
 681   index += list->start;
 682   if(size > list->array[index].size)
 683     TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
 684   memcpy(list->array[index].ptr, ptr, size);
 685   list->array[index].size = size;
 686   list->array[index].ptr[size] = '\0';
 687 }
 688
 689
 690 /* Overwrite a string element at the specified location of a list object. */
 691 void tclistover2(TCLIST *list, int index, const char *str){
 692   assert(list && index >= 0 && str);
 693   if(index >= list->num) return;
 694   index += list->start;
 695   int size = strlen(str);
 696   if(size > list->array[index].size)
 697     TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
 698   memcpy(list->array[index].ptr, str, size + 1);
 699   list->array[index].size = size;
 700 }
 701
 702
 703 /* Sort elements of a list object in lexical order. */
 704 void tclistsort(TCLIST *list){
 705   assert(list);
 706   qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmp);
 707 }
 708
 709
 710 /* Sort elements of a list object in case-insensitive lexical order. */
 711 void tclistsortci(TCLIST *list){
 712   assert(list);
 713   qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmpci);
 714 }
 715
 716
 717 /* Sort elements of a list object by an arbitrary comparison function. */
 718 void tclistsortex(TCLIST *list, int (*cmp)(const TCLISTDATUM *, const TCLISTDATUM *)){
 719   assert(list && cmp);
 720   qsort(list->array + list->start, list->num, sizeof(list->array[0]),
 721         (int (*)(const void *, const void *))cmp);
 722 }
 723
 724
 725 /* Search a list object for an element using liner search. */
 726 int tclistlsearch(const TCLIST *list, const void *ptr, int size){
 727   assert(list && ptr && size >= 0);
 728   int end = list->start + list->num;
 729   for(int i = list->start; i < end; i++){
 730     if(list->array[i].size == size && !memcmp(list->array[i].ptr, ptr, size))
 731       return i - list->start;
 732   }
 733   return -1;
 734 }
 735
 736
 737 /* Search a list object for an element using binary search. */
 738 int tclistbsearch(const TCLIST *list, const void *ptr, int size){
 739   assert(list && ptr && size >= 0);
 740   TCLISTDATUM key;
 741   key.ptr = (char *)ptr;
 742   key.size = size;
 743   TCLISTDATUM *res = bsearch(&key, list->array + list->start,
 744                              list->num, sizeof(list->array[0]), tclistelemcmp);
 745   return res ? res - list->array - list->start : -1;
 746 }
 747
 748
 749 /* Clear a list object. */
 750 void tclistclear(TCLIST *list){
 751   assert(list);
 752   TCLISTDATUM *array = list->array;
 753   int end = list->start + list->num;
 754   for(int i = list->start; i < end; i++){
 755     free(array[i].ptr);
 756   }
 757   list->start = 0;
 758   list->num = 0;
 759 }
 760
 761
 762 /* Serialize a list object into a byte array. */
 763 void *tclistdump(const TCLIST *list, int *sp){
 764   assert(list && sp);
 765   const TCLISTDATUM *array = list->array;
 766   int end = list->start + list->num;
 767   int tsiz = 0;
 768   for(int i = list->start; i < end; i++){
 769     tsiz += array[i].size + sizeof(int);
 770   }
 771   char *buf;
 772   TCMALLOC(buf, tsiz + 1);
 773   char *wp = buf;
 774   for(int i = list->start; i < end; i++){
 775     int step;
 776     TCSETVNUMBUF(step, wp, array[i].size);
 777     wp += step;
 778     memcpy(wp, array[i].ptr, array[i].size);
 779     wp += array[i].size;
 780   }
 781   *sp = wp - buf;
 782   return buf;
 783 }
 784
 785
 786 /* Create a list object from a serialized byte array. */
 787 TCLIST *tclistload(const void *ptr, int size){
 788   assert(ptr && size >= 0);
 789   TCLIST *list;
 790   TCMALLOC(list, sizeof(*list));
 791   int anum = size / sizeof(int) + 1;
 792   TCLISTDATUM *array;
 793   TCMALLOC(array, sizeof(array[0]) * anum);
 794   int num = 0;
 795   const char *rp = ptr;
 796   const char *ep = (char *)ptr + size;
 797   while(rp < ep){
 798     int step, vsiz;
 799     TCREADVNUMBUF(rp, vsiz, step);
 800     rp += step;
 801     if(num >= anum){
 802       anum *= 2;
 803       TCREALLOC(array, array, anum * sizeof(array[0]));
 804     }
 805     TCMALLOC(array[num].ptr, tclmax(vsiz + 1, TCXSTRUNIT));
 806     memcpy(array[num].ptr, rp, vsiz);
 807     array[num].ptr[vsiz] = '\0';
 808     array[num].size = vsiz;
 809     num++;
 810     rp += vsiz;
 811   }
 812   list->anum = anum;
 813   list->array = array;
 814   list->start = 0;
 815   list->num = num;
 816   return list;
 817 }
 818
 819
 820 /* Compare two list elements in lexical order.
 821    `a' specifies the pointer to one element.
 822    `b' specifies the pointer to the other element.
 823    The return value is positive if the former is big, negative if the latter is big, 0 if both
 824    are equivalent. */
 825 static int tclistelemcmp(const void *a, const void *b){
 826   assert(a && b);
 827   unsigned char *ao = (unsigned char *)((TCLISTDATUM *)a)->ptr;
 828   unsigned char *bo = (unsigned char *)((TCLISTDATUM *)b)->ptr;
 829   int size = (((TCLISTDATUM *)a)->size < ((TCLISTDATUM *)b)->size) ?
 830     ((TCLISTDATUM *)a)->size : ((TCLISTDATUM *)b)->size;
 831   for(int i = 0; i < size; i++){
 832     if(ao[i] > bo[i]) return 1;
 833     if(ao[i] < bo[i]) return -1;
 834   }
 835   return ((TCLISTDATUM *)a)->size - ((TCLISTDATUM *)b)->size;
 836 }
 837
 838
 839 /* Compare two list elements in case-insensitive lexical order..
 840    `a' specifies the pointer to one element.
 841    `b' specifies the pointer to the other element.
 842    The return value is positive if the former is big, negative if the latter is big, 0 if both
 843    are equivalent. */
 844 static int tclistelemcmpci(const void *a, const void *b){
 845   assert(a && b);
 846   TCLISTDATUM *ap = (TCLISTDATUM *)a;
 847   TCLISTDATUM *bp = (TCLISTDATUM *)b;
 848   unsigned char *ao = (unsigned char *)ap->ptr;
 849   unsigned char *bo = (unsigned char *)bp->ptr;
 850   int size = (ap->size < bp->size) ? ap->size : bp->size;
 851   for(int i = 0; i < size; i++){
 852     int ac = ao[i];
 853     bool ab = false;
 854     if(ac >= 'A' && ac <= 'Z'){
 855       ac += 'a' - 'A';
 856       ab = true;
 857     }
 858     int bc = bo[i];
 859     bool bb = false;
 860     if(bc >= 'A' && bc <= 'Z'){
 861       bc += 'a' - 'A';
 862       bb = true;
 863     }
 864     if(ac > bc) return 1;
 865     if(ac < bc) return -1;
 866     if(!ab && bb) return 1;
 867     if(ab && !bb) return -1;
 868   }
 869   return ap->size - bp->size;
 870 }
 871
 872
 873
 874 /*************************************************************************************************
 875  * hash map
 876  *************************************************************************************************/
 877
 878
 879 #define TCMAPBNUM      4093              // allocation unit number of a map
 880 #define TCMAPCSUNIT    52                // small allocation unit size of map concatenation
 881 #define TCMAPCBUNIT    252               // big allocation unit size of map concatenation
 882
 883 /* get the first hash value */
 884 #define TCMAPHASH1(TC_res, TC_kbuf, TC_ksiz) \
 885   do { \
 886     const unsigned char *_TC_p = (const unsigned char *)(TC_kbuf); \
 887     int _TC_ksiz = TC_ksiz; \
 888     for((TC_res) = 19780211; _TC_ksiz--;){ \
 889       (TC_res) = ((TC_res) << 5) + ((TC_res) << 2) + (TC_res) + *(_TC_p)++; \
 890     } \
 891   } while(false)
 892
 893 /* get the second hash value */
 894 #define TCMAPHASH2(TC_res, TC_kbuf, TC_ksiz) \
 895   do { \
 896     const unsigned char *_TC_p = (const unsigned char *)(TC_kbuf) + TC_ksiz - 1; \
 897     int _TC_ksiz = TC_ksiz; \
 898     for((TC_res) = 0x13579bdf; _TC_ksiz--;){ \
 899       (TC_res) = ((TC_res) << 5) - (TC_res) + *(_TC_p)--; \
 900     } \
 901   } while(false)
 902
 903 /* get the size of padding bytes for pointer alignment */
 904 #define TCALIGNPAD(TC_hsiz) \
 905   (((TC_hsiz | ~-(int)sizeof(void *)) + 1) - TC_hsiz)
 906
 907 /* compare two keys */
 908 #define TCKEYCMP(TC_abuf, TC_asiz, TC_bbuf, TC_bsiz) \
 909   ((TC_asiz > TC_bsiz) ? 1 : (TC_asiz < TC_bsiz) ? -1 : memcmp(TC_abuf, TC_bbuf, TC_asiz))
 910
 911
 912 /* Create a map object. */
 913 TCMAP *tcmapnew(void){
 914   return tcmapnew2(TCMAPBNUM);
 915 }
 916
 917
 918 /* Create a map object with specifying the number of the buckets. */
 919 TCMAP *tcmapnew2(uint32_t bnum){
 920   if(bnum < 1) bnum = 1;
 921   TCMAP *map;
 922   TCMALLOC(map, sizeof(*map));
 923   TCMAPREC **buckets;
 924   TCCALLOC(buckets, bnum, sizeof(map->buckets[0]));
 925   map->buckets = buckets;
 926   map->first = NULL;
 927   map->last = NULL;
 928   map->cur = NULL;
 929   map->bnum = bnum;
 930   map->rnum = 0;
 931   map->msiz = 0;
 932   return map;
 933 }
 934
 935
 936 /* Copy a map object. */
 937 TCMAP *tcmapdup(const TCMAP *map){
 938   assert(map);
 939   TCMAP *nmap = tcmapnew2(tclmax(tclmax(map->bnum, map->rnum), TCMAPBNUM));
 940   TCMAPREC *cur = map->cur;
 941   const char *kbuf;
 942   int ksiz;
 943   ((TCMAP *)map)->cur = map->first;
 944   while((kbuf = tcmapiternext((TCMAP *)map, &ksiz)) != NULL){
 945     int vsiz;
 946     const char *vbuf = tcmapiterval(kbuf, &vsiz);
 947     tcmapputkeep(nmap, kbuf, ksiz, vbuf, vsiz);
 948   }
 949   ((TCMAP *)map)->cur = cur;
 950   return nmap;
 951 }
 952
 953
 954 /* Close a map object. */
 955 void tcmapdel(TCMAP *map){
 956   assert(map);
 957   TCMAPREC *rec = map->first;
 958   while(rec){
 959     TCMAPREC *next = rec->next;
 960     free(rec);
 961     rec = next;
 962   }
 963   free(map->buckets);
 964   free(map);
 965 }
 966
 967
 968 /* Store a record into a map object. */
 969 void tcmapput(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 970   assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 971   unsigned int hash;
 972   TCMAPHASH1(hash, kbuf, ksiz);
 973   int bidx = hash % map->bnum;
 974   TCMAPREC *rec = map->buckets[bidx];
 975   TCMAPREC **entp = map->buckets + bidx;
 976   TCMAPHASH2(hash, kbuf, ksiz);
 977   while(rec){
 978     if(hash > rec->hash){
 979       entp = &(rec->left);
 980       rec = rec->left;
 981     } else if(hash < rec->hash){
 982       entp = &(rec->right);
 983       rec = rec->right;
 984     } else {
 985       char *dbuf = (char *)rec + sizeof(*rec);
 986       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
 987       if(kcmp < 0){
 988         entp = &(rec->left);
 989         rec = rec->left;
 990       } else if(kcmp > 0){
 991         entp = &(rec->right);
 992         rec = rec->right;
 993       } else {
 994         map->msiz += vsiz - rec->vsiz;
 995         int psiz = TCALIGNPAD(ksiz);
 996         if(vsiz > rec->vsiz){
 997           TCMAPREC *old = rec;
 998           TCREALLOC(rec, rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
 999           if(rec != old){
1000             if(map->first == old) map->first = rec;
1001             if(map->last == old) map->last = rec;
1002             if(map->cur == old) map->cur = rec;
1003             if(*entp == old) *entp = rec;
1004             if(rec->prev) rec->prev->next = rec;
1005             if(rec->next) rec->next->prev = rec;
1006             dbuf = (char *)rec + sizeof(*rec);
1007           }
1008         }
1009         memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
1010         dbuf[ksiz+psiz+vsiz] = '\0';
1011         rec->vsiz = vsiz;
1012         return;
1013       }
1014     }
1015   }
1016   int psiz = TCALIGNPAD(ksiz);
1017   map->msiz += ksiz + vsiz;
1018   TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
1019   char *dbuf = (char *)rec + sizeof(*rec);
1020   memcpy(dbuf, kbuf, ksiz);
1021   dbuf[ksiz] = '\0';
1022   rec->ksiz = ksiz;
1023   memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
1024   dbuf[ksiz+psiz+vsiz] = '\0';
1025   rec->vsiz = vsiz;
1026   rec->hash = hash;
1027   rec->left = NULL;
1028   rec->right = NULL;
1029   rec->prev = map->last;
1030   rec->next = NULL;
1031   *entp = rec;
1032   if(!map->first) map->first = rec;
1033   if(map->last) map->last->next = rec;
1034   map->last = rec;
1035   map->rnum++;
1036 }
1037
1038
1039 /* Store a string record into a map object. */
1040 void tcmapput2(TCMAP *map, const char *kstr, const char *vstr){
1041   assert(map && kstr && vstr);
1042   tcmapput(map, kstr, strlen(kstr), vstr, strlen(vstr));
1043 }
1044
1045
1046 /* Store a record of the value of two regions into a map object. */
1047 void tcmapput3(TCMAP *map, const char *kbuf, int ksiz,
1048                const void *fvbuf, int fvsiz, const char *lvbuf, int lvsiz){
1049   assert(map && kbuf && ksiz >= 0 && fvbuf && fvsiz >= 0 && lvbuf && lvsiz >= 0);
1050   unsigned int hash;
1051   TCMAPHASH1(hash, kbuf, ksiz);
1052   int bidx = hash % map->bnum;
1053   TCMAPREC *rec = map->buckets[bidx];
1054   TCMAPREC **entp = map->buckets + bidx;
1055   TCMAPHASH2(hash, kbuf, ksiz);
1056   while(rec){
1057     if(hash > rec->hash){
1058       entp = &(rec->left);
1059       rec = rec->left;
1060     } else if(hash < rec->hash){
1061       entp = &(rec->right);
1062       rec = rec->right;
1063     } else {
1064       char *dbuf = (char *)rec + sizeof(*rec);
1065       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1066       if(kcmp < 0){
1067         entp = &(rec->left);
1068         rec = rec->left;
1069       } else if(kcmp > 0){
1070         entp = &(rec->right);
1071         rec = rec->right;
1072       } else {
1073         int vsiz = fvsiz + lvsiz;
1074         map->msiz += vsiz - rec->vsiz;
1075         int psiz = TCALIGNPAD(ksiz);
1076         ksiz += psiz;
1077         if(vsiz > rec->vsiz){
1078           TCMAPREC *old = rec;
1079           TCREALLOC(rec, rec, sizeof(*rec) + ksiz + vsiz + 1);
1080           if(rec != old){
1081             if(map->first == old) map->first = rec;
1082             if(map->last == old) map->last = rec;
1083             if(map->cur == old) map->cur = rec;
1084             if(*entp == old) *entp = rec;
1085             if(rec->prev) rec->prev->next = rec;
1086             if(rec->next) rec->next->prev = rec;
1087             dbuf = (char *)rec + sizeof(*rec);
1088           }
1089         }
1090         memcpy(dbuf + ksiz, fvbuf, fvsiz);
1091         memcpy(dbuf + ksiz + fvsiz, lvbuf, lvsiz);
1092         dbuf[ksiz+vsiz] = '\0';
1093         rec->vsiz = vsiz;
1094         return;
1095       }
1096     }
1097   }
1098   int vsiz = fvsiz + lvsiz;
1099   int psiz = TCALIGNPAD(ksiz);
1100   map->msiz += ksiz + vsiz;
1101   TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
1102   char *dbuf = (char *)rec + sizeof(*rec);
1103   memcpy(dbuf, kbuf, ksiz);
1104   dbuf[ksiz] = '\0';
1105   rec->ksiz = ksiz;
1106   ksiz += psiz;
1107   memcpy(dbuf + ksiz, fvbuf, fvsiz);
1108   memcpy(dbuf + ksiz + fvsiz, lvbuf, lvsiz);
1109   dbuf[ksiz+vsiz] = '\0';
1110   rec->vsiz = vsiz;
1111   rec->hash = hash;
1112   rec->left = NULL;
1113   rec->right = NULL;
1114   rec->prev = map->last;
1115   rec->next = NULL;
1116   *entp = rec;
1117   if(!map->first) map->first = rec;
1118   if(map->last) map->last->next = rec;
1119   map->last = rec;
1120   map->rnum++;
1121 }
1122
1123
1124 /* Store a new record into a map object. */
1125 bool tcmapputkeep(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
1126   assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1127   unsigned int hash;
1128   TCMAPHASH1(hash, kbuf, ksiz);
1129   int bidx = hash % map->bnum;
1130   TCMAPREC *rec = map->buckets[bidx];
1131   TCMAPREC **entp = map->buckets + bidx;
1132   TCMAPHASH2(hash, kbuf, ksiz);
1133   while(rec){
1134     if(hash > rec->hash){
1135       entp = &(rec->left);
1136       rec = rec->left;
1137     } else if(hash < rec->hash){
1138       entp = &(rec->right);
1139       rec = rec->right;
1140     } else {
1141       char *dbuf = (char *)rec + sizeof(*rec);
1142       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1143       if(kcmp < 0){
1144         entp = &(rec->left);
1145         rec = rec->left;
1146       } else if(kcmp > 0){
1147         entp = &(rec->right);
1148         rec = rec->right;
1149       } else {
1150         return false;
1151       }
1152     }
1153   }
1154   int psiz = TCALIGNPAD(ksiz);
1155   map->msiz += ksiz + vsiz;
1156   TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
1157   char *dbuf = (char *)rec + sizeof(*rec);
1158   memcpy(dbuf, kbuf, ksiz);
1159   dbuf[ksiz] = '\0';
1160   rec->ksiz = ksiz;
1161   memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
1162   dbuf[ksiz+psiz+vsiz] = '\0';
1163   rec->vsiz = vsiz;
1164   rec->hash = hash;
1165   rec->left = NULL;
1166   rec->right = NULL;
1167   rec->prev = map->last;
1168   rec->next = NULL;
1169   *entp = rec;
1170   if(!map->first) map->first = rec;
1171   if(map->last) map->last->next = rec;
1172   map->last = rec;
1173   map->rnum++;
1174   return true;
1175 }
1176
1177
1178 /* Store a new string record into a map object.
1179    `map' specifies the map object.
1180    `kstr' specifies the string of the key.
1181    `vstr' specifies the string of the value.
1182    If successful, the return value is true, else, it is false.
1183    If a record with the same key exists in the database, this function has no effect. */
1184 bool tcmapputkeep2(TCMAP *map, const char *kstr, const char *vstr){
1185   assert(map && kstr && vstr);
1186   return tcmapputkeep(map, kstr, strlen(kstr), vstr, strlen(vstr));
1187 }
1188
1189
1190 /* Concatenate a value at the end of the value of the existing record in a map object. */
1191 void tcmapputcat(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
1192   assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1193   unsigned int hash;
1194   TCMAPHASH1(hash, kbuf, ksiz);
1195   int bidx = hash % map->bnum;
1196   TCMAPREC *rec = map->buckets[bidx];
1197   TCMAPREC **entp = map->buckets + bidx;
1198   TCMAPHASH2(hash, kbuf, ksiz);
1199   while(rec){
1200     if(hash > rec->hash){
1201       entp = &(rec->left);
1202       rec = rec->left;
1203     } else if(hash < rec->hash){
1204       entp = &(rec->right);
1205       rec = rec->right;
1206     } else {
1207       char *dbuf = (char *)rec + sizeof(*rec);
1208       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1209       if(kcmp < 0){
1210         entp = &(rec->left);
1211         rec = rec->left;
1212       } else if(kcmp > 0){
1213         entp = &(rec->right);
1214         rec = rec->right;
1215       } else {
1216         map->msiz += vsiz;
1217         int psiz = TCALIGNPAD(ksiz);
1218         int asiz = sizeof(*rec) + ksiz + psiz + rec->vsiz + vsiz + 1;
1219         int unit = (asiz <= TCMAPCSUNIT) ? TCMAPCSUNIT : TCMAPCBUNIT;
1220         asiz = (asiz - 1) + unit - (asiz - 1) % unit;
1221         TCMAPREC *old = rec;
1222         TCREALLOC(rec, rec, asiz);
1223         if(rec != old){
1224           if(map->first == old) map->first = rec;
1225           if(map->last == old) map->last = rec;
1226           if(map->cur == old) map->cur = rec;
1227           if(*entp == old) *entp = rec;
1228           if(rec->prev) rec->prev->next = rec;
1229           if(rec->next) rec->next->prev = rec;
1230           dbuf = (char *)rec + sizeof(*rec);
1231         }
1232         memcpy(dbuf + ksiz + psiz + rec->vsiz, vbuf, vsiz);
1233         dbuf[ksiz+psiz+rec->vsiz+vsiz] = '\0';
1234         rec->vsiz += vsiz;
1235         return;
1236       }
1237     }
1238   }
1239   int psiz = TCALIGNPAD(ksiz);
1240   int asiz = sizeof(*rec) + ksiz + psiz + vsiz + 1;
1241   int unit = (asiz <= TCMAPCSUNIT) ? TCMAPCSUNIT : TCMAPCBUNIT;
1242   asiz = (asiz - 1) + unit - (asiz - 1) % unit;
1243   map->msiz += ksiz + vsiz;
1244   TCMALLOC(rec, asiz);
1245   char *dbuf = (char *)rec + sizeof(*rec);
1246   memcpy(dbuf, kbuf, ksiz);
1247   dbuf[ksiz] = '\0';
1248   rec->ksiz = ksiz;
1249   memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
1250   dbuf[ksiz+psiz+vsiz] = '\0';
1251   rec->vsiz = vsiz;
1252   rec->hash = hash;
1253   rec->left = NULL;
1254   rec->right = NULL;
1255   rec->prev = map->last;
1256   rec->next = NULL;
1257   *entp = rec;
1258   if(!map->first) map->first = rec;
1259   if(map->last) map->last->next = rec;
1260   map->last = rec;
1261   map->rnum++;
1262 }
1263
1264
1265 /* Concatenate a string value at the end of the value of the existing record in a map object. */
1266 void tcmapputcat2(TCMAP *map, const char *kstr, const char *vstr){
1267   assert(map && kstr && vstr);
1268   tcmapputcat(map, kstr, strlen(kstr), vstr, strlen(vstr));
1269 }
1270
1271
1272 /* Remove a record of a map object. */
1273 bool tcmapout(TCMAP *map, const void *kbuf, int ksiz){
1274   assert(map && kbuf && ksiz >= 0);
1275   unsigned int hash;
1276   TCMAPHASH1(hash, kbuf, ksiz);
1277   int bidx = hash % map->bnum;
1278   TCMAPREC *rec = map->buckets[bidx];
1279   TCMAPREC **entp = map->buckets + bidx;
1280   TCMAPHASH2(hash, kbuf, ksiz);
1281   while(rec){
1282     if(hash > rec->hash){
1283       entp = &(rec->left);
1284       rec = rec->left;
1285     } else if(hash < rec->hash){
1286       entp = &(rec->right);
1287       rec = rec->right;
1288     } else {
1289       char *dbuf = (char *)rec + sizeof(*rec);
1290       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1291       if(kcmp < 0){
1292         entp = &(rec->left);
1293         rec = rec->left;
1294       } else if(kcmp > 0){
1295         entp = &(rec->right);
1296         rec = rec->right;
1297       } else {
1298         map->rnum--;
1299         map->msiz -= rec->ksiz + rec->vsiz;
1300         if(rec->prev) rec->prev->next = rec->next;
1301         if(rec->next) rec->next->prev = rec->prev;
1302         if(rec == map->first) map->first = rec->next;
1303         if(rec == map->last) map->last = rec->prev;
1304         if(rec == map->cur) map->cur = rec->next;
1305         if(rec->left && !rec->right){
1306           *entp = rec->left;
1307         } else if(!rec->left && rec->right){
1308           *entp = rec->right;
1309         } else if(!rec->left && !rec->left){
1310           *entp = NULL;
1311         } else {
1312           *entp = rec->left;
1313           TCMAPREC *tmp = *entp;
1314           while(tmp->right){
1315             tmp = tmp->right;
1316           }
1317           tmp->right = rec->right;
1318         }
1319         free(rec);
1320         return true;
1321       }
1322     }
1323   }
1324   return false;
1325 }
1326
1327
1328 /* Remove a string record of a map object. */
1329 bool tcmapout2(TCMAP *map, const char *kstr){
1330   assert(map && kstr);
1331   return tcmapout(map, kstr, strlen(kstr));
1332 }
1333
1334
1335 /* Retrieve a record in a map object. */
1336 const void *tcmapget(const TCMAP *map, const void *kbuf, int ksiz, int *sp){
1337   assert(map && kbuf && ksiz >= 0 && sp);
1338   unsigned int hash;
1339   TCMAPHASH1(hash, kbuf, ksiz);
1340   TCMAPREC *rec = map->buckets[hash%map->bnum];
1341   TCMAPHASH2(hash, kbuf, ksiz);
1342   while(rec){
1343     if(hash > rec->hash){
1344       rec = rec->left;
1345     } else if(hash < rec->hash){
1346       rec = rec->right;
1347     } else {
1348       char *dbuf = (char *)rec + sizeof(*rec);
1349       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1350       if(kcmp < 0){
1351         rec = rec->left;
1352       } else if(kcmp > 0){
1353         rec = rec->right;
1354       } else {
1355         *sp = rec->vsiz;
1356         return dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz);
1357       }
1358     }
1359   }
1360   return NULL;
1361 }
1362
1363
1364 /* Retrieve a string record in a map object. */
1365 const char *tcmapget2(const TCMAP *map, const char *kstr){
1366   assert(map && kstr);
1367   int ksiz = strlen(kstr);
1368   unsigned int hash;
1369   TCMAPHASH1(hash, kstr, ksiz);
1370   TCMAPREC *rec = map->buckets[hash%map->bnum];
1371   TCMAPHASH2(hash, kstr, ksiz);
1372   while(rec){
1373     if(hash > rec->hash){
1374       rec = rec->left;
1375     } else if(hash < rec->hash){
1376       rec = rec->right;
1377     } else {
1378       char *dbuf = (char *)rec + sizeof(*rec);
1379       int kcmp = TCKEYCMP(kstr, ksiz, dbuf, rec->ksiz);
1380       if(kcmp < 0){
1381         rec = rec->left;
1382       } else if(kcmp > 0){
1383         rec = rec->right;
1384       } else {
1385         return dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz);
1386       }
1387     }
1388   }
1389   return NULL;
1390 }
1391
1392
1393 /* Retrieve a semivolatile record in a map object. */
1394 const void *tcmapget3(TCMAP *map, const void *kbuf, int ksiz, int *sp){
1395   assert(map && kbuf && ksiz >= 0 && sp);
1396   unsigned int hash;
1397   TCMAPHASH1(hash, kbuf, ksiz);
1398   TCMAPREC *rec = map->buckets[hash%map->bnum];
1399   TCMAPHASH2(hash, kbuf, ksiz);
1400   while(rec){
1401     if(hash > rec->hash){
1402       rec = rec->left;
1403     } else if(hash < rec->hash){
1404       rec = rec->right;
1405     } else {
1406       char *dbuf = (char *)rec + sizeof(*rec);
1407       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1408       if(kcmp < 0){
1409         rec = rec->left;
1410       } else if(kcmp > 0){
1411         rec = rec->right;
1412       } else {
1413         if(map->last != rec){
1414           if(map->first == rec) map->first = rec->next;
1415           if(rec->prev) rec->prev->next = rec->next;
1416           if(rec->next) rec->next->prev = rec->prev;
1417           rec->prev = map->last;
1418           rec->next = NULL;
1419           map->last->next = rec;
1420           map->last = rec;
1421         }
1422         *sp = rec->vsiz;
1423         return dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz);
1424       }
1425     }
1426   }
1427   return NULL;
1428 }
1429
1430
1431 /* Move a record to the edge of a map object. */
1432 bool tcmapmove(TCMAP *map, const void *kbuf, int ksiz, bool head){
1433   assert(map && kbuf && ksiz >= 0);
1434   unsigned int hash;
1435   TCMAPHASH1(hash, kbuf, ksiz);
1436   TCMAPREC *rec = map->buckets[hash%map->bnum];
1437   TCMAPHASH2(hash, kbuf, ksiz);
1438   while(rec){
1439     if(hash > rec->hash){
1440       rec = rec->left;
1441     } else if(hash < rec->hash){
1442       rec = rec->right;
1443     } else {
1444       char *dbuf = (char *)rec + sizeof(*rec);
1445       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1446       if(kcmp < 0){
1447         rec = rec->left;
1448       } else if(kcmp > 0){
1449         rec = rec->right;
1450       } else {
1451         if(head){
1452           if(map->first == rec) return true;
1453           if(map->last == rec) map->last = rec->prev;
1454           if(rec->prev) rec->prev->next = rec->next;
1455           if(rec->next) rec->next->prev = rec->prev;
1456           rec->prev = NULL;
1457           rec->next = map->first;
1458           map->first->prev = rec;
1459           map->first = rec;
1460         } else {
1461           if(map->last == rec) return true;
1462           if(map->first == rec) map->first = rec->next;
1463           if(rec->prev) rec->prev->next = rec->next;
1464           if(rec->next) rec->next->prev = rec->prev;
1465           rec->prev = map->last;
1466           rec->next = NULL;
1467           map->last->next = rec;
1468           map->last = rec;
1469         }
1470         return true;
1471       }
1472     }
1473   }
1474   return false;
1475 }
1476
1477
1478 /* Move a string record to the edge of a map object. */
1479 bool tcmapmove2(TCMAP *map, const char *kstr, bool head){
1480   assert(map && kstr);
1481   return tcmapmove(map, kstr, strlen(kstr), head);
1482 }
1483
1484
1485 /* Initialize the iterator of a map object. */
1486 void tcmapiterinit(TCMAP *map){
1487   assert(map);
1488   map->cur = map->first;
1489 }
1490
1491
1492 /* Get the next key of the iterator of a map object. */
1493 const void *tcmapiternext(TCMAP *map, int *sp){
1494   assert(map && sp);
1495   TCMAPREC *rec;
1496   if(!map->cur) return NULL;
1497   rec = map->cur;
1498   map->cur = rec->next;
1499   *sp = rec->ksiz;
1500   return (char *)rec + sizeof(*rec);
1501 }
1502
1503
1504 /* Get the next key string of the iterator of a map object. */
1505 const char *tcmapiternext2(TCMAP *map){
1506   assert(map);
1507   TCMAPREC *rec;
1508   if(!map->cur) return NULL;
1509   rec = map->cur;
1510   map->cur = rec->next;
1511   return (char *)rec + sizeof(*rec);
1512 }
1513
1514
1515 /* Get the value bound to the key fetched from the iterator of a map object. */
1516 const void *tcmapiterval(const void *kbuf, int *sp){
1517   assert(kbuf && sp);
1518   TCMAPREC *rec = (TCMAPREC *)((char *)kbuf - sizeof(*rec));
1519   *sp = rec->vsiz;
1520   return (char *)kbuf + rec->ksiz + TCALIGNPAD(rec->ksiz);
1521 }
1522
1523
1524 /* Get the value string bound to the key fetched from the iterator of a map object. */
1525 const char *tcmapiterval2(const char *kstr){
1526   assert(kstr);
1527   TCMAPREC *rec = (TCMAPREC *)(kstr - sizeof(*rec));
1528   return kstr + rec->ksiz + TCALIGNPAD(rec->ksiz);
1529 }
1530
1531
1532 /* Get the number of records stored in a map object. */
1533 uint64_t tcmaprnum(const TCMAP *map){
1534   assert(map);
1535   return map->rnum;
1536 }
1537
1538
1539 /* Get the total size of memory used in a map object. */
1540 uint64_t tcmapmsiz(const TCMAP *map){
1541   assert(map);
1542   return map->msiz + map->rnum * (sizeof(*map->first) + sizeof(void *)) +
1543     map->bnum * sizeof(void *);
1544 }
1545
1546
1547 /* Create a list object containing all keys in a map object. */
1548 TCLIST *tcmapkeys(const TCMAP *map){
1549   assert(map);
1550   TCLIST *list = tclistnew2(map->rnum);
1551   TCMAPREC *cur = map->cur;
1552   const char *kbuf;
1553   int ksiz;
1554   ((TCMAP *)map)->cur = map->first;
1555   while((kbuf = tcmapiternext((TCMAP *)map, &ksiz)) != NULL){
1556     TCLISTPUSH(list, kbuf, ksiz);
1557   }
1558   ((TCMAP *)map)->cur = cur;
1559   return list;
1560 }
1561
1562
1563 /* Create a list object containing all values in a map object. */
1564 TCLIST *tcmapvals(const TCMAP *map){
1565   assert(map);
1566   TCLIST *list = tclistnew2(map->rnum);
1567   TCMAPREC *cur = map->cur;
1568   const char *kbuf;
1569   int ksiz;
1570   ((TCMAP *)map)->cur = map->first;
1571   while((kbuf = tcmapiternext((TCMAP *)map, &ksiz)) != NULL){
1572     int vsiz;
1573     const char *vbuf = tcmapiterval(kbuf, &vsiz);
1574     TCLISTPUSH(list, vbuf, vsiz);
1575   }
1576   ((TCMAP *)map)->cur = cur;
1577   return list;
1578 }
1579
1580
1581 /* Add an integer to a record in a map object. */
1582 void tcmapaddint(TCMAP *map, const char *kbuf, int ksiz, int num){
1583   assert(map && kbuf && ksiz >= 0);
1584   unsigned int hash;
1585   TCMAPHASH1(hash, kbuf, ksiz);
1586   int bidx = hash % map->bnum;
1587   TCMAPREC *rec = map->buckets[bidx];
1588   TCMAPREC **entp = map->buckets + bidx;
1589   TCMAPHASH2(hash, kbuf, ksiz);
1590   while(rec){
1591     if(hash > rec->hash){
1592       entp = &(rec->left);
1593       rec = rec->left;
1594     } else if(hash < rec->hash){
1595       entp = &(rec->right);
1596       rec = rec->right;
1597     } else {
1598       char *dbuf = (char *)rec + sizeof(*rec);
1599       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
1600       if(kcmp < 0){
1601         entp = &(rec->left);
1602         rec = rec->left;
1603       } else if(kcmp > 0){
1604         entp = &(rec->right);
1605         rec = rec->right;
1606       } else {
1607         int psiz = TCALIGNPAD(ksiz);
1608         *(int *)(dbuf + ksiz + psiz) += num;
1609         return;
1610       }
1611     }
1612   }
1613   int psiz = TCALIGNPAD(ksiz);
1614   TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + sizeof(num) + 1);
1615   char *dbuf = (char *)rec + sizeof(*rec);
1616   memcpy(dbuf, kbuf, ksiz);
1617   dbuf[ksiz] = '\0';
1618   rec->ksiz = ksiz;
1619   memcpy(dbuf + ksiz + psiz, &num, sizeof(num));
1620   dbuf[ksiz+psiz+sizeof(num)] = '\0';
1621   rec->vsiz = sizeof(num);
1622   rec->hash = hash;
1623   rec->left = NULL;
1624   rec->right = NULL;
1625   rec->prev = map->last;
1626   rec->next = NULL;
1627   *entp = rec;
1628   if(!map->first) map->first = rec;
1629   if(map->last) map->last->next = rec;
1630   map->last = rec;
1631   map->rnum++;
1632 }
1633
1634
1635 /* Clear a map object. */
1636 void tcmapclear(TCMAP *map){
1637   assert(map);
1638   TCMAPREC *rec = map->first;
1639   while(rec){
1640     TCMAPREC *next = rec->next;
1641     free(rec);
1642     rec = next;
1643   }
1644   TCMAPREC **buckets = map->buckets;
1645   int bnum = map->bnum;
1646   for(int i = 0; i < bnum; i++){
1647     buckets[i] = NULL;
1648   }
1649   map->first = NULL;
1650   map->last = NULL;
1651   map->cur = NULL;
1652   map->rnum = 0;
1653   map->msiz = 0;
1654 }
1655
1656
1657 /* Remove front records of a map object. */
1658 void tcmapcutfront(TCMAP *map, int num){
1659   assert(map && num >= 0);
1660   tcmapiterinit(map);
1661   while(num-- > 0){
1662     int ksiz;
1663     const char *kbuf = tcmapiternext(map, &ksiz);
1664     if(!kbuf) break;
1665     tcmapout(map, kbuf, ksiz);
1666   }
1667 }
1668
1669
1670 /* Serialize a map object into a byte array. */
1671 void *tcmapdump(const TCMAP *map, int *sp){
1672   assert(map && sp);
1673   TCMAPREC *cur = map->cur;
1674   int tsiz = 0;
1675   const char *kbuf, *vbuf;
1676   int ksiz, vsiz;
1677   ((TCMAP *)map)->cur = map->first;
1678   while((kbuf = tcmapiternext((TCMAP *)map, &ksiz)) != NULL){
1679     vbuf = tcmapiterval(kbuf, &vsiz);
1680     tsiz += ksiz + vsiz + sizeof(int) * 2;
1681   }
1682   char *buf;
1683   TCMALLOC(buf, tsiz + 1);
1684   char *wp = buf;
1685   ((TCMAP *)map)->cur = map->first;
1686   while((kbuf = tcmapiternext((TCMAP *)map, &ksiz)) != NULL){
1687     vbuf = tcmapiterval(kbuf, &vsiz);
1688     int step;
1689     TCSETVNUMBUF(step, wp, ksiz);
1690     wp += step;
1691     memcpy(wp, kbuf, ksiz);
1692     wp += ksiz;
1693     TCSETVNUMBUF(step, wp, vsiz);
1694     wp += step;
1695     memcpy(wp, vbuf, vsiz);
1696     wp += vsiz;
1697   }
1698   ((TCMAP *)map)->cur = cur;
1699   *sp = wp - buf;
1700   return buf;
1701 }
1702
1703
1704 /* Create a map object from a serialized byte array. */
1705 TCMAP *tcmapload(const void *ptr, int size){
1706   assert(ptr && size >= 0);
1707   TCMAP *map = tcmapnew();
1708   const char *rp = ptr;
1709   const char *ep = (char *)ptr + size;
1710   while(rp < ep){
1711     int step, ksiz, vsiz;
1712     TCREADVNUMBUF(rp, ksiz, step);
1713     rp += step;
1714     const char *kbuf = rp;
1715     rp += ksiz;
1716     TCREADVNUMBUF(rp, vsiz, step);
1717     rp += step;
1718     tcmapputkeep(map, kbuf, ksiz, rp, vsiz);
1719     rp += vsiz;
1720   }
1721   return map;
1722 }
1723
1724
1725 /* Extract a map record from a serialized byte array. */
1726 void *tcmaploadone(const void *ptr, int size, const void *kbuf, int ksiz, int *sp){
1727   assert(ptr && size >= 0 && kbuf && ksiz >= 0 && sp);
1728   const char *rp = ptr;
1729   const char *ep = (char *)ptr + size;
1730   while(rp < ep){
1731     int step, rsiz;
1732     TCREADVNUMBUF(rp, rsiz, step);
1733     rp += step;
1734     if(rsiz == ksiz && !memcmp(kbuf, rp, rsiz)){
1735       rp += rsiz;
1736       TCREADVNUMBUF(rp, rsiz, step);
1737       rp += step;
1738       *sp = rsiz;
1739       char *rv;
1740       TCMEMDUP(rv, rp, rsiz);
1741       return rv;
1742     }
1743     rp += rsiz;
1744     TCREADVNUMBUF(rp, rsiz, step);
1745     rp += step;
1746     rp += rsiz;
1747   }
1748   return NULL;
1749 }
1750
1751
1752
1753 /*************************************************************************************************
1754  * on-memory database
1755  *************************************************************************************************/
1756
1757
1758 #define TCMDBMNUM      8                 // number of internal maps
1759 #define TCMDBBNUM      65536             // allocation unit number of a map
1760
1761 /* get the first hash value */
1762 #define TCMDBHASH(TC_res, TC_kbuf, TC_ksiz) \
1763   do { \
1764     const unsigned char *_TC_p = (const unsigned char *)(TC_kbuf) + TC_ksiz - 1; \
1765     int _TC_ksiz = TC_ksiz; \
1766     for((TC_res) = 0x20071123; _TC_ksiz--;){ \
1767       (TC_res) = ((TC_res) << 5) + (TC_res) + *(_TC_p)--; \
1768     } \
1769     (TC_res) &= TCMDBMNUM - 1; \
1770   } while(false)
1771
1772
1773 /* Create an on-memory database object. */
1774 TCMDB *tcmdbnew(void){
1775   return tcmdbnew2(TCMDBBNUM);
1776 }
1777
1778
1779 /* Create an on-memory database with specifying the number of the buckets. */
1780 TCMDB *tcmdbnew2(uint32_t bnum){
1781   TCMDB *mdb;
1782   if(bnum < 1) bnum = TCMDBBNUM;
1783   bnum = bnum / TCMDBMNUM + 17;
1784   TCMALLOC(mdb, sizeof(*mdb));
1785   TCMALLOC(mdb->mmtxs, sizeof(pthread_rwlock_t) * TCMDBMNUM);
1786   TCMALLOC(mdb->imtx, sizeof(pthread_mutex_t));
1787   TCMALLOC(mdb->maps, sizeof(TCMAP *) * TCMDBMNUM);
1788   if(pthread_mutex_init(mdb->imtx, NULL) != 0) tcmyfatal("mutex error");
1789   for(int i = 0; i < TCMDBMNUM; i++){
1790     if(pthread_rwlock_init((pthread_rwlock_t *)mdb->mmtxs + i, NULL) != 0)
1791       tcmyfatal("rwlock error");
1792     mdb->maps[i] = tcmapnew2(bnum);
1793   }
1794   mdb->iter = -1;
1795   return mdb;
1796 }
1797
1798
1799 /* Delete an on-memory database object. */
1800 void tcmdbdel(TCMDB *mdb){
1801   assert(mdb);
1802   for(int i = TCMDBMNUM - 1; i >= 0; i--){
1803     tcmapdel(mdb->maps[i]);
1804     pthread_rwlock_destroy((pthread_rwlock_t *)mdb->mmtxs + i);
1805   }
1806   pthread_mutex_destroy(mdb->imtx);
1807   free(mdb->maps);
1808   free(mdb->imtx);
1809   free(mdb->mmtxs);
1810   free(mdb);
1811 }
1812
1813
1814 /* Store a record into an on-memory database. */
1815 void tcmdbput(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
1816   assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1817   unsigned int mi;
1818   TCMDBHASH(mi, kbuf, ksiz);
1819   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;
1820   tcmapput(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);
1821   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1822 }
1823
1824
1825 /* Store a string record into an on-memory database. */
1826 void tcmdbput2(TCMDB *mdb, const char *kstr, const char *vstr){
1827   assert(mdb && kstr && vstr);
1828   tcmdbput(mdb, kstr, strlen(kstr), vstr, strlen(vstr));
1829 }
1830
1831
1832 /* Store a record of the value of two regions into an on-memory database object. */
1833 void tcmdbput3(TCMDB *mdb, const char *kbuf, int ksiz,
1834                const void *fvbuf, int fvsiz, const char *lvbuf, int lvsiz){
1835   assert(mdb && kbuf && ksiz >= 0 && fvbuf && fvsiz >= 0 && lvbuf && lvsiz >= 0);
1836   unsigned int mi;
1837   TCMDBHASH(mi, kbuf, ksiz);
1838   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;
1839   tcmapput3(mdb->maps[mi], kbuf, ksiz, fvbuf, fvsiz, lvbuf, lvsiz);
1840   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1841 }
1842
1843
1844 /* Store a new record into an on-memory database. */
1845 bool tcmdbputkeep(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
1846   assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1847   unsigned int mi;
1848   TCMDBHASH(mi, kbuf, ksiz);
1849   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return false;
1850   bool rv = tcmapputkeep(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);
1851   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1852   return rv;
1853 }
1854
1855
1856 /* Store a new string record into an on-memory database. */
1857 bool tcmdbputkeep2(TCMDB *mdb, const char *kstr, const char *vstr){
1858   assert(mdb && kstr && vstr);
1859   return tcmdbputkeep(mdb, kstr, strlen(kstr), vstr, strlen(vstr));
1860 }
1861
1862
1863 /* Concatenate a value at the end of the value of the existing record in an on-memory database. */
1864 void tcmdbputcat(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
1865   assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1866   unsigned int mi;
1867   TCMDBHASH(mi, kbuf, ksiz);
1868   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;
1869   tcmapputcat(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);
1870   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1871 }
1872
1873
1874 /* Concatenate a string at the end of the value of the existing record in an on-memory database. */
1875 void tcmdbputcat2(TCMDB *mdb, const char *kstr, const char *vstr){
1876   assert(mdb && kstr && vstr);
1877   tcmdbputcat(mdb, kstr, strlen(kstr), vstr, strlen(vstr));
1878 }
1879
1880
1881 /* Remove a record of an on-memory database. */
1882 bool tcmdbout(TCMDB *mdb, const void *kbuf, int ksiz){
1883   assert(mdb && kbuf && ksiz >= 0);
1884   unsigned int mi;
1885   TCMDBHASH(mi, kbuf, ksiz);
1886   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return false;
1887   bool rv = tcmapout(mdb->maps[mi], kbuf, ksiz);
1888   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1889   return rv;
1890 }
1891
1892
1893 /* Remove a string record of an on-memory database. */
1894 bool tcmdbout2(TCMDB *mdb, const char *kstr){
1895   assert(mdb && kstr);
1896   return tcmdbout(mdb, kstr, strlen(kstr));
1897 }
1898
1899
1900 /* Retrieve a record in an on-memory database. */
1901 void *tcmdbget(TCMDB *mdb, const void *kbuf, int ksiz, int *sp){
1902   assert(mdb && kbuf && ksiz >= 0 && sp);
1903   unsigned int mi;
1904   TCMDBHASH(mi, kbuf, ksiz);
1905   if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return NULL;
1906   int vsiz;
1907   const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);
1908   char *rv;
1909   if(vbuf){
1910     TCMEMDUP(rv, vbuf, vsiz);
1911     *sp = vsiz;
1912   } else {
1913     rv = NULL;
1914   }
1915   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1916   return rv;
1917 }
1918
1919
1920 /* Retrieve a string record in an on-memory database. */
1921 char *tcmdbget2(TCMDB *mdb, const char *kstr){
1922   assert(mdb && kstr);
1923   int vsiz;
1924   return tcmdbget(mdb, kstr, strlen(kstr), &vsiz);
1925 }
1926
1927
1928 /* Retrieve a record and move it astern in an on-memory database. */
1929 void *tcmdbget3(TCMDB *mdb, const void *kbuf, int ksiz, int *sp){
1930   assert(mdb && kbuf && ksiz >= 0 && sp);
1931   unsigned int mi;
1932   TCMDBHASH(mi, kbuf, ksiz);
1933   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return NULL;
1934   int vsiz;
1935   const char *vbuf = tcmapget3(mdb->maps[mi], kbuf, ksiz, &vsiz);
1936   char *rv;
1937   if(vbuf){
1938     TCMEMDUP(rv, vbuf, vsiz);
1939     *sp = vsiz;
1940   } else {
1941     rv = NULL;
1942   }
1943   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1944   return rv;
1945 }
1946
1947
1948 /* Get the size of the value of a record in an on-memory database object. */
1949 int tcmdbvsiz(TCMDB *mdb, const void *kbuf, int ksiz){
1950   assert(mdb && kbuf && ksiz >= 0);
1951   unsigned int mi;
1952   TCMDBHASH(mi, kbuf, ksiz);
1953   if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return -1;
1954   int vsiz;
1955   const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);
1956   if(!vbuf) vsiz = -1;
1957   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1958   return vsiz;
1959 }
1960
1961
1962 /* Get the size of the value of a string record in an on-memory database object. */
1963 int tcmdbvsiz2(TCMDB *mdb, const char *kstr){
1964   assert(mdb && kstr);
1965   return tcmdbvsiz(mdb, kstr, strlen(kstr));
1966 }
1967
1968
1969 /* Initialize the iterator of an on-memory database. */
1970 void tcmdbiterinit(TCMDB *mdb){
1971   assert(mdb);
1972   if(pthread_mutex_lock(mdb->imtx) != 0) return;
1973   for(int i = 0; i < TCMDBMNUM; i++){
1974     tcmapiterinit(mdb->maps[i]);
1975   }
1976   mdb->iter = 0;
1977   pthread_mutex_unlock(mdb->imtx);
1978 }
1979
1980
1981 /* Get the next key of the iterator of an on-memory database. */
1982 void *tcmdbiternext(TCMDB *mdb, int *sp){
1983   assert(mdb && sp);
1984   if(pthread_mutex_lock(mdb->imtx) != 0) return NULL;
1985   if(mdb->iter < 0 || mdb->iter >= TCMDBMNUM){
1986     pthread_mutex_unlock(mdb->imtx);
1987     return NULL;
1988   }
1989   int mi = mdb->iter;
1990   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0){
1991     pthread_mutex_unlock(mdb->imtx);
1992     return NULL;
1993   }
1994   int ksiz;
1995   const char *kbuf;
1996   while(!(kbuf = tcmapiternext(mdb->maps[mi], &ksiz)) && mi < TCMDBMNUM - 1){
1997     pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
1998     mi = ++mdb->iter;
1999     if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0){
2000       pthread_mutex_unlock(mdb->imtx);
2001       return NULL;
2002     }
2003   }
2004   char *rv;
2005   if(kbuf){
2006     TCMEMDUP(rv, kbuf, ksiz);
2007     *sp = ksiz;
2008   } else {
2009     rv = NULL;
2010   }
2011   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
2012   pthread_mutex_unlock(mdb->imtx);
2013   return rv;
2014 }
2015
2016
2017 /* Get the next key string of the iterator of an on-memory database. */
2018 char *tcmdbiternext2(TCMDB *mdb){
2019   assert(mdb);
2020   int ksiz;
2021   return tcmdbiternext(mdb, &ksiz);
2022 }
2023
2024
2025 /* Get forward matching keys in an on-memory database object. */
2026 TCLIST *tcmdbfwmkeys(TCMDB *mdb, const void *pbuf, int psiz, int max){
2027   assert(mdb && pbuf && psiz >= 0);
2028   TCLIST* keys = tclistnew();
2029   if(pthread_mutex_lock(mdb->imtx) != 0) return keys;
2030   if(max < 0) max = INT_MAX;
2031   for(int i = 0; i < TCMDBMNUM && TCLISTNUM(keys) < max; i++){
2032     if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + i) == 0){
2033       TCMAP *map = mdb->maps[i];
2034       TCMAPREC *cur = map->cur;
2035       tcmapiterinit(map);
2036       int ksiz;
2037       const char *kbuf;
2038       while(TCLISTNUM(keys) < max && (kbuf = tcmapiternext(map, &ksiz)) != NULL){
2039         if(ksiz >= psiz && !memcmp(kbuf, pbuf, psiz)) tclistpush(keys, kbuf, ksiz);
2040       }
2041       map->cur = cur;
2042       pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + i);
2043     }
2044   }
2045   pthread_mutex_unlock(mdb->imtx);
2046   return keys;
2047 }
2048
2049
2050 /* Get forward matching string keys in an on-memory database object. */
2051 TCLIST *tcmdbfwmkeys2(TCMDB *mdb, const char *pstr, int max){
2052   assert(mdb && pstr);
2053   return tcmdbfwmkeys(mdb, pstr, strlen(pstr), max);
2054 }
2055
2056
2057 /* Get the number of records stored in an on-memory database. */
2058 uint64_t tcmdbrnum(TCMDB *mdb){
2059   assert(mdb);
2060   uint64_t rnum = 0;
2061   for(int i = 0; i < TCMDBMNUM; i++){
2062     rnum += tcmaprnum(mdb->maps[i]);
2063   }
2064   return rnum;
2065 }
2066
2067
2068 /* Get the total size of memory used in an on-memory database object. */
2069 uint64_t tcmdbmsiz(TCMDB *mdb){
2070   assert(mdb);
2071   uint64_t msiz = 0;
2072   for(int i = 0; i < TCMDBMNUM; i++){
2073     msiz += tcmapmsiz(mdb->maps[i]);
2074   }
2075   return msiz;
2076 }
2077
2078
2079 /* Clear an on-memory database object. */
2080 void tcmdbvanish(TCMDB *mdb){
2081   assert(mdb);
2082   for(int i = 0; i < TCMDBMNUM; i++){
2083     if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + i) == 0){
2084       tcmapclear(mdb->maps[i]);
2085       pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + i);
2086     }
2087   }
2088 }
2089
2090
2091 /* Remove front records of a map object. */
2092 void tcmdbcutfront(TCMDB *mdb, int num){
2093   assert(mdb && num >= 0);
2094   num = num / TCMDBMNUM + 1;
2095   for(int i = 0; i < TCMDBMNUM; i++){
2096     if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + i) == 0){
2097       tcmapcutfront(mdb->maps[i], num);
2098       pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + i);
2099     }
2100   }
2101 }
2102
2103
2104
2105 /*************************************************************************************************
2106  * memory pool
2107  *************************************************************************************************/
2108
2109
2110 #define TCMPOOLUNIT    128               // allocation unit size of memory pool elements
2111
2112
2113 /* Global memory pool object. */
2114 TCMPOOL *tcglobalmemorypool = NULL;
2115
2116
2117 /* private function prototypes */
2118 static void tcmpooldelglobal(void);
2119
2120
2121 /* Create a memory pool object. */
2122 TCMPOOL *tcmpoolnew(void){
2123   TCMPOOL *mpool;
2124   TCMALLOC(mpool, sizeof(*mpool));
2125   TCMALLOC(mpool->mutex, sizeof(pthread_mutex_t));
2126   if(pthread_mutex_init(mpool->mutex, NULL) != 0) tcmyfatal("locking failed");
2127   mpool->anum = TCMPOOLUNIT;
2128   TCMALLOC(mpool->elems, sizeof(mpool->elems[0]) * mpool->anum);
2129   mpool->num = 0;
2130   return mpool;
2131 }
2132
2133
2134 /* Delete a memory pool object. */
2135 void tcmpooldel(TCMPOOL *mpool){
2136   assert(mpool);
2137   TCMPELEM *elems = mpool->elems;
2138   for(int i = mpool->num - 1; i >= 0; i--){
2139     elems[i].del(elems[i].ptr);
2140   }
2141   free(elems);
2142   pthread_mutex_destroy(mpool->mutex);
2143   free(mpool->mutex);
2144   free(mpool);
2145 }
2146
2147
2148 /* Relegate an arbitrary object to a memory pool object. */
2149 void tcmpoolput(TCMPOOL *mpool, void *ptr, void (*del)(void *)){
2150   assert(mpool && ptr && del);
2151   if(pthread_mutex_lock(mpool->mutex) != 0) tcmyfatal("locking failed");
2152   int num = mpool->num;
2153   if(num >= mpool->anum){
2154     mpool->anum *= 2;
2155     TCREALLOC(mpool->elems, mpool->elems, mpool->anum * sizeof(mpool->elems[0]));
2156   }
2157   mpool->elems[num].ptr = ptr;
2158   mpool->elems[num].del = del;
2159   mpool->num++;
2160   pthread_mutex_unlock(mpool->mutex);
2161 }
2162
2163
2164 /* Relegate an allocated region to a memory pool object. */
2165 void tcmpoolputptr(TCMPOOL *mpool, void *ptr){
2166   assert(mpool && ptr);
2167   tcmpoolput(mpool, ptr, (void (*)(void *))free);
2168 }
2169
2170
2171 /* Relegate an extensible string object to a memory pool object. */
2172 void tcmpoolputxstr(TCMPOOL *mpool, TCXSTR *xstr){
2173   assert(mpool && xstr);
2174   tcmpoolput(mpool, xstr, (void (*)(void *))tcxstrdel);
2175 }
2176
2177
2178 /* Relegate a list object to a memory pool object. */
2179 void tcmpoolputlist(TCMPOOL *mpool, TCLIST *list){
2180   assert(mpool && list);
2181   tcmpoolput(mpool, list, (void (*)(void *))tclistdel);
2182 }
2183
2184
2185 /* Relegate a map object to a memory pool object. */
2186 void tcmpoolputmap(TCMPOOL *mpool, TCMAP *map){
2187   assert(mpool && map);
2188   tcmpoolput(mpool, map, (void (*)(void *))tcmapdel);
2189 }
2190
2191
2192 /* Allocate a region relegated to a memory pool object. */
2193 void *tcmpoolmalloc(TCMPOOL *mpool, size_t size){
2194   assert(mpool && size > 0);
2195   void *ptr;
2196   TCMALLOC(ptr, size);
2197   tcmpoolput(mpool, ptr, (void (*)(void *))free);
2198   return ptr;
2199 }
2200
2201
2202 /* Create an extensible string object relegated to a memory pool object. */
2203 TCXSTR *tcmpoolxstrnew(TCMPOOL *mpool){
2204   assert(mpool);
2205   TCXSTR *xstr = tcxstrnew();
2206   tcmpoolput(mpool, xstr, (void (*)(void *))tcxstrdel);
2207   return xstr;
2208 }
2209
2210
2211 /* Create a list object relegated to a memory pool object. */
2212 TCLIST *tcmpoollistnew(TCMPOOL *mpool){
2213   assert(mpool);
2214   TCLIST *list = tclistnew();
2215   tcmpoolput(mpool, list, (void (*)(void *))tclistdel);
2216   return list;
2217 }
2218
2219
2220 /* Create a map object relegated to a memory pool object. */
2221 TCMAP *tcmpoolmapnew(TCMPOOL *mpool){
2222   assert(mpool);
2223   TCMAP *map = tcmapnew();
2224   tcmpoolput(mpool, map, (void (*)(void *))tcmapdel);
2225   return map;
2226 }
2227
2228
2229 /* Get the global memory pool object. */
2230 TCMPOOL *tcmpoolglobal(void){
2231   if(tcglobalmemorypool) return tcglobalmemorypool;
2232   tcglobalmemorypool = tcmpoolnew();
2233   atexit(tcmpooldelglobal);
2234   return tcglobalmemorypool;
2235 }
2236
2237
2238 /* Detete global memory pool object. */
2239 static void tcmpooldelglobal(void){
2240   if(tcglobalmemorypool) tcmpooldel(tcglobalmemorypool);
2241 }
2242
2243
2244
2245 /*************************************************************************************************
2246  * miscellaneous utilities
2247  *************************************************************************************************/
2248
2249
2250 #define TCRANDDEV      "/dev/urandom"    // path of the random device file
2251 #define TCDISTBUFSIZ   16384             // size of an distance buffer
2252
2253
2254 /* File descriptor of random number generator. */
2255 int tcrandomdevfd = -1;
2256
2257
2258 /* private function prototypes */
2259 static void tcrandomfdclose(void);
2260 static time_t tcmkgmtime(struct tm *tm);
2261
2262
2263 /* Get the larger value of two integers. */
2264 long tclmax(long a, long b){
2265   return (a > b) ? a : b;
2266 }
2267
2268
2269 /* Get the lesser value of two integers. */
2270 long tclmin(long a, long b){
2271   return (a < b) ? a : b;
2272 }
2273
2274
2275 /* Get a random number as long integer based on uniform distribution. */
2276 unsigned long tclrand(void){
2277   static unsigned int cnt = 0;
2278   static unsigned int seed = 0;
2279   static unsigned long mask = 0;
2280   static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
2281   if((cnt & 0xff) == 0 && pthread_mutex_lock(&mutex) == 0){
2282     if(cnt++ == 0) seed = time(NULL);
2283     if(tcrandomdevfd == -1 && (tcrandomdevfd = open(TCRANDDEV, O_RDONLY, 00644)) != -1)
2284       atexit(tcrandomfdclose);
2285     if(tcrandomdevfd != -1) read(tcrandomdevfd, &mask, sizeof(mask));
2286     pthread_mutex_unlock(&mutex);
2287   }
2288   return (mask ^ cnt++) ^ (unsigned long)rand_r(&seed);
2289 }
2290
2291
2292 /* Get a random number as double decimal based on uniform distribution. */
2293 double tcdrand(void){
2294   return tclrand() / (ULONG_MAX + 0.01);
2295 }
2296
2297
2298 /* Get a random number as double decimal based on normal distribution. */
2299 double tcdrandnd(double avg, double sd){
2300   assert(sd >= 0.0);
2301   return sqrt(-2.0 * log(tcdrand())) * cos(2 * 3.141592653589793 * tcdrand()) * sd + avg;
2302 }
2303
2304
2305 /* Compare two strings with case insensitive evaluation. */
2306 int tcstricmp(const char *astr, const char *bstr){
2307   assert(astr && bstr);
2308   while(*astr != '\0'){
2309     if(*bstr == '\0') return 1;
2310     int ac = (*astr >= 'A' && *astr <= 'Z') ? *astr + ('a' - 'A') : *(unsigned char *)astr;
2311     int bc = (*bstr >= 'A' && *bstr <= 'Z') ? *bstr + ('a' - 'A') : *(unsigned char *)bstr;
2312     if(ac != bc) return ac - bc;
2313     astr++;
2314     bstr++;
2315   }
2316   return (*bstr == '\0') ? 0 : -1;
2317 }
2318
2319
2320 /* Check whether a string begins with a key. */
2321 bool tcstrfwm(const char *str, const char *key){
2322   assert(str && key);
2323   while(*key != '\0'){
2324     if(*str != *key || *str == '\0') return false;
2325     key++;
2326     str++;
2327   }
2328   return true;
2329 }
2330
2331
2332 /* Check whether a string begins with a key with case insensitive evaluation. */
2333 bool tcstrifwm(const char *str, const char *key){
2334   assert(str && key);
2335   while(*key != '\0'){
2336     if(*str == '\0') return false;
2337     int sc = *str;
2338     if(sc >= 'A' && sc <= 'Z') sc += 'a' - 'A';
2339     int kc = *key;
2340     if(kc >= 'A' && kc <= 'Z') kc += 'a' - 'A';
2341     if(sc != kc) return false;
2342     key++;
2343     str++;
2344   }
2345   return true;
2346 }
2347
2348
2349 /* Check whether a string ends with a key. */
2350 bool tcstrbwm(const char *str, const char *key){
2351   assert(str && key);
2352   int slen = strlen(str);
2353   int klen = strlen(key);
2354   for(int i = 1; i <= klen; i++){
2355     if(i > slen || str[slen-i] != key[klen-i]) return false;
2356   }
2357   return true;
2358 }
2359
2360
2361 /* Check whether a string ends with a key with case insensitive evaluation. */
2362 bool tcstribwm(const char *str, const char *key){
2363   assert(str && key);
2364   int slen = strlen(str);
2365   int klen = strlen(key);
2366   for(int i = 1; i <= klen; i++){
2367     if(i > slen) return false;
2368     int sc = str[slen-i];
2369     if(sc >= 'A' && sc <= 'Z') sc += 'a' - 'A';
2370     int kc = key[klen-i];
2371     if(kc >= 'A' && kc <= 'Z') kc += 'a' - 'A';
2372     if(sc != kc) return false;
2373   }
2374   return true;
2375 }
2376
2377
2378 /* Calculate the edit distance of two strings. */
2379 int tcstrdist(const char *astr, const char *bstr){
2380   assert(astr && bstr);
2381   int alen = strlen(astr);
2382   int blen = strlen(bstr);
2383   int dsiz = blen + 1;
2384   int tbuf[TCDISTBUFSIZ];
2385   int *tbl;
2386   if((alen + 1) * dsiz < TCDISTBUFSIZ){
2387     tbl = tbuf;
2388   } else {
2389     TCMALLOC(tbl, (alen + 1) * dsiz * sizeof(*tbl));
2390   }
2391   for(int i = 0; i <= alen; i++){
2392     tbl[i*dsiz] = i;
2393   }
2394   for(int i = 1; i <= blen; i++){
2395     tbl[i] = i;
2396   }
2397   astr--;
2398   bstr--;
2399   for(int i = 1; i <= alen; i++){
2400     for(int j = 1; j <= blen; j++){
2401       int ac = tbl[(i-1)*dsiz+j] + 1;
2402       int bc = tbl[i*dsiz+j-1] + 1;
2403       int cc = tbl[(i-1)*dsiz+j-1] + (astr[i] != bstr[j]);
2404       ac = ac < bc ? ac : bc;
2405       tbl[i*dsiz+j] = ac < cc ? ac : cc;
2406     }
2407   }
2408   int rv = tbl[alen*dsiz+blen];
2409   if(tbl != tbuf) free(tbl);
2410   return rv;
2411 }
2412
2413
2414 /* Calculate the edit distance of two UTF-8 strings. */
2415 int tcstrdistutf(const char *astr, const char *bstr){
2416   assert(astr && bstr);
2417   int alen = strlen(astr);
2418   uint16_t abuf[TCDISTBUFSIZ];
2419   uint16_t *aary;
2420   if(alen < TCDISTBUFSIZ){
2421     aary = abuf;
2422   } else {
2423     TCMALLOC(aary, alen * sizeof(*aary));
2424   }
2425   tcstrutftoucs(astr, aary, &alen);
2426   int blen = strlen(bstr);
2427   uint16_t bbuf[TCDISTBUFSIZ];
2428   uint16_t *bary;
2429   if(blen < TCDISTBUFSIZ){
2430     bary = bbuf;
2431   } else {
2432     TCMALLOC(bary, blen * sizeof(*bary));
2433   }
2434   tcstrutftoucs(bstr, bary, &blen);
2435   int dsiz = blen + 1;
2436   int tbuf[TCDISTBUFSIZ];
2437   int *tbl;
2438   if((alen + 1) * dsiz < TCDISTBUFSIZ){
2439     tbl = tbuf;
2440   } else {
2441     TCMALLOC(tbl, (alen + 1) * dsiz * sizeof(*tbl));
2442   }
2443   for(int i = 0; i <= alen; i++){
2444     tbl[i*dsiz] = i;
2445   }
2446   for(int i = 1; i <= blen; i++){
2447     tbl[i] = i;
2448   }
2449   aary--;
2450   bary--;
2451   for(int i = 1; i <= alen; i++){
2452     for(int j = 1; j <= blen; j++){
2453       int ac = tbl[(i-1)*dsiz+j] + 1;
2454       int bc = tbl[i*dsiz+j-1] + 1;
2455       int cc = tbl[(i-1)*dsiz+j-1] + (aary[i] != bary[j]);
2456       ac = ac < bc ? ac : bc;
2457       tbl[i*dsiz+j] = ac < cc ? ac : cc;
2458     }
2459   }
2460   aary++;
2461   bary++;
2462   int rv = tbl[alen*dsiz+blen];
2463   if(tbl != tbuf) free(tbl);
2464   if(bary != bbuf) free(bary);
2465   if(aary != abuf) free(aary);
2466   return rv;
2467 }
2468
2469
2470 /* Convert the letters of a string into upper case. */
2471 char *tcstrtoupper(char *str){
2472   assert(str);
2473   char *wp = str;
2474   while(*wp != '\0'){
2475     if(*wp >= 'a' && *wp <= 'z') *wp -= 'a' - 'A';
2476     wp++;
2477   }
2478   return str;
2479 }
2480
2481
2482 /* Convert the letters of a string into lower case. */
2483 char *tcstrtolower(char *str){
2484   assert(str);
2485   char *wp = str;
2486   while(*wp != '\0'){
2487     if(*wp >= 'A' && *wp <= 'Z') *wp += 'a' - 'A';
2488     wp++;
2489   }
2490   return str;
2491 }
2492
2493
2494 /* Cut space characters at head or tail of a string. */
2495 char *tcstrtrim(char *str){
2496   assert(str);
2497   const char *rp = str;
2498   char *wp = str;
2499   bool head = true;
2500   while(*rp != '\0'){
2501     if(*rp > '\0' && *rp <= ' '){
2502       if(!head) *(wp++) = *rp;
2503     } else {
2504       *(wp++) = *rp;
2505       head = false;
2506     }
2507     rp++;
2508   }
2509   *wp = '\0';
2510   while(wp > str && wp[-1] > '\0' && wp[-1] <= ' '){
2511     *(--wp) = '\0';
2512   }
2513   return str;
2514 }
2515
2516
2517 /* Squeeze space characters in a string and trim it. */
2518 char *tcstrsqzspc(char *str){
2519   assert(str);
2520   char *rp = str;
2521   char *wp = str;
2522   bool spc = true;
2523   while(*rp != '\0'){
2524     if(*rp > 0 && *rp <= ' '){
2525       if(!spc) *(wp++) = *rp;
2526       spc = true;
2527     } else {
2528       *(wp++) = *rp;
2529       spc = false;
2530     }
2531     rp++;
2532   }
2533   *wp = '\0';
2534   for(wp--; wp >= str; wp--){
2535     if(*wp > 0 && *wp <= ' '){
2536       *wp = '\0';
2537     } else {
2538       break;
2539     }
2540   }
2541   return str;
2542 }
2543
2544
2545 /* Substitute characters in a string. */
2546 char *tcstrsubchr(char *str, const char *rstr, const char *sstr){
2547   assert(str && rstr && sstr);
2548   int slen = strlen(sstr);
2549   char *wp = str;
2550   for(int i = 0; str[i] != '\0'; i++){
2551     const char *p = strchr(rstr, str[i]);
2552     if(p){
2553       int idx = p - rstr;
2554       if(idx < slen) *(wp++) = sstr[idx];
2555     } else {
2556       *(wp++) = str[i];
2557     }
2558   }
2559   *wp = '\0';
2560   return str;
2561 }
2562
2563
2564 /* Count the number of characters in a string of UTF-8. */
2565 int tcstrcntutf(const char *str){
2566   assert(str);
2567   const unsigned char *rp = (unsigned char *)str;
2568   int cnt = 0;
2569   while(*rp != '\0'){
2570     if((*rp & 0x80) == 0x00 || (*rp & 0xe0) == 0xc0 ||
2571        (*rp & 0xf0) == 0xe0 || (*rp & 0xf8) == 0xf0) cnt++;
2572     rp++;
2573   }
2574   return cnt;
2575 }
2576
2577
2578 /* Cut a string of UTF-8 at the specified number of characters. */
2579 char *tcstrcututf(char *str, int num){
2580   assert(str && num >= 0);
2581   unsigned char *wp = (unsigned char *)str;
2582   int cnt = 0;
2583   while(*wp != '\0'){
2584     if((*wp & 0x80) == 0x00 || (*wp & 0xe0) == 0xc0 ||
2585        (*wp & 0xf0) == 0xe0 || (*wp & 0xf8) == 0xf0){
2586       cnt++;
2587       if(cnt > num){
2588         *wp = '\0';
2589         break;
2590       }
2591     }
2592     wp++;
2593   }
2594   return str;
2595 }
2596
2597
2598 /* Convert a UTF-8 string into a UCS-2 array. */
2599 void tcstrutftoucs(const char *str, uint16_t *ary, int *np){
2600   assert(str && ary && np);
2601   const unsigned char *rp = (unsigned char *)str;
2602   unsigned int wi = 0;
2603   while(*rp != '\0'){
2604     int c = *(unsigned char *)rp;
2605     if(c < 0x80){
2606       ary[wi++] = c;
2607     } else if(c < 0xe0){
2608       if(rp[1] >= 0x80){
2609         ary[wi++] = ((rp[0] & 0x1f) << 6) | (rp[1] & 0x3f);
2610         rp++;
2611       }
2612     } else if(c < 0xf0){
2613       if(rp[1] >= 0x80 && rp[2] >= 0x80){
2614         ary[wi++] = ((rp[0] & 0xf) << 12) | ((rp[1] & 0x3f) << 6) | (rp[2] & 0x3f);
2615         rp += 2;
2616       }
2617     }
2618     rp++;
2619   }
2620   *np = wi;
2621 }
2622
2623
2624 /* Convert a UCS-2 array into a UTF-8 string. */
2625 void tcstrucstoutf(const uint16_t *ary, int num, char *str){
2626   assert(ary && num >= 0 && str);
2627   unsigned char *wp = (unsigned char *)str;
2628   for(int i = 0; i < num; i++){
2629     unsigned int c = ary[i];
2630     if(c < 0x80){
2631       *(wp++) = c;
2632     } else if(c < 0x800){
2633       *(wp++) = 0xc0 | (c >> 6);
2634       *(wp++) = 0x80 | (c & 0x3f);
2635     } else {
2636       *(wp++) = 0xe0 | (c >> 12);
2637       *(wp++) = 0x80 | ((c & 0xfff) >> 6);
2638       *(wp++) = 0x80 | (c & 0x3f);
2639     }
2640   }
2641   *wp = '\0';
2642 }
2643
2644
2645 /* Create a list object by splitting a string. */
2646 TCLIST *tcstrsplit(const char *str, const char *delims){
2647   assert(str && delims);
2648   TCLIST *list = tclistnew();
2649   while(true){
2650     const char *sp = str;
2651     while(*str != '\0' && !strchr(delims, *str)){
2652       str++;
2653     }
2654     TCLISTPUSH(list, sp, str - sp);
2655     if(*str == '\0') break;
2656     str++;
2657   }
2658   return list;
2659 }
2660
2661
2662 /* Create a string by joining all elements of a list object. */
2663 char *tcstrjoin(TCLIST *list, char delim){
2664   assert(list);
2665   int num = TCLISTNUM(list);
2666   int size = num + 1;
2667   for(int i = 0; i < num; i++){
2668     size += TCLISTVALNUM(list, i);
2669   }
2670   char *buf;
2671   TCMALLOC(buf, size);
2672   char *wp = buf;
2673   for(int i = 0; i < num; i++){
2674     if(i > 0) *(wp++) = delim;
2675     int vsiz;
2676     const char *vbuf = tclistval(list, i, &vsiz);
2677     memcpy(wp, vbuf, vsiz);
2678     wp += vsiz;
2679   }
2680   *wp = '\0';
2681   return buf;
2682 }
2683
2684
2685 /* Check whether a string matches a regular expression. */
2686 bool tcregexmatch(const char *str, const char *regex){
2687   assert(str && regex);
2688   int options = REG_EXTENDED | REG_NOSUB;
2689   if(*regex == '*'){
2690     options |= REG_ICASE;
2691     regex++;
2692   }
2693   regex_t rbuf;
2694   if(regcomp(&rbuf, regex, options) != 0) return false;
2695   bool rv = regexec(&rbuf, str, 0, NULL, 0) == 0;
2696   regfree(&rbuf);
2697   return rv;
2698 }
2699
2700
2701 /* Replace each substring matching a regular expression string. */
2702 char *tcregexreplace(const char *str, const char *regex, const char *alt){
2703   assert(str && regex && alt);
2704   int options = REG_EXTENDED;
2705   if(*regex == '*'){
2706     options |= REG_ICASE;
2707     regex++;
2708   }
2709   regex_t rbuf;
2710   if(regex[0] == '\0' || regcomp(&rbuf, regex, options) != 0) return tcstrdup(str);
2711   regmatch_t subs[256];
2712   if(regexec(&rbuf, str, 32, subs, 0) != 0){
2713     regfree(&rbuf);
2714     return tcstrdup(str);
2715   }
2716   const char *sp = str;
2717   TCXSTR *xstr = tcxstrnew();
2718   bool first = true;
2719   while(sp[0] != '\0' && regexec(&rbuf, sp, 10, subs, first ? 0 : REG_NOTBOL) == 0){
2720     first = false;
2721     if(subs[0].rm_so == -1) break;
2722     tcxstrcat(xstr, sp, subs[0].rm_so);
2723     for(const char *rp = alt; *rp != '\0'; rp++){
2724       if(*rp == '\\'){
2725         if(rp[1] >= '0' && rp[1] <= '9'){
2726           int num = rp[1] - '0';
2727           if(subs[num].rm_so != -1 && subs[num].rm_eo != -1)
2728             tcxstrcat(xstr, sp + subs[num].rm_so, subs[num].rm_eo - subs[num].rm_so);
2729           ++rp;
2730         } else if(rp[1] != '\0'){
2731           tcxstrcat(xstr, ++rp, 1);
2732         }
2733       } else if(*rp == '&'){
2734         tcxstrcat(xstr, sp + subs[0].rm_so, subs[0].rm_eo - subs[0].rm_so);
2735       } else {
2736         tcxstrcat(xstr, rp, 1);
2737       }
2738     }
2739     sp += subs[0].rm_eo;
2740     if(subs[0].rm_eo < 1) break;
2741   }
2742   tcxstrcat2(xstr, sp);
2743   regfree(&rbuf);
2744   return tcxstrtomalloc(xstr);
2745 }
2746
2747
2748 /* Get the time of day in seconds. */
2749 double tctime(void){
2750   struct timeval tv;
2751   if(gettimeofday(&tv, NULL) == -1) return 0.0;
2752   return (double)tv.tv_sec + (double)tv.tv_usec / 1000000.0;
2753 }
2754
2755
2756 /* Get the Gregorian calendar of a time. */
2757 void tccalendar(int64_t t, int jl, int *yearp, int *monp, int *dayp,
2758                 int *hourp, int *minp, int *secp){
2759   if(t == INT64_MAX || jl == INT_MAX){
2760     struct timeval tv;
2761     struct timezone tz;
2762     if(gettimeofday(&tv, &tz) == 0){
2763       if(t == INT64_MAX) t = tv.tv_sec;
2764       if(jl == INT_MAX) jl = tz.tz_minuteswest * -60;
2765     } else {
2766       if(yearp) *yearp = 0;
2767       if(monp) *monp = 0;
2768       if(dayp) *dayp = 0;
2769       if(hourp) *hourp = 0;
2770       if(minp) *minp = 0;
2771       if(secp) *secp = 0;
2772     }
2773   }
2774   time_t tt = (time_t)t + jl;
2775   struct tm ts;
2776   if(!gmtime_r(&tt, &ts)){
2777     if(yearp) *yearp = 0;
2778     if(monp) *monp = 0;
2779     if(dayp) *dayp = 0;
2780     if(hourp) *hourp = 0;
2781     if(minp) *minp = 0;
2782     if(secp) *secp = 0;
2783   }
2784   if(yearp) *yearp = ts.tm_year + 1900;
2785   if(monp) *monp = ts.tm_mon + 1;
2786   if(dayp) *dayp = ts.tm_mday;
2787   if(hourp) *hourp = ts.tm_hour;
2788   if(minp) *minp = ts.tm_min;
2789   if(secp) *secp = ts.tm_sec;
2790 }
2791
2792
2793 /* Format a date as a string in W3CDTF. */
2794 void tcdatestrwww(int64_t t, int jl, char *buf){
2795   assert(buf);
2796   if(t == INT64_MAX || jl == INT_MAX){
2797     struct timeval tv;
2798     struct timezone tz;
2799     if(gettimeofday(&tv, &tz) == 0){
2800       if(t == INT64_MAX) t = tv.tv_sec;
2801       if(jl == INT_MAX) jl = tz.tz_minuteswest * -60;
2802     } else {
2803       if(t == INT64_MAX) t = time(NULL);
2804       if(jl == INT_MAX) jl = 0;
2805     }
2806   }
2807   time_t tt = (time_t)t + jl;
2808   struct tm ts;
2809   if(!gmtime_r(&tt, &ts)) memset(&ts, 0, sizeof(ts));
2810   ts.tm_year += 1900;
2811   ts.tm_mon += 1;
2812   jl /= 60;
2813   char tzone[16];
2814   if(jl == 0){
2815     sprintf(tzone, "Z");
2816   } else if(jl < 0){
2817     jl *= -1;
2818     sprintf(tzone, "-%02d:%02d", jl / 60, jl % 60);
2819   } else {
2820     sprintf(tzone, "+%02d:%02d", jl / 60, jl % 60);
2821   }
2822   sprintf(buf, "%04d-%02d-%02dT%02d:%02d:%02d%s",
2823           ts.tm_year, ts.tm_mon, ts.tm_mday, ts.tm_hour, ts.tm_min, ts.tm_sec, tzone);
2824 }
2825
2826
2827 /* Format a date as a string in RFC 1123 format. */
2828 void tcdatestrhttp(int64_t t, int jl, char *buf){
2829   assert(buf);
2830   if(t == INT64_MAX || jl == INT_MAX){
2831     struct timeval tv;
2832     struct timezone tz;
2833     if(gettimeofday(&tv, &tz) == 0){
2834       if(t == INT64_MAX) t = tv.tv_sec;
2835       if(jl == INT_MAX) jl = tz.tz_minuteswest * -60;
2836     } else {
2837       if(t == INT64_MAX) t = time(NULL);
2838       if(jl == INT_MAX) jl = 0;
2839     }
2840   }
2841   time_t tt = (time_t)t + jl;
2842   struct tm ts;
2843   if(!gmtime_r(&tt, &ts)) memset(&ts, 0, sizeof(ts));
2844   ts.tm_year += 1900;
2845   ts.tm_mon += 1;
2846   jl /= 60;
2847   char *wp = buf;
2848   switch(tcdayofweek(ts.tm_year, ts.tm_mon, ts.tm_mday)){
2849   case 0: wp += sprintf(wp, "Sun, "); break;
2850   case 1: wp += sprintf(wp, "Mon, "); break;
2851   case 2: wp += sprintf(wp, "Tue, "); break;
2852   case 3: wp += sprintf(wp, "Wed, "); break;
2853   case 4: wp += sprintf(wp, "Thu, "); break;
2854   case 5: wp += sprintf(wp, "Fri, "); break;
2855   case 6: wp += sprintf(wp, "Sat, "); break;
2856   }
2857   wp += sprintf(wp, "%02d ", ts.tm_mday);
2858   switch(ts.tm_mon){
2859   case 1: wp += sprintf(wp, "Jan "); break;
2860   case 2: wp += sprintf(wp, "Feb "); break;
2861   case 3: wp += sprintf(wp, "Mar "); break;
2862   case 4: wp += sprintf(wp, "Apr "); break;
2863   case 5: wp += sprintf(wp, "May "); break;
2864   case 6: wp += sprintf(wp, "Jun "); break;
2865   case 7: wp += sprintf(wp, "Jul "); break;
2866   case 8: wp += sprintf(wp, "Aug "); break;
2867   case 9: wp += sprintf(wp, "Sep "); break;
2868   case 10: wp += sprintf(wp, "Oct "); break;
2869   case 11: wp += sprintf(wp, "Nov "); break;
2870   case 12: wp += sprintf(wp, "Dec "); break;
2871   }
2872   wp += sprintf(wp, "%04d %02d:%02d:%02d ", ts.tm_year, ts.tm_hour, ts.tm_min, ts.tm_sec);
2873   if(jl == 0){
2874     sprintf(wp, "GMT");
2875   } else if(jl < 0){
2876     jl *= -1;
2877     sprintf(wp, "-%02d%02d", jl / 60, jl % 60);
2878   } else {
2879     sprintf(wp, "+%02d%02d", jl / 60, jl % 60);
2880   }
2881 }
2882
2883
2884 /* Get the time value of a date string. */
2885 int64_t tcstrmktime(const char *str){
2886   assert(str);
2887   while(*str > '\0' && *str <= ' '){
2888     str++;
2889   }
2890   if(*str == '\0') return 0;
2891   if(str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
2892     return (int64_t)strtoll(str + 2, NULL, 16);
2893   struct tm ts;
2894   memset(&ts, 0, sizeof(ts));
2895   ts.tm_year = 70;
2896   ts.tm_mon = 0;
2897   ts.tm_mday = 1;
2898   ts.tm_hour = 0;
2899   ts.tm_min = 0;
2900   ts.tm_sec = 0;
2901   ts.tm_isdst = 0;
2902   int len = strlen(str);
2903   char *pv;
2904   time_t t = (time_t)strtoll(str, &pv, 10);
2905   if(*(signed char *)pv >= '\0' && *pv <= ' '){
2906     while(*pv > '\0' && *pv <= ' '){
2907       pv++;
2908     }
2909     if(*pv == '\0') return (int64_t)t;
2910   }
2911   if((pv[0] == 's' || pv[0] == 'S') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ')
2912     return (int64_t)t;
2913   if((pv[0] == 'm' || pv[0] == 'M') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ')
2914     return (int64_t)t * 60;
2915   if((pv[0] == 'h' || pv[0] == 'H') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ')
2916     return (int64_t)t * 60 * 60;
2917   if((pv[0] == 'd' || pv[0] == 'D') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ')
2918     return (int64_t)t * 60 * 60 * 24;
2919   if(len > 4 && str[4] == '-'){
2920     ts.tm_year = atoi(str) - 1900;
2921     if((pv = strchr(str, '-')) != NULL && pv - str == 4){
2922       char *rp = pv + 1;
2923       ts.tm_mon = atoi(rp) - 1;
2924       if((pv = strchr(rp, '-')) != NULL && pv - str == 7){
2925         rp = pv + 1;
2926         ts.tm_mday = atoi(rp);
2927         if((pv = strchr(rp, 'T')) != NULL && pv - str == 10){
2928           rp = pv + 1;
2929           ts.tm_hour = atoi(rp);
2930           if((pv = strchr(rp, ':')) != NULL && pv - str == 13){
2931             rp = pv + 1;
2932             ts.tm_min = atoi(rp);
2933           }
2934           if((pv = strchr(rp, ':')) != NULL && pv - str == 16){
2935             rp = pv + 1;
2936             ts.tm_sec = atoi(rp);
2937           }
2938           if((pv = strchr(rp, '.')) != NULL && pv - str >= 19) rp = pv + 1;
2939           strtol(rp, &pv, 10);
2940           if((*pv == '+' || *pv == '-') && strlen(pv) >= 6 && pv[3] == ':')
2941             ts.tm_sec -= (atoi(pv + 1) * 3600 + atoi(pv + 4) * 60) * (pv[0] == '+' ? 1 : -1);
2942         }
2943       }
2944     }
2945     return (int64_t)tcmkgmtime(&ts);
2946   }
2947   if(len > 4 && str[4] == '/'){
2948     ts.tm_year = atoi(str) - 1900;
2949     if((pv = strchr(str, '/')) != NULL && pv - str == 4){
2950       char *rp = pv + 1;
2951       ts.tm_mon = atoi(rp) - 1;
2952       if((pv = strchr(rp, '/')) != NULL && pv - str == 7){
2953         rp = pv + 1;
2954         ts.tm_mday = atoi(rp);
2955         if((pv = strchr(rp, ' ')) != NULL && pv - str == 10){
2956           rp = pv + 1;
2957           ts.tm_hour = atoi(rp);
2958           if((pv = strchr(rp, ':')) != NULL && pv - str == 13){
2959             rp = pv + 1;
2960             ts.tm_min = atoi(rp);
2961           }
2962           if((pv = strchr(rp, ':')) != NULL && pv - str == 16){
2963             rp = pv + 1;
2964             ts.tm_sec = atoi(rp);
2965           }
2966           if((pv = strchr(rp, '.')) != NULL && pv - str >= 19) rp = pv + 1;
2967           strtol(rp, &pv, 10);
2968           if((*pv == '+' || *pv == '-') && strlen(pv) >= 6 && pv[3] == ':')
2969             ts.tm_sec -= (atoi(pv + 1) * 3600 + atoi(pv + 4) * 60) * (pv[0] == '+' ? 1 : -1);
2970         }
2971       }
2972     }
2973     return (int64_t)tcmkgmtime(&ts);
2974   }
2975   const char *crp = str;
2976   if(len >= 4 && str[3] == ',') crp = str + 4;
2977   while(*crp == ' '){
2978     crp++;
2979   }
2980   ts.tm_mday = atoi(crp);
2981   while((*crp >= '0' && *crp <= '9') || *crp == ' '){
2982     crp++;
2983   }
2984   if(tcstrifwm(crp, "Jan")){
2985     ts.tm_mon = 0;
2986   } else if(tcstrifwm(crp, "Feb")){
2987     ts.tm_mon = 1;
2988   } else if(tcstrifwm(crp, "Mar")){
2989     ts.tm_mon = 2;
2990   } else if(tcstrifwm(crp, "Apr")){
2991     ts.tm_mon = 3;
2992   } else if(tcstrifwm(crp, "May")){
2993     ts.tm_mon = 4;
2994   } else if(tcstrifwm(crp, "Jun")){
2995     ts.tm_mon = 5;
2996   } else if(tcstrifwm(crp, "Jul")){
2997     ts.tm_mon = 6;
2998   } else if(tcstrifwm(crp, "Aug")){
2999     ts.tm_mon = 7;
3000   } else if(tcstrifwm(crp, "Sep")){
3001     ts.tm_mon = 8;
3002   } else if(tcstrifwm(crp, "Oct")){
3003     ts.tm_mon = 9;
3004   } else if(tcstrifwm(crp, "Nov")){
3005     ts.tm_mon = 10;
3006   } else if(tcstrifwm(crp, "Dec")){
3007     ts.tm_mon = 11;
3008   } else {
3009     ts.tm_mon = -1;
3010   }
3011   if(ts.tm_mon >= 0) crp += 3;
3012   while(*crp == ' '){
3013     crp++;
3014   }
3015   ts.tm_year = atoi(crp);
3016   if(ts.tm_year >= 1969) ts.tm_year -= 1900;
3017   while(*crp >= '0' && *crp <= '9'){
3018     crp++;
3019   }
3020   while(*crp == ' '){
3021     crp++;
3022   }
3023   if(ts.tm_mday > 0 && ts.tm_mon >= 0 && ts.tm_year >= 0){
3024     int clen = strlen(crp);
3025     if(clen >= 8 && crp[2] == ':' && crp[5] == ':'){
3026       ts.tm_hour = atoi(crp + 0);
3027       ts.tm_min = atoi(crp + 3);
3028       ts.tm_sec = atoi(crp + 6);
3029       if(clen >= 14 && crp[8] == ' ' && (crp[9] == '+' || crp[9] == '-')){
3030         ts.tm_sec -= ((crp[10] - '0') * 36000 + (crp[11] - '0') * 3600 +
3031                       (crp[12] - '0') * 600 + (crp[13] - '0') * 60) * (crp[9] == '+' ? 1 : -1);
3032       } else if(clen > 9){
3033         if(!strcmp(crp + 9, "JST")){
3034           ts.tm_sec -= 9 * 3600;
3035         } else if(!strcmp(crp + 9, "CCT")){
3036           ts.tm_sec -= 8 * 3600;
3037         } else if(!strcmp(crp + 9, "KST")){
3038           ts.tm_sec -= 9 * 3600;
3039         } else if(!strcmp(crp + 9, "EDT")){
3040           ts.tm_sec -= -4 * 3600;
3041         } else if(!strcmp(crp + 9, "EST")){
3042           ts.tm_sec -= -5 * 3600;
3043         } else if(!strcmp(crp + 9, "CDT")){
3044           ts.tm_sec -= -5 * 3600;
3045         } else if(!strcmp(crp + 9, "CST")){
3046           ts.tm_sec -= -6 * 3600;
3047         } else if(!strcmp(crp + 9, "MDT")){
3048           ts.tm_sec -= -6 * 3600;
3049         } else if(!strcmp(crp + 9, "MST")){
3050           ts.tm_sec -= -7 * 3600;
3051         } else if(!strcmp(crp + 9, "PDT")){
3052           ts.tm_sec -= -7 * 3600;
3053         } else if(!strcmp(crp + 9, "PST")){
3054           ts.tm_sec -= -8 * 3600;
3055         } else if(!strcmp(crp + 9, "HDT")){
3056           ts.tm_sec -= -9 * 3600;
3057         } else if(!strcmp(crp + 9, "HST")){
3058           ts.tm_sec -= -10 * 3600;
3059         }
3060       }
3061     }
3062     return (int64_t)tcmkgmtime(&ts);
3063   }
3064   return 0;
3065 }
3066
3067
3068 /* Get the day of week of a date. */
3069 int tcdayofweek(int year, int mon, int day){
3070   if(mon < 3){
3071     year--;
3072     mon += 12;
3073   }
3074   return (day + ((8 + (13 * mon)) / 5) + (year + (year / 4) - (year / 100) + (year / 400))) % 7;
3075 }
3076
3077
3078 /* Close the random number generator. */
3079 static void tcrandomfdclose(void){
3080   close(tcrandomdevfd);
3081 }
3082
3083
3084 /* Make the GMT from a time structure.
3085    `tm' specifies the pointer to the time structure.
3086    The return value is the GMT. */
3087 static time_t tcmkgmtime(struct tm *tm){
3088 #if defined(_SYS_LINUX_)
3089   assert(tm);
3090   return timegm(tm);
3091 #else
3092   assert(tm);
3093   static int jl = INT_MAX;
3094   if(jl == INT_MAX){
3095     struct timeval tv;
3096     struct timezone tz;
3097     if(gettimeofday(&tv, &tz) == 0){
3098       jl = tz.tz_minuteswest * -60;
3099     } else {
3100       jl = 0;
3101     }
3102   }
3103   tm->tm_sec += jl;
3104   return mktime(tm);
3105 #endif
3106 }
3107
3108
3109
3110 /*************************************************************************************************
3111  * filesystem utilities
3112  *************************************************************************************************/
3113
3114
3115 #define TCFILEMODE     00644             // permission of a creating file
3116 #define TCIOBUFSIZ     16384             // size of an I/O buffer
3117
3118
3119 /* Get the canonicalized absolute path of a file. */
3120 char *tcrealpath(const char *path){
3121   assert(path);
3122   char buf[PATH_MAX];
3123   if(!realpath(path, buf)) return NULL;
3124   return tcstrdup(buf);
3125 }
3126
3127
3128 /* Read whole data of a file. */
3129 void *tcreadfile(const char *path, int limit, int *sp){
3130   int fd = path ? open(path, O_RDONLY, TCFILEMODE) : 0;
3131   if(fd == -1) return NULL;
3132   if(fd == 0){
3133     TCXSTR *xstr = tcxstrnew();
3134     char buf[TCIOBUFSIZ];
3135     limit = limit > 0 ? limit : INT_MAX;
3136     int rsiz;
3137     while((rsiz = read(fd, buf, tclmin(TCIOBUFSIZ, limit))) > 0){
3138       TCXSTRCAT(xstr, buf, rsiz);
3139       limit -= rsiz;
3140     }
3141     if(sp) *sp = TCXSTRSIZE(xstr);
3142     return tcxstrtomalloc(xstr);
3143   }
3144   struct stat sbuf;
3145   if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode)){
3146     close(fd);
3147     return NULL;
3148   }
3149   limit = limit > 0 ? tclmin((int)sbuf.st_size, limit) : sbuf.st_size;
3150   char *buf;
3151   TCMALLOC(buf, sbuf.st_size + 1);
3152   char *wp = buf;
3153   int rsiz;
3154   while((rsiz = read(fd, wp, limit - (wp - buf))) > 0){
3155     wp += rsiz;
3156   }
3157   *wp = '\0';
3158   close(fd);
3159   if(sp) *sp = wp - buf;
3160   return buf;
3161 }
3162
3163
3164 /* Read every line of a file. */
3165 TCLIST *tcreadfilelines(const char *path){
3166   int fd = path ? open(path, O_RDONLY, TCFILEMODE) : 0;
3167   if(fd == -1) return NULL;
3168   TCLIST *list = tclistnew();
3169   TCXSTR *xstr = tcxstrnew();
3170   char buf[TCIOBUFSIZ];
3171   int rsiz;
3172   while((rsiz = read(fd, buf, TCIOBUFSIZ)) > 0){
3173     for(int i = 0; i < rsiz; i++){
3174       switch(buf[i]){
3175       case '\r':
3176         break;
3177       case '\n':
3178         TCLISTPUSH(list, TCXSTRPTR(xstr), TCXSTRSIZE(xstr));
3179         tcxstrclear(xstr);
3180         break;
3181       default:
3182         TCXSTRCAT(xstr, buf + i, 1);
3183         break;
3184       }
3185     }
3186   }
3187   TCLISTPUSH(list, TCXSTRPTR(xstr), TCXSTRSIZE(xstr));
3188   tcxstrdel(xstr);
3189   if(path) close(fd);
3190   return list;
3191 }
3192
3193
3194 /* Write data into a file. */
3195 bool tcwritefile(const char *path, const void *ptr, int size){
3196   assert(ptr && size >= 0);
3197   int fd = 1;
3198   if(path && (fd = open(path, O_WRONLY | O_CREAT | O_TRUNC, TCFILEMODE)) == -1) return false;
3199   bool err = false;
3200   if(!tcwrite(fd, ptr, size)) err = true;
3201   if(close(fd) == -1) err = true;
3202   return !err;
3203 }
3204
3205
3206 /* Copy a file. */
3207 bool tccopyfile(const char *src, const char *dest){
3208   int ifd = open(src, O_RDONLY, TCFILEMODE);
3209   if(ifd == -1) return false;
3210   int ofd = open(dest, O_WRONLY | O_CREAT | O_TRUNC, TCFILEMODE);
3211   if(ofd == -1){
3212     close(ifd);
3213     return false;
3214   }
3215   bool err = false;
3216   while(true){
3217     char buf[TCIOBUFSIZ];
3218     int size = read(ifd, buf, TCIOBUFSIZ);
3219     if(size > 0){
3220       if(!tcwrite(ofd, buf, size)){
3221         err = true;
3222         break;
3223       }
3224     } else if(size == -1){
3225       if(errno != EINTR){
3226         err = true;
3227         break;
3228       }
3229     } else {
3230       break;
3231     }
3232   }
3233   if(close(ofd) == -1) err = true;
3234   if(close(ifd) == -1) err = true;
3235   return !err;
3236 }
3237
3238
3239 /* Read names of files in a directory. */
3240 TCLIST *tcreaddir(const char *path){
3241   assert(path);
3242   DIR *DD;
3243   struct dirent *dp;
3244   if(!(DD = opendir(path))) return NULL;
3245   TCLIST *list = tclistnew();
3246   while((dp = readdir(DD)) != NULL){
3247     if(!strcmp(dp->d_name, MYCDIRSTR) || !strcmp(dp->d_name, MYPDIRSTR)) continue;
3248     TCLISTPUSH(list, dp->d_name, strlen(dp->d_name));
3249   }
3250   closedir(DD);
3251   return list;
3252 }
3253
3254
3255 /* Expand a pattern into a list of matched paths. */
3256 TCLIST *tcglobpat(const char *pattern){
3257   assert(pattern);
3258   TCLIST *list = tclistnew();
3259   glob_t gbuf;
3260   memset(&gbuf, 0, sizeof(gbuf));
3261   if(glob(pattern, GLOB_ERR | GLOB_NOSORT, NULL, &gbuf) == 0){
3262     for(int i = 0; i < gbuf.gl_pathc; i++){
3263       tclistpush2(list, gbuf.gl_pathv[i]);
3264     }
3265     globfree(&gbuf);
3266   }
3267   return list;
3268 }
3269
3270
3271 /* Remove a file or a directory and its sub ones recursively. */
3272 bool tcremovelink(const char *path){
3273   assert(path);
3274   struct stat sbuf;
3275   if(lstat(path, &sbuf) == -1) return false;
3276   if(unlink(path) == 0) return true;
3277   TCLIST *list;
3278   if(!S_ISDIR(sbuf.st_mode) || !(list = tcreaddir(path))) return false;
3279   bool tail = path[0] != '\0' && path[strlen(path)-1] == MYPATHCHR;
3280   for(int i = 0; i < TCLISTNUM(list); i++){
3281     const char *elem = TCLISTVALPTR(list, i);
3282     if(!strcmp(MYCDIRSTR, elem) || !strcmp(MYPDIRSTR, elem)) continue;
3283     char *cpath;
3284     if(tail){
3285       cpath = tcsprintf("%s%s", path, elem);
3286     } else {
3287       cpath = tcsprintf("%s%c%s", path, MYPATHCHR, elem);
3288     }
3289     tcremovelink(cpath);
3290     free(cpath);
3291   }
3292   tclistdel(list);
3293   return rmdir(path) == 0 ? true : false;
3294 }
3295
3296
3297 /* Write data into a file. */
3298 bool tcwrite(int fd, const void *buf, size_t size){
3299   assert(fd >= 0 && buf && size >= 0);
3300   const char *rp = buf;
3301   do {
3302     int wb = write(fd, rp, size);
3303     switch(wb){
3304     case -1: if(errno != EINTR) return false;
3305     case 0: break;
3306     default:
3307       rp += wb;
3308       size -= wb;
3309       break;
3310     }
3311   } while(size > 0);
3312   return true;
3313 }
3314
3315
3316 /* Read data from a file. */
3317 bool tcread(int fd, void *buf, size_t size){
3318   assert(fd >= 0 && buf && size >= 0);
3319   char *wp = buf;
3320   do {
3321     int rb = read(fd, wp, size);
3322     switch(rb){
3323     case -1: if(errno != EINTR) return false;
3324     case 0: return size < 1;
3325     default:
3326       wp += rb;
3327       size -= rb;
3328     }
3329   } while(size > 0);
3330   return true;
3331 }
3332
3333
3334 /* Lock a file. */
3335 bool tclock(int fd, bool ex, bool nb){
3336   assert(fd >= 0);
3337   struct flock lock;
3338   memset(&lock, 0, sizeof(struct flock));
3339   lock.l_type = ex ? F_WRLCK : F_RDLCK;
3340   lock.l_whence = SEEK_SET;
3341   lock.l_start = 0;
3342   lock.l_len = 0;
3343   lock.l_pid = 0;
3344   while(fcntl(fd, nb ? F_SETLK : F_SETLKW, &lock) == -1){
3345     if(errno != EINTR) return false;
3346   }
3347   return true;
3348 }
3349
3350
3351
3352 /*************************************************************************************************
3353  * encoding utilities
3354  *************************************************************************************************/
3355
3356
3357 #define TCURLELBNUM    31                // bucket number of URL elements
3358 #define TCENCBUFSIZ    32                // size of a buffer for encoding name
3359 #define TCXMLATBNUM    31                // bucket number of XML attributes
3360
3361
3362 /* Encode a serial object with URL encoding. */
3363 char *tcurlencode(const char *ptr, int size){
3364   assert(ptr && size >= 0);
3365   char *buf;
3366   TCMALLOC(buf, size * 3 + 1);
3367   char *wp = buf;
3368   for(int i = 0; i < size; i++){
3369     int c = ((unsigned char *)ptr)[i];
3370     if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
3371        (c >= '0' && c <= '9') || (c != '\0' && strchr("_-.!~*'()", c))){
3372       *(wp++) = c;
3373     } else {
3374       wp += sprintf(wp, "%%%02X", c);
3375     }
3376   }
3377   *wp = '\0';
3378   return buf;
3379 }
3380
3381
3382 /* Decode a string encoded with URL encoding. */
3383 char *tcurldecode(const char *str, int *sp){
3384   assert(str && sp);
3385   char *buf = tcstrdup(str);
3386   char *wp = buf;
3387   while(*str != '\0'){
3388     if(*str == '%'){
3389       str++;
3390       if(((str[0] >= '0' && str[0] <= '9') || (str[0] >= 'A' && str[0] <= 'F') ||
3391           (str[0] >= 'a' && str[0] <= 'f')) &&
3392          ((str[1] >= '0' && str[1] <= '9') || (str[1] >= 'A' && str[1] <= 'F') ||
3393           (str[1] >= 'a' && str[1] <= 'f'))){
3394         unsigned char c = *str;
3395         if(c >= 'A' && c <= 'Z') c += 'a' - 'A';
3396         if(c >= 'a' && c <= 'z'){
3397           *wp = c - 'a' + 10;
3398         } else {
3399           *wp = c - '0';
3400         }
3401         *wp *= 0x10;
3402         str++;
3403         c = *str;
3404         if(c >= 'A' && c <= 'Z') c += 'a' - 'A';
3405         if(c >= 'a' && c <= 'z'){
3406           *wp += c - 'a' + 10;
3407         } else {
3408           *wp += c - '0';
3409         }
3410         str++;
3411         wp++;
3412       } else {
3413         break;
3414       }
3415     } else if(*str == '+'){
3416       *wp = ' ';
3417       str++;
3418       wp++;
3419     } else {
3420       *wp = *str;
3421       str++;
3422       wp++;
3423     }
3424   }
3425   *wp = '\0';
3426   *sp = wp - buf;
3427   return buf;
3428 }
3429
3430
3431 /* Break up a URL into elements. */
3432 TCMAP *tcurlbreak(const char *str){
3433   assert(str);
3434   TCMAP *map = tcmapnew2(TCURLELBNUM);
3435   char *tmp = tcstrdup(str);
3436   const char *rp = tcstrtrim(tmp);
3437   tcmapput2(map, "self", rp);
3438   bool serv = false;
3439   if(tcstrifwm(rp, "http://")){
3440     tcmapput2(map, "scheme", "http");
3441     rp += 7;
3442     serv = true;
3443   } else if(tcstrifwm(rp, "https://")){
3444     tcmapput2(map, "scheme", "https");
3445     rp += 8;
3446     serv = true;
3447   } else if(tcstrifwm(rp, "ftp://")){
3448     tcmapput2(map, "scheme", "ftp");
3449     rp += 6;
3450     serv = true;
3451   } else if(tcstrifwm(rp, "sftp://")){
3452     tcmapput2(map, "scheme", "sftp");
3453     rp += 7;
3454     serv = true;
3455   } else if(tcstrifwm(rp, "ftps://")){
3456     tcmapput2(map, "scheme", "ftps");
3457     rp += 7;
3458     serv = true;
3459   } else if(tcstrifwm(rp, "tftp://")){
3460     tcmapput2(map, "scheme", "tftp");
3461     rp += 7;
3462     serv = true;
3463   } else if(tcstrifwm(rp, "ldap://")){
3464     tcmapput2(map, "scheme", "ldap");
3465     rp += 7;
3466     serv = true;
3467   } else if(tcstrifwm(rp, "ldaps://")){
3468     tcmapput2(map, "scheme", "ldaps");
3469     rp += 8;
3470     serv = true;
3471   } else if(tcstrifwm(rp, "file://")){
3472     tcmapput2(map, "scheme", "file");
3473     rp += 7;
3474     serv = true;
3475   }
3476   char *ep;
3477   if((ep = strchr(rp, '#')) != NULL){
3478     tcmapput2(map, "fragment", ep + 1);
3479     *ep = '\0';
3480   }
3481   if((ep = strchr(rp, '?')) != NULL){
3482     tcmapput2(map, "query", ep + 1);
3483     *ep = '\0';
3484   }
3485   if(serv){
3486     if((ep = strchr(rp, '/')) != NULL){
3487       tcmapput2(map, "path", ep);
3488       *ep = '\0';
3489     } else {
3490       tcmapput2(map, "path", "/");
3491     }
3492     if((ep = strchr(rp, '@')) != NULL){
3493       *ep = '\0';
3494       if(rp[0] != '\0') tcmapput2(map, "authority", rp);
3495       rp = ep + 1;
3496     }
3497     if((ep = strchr(rp, ':')) != NULL){
3498       if(ep[1] != '\0') tcmapput2(map, "port", ep + 1);
3499       *ep = '\0';
3500     }
3501     if(rp[0] != '\0') tcmapput2(map, "host", rp);
3502   } else {
3503     tcmapput2(map, "path", rp);
3504   }
3505   free(tmp);
3506   if((rp = tcmapget2(map, "path")) != NULL){
3507     if((ep = strrchr(rp, '/')) != NULL){
3508       if(ep[1] != '\0') tcmapput2(map, "file", ep + 1);
3509     } else {
3510       tcmapput2(map, "file", rp);
3511     }
3512   }
3513   if((rp = tcmapget2(map, "file")) != NULL && (!strcmp(rp, ".") || !strcmp(rp, "..")))
3514     tcmapout2(map, "file");
3515   return map;
3516 }
3517
3518
3519 /* Resolve a relative URL with an absolute URL. */
3520 char *tcurlresolve(const char *base, const char *target){
3521   assert(base && target);
3522   const char *vbuf, *path;
3523   char *tmp, *wp, *enc;
3524   while(*base > '\0' && *base <= ' '){
3525     base++;
3526   }
3527   while(*target > '\0' && *target <= ' '){
3528     target++;
3529   }
3530   if(*target == '\0') target = base;
3531   TCXSTR *rbuf = tcxstrnew();
3532   TCMAP *telems = tcurlbreak(target);
3533   int port = 80;
3534   TCMAP *belems = tcurlbreak(tcmapget2(telems, "scheme") ? target : base);
3535   if((vbuf = tcmapget2(belems, "scheme")) != NULL){
3536     tcxstrcat2(rbuf, vbuf);
3537     TCXSTRCAT(rbuf, "://", 3);
3538     if(!tcstricmp(vbuf, "https")){
3539       port = 443;
3540     } else if(!tcstricmp(vbuf, "ftp")){
3541       port = 21;
3542     } else if(!tcstricmp(vbuf, "sftp")){
3543       port = 115;
3544     } else if(!tcstricmp(vbuf, "ftps")){
3545       port = 22;
3546     } else if(!tcstricmp(vbuf, "tftp")){
3547       port = 69;
3548     } else if(!tcstricmp(vbuf, "ldap")){
3549       port = 389;
3550     } else if(!tcstricmp(vbuf, "ldaps")){
3551       port = 636;
3552     }
3553   } else {
3554     tcxstrcat2(rbuf, "http://");
3555   }
3556   int vsiz;
3557   if((vbuf = tcmapget2(belems, "authority")) != NULL){
3558     if((wp = strchr(vbuf, ':')) != NULL){
3559       *wp = '\0';
3560       tmp = tcurldecode(vbuf, &vsiz);
3561       enc = tcurlencode(tmp, vsiz);
3562       tcxstrcat2(rbuf, enc);
3563       free(enc);
3564       free(tmp);
3565       TCXSTRCAT(rbuf, ":", 1);
3566       wp++;
3567       tmp = tcurldecode(wp, &vsiz);
3568       enc = tcurlencode(tmp, vsiz);
3569       tcxstrcat2(rbuf, enc);
3570       free(enc);
3571       free(tmp);
3572     } else {
3573       tmp = tcurldecode(vbuf, &vsiz);
3574       enc = tcurlencode(tmp, vsiz);
3575       tcxstrcat2(rbuf, enc);
3576       free(enc);
3577       free(tmp);
3578     }
3579     TCXSTRCAT(rbuf, "@", 1);
3580   }
3581   if((vbuf = tcmapget2(belems, "host")) != NULL){
3582     tmp = tcurldecode(vbuf, &vsiz);
3583     tcstrtolower(tmp);
3584     enc = tcurlencode(tmp, vsiz);
3585     tcxstrcat2(rbuf, enc);
3586     free(enc);
3587     free(tmp);
3588   } else {
3589     TCXSTRCAT(rbuf, "localhost", 9);
3590   }
3591   int num;
3592   char numbuf[TCNUMBUFSIZ];
3593   if((vbuf = tcmapget2(belems, "port")) != NULL && (num = atoi(vbuf)) != port && num > 0){
3594     sprintf(numbuf, ":%d", num);
3595     tcxstrcat2(rbuf, numbuf);
3596   }
3597   if(!(path = tcmapget2(telems, "path"))) path = "/";
3598   if(path[0] == '\0' && (vbuf = tcmapget2(belems, "path")) != NULL) path = vbuf;
3599   if(path[0] == '\0') path = "/";
3600   TCLIST *bpaths = tclistnew();
3601   TCLIST *opaths;
3602   if(path[0] != '/' && (vbuf = tcmapget2(belems, "path")) != NULL){
3603     opaths = tcstrsplit(vbuf, "/");
3604   } else {
3605     opaths = tcstrsplit("/", "/");
3606   }
3607   free(tclistpop2(opaths));
3608   for(int i = 0; i < TCLISTNUM(opaths); i++){
3609     vbuf = tclistval(opaths, i, &vsiz);
3610     if(vsiz < 1 || !strcmp(vbuf, ".")) continue;
3611     if(!strcmp(vbuf, "..")){
3612       free(tclistpop2(bpaths));
3613     } else {
3614       TCLISTPUSH(bpaths, vbuf, vsiz);
3615     }
3616   }
3617   tclistdel(opaths);
3618   opaths = tcstrsplit(path, "/");
3619   for(int i = 0; i < TCLISTNUM(opaths); i++){
3620     vbuf = tclistval(opaths, i, &vsiz);
3621     if(vsiz < 1 || !strcmp(vbuf, ".")) continue;
3622     if(!strcmp(vbuf, "..")){
3623       free(tclistpop2(bpaths));
3624     } else {
3625       TCLISTPUSH(bpaths, vbuf, vsiz);
3626     }
3627   }
3628   tclistdel(opaths);
3629   for(int i = 0; i < TCLISTNUM(bpaths); i++){
3630     vbuf = TCLISTVALPTR(bpaths, i);
3631     if(strchr(vbuf, '%')){
3632       tmp = tcurldecode(vbuf, &vsiz);
3633     } else {
3634       tmp = tcstrdup(vbuf);
3635     }
3636     enc = tcurlencode(tmp, strlen(tmp));
3637     TCXSTRCAT(rbuf, "/", 1);
3638     tcxstrcat2(rbuf, enc);
3639     free(enc);
3640     free(tmp);
3641   }
3642   if(tcstrbwm(path, "/")) TCXSTRCAT(rbuf, "/", 1);
3643   tclistdel(bpaths);
3644   if((vbuf = tcmapget2(telems, "query")) != NULL ||
3645      (*target == '#' && (vbuf = tcmapget2(belems, "query")) != NULL)){
3646     TCXSTRCAT(rbuf, "?", 1);
3647     TCLIST *qelems = tcstrsplit(vbuf, "&;");
3648     for(int i = 0; i < TCLISTNUM(qelems); i++){
3649       vbuf = TCLISTVALPTR(qelems, i);
3650       if(i > 0) TCXSTRCAT(rbuf, "&", 1);
3651       if((wp = strchr(vbuf, '=')) != NULL){
3652         *wp = '\0';
3653         tmp = tcurldecode(vbuf, &vsiz);
3654         enc = tcurlencode(tmp, vsiz);
3655         tcxstrcat2(rbuf, enc);
3656         free(enc);
3657         free(tmp);
3658         TCXSTRCAT(rbuf, "=", 1);
3659         wp++;
3660         tmp = tcurldecode(wp, &vsiz);
3661         enc = tcurlencode(tmp, strlen(tmp));
3662         tcxstrcat2(rbuf, enc);
3663         free(enc);
3664         free(tmp);
3665       } else {
3666         tmp = tcurldecode(vbuf, &vsiz);
3667         enc = tcurlencode(tmp, vsiz);
3668         tcxstrcat2(rbuf, enc);
3669         free(enc);
3670         free(tmp);
3671       }
3672     }
3673     tclistdel(qelems);
3674   }
3675   if((vbuf = tcmapget2(telems, "fragment")) != NULL){
3676     tmp = tcurldecode(vbuf, &vsiz);
3677     enc = tcurlencode(tmp, vsiz);
3678     TCXSTRCAT(rbuf, "#", 1);
3679     tcxstrcat2(rbuf, enc);
3680     free(enc);
3681     free(tmp);
3682   }
3683   tcmapdel(belems);
3684   tcmapdel(telems);
3685   return tcxstrtomalloc(rbuf);
3686 }
3687
3688
3689 /* Encode a serial object with Base64 encoding. */
3690 char *tcbaseencode(const char *ptr, int size){
3691   assert(ptr && size >= 0);
3692   char *tbl = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
3693   const unsigned char *obj = (const unsigned char *)ptr;
3694   char *buf;
3695   TCMALLOC(buf, 4 * (size + 2) / 3 + 1);
3696   char *wp = buf;
3697   for(int i = 0; i < size; i += 3){
3698     switch(size - i){
3699     case 1:
3700       *wp++ = tbl[obj[0] >> 2];
3701       *wp++ = tbl[(obj[0] & 3) << 4];
3702       *wp++ = '=';
3703       *wp++ = '=';
3704       break;
3705     case 2:
3706       *wp++ = tbl[obj[0] >> 2];
3707       *wp++ = tbl[((obj[0] & 3) << 4) + (obj[1] >> 4)];
3708       *wp++ = tbl[(obj[1] & 0xf) << 2];
3709       *wp++ = '=';
3710       break;
3711     default:
3712       *wp++ = tbl[obj[0] >> 2];
3713       *wp++ = tbl[((obj[0] & 3) << 4) + (obj[1] >> 4)];
3714       *wp++ = tbl[((obj[1] & 0xf) << 2) + (obj[2] >> 6)];
3715       *wp++ = tbl[obj[2] & 0x3f];
3716       break;
3717     }
3718     obj += 3;
3719   }
3720   *wp = '\0';
3721   return buf;
3722 }
3723
3724
3725 /* Decode a string encoded with Base64 encoding. */
3726 char *tcbasedecode(const char *str, int *sp){
3727   assert(str && sp);
3728   int cnt = 0;
3729   int bpos = 0;
3730   int eqcnt = 0;
3731   int len = strlen(str);
3732   unsigned char *obj;
3733   TCMALLOC(obj, len + 4);
3734   unsigned char *wp = obj;
3735   while(bpos < len && eqcnt == 0){
3736     int bits = 0;
3737     int i;
3738     for(i = 0; bpos < len && i < 4; bpos++){
3739       if(str[bpos] >= 'A' && str[bpos] <= 'Z'){
3740         bits = (bits << 6) | (str[bpos] - 'A');
3741         i++;
3742       } else if(str[bpos] >= 'a' && str[bpos] <= 'z'){
3743         bits = (bits << 6) | (str[bpos] - 'a' + 26);
3744         i++;
3745       } else if(str[bpos] >= '0' && str[bpos] <= '9'){
3746         bits = (bits << 6) | (str[bpos] - '0' + 52);
3747         i++;
3748       } else if(str[bpos] == '+'){
3749         bits = (bits << 6) | 62;
3750         i++;
3751       } else if(str[bpos] == '/'){
3752         bits = (bits << 6) | 63;
3753         i++;
3754       } else if(str[bpos] == '='){
3755         bits <<= 6;
3756         i++;
3757         eqcnt++;
3758       }
3759     }
3760     if(i == 0 && bpos >= len) continue;
3761     switch(eqcnt){
3762     case 0:
3763       *wp++ = (bits >> 16) & 0xff;
3764       *wp++ = (bits >> 8) & 0xff;
3765       *wp++ = bits & 0xff;
3766       cnt += 3;
3767       break;
3768     case 1:
3769       *wp++ = (bits >> 16) & 0xff;
3770       *wp++ = (bits >> 8) & 0xff;
3771       cnt += 2;
3772       break;
3773     case 2:
3774       *wp++ = (bits >> 16) & 0xff;
3775       cnt += 1;
3776       break;
3777     }
3778   }
3779   obj[cnt] = '\0';
3780   *sp = cnt;
3781   return (char *)obj;
3782 }
3783
3784
3785 /* Encode a serial object with Quoted-printable encoding. */
3786 char *tcquoteencode(const char *ptr, int size){
3787   assert(ptr && size >= 0);
3788   const unsigned char *rp = (const unsigned char *)ptr;
3789   char *buf;
3790   TCMALLOC(buf, size * 3 + 1);
3791   char *wp = buf;
3792   int cols = 0;
3793   for(int i = 0; i < size; i++){
3794     if(rp[i] == '=' || (rp[i] < 0x20 && rp[i] != '\r' && rp[i] != '\n' && rp[i] != '\t') ||
3795        rp[i] > 0x7e){
3796       wp += sprintf(wp, "=%02X", rp[i]);
3797       cols += 3;
3798     } else {
3799       *(wp++) = rp[i];
3800       cols++;
3801     }
3802   }
3803   *wp = '\0';
3804   return buf;
3805 }
3806
3807
3808 /* Decode a string encoded with Quoted-printable encoding. */
3809 char *tcquotedecode(const char *str, int *sp){
3810   assert(str && sp);
3811   char *buf;
3812   TCMALLOC(buf, strlen(str) + 1);
3813   char *wp = buf;
3814   for(; *str != '\0'; str++){
3815     if(*str == '='){
3816       str++;
3817       if(*str == '\0'){
3818         break;
3819       } else if(str[0] == '\r' && str[1] == '\n'){
3820         str++;
3821       } else if(str[0] != '\n' && str[0] != '\r'){
3822         if(*str >= 'A' && *str <= 'Z'){
3823           *wp = (*str - 'A' + 10) * 16;
3824         } else if(*str >= 'a' && *str <= 'z'){
3825           *wp = (*str - 'a' + 10) * 16;
3826         } else {
3827           *wp = (*str - '0') * 16;
3828         }
3829         str++;
3830         if(*str == '\0') break;
3831         if(*str >= 'A' && *str <= 'Z'){
3832           *wp += *str - 'A' + 10;
3833         } else if(*str >= 'a' && *str <= 'z'){
3834           *wp += *str - 'a' + 10;
3835         } else {
3836           *wp += *str - '0';
3837         }
3838         wp++;
3839       }
3840     } else {
3841       *wp = *str;
3842       wp++;
3843     }
3844   }
3845   *wp = '\0';
3846   *sp = wp - buf;
3847   return buf;
3848 }
3849
3850
3851 /* Encode a string with MIME encoding. */
3852 char *tcmimeencode(const char *str, const char *encname, bool base){
3853   assert(str && encname);
3854   int len = strlen(str);
3855   char *buf;
3856   TCMALLOC(buf, len * 3 + strlen(encname) + 16);
3857   char *wp = buf;
3858   wp += sprintf(wp, "=?%s?%c?", encname, base ? 'B' : 'Q');
3859   char *enc = base ? tcbaseencode(str, len) : tcquoteencode(str, len);
3860   wp += sprintf(wp, "%s?=", enc);
3861   free(enc);
3862   return buf;
3863 }
3864
3865
3866 /* Decode a string encoded with MIME encoding. */
3867 char *tcmimedecode(const char *str, char *enp){
3868   assert(str);
3869   if(enp) sprintf(enp, "US-ASCII");
3870   char *buf;
3871   TCMALLOC(buf, strlen(str) + 1);
3872   char *wp = buf;
3873   while(*str != '\0'){
3874     if(tcstrfwm(str, "=?")){
3875       str += 2;
3876       const char *pv = str;
3877       const char *ep = strchr(str, '?');
3878       if(!ep) continue;
3879       if(enp && ep - pv < TCENCBUFSIZ){
3880         memcpy(enp, pv, ep - pv);
3881         enp[ep-pv] = '\0';
3882       }
3883       pv = ep + 1;
3884       bool quoted = (*pv == 'Q' || *pv == 'q');
3885       if(*pv != '\0') pv++;
3886       if(*pv != '\0') pv++;
3887       if(!(ep = strchr(pv, '?'))) continue;
3888       char *tmp;
3889       TCMEMDUP(tmp, pv, ep - pv);
3890       int len;
3891       char *dec = quoted ? tcquotedecode(tmp, &len) : tcbasedecode(tmp, &len);
3892       wp += sprintf(wp, "%s", dec);
3893       free(dec);
3894       free(tmp);
3895       str = ep + 1;
3896       if(*str != '\0') str++;
3897     } else {
3898       *(wp++) = *str;
3899       str++;
3900     }
3901   }
3902   *wp = '\0';
3903   return buf;
3904 }
3905
3906
3907 /* Compress a serial object with Packbits encoding. */
3908 char *tcpackencode(const char *ptr, int size, int *sp){
3909   assert(ptr && size >= 0 && sp);
3910   char *buf;
3911   TCMALLOC(buf, size * 2 + 1);
3912   char *wp = buf;
3913   const char *end = ptr + size;
3914   while(ptr < end){
3915     char *sp = wp;
3916     const char *rp = ptr + 1;
3917     int step = 1;
3918     while(rp < end && step < 0x7f && *rp == *ptr){
3919       step++;
3920       rp++;
3921     }
3922     if(step <= 1 && rp < end){
3923       wp = sp + 1;
3924       *(wp++) = *ptr;
3925       while(rp < end && step < 0x7f && *rp != *(rp - 1)){
3926         *(wp++) = *rp;
3927         step++;
3928         rp++;
3929       }
3930       if(rp < end && *(rp - 1) == *rp){
3931         wp--;
3932         rp--;
3933         step--;
3934       }
3935       *sp = step == 1 ? 1 : -step;
3936     } else {
3937       *(wp++) = step;
3938       *(wp++) = *ptr;
3939     }
3940     ptr += step;
3941   }
3942   *sp = wp - buf;
3943   return buf;
3944 }
3945
3946
3947 /* Decompress a serial object compressed with Packbits encoding. */
3948 char *tcpackdecode(const char *ptr, int size, int *sp){
3949   assert(ptr && size >= 0 && sp);
3950   int asiz = size * 3;
3951   char *buf;
3952   TCMALLOC(buf, asiz + 1);
3953   int wi = 0;
3954   const char *end = ptr + size;
3955   while(ptr < end){
3956     int step = abs(*ptr);
3957     if(wi + step >= asiz){
3958       asiz = asiz * 2 + step;
3959       TCREALLOC(buf, buf, asiz + 1);
3960     }
3961     if(*(ptr++) >= 0){
3962       memset(buf + wi, *ptr, step);
3963       ptr++;
3964     } else {
3965       step = tclmin(step, end - ptr);
3966       memcpy(buf + wi, ptr, step);
3967       ptr += step;
3968     }
3969     wi += step;
3970   }
3971   buf[wi] = '\0';
3972   *sp = wi;
3973   return buf;
3974 }
3975
3976
3977 /* Compress a serial object with Deflate encoding. */
3978 char *tcdeflate(const char *ptr, int size, int *sp){
3979   assert(ptr && sp);
3980   if(!_tc_deflate) return NULL;
3981   return _tc_deflate(ptr, size, sp, _TCZMZLIB);
3982 }
3983
3984
3985 /* Decompress a serial object compressed with Deflate encoding. */
3986 char *tcinflate(const char *ptr, int size, int *sp){
3987   assert(ptr && size >= 0);
3988   if(!_tc_inflate) return NULL;
3989   return _tc_inflate(ptr, size, sp, _TCZMZLIB);
3990 }
3991
3992
3993 /* Compress a serial object with GZIP encoding. */
3994 char *tcgzipencode(const char *ptr, int size, int *sp){
3995   assert(ptr && sp);
3996   if(!_tc_deflate) return NULL;
3997   return _tc_deflate(ptr, size, sp, _TCZMGZIP);
3998 }
3999
4000
4001 /* Decompress a serial object compressed with GZIP encoding. */
4002 char *tcgzipdecode(const char *ptr, int size, int *sp){
4003   assert(ptr && size >= 0);
4004   if(!_tc_inflate) return NULL;
4005   return _tc_inflate(ptr, size, sp, _TCZMGZIP);
4006 }
4007
4008
4009 /* Get the CRC32 checksum of a serial object. */
4010 unsigned int tcgetcrc(const char *ptr, int size){
4011   assert(ptr && size >= 0);
4012   if(!_tc_getcrc) return 0;
4013   return _tc_getcrc(ptr, size);
4014 }
4015
4016
4017 /* Encode an array of nonnegative integers with BER encoding. */
4018 char *tcberencode(const unsigned int *ary, int anum, int *sp){
4019   assert(ary && anum >= 0 && sp);
4020   char *buf;
4021   TCMALLOC(buf, anum * (sizeof(int) + 1) + 1);
4022   char *wp = buf;
4023   for(int i = 0; i < anum; i++){
4024     unsigned int num = ary[i];
4025     if(num < (1 << 7)){
4026       *(wp++) = num;
4027     } else if(num < (1 << 14)){
4028       *(wp++) = (num >> 7) | 0x80;
4029       *(wp++) = num & 0x7f;
4030     } else if(num < (1 << 21)){
4031       *(wp++) = (num >> 14) | 0x80;
4032       *(wp++) = ((num >> 7) & 0x7f) | 0x80;
4033       *(wp++) = num & 0x7f;
4034     } else if(num < (1 << 28)){
4035       *(wp++) = (num >> 21) | 0x80;
4036       *(wp++) = ((num >> 14) & 0x7f) | 0x80;
4037       *(wp++) = ((num >> 7) & 0x7f) | 0x80;
4038       *(wp++) = num & 0x7f;
4039     } else {
4040       *(wp++) = (num >> 28) | 0x80;
4041       *(wp++) = ((num >> 21) & 0x7f) | 0x80;
4042       *(wp++) = ((num >> 14) & 0x7f) | 0x80;
4043       *(wp++) = ((num >> 7) & 0x7f) | 0x80;
4044       *(wp++) = num & 0x7f;
4045     }
4046   }
4047   *sp = wp - buf;
4048   return buf;
4049 }
4050
4051
4052 /* Decode a serial object encoded with BER encoding. */
4053 unsigned int *tcberdecode(const char *ptr, int size, int *np){
4054   assert(ptr && size >= 0 && np);
4055   unsigned int *buf;
4056   TCMALLOC(buf, size * sizeof(*buf) + 1);
4057   unsigned int *wp = buf;
4058   while(size > 0){
4059     unsigned int num = 0;
4060     int c;
4061     do {
4062       c = *(unsigned char *)ptr;
4063       num = num * 0x80 + (c & 0x7f);
4064       ptr++;
4065       size--;
4066     } while(c >= 0x80 && size > 0);
4067     *(wp++) = num;
4068   }
4069   *np = wp - buf;
4070   return buf;
4071 }
4072
4073
4074 /* Escape meta characters in a string with the entity references of XML. */
4075 char *tcxmlescape(const char *str){
4076   assert(str);
4077   const char *rp = str;
4078   int bsiz = 0;
4079   while(*rp != '\0'){
4080     switch(*rp){
4081     case '&':
4082       bsiz += 5;
4083       break;
4084     case '<':
4085       bsiz += 4;
4086       break;
4087     case '>':
4088       bsiz += 4;
4089       break;
4090     case '"':
4091       bsiz += 6;
4092       break;
4093     default:
4094       bsiz++;
4095       break;
4096     }
4097     rp++;
4098   }
4099   char *buf;
4100   TCMALLOC(buf, bsiz + 1);
4101   char *wp = buf;
4102   while(*str != '\0'){
4103     switch(*str){
4104     case '&':
4105       memcpy(wp, "&amp;", 5);
4106       wp += 5;
4107       break;
4108     case '<':
4109       memcpy(wp, "&lt;", 4);
4110       wp += 4;
4111       break;
4112     case '>':
4113       memcpy(wp, "&gt;", 4);
4114       wp += 4;
4115       break;
4116     case '"':
4117       memcpy(wp, "&quot;", 6);
4118       wp += 6;
4119       break;
4120     default:
4121       *(wp++) = *str;
4122       break;
4123     }
4124     str++;
4125   }
4126   *wp = '\0';
4127   return buf;
4128 }
4129
4130
4131 /* Unescape entity references in a string of XML. */
4132 char *tcxmlunescape(const char *str){
4133   assert(str);
4134   char *buf;
4135   TCMALLOC(buf, strlen(str) + 1);
4136   char *wp = buf;
4137   while(*str != '\0'){
4138     if(*str == '&'){
4139       if(tcstrfwm(str, "&amp;")){
4140         *(wp++) = '&';
4141         str += 5;
4142       } else if(tcstrfwm(str, "&lt;")){
4143         *(wp++) = '<';
4144         str += 4;
4145       } else if(tcstrfwm(str, "&gt;")){
4146         *(wp++) = '>';
4147         str += 4;
4148       } else if(tcstrfwm(str, "&quot;")){
4149         *(wp++) = '"';
4150         str += 6;
4151       } else {
4152         *(wp++) = *(str++);
4153       }
4154     } else {
4155       *(wp++) = *(str++);
4156     }
4157   }
4158   *wp = '\0';
4159   return buf;
4160 }
4161
4162
4163 /* Split an XML string into tags and text sections. */
4164 TCLIST *tcxmlbreak(const char *str){
4165   assert(str);
4166   TCLIST *list = tclistnew();
4167   int i = 0;
4168   int pv = 0;
4169   bool tag = false;
4170   char *ep;
4171   while(true){
4172     if(str[i] == '\0'){
4173       if(i > pv) TCLISTPUSH(list, str + pv, i - pv);
4174       break;
4175     } else if(!tag && str[i] == '<'){
4176       if(str[i+1] == '!' && str[i+2] == '-' && str[i+3] == '-'){
4177         if(i > pv) TCLISTPUSH(list, str + pv, i - pv);
4178         if((ep = strstr(str + i, "-->")) != NULL){
4179           TCLISTPUSH(list, str + i, ep - str - i + 3);
4180           i = ep - str + 2;
4181           pv = i + 1;
4182         }
4183       } else if(str[i+1] == '!' && str[i+2] == '[' && tcstrifwm(str + i, "<![CDATA[")){
4184         if(i > pv) TCLISTPUSH(list, str + pv, i - pv);
4185         if((ep = strstr(str + i, "]]>")) != NULL){
4186           i += 9;
4187           TCXSTR *xstr = tcxstrnew();
4188           while(str + i < ep){
4189             if(str[i] == '&'){
4190               TCXSTRCAT(xstr, "&amp;", 5);
4191             } else if(str[i] == '<'){
4192               TCXSTRCAT(xstr, "&lt;", 4);
4193             } else if(str[i] == '>'){
4194               TCXSTRCAT(xstr, "&gt;", 4);
4195             } else {
4196               TCXSTRCAT(xstr, str + i, 1);
4197             }
4198             i++;
4199           }
4200           if(TCXSTRSIZE(xstr) > 0) TCLISTPUSH(list, TCXSTRPTR(xstr), TCXSTRSIZE(xstr));
4201           tcxstrdel(xstr);
4202           i = ep - str + 2;
4203           pv = i + 1;
4204         }
4205       } else {
4206         if(i > pv) TCLISTPUSH(list, str + pv, i - pv);
4207         tag = true;
4208         pv = i;
4209       }
4210     } else if(tag && str[i] == '>'){
4211       if(i > pv) TCLISTPUSH(list, str + pv, i - pv + 1);
4212       tag = false;
4213       pv = i + 1;
4214     }
4215     i++;
4216   }
4217   return list;
4218 }
4219
4220
4221 /* Get the map of attributes of an XML tag. */
4222 TCMAP *tcxmlattrs(const char *str){
4223   assert(str);
4224   TCMAP *map = tcmapnew2(TCXMLATBNUM);
4225   const unsigned char *rp = (unsigned char *)str;
4226   while(*rp == '<' || *rp == '/' || *rp == '?' || *rp == '!' || *rp == ' '){
4227     rp++;
4228   }
4229   const unsigned char *key = rp;
4230   while(*rp > 0x20 && *rp != '/' && *rp != '>'){
4231     rp++;
4232   }
4233   tcmapputkeep(map, "", 0, (char *)key, rp - key);
4234   while(*rp != '\0'){
4235     while(*rp != '\0' && (*rp <= 0x20 || *rp == '/' || *rp == '?' || *rp == '>')){
4236       rp++;
4237     }
4238     key = rp;
4239     while(*rp > 0x20 && *rp != '/' && *rp != '>' && *rp != '='){
4240       rp++;
4241     }
4242     int ksiz = rp - key;
4243     while(*rp != '\0' && (*rp == '=' || *rp <= 0x20)){
4244       rp++;
4245     }
4246     const unsigned char *val;
4247     int vsiz;
4248     if(*rp == '"'){
4249       rp++;
4250       val = rp;
4251       while(*rp != '\0' && *rp != '"'){
4252         rp++;
4253       }
4254       vsiz = rp - val;
4255     } else if(*rp == '\''){
4256       rp++;
4257       val = rp;
4258       while(*rp != '\0' && *rp != '\''){
4259         rp++;
4260       }
4261       vsiz = rp - val;
4262     } else {
4263       val = rp;
4264       while(*rp > 0x20 && *rp != '"' && *rp != '\'' && *rp != '>'){
4265         rp++;
4266       }
4267       vsiz = rp - val;
4268     }
4269     if(*rp != '\0') rp++;
4270     if(ksiz > 0){
4271       char *copy;
4272       TCMEMDUP(copy, val, vsiz);
4273       char *raw = tcxmlunescape(copy);
4274       tcmapputkeep(map, (char *)key, ksiz, raw, strlen(raw));
4275       free(raw);
4276       free(copy);
4277     }
4278   }
4279   return map;
4280 }
4281
4282
4283
4284 /*************************************************************************************************
4285  * features for experts
4286  *************************************************************************************************/
4287
4288
4289 #define TCBSENCUNIT    8192             // unit size of TCBS encoding
4290 #define TCBWTCNTMIN    64               // minimum element number of counting sort
4291 #define TCBWTCNTLV     4                // maximum recursion level of counting sort
4292 #define TCBWTBUFNUM    16384            // number of elements of BWT buffer
4293
4294 typedef struct {                         // type of structure for a BWT character
4295   int fchr;                              // character code of the first character
4296   int tchr;                              // character code of the last character
4297 } TCBWTREC;
4298
4299
4300 /* private function prototypes */
4301 static void tcglobalmutexinit(void);
4302 static void tcglobalmutexdestroy(void);
4303 static void tcbwtsortstrcount(const char **arrays, int anum, int len, int level);
4304 static void tcbwtsortstrinsert(const char **arrays, int anum, int len, int skip);
4305 static void tcbwtsortstrheap(const char **arrays, int anum, int len, int skip);
4306 static void tcbwtsortchrcount(unsigned char *str, int len);
4307 static void tcbwtsortchrinsert(unsigned char *str, int len);
4308 static void tcbwtsortreccount(TCBWTREC *arrays, int anum);
4309 static void tcbwtsortrecinsert(TCBWTREC *array, int anum);
4310 static int tcbwtsearchrec(TCBWTREC *array, int anum, int tchr);
4311 static void tcmtfencode(char *ptr, int size);
4312 static void tcmtfdecode(char *ptr, int size);
4313 static int tcgammaencode(const char *ptr, int size, char *obuf);
4314 static int tcgammadecode(const char *ptr, int size, char *obuf);
4315
4316
4317 /* Show error message on the standard error output and exit. */
4318 void *tcmyfatal(const char *message){
4319   assert(message);
4320   if(tcfatalfunc){
4321     tcfatalfunc(message);
4322   } else {
4323     fprintf(stderr, "fatal error: %s\n", message);
4324   }
4325   exit(1);
4326   return NULL;
4327 }
4328
4329
4330 /* Global mutex object. */
4331 static pthread_rwlock_t tcglobalmutex;
4332 static pthread_once_t tcglobalmutexonce = PTHREAD_ONCE_INIT;
4333
4334
4335 /* Lock the global mutex object. */
4336 bool tcglobalmutexlock(void){
4337   pthread_once(&tcglobalmutexonce, tcglobalmutexinit);
4338   return pthread_rwlock_wrlock(&tcglobalmutex) == 0;
4339 }
4340
4341
4342 /* Lock the global mutex object by shared locking. */
4343 bool tcglobalmutexlockshared(void){
4344   pthread_once(&tcglobalmutexonce, tcglobalmutexinit);
4345   return pthread_rwlock_rdlock(&tcglobalmutex) == 0;
4346 }
4347
4348
4349 /* Unlock the global mutex object. */
4350 bool tcglobalmutexunlock(void){
4351   return pthread_rwlock_unlock(&tcglobalmutex) == 0;
4352 }
4353
4354
4355 /* Compress a serial object with TCBS encoding. */
4356 char *tcbsencode(const char *ptr, int size, int *sp){
4357   assert(ptr && size >= 0 && sp);
4358   char *result;
4359   TCMALLOC(result, (size * 7) / 3 + (size / TCBSENCUNIT + 1) * sizeof(uint16_t) +
4360            TCBSENCUNIT * 2 + 0x200);
4361   char *pv = result + size + 0x100;
4362   char *wp = pv;
4363   char *tp = pv + size + 0x100;
4364   const char *end = ptr + size;
4365   while(ptr < end){
4366     int usiz = tclmin(TCBSENCUNIT, end - ptr);
4367     memcpy(tp, ptr, usiz);
4368     memcpy(tp + usiz, ptr, usiz);
4369     char *sp = wp;
4370     uint16_t idx = 0;
4371     wp += sizeof(idx);
4372     const char *arrays[usiz+1];
4373     for(int i = 0; i < usiz; i++){
4374       arrays[i] = tp + i;
4375     }
4376     const char *fp = arrays[0];
4377     if(usiz >= TCBWTCNTMIN){
4378       tcbwtsortstrcount(arrays, usiz, usiz, 0);
4379     } else if(usiz > 1){
4380       tcbwtsortstrinsert(arrays, usiz, usiz, 0);
4381     }
4382     for(int i = 0; i < usiz; i++){
4383       int tidx = arrays[i] - fp;
4384       if(tidx == 0){
4385         idx = i;
4386         *(wp++) = ptr[usiz-1];
4387       } else {
4388         *(wp++) = ptr[tidx-1];
4389       }
4390     }
4391     idx = TCHTOIS(idx);
4392     memcpy(sp, &idx, sizeof(idx));
4393     ptr += TCBSENCUNIT;
4394   }
4395   size = wp - pv;
4396   tcmtfencode(pv, size);
4397   int nsiz = tcgammaencode(pv, size, result);
4398   *sp = nsiz;
4399   return result;
4400 }
4401
4402
4403 /* Decompress a serial object compressed with TCBS encoding. */
4404 char *tcbsdecode(const char *ptr, int size, int *sp){
4405   char *result;
4406   TCMALLOC(result, size * 9 + 0x200);
4407   char *wp = result + size + 0x100;
4408   int nsiz = tcgammadecode(ptr, size, wp);
4409   tcmtfdecode(wp, nsiz);
4410   ptr = wp;
4411   wp = result;
4412   const char *end = ptr + nsiz;
4413   while(ptr < end){
4414     uint16_t idx;
4415     memcpy(&idx, ptr, sizeof(idx));
4416     idx = TCITOHS(idx);
4417     ptr += sizeof(idx);
4418     int usiz = tclmin(TCBSENCUNIT, end - ptr);
4419     if(idx >= usiz) idx = 0;
4420     char rbuf[usiz+1];
4421     memcpy(rbuf, ptr, usiz);
4422     if(usiz >= TCBWTCNTMIN){
4423       tcbwtsortchrcount((unsigned char *)rbuf, usiz);
4424     } else if(usiz > 0){
4425       tcbwtsortchrinsert((unsigned char *)rbuf, usiz);
4426     }
4427     int fnums[0x100], tnums[0x100];
4428     memset(fnums, 0, sizeof(fnums));
4429     memset(tnums, 0, sizeof(tnums));
4430     TCBWTREC array[usiz+1];
4431     TCBWTREC *rp = array;
4432     for(int i = 0; i < usiz; i++){
4433       int fc = *(unsigned char *)(rbuf + i);
4434       rp->fchr = (fc << 23) + fnums[fc]++;
4435       int tc = *(unsigned char *)(ptr + i);
4436       rp->tchr = (tc << 23) + tnums[tc]++;
4437       rp++;
4438     }
4439     unsigned int fchr = array[idx].fchr;
4440     if(usiz >= TCBWTCNTMIN){
4441       tcbwtsortreccount(array, usiz);
4442     } else if(usiz > 1){
4443       tcbwtsortrecinsert(array, usiz);
4444     }
4445     for(int i = 0; i < usiz; i++){
4446       if(array[i].fchr == fchr){
4447         idx = i;
4448         break;
4449       }
4450     }
4451     for(int i = 0; i < usiz; i++){
4452       *(wp++) = array[idx].fchr >> 23;
4453       idx = tcbwtsearchrec(array, usiz, array[idx].fchr);
4454     }
4455     ptr += usiz;
4456   }
4457   *wp = '\0';
4458   *sp = wp - result;
4459   return result;
4460 }
4461
4462
4463 /* Encode a serial object with BWT encoding. */
4464 char *tcbwtencode(const char *ptr, int size, int *idxp){
4465   assert(ptr && size >= 0 && idxp);
4466   if(size < 1){
4467     *idxp = 0;
4468     char *rv;
4469     TCMEMDUP(rv, "", 0);
4470     return rv;
4471   }
4472   char *result;
4473   TCMALLOC(result, size * 3 + 1);
4474   char *tp = result + size + 1;
4475   memcpy(tp, ptr, size);
4476   memcpy(tp + size, ptr, size);
4477   const char *abuf[TCBWTBUFNUM];
4478   const char **arrays = abuf;
4479   if(size > TCBWTBUFNUM) TCMALLOC(arrays, sizeof(*arrays) * size);
4480   for(int i = 0; i < size; i++){
4481     arrays[i] = tp + i;
4482   }
4483   const char *fp = arrays[0];
4484   if(size >= TCBWTCNTMIN){
4485     tcbwtsortstrcount(arrays, size, size, -1);
4486   } else if(size > 1){
4487     tcbwtsortstrinsert(arrays, size, size, 0);
4488   }
4489   for(int i = 0; i < size; i++){
4490     int idx = arrays[i] - fp;
4491     if(idx == 0){
4492       *idxp = i;
4493       result[i] = ptr[size-1];
4494     } else {
4495       result[i] = ptr[idx-1];
4496     }
4497   }
4498   if(arrays != abuf) free(arrays);
4499   result[size] = '\0';
4500   return result;
4501 }
4502
4503
4504 /* Decode a serial object encoded with BWT encoding. */
4505 char *tcbwtdecode(const char *ptr, int size, int idx){
4506   assert(ptr && size >= 0);
4507   if(size < 1 || idx < 0){
4508     char *rv;
4509     TCMEMDUP(rv, "", 0);
4510     return rv;
4511   }
4512   if(idx >= size) idx = 0;
4513   char *result;
4514   TCMALLOC(result, size + 1);
4515   memcpy(result, ptr, size);
4516   if(size >= TCBWTCNTMIN){
4517     tcbwtsortchrcount((unsigned char *)result, size);
4518   } else {
4519     tcbwtsortchrinsert((unsigned char *)result, size);
4520   }
4521   int fnums[0x100], tnums[0x100];
4522   memset(fnums, 0, sizeof(fnums));
4523   memset(tnums, 0, sizeof(tnums));
4524   TCBWTREC abuf[TCBWTBUFNUM];
4525   TCBWTREC *array = abuf;
4526   if(size > TCBWTBUFNUM) TCMALLOC(array, sizeof(*array) * size);
4527   TCBWTREC *rp = array;
4528   for(int i = 0; i < size; i++){
4529     int fc = *(unsigned char *)(result + i);
4530     rp->fchr = (fc << 23) + fnums[fc]++;
4531     int tc = *(unsigned char *)(ptr + i);
4532     rp->tchr = (tc << 23) + tnums[tc]++;
4533     rp++;
4534   }
4535   unsigned int fchr = array[idx].fchr;
4536   if(size >= TCBWTCNTMIN){
4537     tcbwtsortreccount(array, size);
4538   } else if(size > 1){
4539     tcbwtsortrecinsert(array, size);
4540   }
4541   for(int i = 0; i < size; i++){
4542     if(array[i].fchr == fchr){
4543       idx = i;
4544       break;
4545     }
4546   }
4547   char *wp = result;
4548   for(int i = 0; i < size; i++){
4549     *(wp++) = array[idx].fchr >> 23;
4550     idx = tcbwtsearchrec(array, size, array[idx].fchr);
4551   }
4552   *wp = '\0';
4553   if(array != abuf) free(array);
4554   return result;
4555 }
4556
4557
4558 /* Initialize the global mutex object */
4559 static void tcglobalmutexinit(void){
4560   if(!TCUSEPTHREAD) memset(&tcglobalmutex, 0, sizeof(tcglobalmutex));
4561   if(pthread_rwlock_init(&tcglobalmutex, NULL) != 0) tcmyfatal("rwlock error");
4562   atexit(tcglobalmutexdestroy);
4563 }
4564
4565
4566 /* Destroy the global mutex object */
4567 static void tcglobalmutexdestroy(void){
4568   pthread_rwlock_destroy(&tcglobalmutex);
4569 }
4570
4571
4572 /* Sort BWT string arrays by dicrionary order by counting sort.
4573    `array' specifies an array of string arrays.
4574    `anum' specifies the number of the array.
4575    `len' specifies the size of each string.
4576    `level' specifies the level of recursion. */
4577 static void tcbwtsortstrcount(const char **arrays, int anum, int len, int level){
4578   assert(arrays && anum >= 0 && len >= 0);
4579   const char *nbuf[TCBWTBUFNUM];
4580   const char **narrays = nbuf;
4581   if(anum > TCBWTBUFNUM) TCMALLOC(narrays, sizeof(*narrays) * anum);
4582   int count[0x100], accum[0x100];
4583   memset(count, 0, sizeof(count));
4584   int skip = level < 0 ? 0 : level;
4585   for(int i = 0; i < anum; i++){
4586     count[((unsigned char *)arrays[i])[skip]]++;
4587   }
4588   memcpy(accum, count, sizeof(count));
4589   for(int i = 1; i < 0x100; i++){
4590     accum[i] = accum[i-1] + accum[i];
4591   }
4592   for(int i = 0; i < anum; i++){
4593     narrays[--accum[((unsigned char *)arrays[i])[skip]]] = arrays[i];
4594   }
4595   int off = 0;
4596   if(level >= 0 && level < TCBWTCNTLV){
4597     for(int i = 0; i < 0x100; i++){
4598       int c = count[i];
4599       if(c > 1){
4600         if(c >= TCBWTCNTMIN){
4601           tcbwtsortstrcount(narrays + off, c, len, level + 1);
4602         } else {
4603           tcbwtsortstrinsert(narrays + off, c, len, skip + 1);
4604         }
4605       }
4606       off += c;
4607     }
4608   } else {
4609     for(int i = 0; i < 0x100; i++){
4610       int c = count[i];
4611       if(c > 1){
4612         if(c >= TCBWTCNTMIN){
4613           tcbwtsortstrheap(narrays + off, c, len, skip + 1);
4614         } else {
4615           tcbwtsortstrinsert(narrays + off, c, len, skip + 1);
4616         }
4617       }
4618       off += c;
4619     }
4620   }
4621   memcpy(arrays, narrays, anum * sizeof(*narrays));
4622   if(narrays != nbuf) free(narrays);
4623 }
4624
4625
4626 /* Sort BWT string arrays by dicrionary order by insertion sort.
4627    `array' specifies an array of string arrays.
4628    `anum' specifies the number of the array.
4629    `len' specifies the size of each string.
4630    `skip' specifies the number of skipped bytes. */
4631 static void tcbwtsortstrinsert(const char **arrays, int anum, int len, int skip){
4632   assert(arrays && anum >= 0 && len >= 0);
4633   for(int i = 1; i < anum; i++){
4634     int cmp = 0;
4635     const unsigned char *ap = (unsigned char *)arrays[i-1];
4636     const unsigned char *bp = (unsigned char *)arrays[i];
4637     for(int j = skip; j < len; j++){
4638       if(ap[j] != bp[j]){
4639         cmp = ap[j] - bp[j];
4640         break;
4641       }
4642     }
4643     if(cmp > 0){
4644       const char *swap = arrays[i];
4645       int j;
4646       for(j = i; j > 0; j--){
4647         int cmp = 0;
4648         const unsigned char *ap = (unsigned char *)arrays[j-1];
4649         const unsigned char *bp = (unsigned char *)swap;
4650         for(int k = skip; k < len; k++){
4651           if(ap[k] != bp[k]){
4652             cmp = ap[k] - bp[k];
4653             break;
4654           }
4655         }
4656         if(cmp < 0) break;
4657         arrays[j] = arrays[j-1];
4658       }
4659       arrays[j] = swap;
4660     }
4661   }
4662 }
4663
4664
4665 /* Sort BWT string arrays by dicrionary order by heap sort.
4666    `array' specifies an array of string arrays.
4667    `anum' specifies the number of the array.
4668    `len' specifies the size of each string.
4669    `skip' specifies the number of skipped bytes. */
4670 static void tcbwtsortstrheap(const char **arrays, int anum, int len, int skip){
4671   assert(arrays && anum >= 0 && len >= 0);
4672   anum--;
4673   int bottom = (anum >> 1) + 1;
4674   int top = anum;
4675   while(bottom > 0){
4676     bottom--;
4677     int mybot = bottom;
4678     int i = mybot << 1;
4679     while(i <= top){
4680       if(i < top){
4681         int cmp = 0;
4682         const unsigned char *ap = (unsigned char *)arrays[i+1];
4683         const unsigned char *bp = (unsigned char *)arrays[i];
4684         for(int j = skip; j < len; j++){
4685           if(ap[j] != bp[j]){
4686             cmp = ap[j] - bp[j];
4687             break;
4688           }
4689         }
4690         if(cmp > 0) i++;
4691       }
4692       int cmp = 0;
4693       const unsigned char *ap = (unsigned char *)arrays[mybot];
4694       const unsigned char *bp = (unsigned char *)arrays[i];
4695       for(int j = skip; j < len; j++){
4696         if(ap[j] != bp[j]){
4697           cmp = ap[j] - bp[j];
4698           break;
4699         }
4700       }
4701       if(cmp >= 0) break;
4702       const char *swap = arrays[mybot];
4703       arrays[mybot] = arrays[i];
4704       arrays[i] = swap;
4705       mybot = i;
4706       i = mybot << 1;
4707     }
4708   }
4709   while(top > 0){
4710     const char *swap = arrays[0];
4711     arrays[0] = arrays[top];
4712     arrays[top] = swap;
4713     top--;
4714     int mybot = bottom;
4715     int i = mybot << 1;
4716     while(i <= top){
4717       if(i < top){
4718         int cmp = 0;
4719         const unsigned char *ap = (unsigned char *)arrays[i+1];
4720         const unsigned char *bp = (unsigned char *)arrays[i];
4721         for(int j = 0; j < len; j++){
4722           if(ap[j] != bp[j]){
4723             cmp = ap[j] - bp[j];
4724             break;
4725           }
4726         }
4727         if(cmp > 0) i++;
4728       }
4729       int cmp = 0;
4730       const unsigned char *ap = (unsigned char *)arrays[mybot];
4731       const unsigned char *bp = (unsigned char *)arrays[i];
4732       for(int j = 0; j < len; j++){
4733         if(ap[j] != bp[j]){
4734           cmp = ap[j] - bp[j];
4735           break;
4736         }
4737       }
4738       if(cmp >= 0) break;
4739       swap = arrays[mybot];
4740       arrays[mybot] = arrays[i];
4741       arrays[i] = swap;
4742       mybot = i;
4743       i = mybot << 1;
4744     }
4745   }
4746 }
4747
4748
4749 /* Sort BWT characters by code number by counting sort.
4750    `str' specifies a string.
4751    `len' specifies the length of the string. */
4752 static void tcbwtsortchrcount(unsigned char *str, int len){
4753   assert(str && len >= 0);
4754   int cnt[0x100];
4755   memset(cnt, 0, sizeof(cnt));
4756   for(int i = 0; i < len; i++){
4757     cnt[str[i]]++;
4758   }
4759   int pos = 0;
4760   for(int i = 0; i < 0x100; i++){
4761     memset(str + pos, i, cnt[i]);
4762     pos += cnt[i];
4763   }
4764 }
4765
4766
4767 /* Sort BWT characters by code number by insertion sort.
4768    `str' specifies a string.
4769    `len' specifies the length of the string. */
4770 static void tcbwtsortchrinsert(unsigned char *str, int len){
4771   assert(str && len >= 0);
4772   for(int i = 1; i < len; i++){
4773     if(str[i-1] - str[i] > 0){
4774       unsigned char swap = str[i];
4775       int j;
4776       for(j = i; j > 0; j--){
4777         if(str[j-1] - swap < 0) break;
4778         str[j] = str[j-1];
4779       }
4780       str[j] = swap;
4781     }
4782   }
4783 }
4784
4785
4786 /* Sort BWT records by code number by counting sort.
4787    `array' specifies an array of records.
4788    `anum' specifies the number of the array. */
4789 static void tcbwtsortreccount(TCBWTREC *array, int anum){
4790   assert(array && anum >= 0);
4791   TCBWTREC nbuf[TCBWTBUFNUM];
4792   TCBWTREC *narray = nbuf;
4793   if(anum > TCBWTBUFNUM) TCMALLOC(narray, sizeof(*narray) * anum);
4794   int count[0x100], accum[0x100];
4795   memset(count, 0, sizeof(count));
4796   for(int i = 0; i < anum; i++){
4797     count[array[i].tchr>>23]++;
4798   }
4799   memcpy(accum, count, sizeof(count));
4800   for(int i = 1; i < 0x100; i++){
4801     accum[i] = accum[i-1] + accum[i];
4802   }
4803   for(int i = 0; i < 0x100; i++){
4804     accum[i] -= count[i];
4805   }
4806   for(int i = 0; i < anum; i++){
4807     narray[accum[array[i].tchr>>23]++] = array[i];
4808   }
4809   memcpy(array, narray, anum * sizeof(*narray));
4810   if(narray != nbuf) free(narray);
4811 }
4812
4813
4814 /* Sort BWT records by code number by insertion sort.
4815    `array' specifies an array of records..
4816    `anum' specifies the number of the array. */
4817 static void tcbwtsortrecinsert(TCBWTREC *array, int anum){
4818   assert(array && anum >= 0);
4819   for(int i = 1; i < anum; i++){
4820     if(array[i-1].tchr - array[i].tchr > 0){
4821       TCBWTREC swap = array[i];
4822       int j;
4823       for(j = i; j > 0; j--){
4824         if(array[j-1].tchr - swap.tchr < 0) break;
4825         array[j] = array[j-1];
4826       }
4827       array[j] = swap;
4828     }
4829   }
4830 }
4831
4832
4833 /* Search the element of BWT records.
4834    `array' specifies an array of records.
4835    `anum' specifies the number of the array.
4836    `tchr' specifies the last code number. */
4837 static int tcbwtsearchrec(TCBWTREC *array, int anum, int tchr){
4838   assert(array && anum >= 0);
4839   int bottom = 0;
4840   int top = anum;
4841   int mid;
4842   do {
4843     mid = (bottom + top) >> 1;
4844     if(array[mid].tchr == tchr){
4845       return mid;
4846     } else if(array[mid].tchr < tchr){
4847       bottom = mid + 1;
4848       if(bottom >= anum) break;
4849     } else {
4850       top = mid - 1;
4851     }
4852   } while(bottom <= top);
4853   return -1;
4854 }
4855
4856
4857 /* Initialization table for MTF encoder. */
4858 const unsigned char tcmtftable[] = {
4859   0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
4860   0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,
4861   0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f,
4862   0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f,
4863   0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f,
4864   0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5a,0x5b,0x5c,0x5d,0x5e,0x5f,
4865   0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
4866   0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f,
4867   0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f,
4868   0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f,
4869   0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf,
4870   0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf,
4871   0xc0,0xc1,0xc2,0xc3,0xc4,0xc5,0xc6,0xc7,0xc8,0xc9,0xca,0xcb,0xcc,0xcd,0xce,0xcf,
4872   0xd0,0xd1,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xdb,0xdc,0xdd,0xde,0xdf,
4873   0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef,
4874   0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff
4875 };
4876
4877
4878 /* Encode a region with MTF encoding.
4879    `ptr' specifies the pointer to the region.
4880    `size' specifies the size of the region. */
4881 static void tcmtfencode(char *ptr, int size){
4882   unsigned char table1[0x100], table2[0x100], *table, *another;
4883   assert(ptr && size >= 0);
4884   memcpy(table1, tcmtftable, sizeof(tcmtftable));
4885   table = table1;
4886   another = table2;
4887   const char *end = ptr + size;
4888   char *wp = ptr;
4889   while(ptr < end){
4890     unsigned char c = *ptr;
4891     unsigned char *tp = table;
4892     unsigned char *tend = table + 0x100;
4893     while(tp < tend && *tp != c){
4894       tp++;
4895     }
4896     int idx = tp - table;
4897     *(wp++) = idx;
4898     if(idx > 0){
4899       memcpy(another, &c, 1);
4900       memcpy(another + 1, table, idx);
4901       memcpy(another + 1 + idx, table + idx + 1, 255 - idx);
4902       unsigned char *swap = table;
4903       table = another;
4904       another = swap;
4905     }
4906     ptr++;
4907   }
4908 }
4909
4910
4911 /* Decode a region compressed with MTF encoding.
4912    `ptr' specifies the pointer to the region.
4913    `size' specifies the size of the region. */
4914 static void tcmtfdecode(char *ptr, int size){
4915   assert(ptr && size >= 0);
4916   unsigned char table1[0x100], table2[0x100], *table, *another;
4917   assert(ptr && size >= 0);
4918   memcpy(table1, tcmtftable, sizeof(tcmtftable));
4919   table = table1;
4920   another = table2;
4921   const char *end = ptr + size;
4922   char *wp = ptr;
4923   while(ptr < end){
4924     int idx = *(unsigned char *)ptr;
4925     unsigned char c = table[idx];
4926     *(wp++) = c;
4927     if(idx > 0){
4928       memcpy(another, &c, 1);
4929       memcpy(another + 1, table, idx);
4930       memcpy(another + 1 + idx, table + idx + 1, 255 - idx);
4931       unsigned char *swap = table;
4932       table = another;
4933       another = swap;
4934     }
4935     ptr++;
4936   }
4937 }
4938
4939
4940 /* Encode a region with Elias gamma encoding.
4941    `ptr' specifies the pointer to the region.
4942    `size' specifies the size of the region.
4943    `ptr' specifies the pointer to the output buffer. */
4944 static int tcgammaencode(const char *ptr, int size, char *obuf){
4945   assert(ptr && size >= 0 && obuf);
4946   TCBITSTRM strm;
4947   TCBITSTRMINITW(strm, obuf);
4948   const char *end = ptr + size;
4949   while(ptr < end){
4950     unsigned int c = *(unsigned char *)ptr;
4951     if(!c){
4952       TCBITSTRMCAT(strm, 1);
4953     } else {
4954       c++;
4955       int plen = 8;
4956       while(plen > 0 && !(c & (1 << plen))){
4957         plen--;
4958       }
4959       int jlen = plen;
4960       while(jlen-- > 0){
4961         TCBITSTRMCAT(strm, 0);
4962       }
4963       while(plen >= 0){
4964         int sign = (c & (1 << plen)) > 0;
4965         TCBITSTRMCAT(strm, sign);
4966         plen--;
4967       }
4968     }
4969     ptr++;
4970   }
4971   TCBITSTRMSETEND(strm);
4972   return TCBITSTRMSIZE(strm);
4973 }
4974
4975
4976 /* Decode a region compressed with Elias gamma encoding.
4977    `ptr' specifies the pointer to the region.
4978    `size' specifies the size of the region.
4979    `ptr' specifies the pointer to the output buffer. */
4980 static int tcgammadecode(const char *ptr, int size, char *obuf){
4981   assert(ptr && size >= 0 && obuf);
4982   char *wp = obuf;
4983   TCBITSTRM strm;
4984   TCBITSTRMINITR(strm, ptr, size);
4985   int bnum = TCBITSTRMNUM(strm);
4986   while(bnum > 0){
4987     int sign;
4988     TCBITSTRMREAD(strm, sign);
4989     bnum--;
4990     if(sign){
4991       *(wp++) = 0;
4992     } else {
4993       int plen = 1;
4994       while(bnum > 0){
4995         TCBITSTRMREAD(strm, sign);
4996         bnum--;
4997         if(sign) break;
4998         plen++;
4999       }
5000       unsigned int c = 1;
5001       while(bnum > 0 && plen-- > 0){
5002         TCBITSTRMREAD(strm, sign);
5003         bnum--;
5004         c = (c << 1) + (sign > 0);
5005       }
5006       *(wp++) = c - 1;
5007     }
5008   }
5009   return wp - obuf;;
5010 }
5011
5012
5013
5014 // END OF FILE