/*************************************************************************************************
 * Implementation of Cabin
 *                                                      Copyright (C) 2000-2003 Mikio Hirabayashi
 * This file is part of QDBM, Quick Database Manager.
 * QDBM is free software; you can redistribute it and/or modify it under the terms of the GNU
 * Lesser General Public License as published by the Free Software Foundation; either version
 * 2.1 of the License or any later version.  QDBM is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
 * details.
 * You should have received a copy of the GNU Lesser General Public License along with QDBM; if
 * not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 * 02111-1307 USA.
 *************************************************************************************************/


#include "cabin.h"
#include "myconf.h"

#define CB_SPBUFSIZ    32                /* size of a buffer for sprintf */
#define CB_SPMAXWIDTH  128               /* max width of a column for sprintf */
#define CB_DATUMUNIT   16                /* allocation unit size of a datum handle */
#define CB_LISTUNIT    64                /* allocation unit number of a list handle */
#define CB_MAPBNUM     8191              /* bucket size of a map handle */
#define CB_MSGBUFSIZ   256               /* size of a buffer for log message */
#define CB_IOBUFSIZ    4096              /* size of an I/O buffer */
#define CB_VNUMBUFSIZ  8                 /* size of a buffer for variable length number */


/* private function prototypes */
static void cbmyfatal(const char *message);
static void cbqsortsub(char *bp, int nmemb, int size, char *pswap, char *vswap,
                       int(*compar)(const void *, const void *));
static int cblistelemcmp(const void *a, const void *b);
static int cbfirsthash(const char *kbuf, int ksiz);
static int cbsecondhash(const char *kbuf, int ksiz);
static int cbkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz);
static int cbsetvnumbuf(char *buf, int num);
static int cbreadvnumbuf(const char *buf, int size, int *sp);



/*************************************************************************************************
 * public objects
 *************************************************************************************************/


/* Call back function for handling a fatal error. */
void (*cbfatalfunc)(const char *message) = NULL;


/* Allocate a region on memory. */
void *cbmalloc(size_t size){
  char *p;
  assert(size > 0);
  if(!(p = malloc(size))){
    if(cbfatalfunc){
      cbfatalfunc("out of memory");
    } else {
      cbmyfatal("out of memory");
    }
  }
  return p;
}


/* Re-allocate a region on memory. */
void *cbrealloc(void *ptr, size_t size){
  char *p;
  assert(size > 0);
  if(!(p = realloc(ptr, size))){
    if(cbfatalfunc){
      cbfatalfunc("out of memory");
    } else {
      cbmyfatal("out of memory");
    }
  }
  return p;
}


/* Duplicate a region on memory. */
char *cbmemdup(const char *ptr, int size){
  char *p;
  assert(ptr);
  if(size < 0) size = strlen(ptr);
  p = cbmalloc(size + 1);
  memcpy(p, ptr, size);
  p[size] = '\0';
  return p;
}


/* Sort an array using insert sort. */
void cbisort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){
  char *bp, *swap;
  int i, j;
  assert(base && nmemb >= 0 && size > 0 && compar);
  bp = (char *)base;
  swap = cbmalloc(size);
  for(i = 1; i < nmemb; i++){
    if(compar(bp + (i - 1) * size, bp + i * size) > 0){
      memcpy(swap, bp + i * size, size);
      for(j = i; j > 0; j--){
        if(compar(bp + (j - 1) * size, swap) < 0) break;
        memcpy(bp + j * size, bp + (j - 1) * size, size);
      }
      memcpy(bp + j * size, swap, size);
    }
  }
  free(swap);
}


/* Sort an array using shell sort. */
void cbssort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){
  char *bp, *swap;
  int step, bottom, i, j;
  assert(base && nmemb >= 0 && size > 0 && compar);
  bp = (char *)base;
  swap = cbmalloc(size);
  for(step = (nmemb - 1) / 3; step >= 0; step = (step - 1) / 3){
    if(step < 5) step = 1;
    for(bottom = 0; bottom < step; bottom++){
      for(i = bottom + step; i < nmemb; i += step){
        if(compar(bp + (i - step) * size, bp + i * size) > 0){
          memcpy(swap, bp + i * size, size);
          for(j = i; j > step - 1; j -= step){
            if(compar(bp + (j - step) * size, swap) < 0) break;
            memcpy(bp + j * size, bp + (j - step) * size, size);
          }
          memcpy(bp + j * size, swap, size);
        }
      }
    }
    if(step < 2) break;
  }
  free(swap);
}


/* Sort an array using heap sort. */
void cbhsort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){
  char *bp, *swap;
  int top, bottom, mybot, i;
  assert(base && nmemb >= 0 && size > 0 && compar);
  bp = (char *)base;
  nmemb--;
  bottom = nmemb / 2 +1;
  top = nmemb;
  swap = cbmalloc(size);
  while(bottom > 0){
    bottom--;
    mybot = bottom;
    i = 2 * mybot;
    while(i <= top) {
      if(i < top && compar(bp + (i + 1) * size, bp + i * size) > 0) i++;
      if(compar(bp + mybot * size, bp + i * size) >= 0) break;
      memcpy(swap, bp + mybot * size, size);
      memcpy(bp + mybot * size, bp + i * size, size);
      memcpy(bp + i * size, swap, size);
      mybot = i;
      i = 2 * mybot;
    }
  }
  while(top > 0){
    memcpy(swap, bp, size);
    memcpy(bp, bp + top * size, size);
    memcpy(bp + top * size, swap, size);
    top--;
    mybot = bottom;
    i = 2 * mybot;
    while(i <= top) {
      if(i < top && compar(bp + (i + 1) * size, bp + i * size) > 0) i++;
      if(compar(bp + mybot * size, bp + i * size) >= 0) break;
      memcpy(swap, bp + mybot * size, size);
      memcpy(bp + mybot * size, bp + i * size, size);
      memcpy(bp + i * size, swap, size);
      mybot = i;
      i = 2 * mybot;
    }
  }
  free(swap);
}


/* Sort an array using quick sort. */
void cbqsort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){
  char *pswap, *vswap;
  assert(base && nmemb >= 0 && size > 0 && compar);
  pswap = cbmalloc(size);
  vswap = cbmalloc(size);
  cbqsortsub(base, nmemb, size, pswap, vswap, compar);
  free(vswap);
  free(pswap);
}


/* Get a datum handle. */
CBDATUM *cbdatumopen(const char *ptr, int size){
  CBDATUM *datum;
  datum = cbmalloc(sizeof(*datum));
  datum->dptr = cbmalloc(CB_DATUMUNIT);
  datum->dsize = 0;
  datum->asize = CB_DATUMUNIT;
  if(ptr) cbdatumcat(datum, ptr, size);
  return datum;
}


/* Copy a datum. */
CBDATUM *cbdatumdup(const CBDATUM *datum){
  assert(datum);
  return cbdatumopen(datum->dptr, datum->dsize);
}


/* Free a datum handle. */
void cbdatumclose(CBDATUM *datum){
  assert(datum);
  free(datum->dptr);
  free(datum);
}


/* Concatenate a datum and a region. */
void cbdatumcat(CBDATUM *datum, const char *ptr, int size){
  assert(datum && ptr);
  if(size < 0) size = strlen(ptr);
  if(datum->dsize + size >= datum->asize){
    datum->asize = datum->asize * 2 + size + 1;
    datum->dptr = cbrealloc(datum->dptr, datum->asize);
  }
  memmove(datum->dptr + datum->dsize, ptr, size);
  datum->dsize += size;
  datum->dptr[datum->dsize] = '\0';
}


/* Get the pointer of the region of a datum. */
const char *cbdatumptr(const CBDATUM *datum){
  assert(datum);
  return datum->dptr;
}


/* Get the size of the region of a datum. */
int cbdatumsize(const CBDATUM *datum){
  assert(datum);
  return datum->dsize;
}


/* Set the size of the region of a datum. */
void cbdatumsetsize(CBDATUM *datum, int size){
  assert(datum && size >= 0);
  if(size <= datum->dsize){
    datum->dsize = size;
    datum->dptr[size] = '\0';
  } else {
    if(size >= datum->asize){
      datum->asize = datum->asize * 2 + size + 1;
      datum->dptr = cbrealloc(datum->dptr, datum->asize);
    }
    memset(datum->dptr + datum->dsize, 0, (size - datum->dsize) + 1);
    datum->dsize = size;
  }
}


/* Get a list handle. */
CBLIST *cblistopen(void){
  CBLIST *list;
  list = cbmalloc(sizeof(*list));
  list->anum = CB_LISTUNIT;
  list->array = cbmalloc(sizeof(list->array[0]) * list->anum);
  list->start = 0;
  list->num = 0;
  return list;
}


/* Copy a list. */
CBLIST *cblistdup(const CBLIST *list){
  CBLIST *newlist;
  int i, size;
  const char *val;
  assert(list);
  newlist = cblistopen();
  for(i = 0; i < cblistnum(list); i++){
    val = cblistval(list, i, &size);
    cblistpush(newlist, val, size);
  }
  return newlist;
}


/* Close a list handle. */
void cblistclose(CBLIST *list){
  int i, end;
  assert(list);
  end = list->start + list->num;
  for(i = list->start; i < end; i++){
    free(list->array[i].dptr);
  }
  free(list->array);
  free(list);
}


/* Get the number of elements of a list. */
int cblistnum(const CBLIST *list){
  assert(list);
  return list->num;
}


/* Get the pointer to the region of an element. */
const char *cblistval(const CBLIST *list, int index, int *sp){
  assert(list && index >= 0);
  if(index >= list->num) return NULL;
  index += list->start;
  if(sp) *sp = list->array[index].dsize;
  return list->array[index].dptr;
}


/* Add an element at the end of a list. */
void cblistpush(CBLIST *list, const char *ptr, int size){
  int index;
  assert(list && ptr);
  if(size < 0) size = strlen(ptr);
  index = list->start + list->num;
  if(index >= list->anum){
    list->anum *= 2;
    list->array = cbrealloc(list->array, list->anum * sizeof(list->array[0]));
  }
  list->array[index].dptr = cbmemdup(ptr, size);
  list->array[index].dsize = size;
  list->num++;
}


/* Remove an element of the end of a list. */
char *cblistpop(CBLIST *list, int *sp){
  int index;
  assert(list);
  if(list->num < 1) return NULL;
  index = list->start + list->num - 1;
  list->num--;
  if(sp) *sp = list->array[index].dsize;
  return list->array[index].dptr;
}


/* Add an element at the top of a list. */
void cblistunshift(CBLIST *list, const char *ptr, int size){
  int index;
  assert(list && ptr);
  if(size < 0) size = strlen(ptr);
  if(list->start < 1){
    if(list->start + list->num >= list->anum){
      list->anum *= 2;
      list->array = cbrealloc(list->array, list->anum * sizeof(list->array[0]));
    }
    list->start = list->anum - list->num;
    memmove(list->array + list->start, list->array, list->num * sizeof(list->array[0]));
  }
  index = list->start - 1;
  list->array[index].dptr = cbmemdup(ptr, size);
  list->array[index].dsize = size;
  list->start--;
  list->num++;
}


/* Remove an element of the top of a list. */
char *cblistshift(CBLIST *list, int *sp){
  int index;
  assert(list);
  if(list->num < 1) return NULL;
  index = list->start;
  list->start++;
  list->num--;
  if(sp) *sp = list->array[index].dsize;
  return list->array[index].dptr;
}


/* Add an element at the specified location of a list. */
void cblistinsert(CBLIST *list, int index, const char *ptr, int size){
  assert(list && index >= 0);
  if(index > list->num) return;
  if(size < 0) size = strlen(ptr);
  index += list->start;
  if(list->start + list->num >= list->anum){
    list->anum *= 2;
    list->array = cbrealloc(list->array, list->anum * sizeof(list->array[0]));
  }
  memmove(list->array + index + 1, list->array + index,
          sizeof(list->array[0]) * (list->start + list->num - index));
  list->array[index].dptr = cbmemdup(ptr, size);
  list->array[index].dsize = size;
  list->num++;
}


/* Remove an element at the specified location of a list. */
char *cblistremove(CBLIST *list, int index, int *sp){
  char *dptr;
  assert(list && index >= 0);
  if(index >= list->num) return NULL;
  index += list->start;
  dptr = list->array[index].dptr;
  if(sp) *sp = list->array[index].dsize;
  memmove(list->array + index, list->array + index + 1,
          sizeof(list->array[0]) * (list->start + list->num - index));
  list->num--;
  return dptr;
}


/* Sort elements of a list in lexical order. */
void cblistsort(CBLIST *list){
  assert(list);
  cbqsort(list->array + list->start, list->num, sizeof(list->array[0]), cblistelemcmp);
}


/* Search a list for an element using liner search. */
int cblistlsearch(const CBLIST *list, const char *ptr, int size){
  int i, end;
  assert(list && ptr);
  if(size < 0) size = strlen(ptr);
  end = list->start + list->num;
  for(i = list->start; i < end; i++){
    if(list->array[i].dsize == size && !memcmp(list->array[i].dptr, ptr, size))
      return i - list->start;
  }
  return -1;
}


/* Search a list for an element using binary search. */
int cblistbsearch(const CBLIST *list, const char *ptr, int size){
  CBLISTDATUM key, *res;
  assert(list && ptr);
  if(size < 0) size = strlen(ptr);
  key.dptr = cbmemdup(ptr, size);
  key.dsize = size;
  res = bsearch(&key, list->array + list->start, list->num, sizeof(list->array[0]), cblistelemcmp);
  free(key.dptr);
  return res ? (res - list->array - list->start) : -1;
}


/* Serialize a list into a byte array. */
char *cblistdump(const CBLIST *list, int *sp){
  char *buf, vnumbuf[CB_VNUMBUFSIZ];
  const char *vbuf;
  int i, bsiz, vnumsiz, ln, vsiz;
  assert(list && sp);
  ln = cblistnum(list);
  vnumsiz = cbsetvnumbuf(vnumbuf, ln);
  buf = cbmalloc(vnumsiz + 1);
  memcpy(buf, vnumbuf, vnumsiz);
  bsiz = vnumsiz;
  for(i = 0; i < ln; i++){
    vbuf = cblistval(list, i, &vsiz);
    vnumsiz = cbsetvnumbuf(vnumbuf, vsiz);
    buf = cbrealloc(buf, bsiz + vnumsiz + vsiz + 1);
    memcpy(buf + bsiz, vnumbuf, vnumsiz);
    bsiz += vnumsiz;
    memcpy(buf + bsiz, vbuf, vsiz);
    bsiz += vsiz;
  }
  *sp = bsiz;
  return buf;
}


/* Redintegrate a serialized list. */
CBLIST *cblistload(const char *ptr, int size){
  CBLIST *list;
  const char *rp;
  int i, step, ln, vsiz;
  list = cblistopen();
  rp = ptr;
  ln = cbreadvnumbuf(rp, size, &step);
  rp += step;
  size -= step;
  if(ln > size) return list;
  for(i = 0; i < ln; i++){
    if(size < 1) break;
    vsiz = cbreadvnumbuf(rp, size, &step);
    rp += step;
    size -= step;
    if(vsiz > size) break;
    cblistpush(list, rp, vsiz);
    rp += vsiz;
  }
  return list;
}


/* Get a map handle. */
CBMAP *cbmapopen(void){
  CBMAP *map;
  int i;
  map = cbmalloc(sizeof(*map));
  map->buckets = cbmalloc(sizeof(map->buckets[0]) * CB_MAPBNUM);
  for(i = 0; i < CB_MAPBNUM; i++){
    map->buckets[i] = NULL;
  }
  map->first = NULL;
  map->last = NULL;
  map->cur = NULL;
  map->rnum = 0;
  return map;
}


/* Copy a map. */
CBMAP *cbmapdup(CBMAP *map){
  CBMAP *newmap;
  const char *kbuf, *vbuf;
  int ksiz, vsiz;
  assert(map);
  cbmapiterinit(map);
  newmap = cbmapopen();
  while((kbuf = cbmapiternext(map, &ksiz)) != NULL){
    vbuf = cbmapget(map, kbuf, ksiz, &vsiz);
    cbmapput(newmap, kbuf, ksiz, vbuf, vsiz, FALSE);
  }
  cbmapiterinit(map);
  return newmap;
}


/* Close a map handle. */
void cbmapclose(CBMAP *map){
  CBMAPDATUM *datum, *next;
  datum = map->first;
  while(datum){
    next = (CBMAPDATUM *)(datum->next);
    free(datum->kbuf);
    free(datum->vbuf);
    free(datum);
    datum = next;
  }
  free(map->buckets);
  free(map);
}


/* Store a record. */
int cbmapput(CBMAP *map, const char *kbuf, int ksiz, const char *vbuf, int vsiz, int over){
  CBMAPDATUM *datum, **entp;
  int bidx, hash, kcmp;
  assert(map && kbuf && vbuf);
  if(ksiz < 0) ksiz = strlen(kbuf);
  if(vsiz < 0) vsiz = strlen(vbuf);
  bidx = cbfirsthash(kbuf, ksiz) % CB_MAPBNUM;
  datum = map->buckets[bidx];
  entp = map->buckets + bidx;
  hash = cbsecondhash(kbuf, ksiz);
  while(datum){
    if(hash > datum->hash){
      entp = (CBMAPDATUM **)&(datum->left);
      datum = (CBMAPDATUM *)datum->left;
    } else if(hash < datum->hash){
      entp = (CBMAPDATUM **)&(datum->right);
      datum = (CBMAPDATUM *)datum->right;
    } else {
      kcmp = cbkeycmp(kbuf, ksiz, datum->kbuf, datum->ksiz);
      if(kcmp < 0){
        entp = (CBMAPDATUM **)&(datum->left);
        datum = (CBMAPDATUM *)datum->left;
      } else if(kcmp > 0){
        entp = (CBMAPDATUM **)&(datum->right);
        datum = (CBMAPDATUM *)datum->right;
      } else {
        if(!over) return FALSE;
        free(datum->vbuf);
        datum->vbuf = cbmemdup(vbuf, vsiz);
        datum->vsiz = vsiz;
        return TRUE;
      }
    }
  }
  datum = cbmalloc(sizeof(*datum));
  datum->kbuf = cbmemdup(kbuf, ksiz);
  datum->ksiz = ksiz;
  datum->vbuf = cbmemdup(vbuf, vsiz);
  datum->vsiz = vsiz;
  datum->hash = hash;
  datum->left = NULL;
  datum->right = NULL;
  datum->prev = (char *)map->last;
  datum->next = NULL;
  *entp = datum;
  if(!map->first) map->first = datum;
  if(map->last) map->last->next = (char *)datum;
  map->last = datum;
  map->rnum++;
  return TRUE;
}


/* Delete a record. */
int cbmapout(CBMAP *map, const char *kbuf, int ksiz){
  CBMAPDATUM *datum, **entp, *tmp;
  int bidx, hash, kcmp;
  assert(map && kbuf);
  if(ksiz < 0) ksiz = strlen(kbuf);
  bidx = cbfirsthash(kbuf, ksiz) % CB_MAPBNUM;
  datum = map->buckets[bidx];
  entp = map->buckets + bidx;
  hash = cbsecondhash(kbuf, ksiz);
  while(datum){
    if(hash > datum->hash){
      entp = (CBMAPDATUM **)&(datum->left);
      datum = (CBMAPDATUM *)datum->left;
    } else if(hash < datum->hash){
      entp = (CBMAPDATUM **)&(datum->right);
      datum = (CBMAPDATUM *)datum->right;
    } else {
      kcmp = cbkeycmp(kbuf, ksiz, datum->kbuf, datum->ksiz);
      if(kcmp < 0){
        entp = (CBMAPDATUM **)&(datum->left);
        datum = (CBMAPDATUM *)datum->left;
      } else if(kcmp > 0){
        entp = (CBMAPDATUM **)&(datum->right);
        datum = (CBMAPDATUM *)datum->right;
      } else {
        if(datum->prev) ((CBMAPDATUM *)(datum->prev))->next = datum->next;
        if(datum->next) ((CBMAPDATUM *)(datum->next))->prev = datum->prev;
        if(datum == map->first) map->first = (CBMAPDATUM *)datum->next;
        if(datum == map->last) map->last = (CBMAPDATUM *)datum->prev;
        if(datum->left && !datum->right){
          *entp = (CBMAPDATUM *)datum->left;
        } else if(!datum->left && datum->right){
          *entp = (CBMAPDATUM *)datum->right;
        } else if(!datum->left && !datum->left){
          *entp = NULL;
        } else {
          *entp = (CBMAPDATUM *)datum->left;
          tmp = *entp;
          while(TRUE){
            if(hash > tmp->hash){
              if(tmp->left){
                tmp = (CBMAPDATUM *)tmp->left;
              } else {
                tmp->left = datum->right;
                break;
              }
            } else if(hash < tmp->hash){
              if(tmp->right){
                tmp = (CBMAPDATUM *)tmp->right;
              } else {
                tmp->right = datum->right;
                break;
              }
            } else {
              kcmp = cbkeycmp(kbuf, ksiz, datum->kbuf, datum->ksiz);
              if(kcmp < 0){
                if(tmp->left){
                  tmp = (CBMAPDATUM *)tmp->left;
                } else {
                  tmp->left = datum->right;
                  break;
                }
              } else {
                if(tmp->right){
                  tmp = (CBMAPDATUM *)tmp->right;
                } else {
                  tmp->right = datum->right;
                  break;
                }
              }
            }
          }
        }
        free(datum->kbuf);
        free(datum->vbuf);
        free(datum);
        map->rnum--;
        return TRUE;
      }
    }
  }
  return FALSE;
}


/* Retrieve a record. */
const char *cbmapget(const CBMAP *map, const char *kbuf, int ksiz, int *sp){
  CBMAPDATUM *datum;
  int hash, kcmp;
  assert(map && kbuf);
  if(ksiz < 0) ksiz = strlen(kbuf);
  datum = map->buckets[cbfirsthash(kbuf, ksiz)%CB_MAPBNUM];
  hash = cbsecondhash(kbuf, ksiz);
  while(datum){
    if(hash > datum->hash){
      datum = (CBMAPDATUM *)datum->left;
    } else if(hash < datum->hash){
      datum = (CBMAPDATUM *)datum->right;
    } else {
      kcmp = cbkeycmp(kbuf, ksiz, datum->kbuf, datum->ksiz);
      if(kcmp < 0){
        datum = (CBMAPDATUM *)datum->left;
      } else if(kcmp > 0){
        datum = (CBMAPDATUM *)datum->right;
      } else {
        if(sp) *sp = datum->vsiz;
        return datum->vbuf;
      }
    }
  }
  return NULL;
}


/* Move a record to the edge. */
int cbmapmove(CBMAP *map, const char *kbuf, int ksiz, int head){
  CBMAPDATUM *datum;
  int hash, kcmp;
  assert(map && kbuf);
  if(ksiz < 0) ksiz = strlen(kbuf);
  datum = map->buckets[cbfirsthash(kbuf, ksiz)%CB_MAPBNUM];
  hash = cbsecondhash(kbuf, ksiz);
  while(datum){
    if(hash > datum->hash){
      datum = (CBMAPDATUM *)datum->left;
    } else if(hash < datum->hash){
      datum = (CBMAPDATUM *)datum->right;
    } else {
      kcmp = cbkeycmp(kbuf, ksiz, datum->kbuf, datum->ksiz);
      if(kcmp < 0){
        datum = (CBMAPDATUM *)datum->left;
      } else if(kcmp > 0){
        datum = (CBMAPDATUM *)datum->right;
      } else {
        if(head){
          if(map->first == datum) return TRUE;
          if(map->last == datum) map->last = (CBMAPDATUM *)(datum->prev);
          if(datum->prev) ((CBMAPDATUM *)(datum->prev))->next = datum->next;
          if(datum->next) ((CBMAPDATUM *)(datum->next))->prev = datum->prev;
          datum->prev = NULL;
          datum->next = (char *)(map->first);
          map->first->prev = (char *)datum;
          map->first = datum;
        } else {
          if(map->last == datum) return TRUE;
          if(map->first == datum) map->first = (CBMAPDATUM *)(datum->next);
          if(datum->prev) ((CBMAPDATUM *)(datum->prev))->next = datum->next;
          if(datum->next) ((CBMAPDATUM *)(datum->next))->prev = datum->prev;
          datum->prev = (char *)(map->last);
          datum->next = NULL;
          map->last->next = (char *)datum;
          map->last = datum;
        }
        return TRUE;
      }
    }
  }
  return FALSE;
}


/* Initialize the iterator of a map handle. */
void cbmapiterinit(CBMAP *map){
  assert(map);
  map->cur = map->first;
}


/* Get the next key of the iterator. */
const char *cbmapiternext(CBMAP *map, int *sp){
  CBMAPDATUM *datum;
  assert(map);
  if(!map->cur) return NULL;
  datum = map->cur;
  map->cur = (CBMAPDATUM *)datum->next;
  if(sp) *sp = datum->ksiz;
  return datum->kbuf;
}


/* Get the number of the records stored in a map. */
int cbmaprnum(const CBMAP *map){
  assert(map);
  return map->rnum;
}


/* Serialize a map into a byte array. */
char *cbmapdump(CBMAP *map, int *sp){
  char *buf, vnumbuf[CB_VNUMBUFSIZ];
  const char *kbuf, *vbuf;
  int bsiz, vnumsiz, rn, ksiz, vsiz;
  assert(map && sp);
  rn = cbmaprnum(map);
  vnumsiz = cbsetvnumbuf(vnumbuf, rn);
  buf = cbmalloc(vnumsiz + 1);
  memcpy(buf, vnumbuf, vnumsiz);
  bsiz = vnumsiz;
  cbmapiterinit(map);
  while((kbuf = cbmapiternext(map, &ksiz)) != NULL){
    vbuf = cbmapget(map, kbuf, ksiz, &vsiz);
    vnumsiz = cbsetvnumbuf(vnumbuf, ksiz);
    buf = cbrealloc(buf, bsiz + vnumsiz + ksiz + 1);
    memcpy(buf + bsiz, vnumbuf, vnumsiz);
    bsiz += vnumsiz;
    memcpy(buf + bsiz, kbuf, ksiz);
    bsiz += ksiz;
    vnumsiz = cbsetvnumbuf(vnumbuf, vsiz);
    buf = cbrealloc(buf, bsiz + vnumsiz + vsiz + 1);
    memcpy(buf + bsiz, vnumbuf, vnumsiz);
    bsiz += vnumsiz;
    memcpy(buf + bsiz, vbuf, vsiz);
    bsiz += vsiz;
  }
  *sp = bsiz;
  return buf;
}


/* Redintegrate a serialized map. */
CBMAP *cbmapload(const char *ptr, int size){
  CBMAP *map;
  const char *rp, *kbuf, *vbuf;
  int i, step, rn, ksiz, vsiz;
  map = cbmapopen();
  rp = ptr;
  rn = cbreadvnumbuf(rp, size, &step);
  rp += step;
  size -= step;
  if(rn > size) return map;
  for(i = 0; i < rn; i++){
    if(size < 1) break;
    ksiz = cbreadvnumbuf(rp, size, &step);
    rp += step;
    size -= step;
    if(ksiz > size) break;
    kbuf = rp;
    rp += ksiz;
    if(size < 1) break;
    vsiz = cbreadvnumbuf(rp, size, &step);
    rp += step;
    size -= step;
    if(vsiz > size) break;
    vbuf = rp;
    rp += vsiz;
    cbmapput(map, kbuf, ksiz, vbuf, vsiz, TRUE);
  }
  return map;
}


/* Allocate a formatted string on memory. */
char *cbsprintf(const char *format, ...){
  va_list ap;
  char *buf, cbuf[CB_SPBUFSIZ], *str;
  int len, cblen, num, slen;
  unsigned int unum;
  double dnum;
  va_start(ap, format);
  assert(format);
  buf = cbmalloc(1);
  len = 0;
  while(*format != '\0'){
    if(*format == '%'){
      cbuf[0] = '%';
      cblen = 1;
      format++;
      while(strchr("0123456789 .+-", *format) && *format != '\0' && cblen < CB_SPBUFSIZ - 1){
        cbuf[cblen++] = *format;
        format++;
      }
      cbuf[cblen] = '\0';
      if(atoi(cbuf + 1) > CB_SPMAXWIDTH - 16){
        sprintf(cbuf, "(err)");
      } else {
        cbuf[cblen++] = *format;
        cbuf[cblen] = '\0';
      }
      switch(*format){
      case 'd':
        num = va_arg(ap, int);
        buf = cbrealloc(buf, len + CB_SPMAXWIDTH + 1);
        len += sprintf(buf + len, cbuf, num);
        break;
      case 'o': case 'u': case 'x': case 'X': case 'c':
        unum = va_arg(ap, unsigned int);
        buf = cbrealloc(buf, len + CB_SPMAXWIDTH + 1);
        len += sprintf(buf + len, cbuf, unum);
        break;
      case 'e': case 'E': case 'f': case 'g': case 'G':
        dnum = va_arg(ap, double);
        buf = cbrealloc(buf, len + CB_SPMAXWIDTH + 1);
        len += sprintf(buf + len, cbuf, dnum);
        break;
      case 's':
        str = va_arg(ap, char *);
        slen = strlen(str);
        buf = cbrealloc(buf, len + slen + 1);
        memcpy(buf + len, str, slen);
        len += slen;
        break;
      case '%':
        buf = cbrealloc(buf, len + 1);
        buf[len++] = '%';
        break;
      default:
        break;
      }
    } else {
      buf = cbrealloc(buf, len + 1);
      buf[len++] = *format;
    }
    format++;
  }
  buf[len] = '\0';
  va_end(ap);
  return buf;
}


/* Replace some patterns in a string. */
char *cbreplace(const char *str, CBMAP *pairs){
  int i, bsiz, wi, rep, ksiz, vsiz;
  char *buf;
  const char *key, *val;
  assert(str && pairs);
  bsiz = CB_DATUMUNIT;
  buf = cbmalloc(bsiz);
  wi = 0;
  while(*str != '\0'){
    rep = FALSE;
    cbmapiterinit(pairs);
    while((key = cbmapiternext(pairs, &ksiz)) != NULL){
      for(i = 0; i < ksiz; i++){
        if(str[i] == '\0' || str[i] != key[i]) break;
      }
      if(i == ksiz){
        val = cbmapget(pairs, key, ksiz, &vsiz);
        if(wi + vsiz >= bsiz){
          bsiz = bsiz * 2 + vsiz;
          buf = cbrealloc(buf, bsiz);
        }
        memcpy(buf + wi, val, vsiz);
        wi += vsiz;
        str += ksiz;
        rep = TRUE;
        break;
      }
    }
    if(!rep){
      if(wi + 1 >= bsiz){
        bsiz = bsiz * 2 + 1;
        buf = cbrealloc(buf, bsiz);
      }
      buf[wi++] = *str;
      str++;
    }
  }
  buf = cbrealloc(buf, wi + 1);
  buf[wi] = '\0';
  return buf;
}


/* Make a list by split a serial datum. */
CBLIST *cbsplit(const char *ptr, int size, const char *delim){
  CBLIST *list;
  int bi, step;
  list = cblistopen();
  if(ptr){
    if(size < 0) size = strlen(ptr);
    if(delim){
      for(bi = 0; bi < size; bi += step){
        step = 0;
        while(!strchr(delim, ptr[bi+step])){
          step++;
        }
        cblistpush(list, ptr + bi, step);
        step++;
      }
      if(size > 0 && strchr(delim, ptr[size-1])) cblistpush(list, "", 0);
    } else {
      for(bi = 0; bi < size; bi += step){
        step = 0;
        while(ptr[bi+step]){
          step++;
        }
        cblistpush(list, ptr + bi, step);
        step++;
      }
      if(size > 0 && ptr[size-1] == 0) cblistpush(list, "", 0);
    }
  }
  return list;
}


/* Read whole data of a file. */
char *cbreadfile(const char *name, int *sp){
  int fd, size, rv;
  char iobuf[CB_IOBUFSIZ], *buf;
  assert(name);
  if((fd = open(name, O_RDONLY, 0)) == -1) return NULL;
  buf = cbmalloc(1);
  size = 0;
  while((rv = read(fd, iobuf, CB_IOBUFSIZ)) > 0){
    buf = cbrealloc(buf, size + rv + 1);
    memcpy(buf + size, iobuf, rv);
    size += rv;
  }
  buf[size] = '\0';
  if(close(fd) == -1 || rv == -1){
    free(buf);
    return NULL;
  }
  if(sp) *sp = size;
  return buf;
}


/* Read every line of a file. */
CBLIST *cbreadlines(const char *name){
  char *buf, *tmp;
  int vsiz;
  CBMAP *pairs;
  CBLIST *list;
  assert(name);
  if(!(buf = cbreadfile(name, NULL))) return NULL;
  pairs = cbmapopen();
  cbmapput(pairs, "\r\n", 2, "\n", 1, TRUE);
  cbmapput(pairs, "\r", 1, "\n", 1, TRUE);
  tmp = cbreplace(buf, pairs);
  list = cbsplit(tmp, strlen(tmp), "\n");
  free(tmp);
  cbmapclose(pairs);
  free(buf);
  if(cblistnum(list) > 0){
    cblistval(list, cblistnum(list) - 1, &vsiz);
    if(vsiz < 1) free(cblistpop(list, NULL));
  }
  return list;
}


/* Read names of files in a directory. */
CBLIST *cbdirlist(const char *name){
  DIR *DD;
  struct dirent *dp;
  CBLIST *list;
  assert(name);
  if(!(DD = opendir(name))) return NULL;
  list = cblistopen();
  while((dp = readdir(DD)) != NULL){
    cblistpush(list, dp->d_name, -1);
  }
  if(closedir(DD) == -1){
    cblistclose(list);
    return NULL;
  }
  return list;
}


/* Get the status of a file or a directory. */
int cbfilestat(const char *name, int *isdirp, int *sizep, int *mtimep){
  struct stat sbuf;
  assert(name);
  if(stat(name, &sbuf) == -1) return FALSE;
  if(isdirp) *isdirp = S_ISDIR(sbuf.st_mode);
  if(sizep) *sizep = (int)sbuf.st_size;
  if(mtimep) *mtimep = (int)sbuf.st_mtime;
  return TRUE;
}


/* Encode a serial object with URL encoding. */
char *cburlencode(const char *ptr, int size){
  char *buf, *wp;
  int i, c;
  assert(ptr);
  if(size < 0) size = strlen(ptr);
  buf = cbmalloc(size * 3 + 1);
  wp = buf;
  for(i = 0; i < size; i++){
    c = ((unsigned char *)ptr)[i];
    if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
       (c >= '0' && c <= '9') || (c != '\0' && strchr("_-.", c))){
      *(wp++) = c;
    } else if(c == ' '){
      *(wp++) = '+';
    } else {
      wp += sprintf(wp, "%%%02X", c);
    }
  }
  *wp = '\0';
  return buf;
}


/* Decode a string encoded with URL encoding. */
char *cburldecode(const char *str, int *sp){
  const char *hex = "1234567890abcdefABCDEF";
  char *buf, *wp;
  unsigned char c;
  buf = cbmemdup(str, -1);
  wp = buf;
  while(*str != '\0'){
    if(*str == '%'){
      str++;
      if(strchr(hex, *str) && strchr(hex, *(str + 1))){
        c = *str;
        if(c >= 'A' && c <= 'Z') c += 'a' - 'A';
        if(c >= 'a' && c <= 'z'){
          *wp = c - 'a' + 10;
        } else {
          *wp = c - '0';
        }
        *wp *= 0x10;
        str++;
        c = *str;
        if(c >= 'A' && c <= 'Z') c += 'a' - 'A';
        if(c >= 'a' && c <= 'z'){
          *wp += c - 'a' + 10;
        } else {
          *wp += c - '0';
        }
        str++;
        wp++;
      } else {
        break;
      }
    } else if(*str == '+'){
      *wp = ' ';
      str++;
      wp++;
    } else {
      *wp = *str;
      str++;
      wp++;
    }
  }
  *wp = '\0';
  if(sp) *sp = wp - buf;
  return buf;
}


/* Encode a serial object with Base64 encoding. */
char *cbbaseencode(const char *ptr, int size){
  char *tbl = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  char *buf, *wp;
  const unsigned char *obj;
  int i;
  assert(ptr);
  if(size < 0) size = strlen(ptr);
  buf = cbmalloc(4 * (size + 2) / 3 + 1);
  obj = (const unsigned char *)ptr;
  wp = buf;
  for(i = 0; i < size; i += 3){
    *wp++ = tbl[obj[0] >> 2];
    *wp++ = tbl[((obj[0] & 3) << 4) + (obj[1] >> 4)];
    *wp++ = tbl[((obj[1] & 0xf) << 2) + (obj[2] >> 6)];
    *wp++ = tbl[obj[2] & 0x3f];
    obj += 3;
  }
  if(i == size + 1){
    *(wp - 1) = '=';
  } else if(i == size + 2){
    *(wp - 1) = *(wp - 2) = '=';
  }
  *wp = '\0';
  return buf;
}


/* Decode a string encoded with Base64 encoding. */
char *cbbasedecode(const char *str, int *sp){
  unsigned char *obj, *wp;
  int len, cnt, bpos, i, bits, eqcnt;
  assert(str && sp);
  cnt = bpos = eqcnt = 0;
  len = strlen(str);
  wp = obj = cbmalloc(len + 1);
  while(bpos < len && eqcnt == 0){
    bits = 0;
    for(i = 0; bpos < len && i < 4; bpos++){
      if(str[bpos] >= 'A' && str[bpos] <= 'Z'){
        bits = (bits << 6) | (str[bpos] - 'A');
        i++;
      } else if(str[bpos] >= 'a' && str[bpos] <= 'z'){
        bits = (bits << 6) | (str[bpos] - 'a' + 26);
        i++;
      } else if(str[bpos] >= '0' && str[bpos] <= '9'){
        bits = (bits << 6) | (str[bpos] - '0' + 52);
        i++;
      } else if(str[bpos] == '+'){
        bits = (bits << 6) | 62;
        i++;
      } else if(str[bpos] == '/'){
        bits = (bits << 6) | 63;
        i++;
      } else if(str[bpos] == '='){
        bits <<= 6;
        i++;
        eqcnt++;
      }
    }
    if(i == 0 && bpos >= len) continue;
    switch(eqcnt){
    case 0:
      *wp++ = (bits >> 16) & 0xff;
      *wp++ = (bits >> 8) & 0xff;
      *wp++ = bits & 0xff;
      cnt += 3;
      break;
    case 1:
      *wp++ = (bits >> 16) & 0xff;
      *wp++ = (bits >> 8) & 0xff;
      cnt += 2;
      break;
    case 2:
      *wp++ = (bits >> 16) & 0xff;
      cnt += 1;
      break;
    }
  }
  obj[cnt] = '\0';
  if(sp) *sp = cnt;
  return (char *)obj;
}


/* Encode a serial object with quoted-printable encoding. */
char *cbquoteencode(const char *ptr, int size){
  const unsigned char *rp;
  char *buf, *wp;
  int i, cols;
  assert(ptr);
  if(size < 0) size = strlen(ptr);
  rp = (const unsigned char *)ptr;
  buf = wp = cbmalloc(size * 3 + 1);
  cols = 0;
  for(i = 0; i < size; i++){
    if(rp[i] == '=' || (rp[i] < 0x20 && rp[i] != '\r' && rp[i] != '\n' && rp[i] != '\t') ||
       rp[i] > 0x7e){
      wp += sprintf(wp, "=%02X", rp[i]);
      cols += 3;
    } else {
      *(wp++) = rp[i];
      cols++;
    }
  }
  *wp = '\0';
  return buf;
}


/* Decode a string encoded with quoted-printable encoding. */
char *cbquotedecode(const char *str, int *sp){
  char *buf, *wp;
  assert(str);
  buf = wp = cbmalloc(strlen(str) + 1);
  for(; *str != '\0'; str++){
    if(*str == '='){
      str++;
      if(*str == '\0'){
        break;
      } else if(str[0] == '\r' && str[1] == '\n'){
        str++;
      } else if(str[0] != '\n' && str[0] != '\r'){
        if(*str >= 'A' && *str <= 'Z'){
          *wp = (*str - 'A' + 10) * 16;
        } else if(*str >= 'a' && *str <= 'z'){
          *wp = (*str - 'a' + 10) * 16;
        } else {
          *wp = (*str - '0') * 16;
        }
        str++;
        if(*str == '\0') break;
        if(*str >= 'A' && *str <= 'Z'){
          *wp += *str - 'A' + 10;
        } else if(*str >= 'a' && *str <= 'z'){
          *wp += *str - 'a' + 10;
        } else {
          *wp += *str - '0';
        }
        wp++;
      }
    } else {
      *wp = *str;
      wp++;
    }
  }
  *wp = '\0';
  if(sp) *sp = wp - buf;
  return buf;
}


/* Compress a serial object with ZLIB. */
char *cbdeflate(const char *ptr, int size, int *sp){
  assert(ptr && sp);
  if(!_qdbm_deflate) return NULL;
  return _qdbm_deflate(ptr, size, sp);
}


/* Decompress a serial object compressed with ZLIB. */
char *cbinflate(const char *ptr, int size, int *sp){
  assert(ptr && size >= 0);
  if(!_qdbm_inflate) return NULL;
  return _qdbm_inflate(ptr, size, sp);
}



/*************************************************************************************************
 * private objects
 *************************************************************************************************/


/* Show error message on the standard error output and exit.
   `message' specifies an error message. */
static void cbmyfatal(const char *message){
  char buf[CB_MSGBUFSIZ];
  assert(message);
  sprintf(buf, "fatal error: %s\n", message);
  write(2, buf, strlen(buf));
  exit(1);
}


/* Utility function for quick sort.
   `bp' specifies the pointer to the pointer to an array.
   `nmemb' specifies the number of elements of the array.
   `size' specifies the size of each element.
   `pswap' specifies the pointer to the swap region for a pivot.
   `vswap' specifies the pointer to the swap region for elements.
   `compar' specifies the pointer to comparing function. */
static void cbqsortsub(char *bp, int nmemb, int size, char *pswap, char *vswap,
                       int(*compar)(const void *, const void *)){
  int top, bottom;
  assert(bp && nmemb >= 0 && size > 0 && pswap && vswap && compar);
  if(nmemb < 10){
    if(nmemb > 1) cbisort(bp, nmemb, size, compar);
    return;
  }
  top = 0;
  bottom = nmemb - 1;
  memcpy(pswap, bp + (nmemb / 2) * size, size);
  while(top - 1 < bottom){
    if(compar(bp + top * size, pswap) < 0){
      top++;
    } else if(compar(bp + bottom * size, pswap) > 0){
      bottom--;
    } else {
      memcpy(vswap, bp + top * size, size);
      memcpy(bp + top * size, bp + bottom * size, size);
      memcpy(bp + bottom * size, vswap, size);
      top++;
      bottom--;
    }
  }
  cbqsortsub(bp, top, size, pswap, vswap, compar);
  cbqsortsub(bp + (bottom + 1) * size, nmemb - bottom - 1, size, pswap, vswap, compar);
}


/* Compare two list elements.
   `a' specifies the pointer to one element.
   `b' specifies the pointer to the other element.
   The return value is positive if a is big, negative if b is big, else, it is 0. */
static int cblistelemcmp(const void *a, const void *b){
  int i, size;
  CBLISTDATUM *ap, *bp;
  char *ao, *bo;
  assert(a && b);
  ap = (CBLISTDATUM *)a;
  bp = (CBLISTDATUM *)b;
  ao = ap->dptr;
  bo = bp->dptr;
  size = ap->dsize < bp->dsize ? ap->dsize : bp->dsize;
  for(i = 0; i < size; i++){
    if(ao[i] > bo[i]) return 1;
    if(ao[i] < bo[i]) return -1;
  }
  return ap->dsize - bp->dsize;
}


/* Get the first hash value.
   `kbuf' specifies the pointer to the region of a key.
   `ksiz' specifies the size of the key.
   The return value is 31 bit hash value of the key. */
static int cbfirsthash(const char *kbuf, int ksiz){
  const unsigned char *p;
  unsigned int sum;
  int i;
  assert(kbuf && ksiz >= 0);
  p = (const unsigned char *)kbuf;
  sum = 751;
  for(i = 0; i < ksiz; i++){
    sum = sum * 31 + p[i];
  }
  return (sum * 87767623) & 0x7FFFFFFF;
}


/* Get the second hash value.
   `kbuf' specifies the pointer to the region of a key.
   `ksiz' specifies the size of the key.
   The return value is 31 bit hash value of the key. */
static int cbsecondhash(const char *kbuf, int ksiz){
  const unsigned char *p;
  unsigned int sum;
  int i;
  assert(kbuf && ksiz >= 0);
  p = (const unsigned char *)kbuf;
  sum = 19780211;
  for(i = ksiz - 1; i >= 0; i--){
    sum = sum * 37 + p[i];
  }
  return (sum * 43321879) & 0x7FFFFFFF;
}


/* Compare two keys.
   `abuf' specifies the pointer to the region of the former.
   `asiz' specifies the size of the region.
   `bbuf' specifies the pointer to the region of the latter.
   `bsiz' specifies the size of the region.
   The return value is 0 if two equals, positive if the formar is big, else, negative. */
static int cbkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz){
  assert(abuf && asiz >= 0 && bbuf && bsiz >= 0);
  if(asiz > bsiz) return 1;
  if(asiz < bsiz) return -1;
  return memcmp(abuf, bbuf, asiz);
}


/* Set a buffer for a variable length number.
   `buf' specifies the pointer to the buffer.
   `num' specifies the number.
   The return value is the size of valid region. */
static int cbsetvnumbuf(char *buf, int num){
  div_t d;
  int len;
  assert(buf && num >= 0);
  if(num == 0){
    ((signed char *)buf)[0] = 0;
    return 1;
  }
  len = 0;
  while(num > 0){
    d = div(num, 128);
    num = d.quot;
    ((signed char *)buf)[len] = d.rem;
    if(num > 0) ((signed char *)buf)[len] = -(((signed char *)buf)[len]) - 1;
    len++;
  }
  return len;
}


/* Read a variable length buffer.
   `buf' specifies the pointer to the buffer.
   `size' specifies the limit size to read.
   `sp' specifies the pointer to a variable to which the size of the read region assigned.
   The return value is the value of the buffer. */
static int cbreadvnumbuf(const char *buf, int size, int *sp){
  int i, num, base;
  assert(buf && size > 0 && sp);
  num = 0;
  base = 1;
  if(size < 2){
    *sp = 1;
    return ((signed char *)buf)[0];
  }
  for(i = 0; i < size; i++){
    if(((signed char *)buf)[i] >= 0){
      num += ((signed char *)buf)[i] * base;
      break;
    }
    num += base * (((signed char *)buf)[i] + 1) * -1;
    base *= 128;
  }
  *sp = i + 1;
  return num;
}



/* END OF FILE */