tcutil.c

Tokyo Cabinet的Tokyo Cabinet 是一个DBM的实现。这里的数据库由一系列key-value对的记录构成。key和value都可以是任意长度的字节序列,既可以是二进制也可以是字符

    TCMALLOC(narray[i].ptr, tclmax(size + 1, TCXSTRUNIT));
    memcpy(narray[i].ptr, array[i].ptr, size + 1);
    narray[i].size = array[i].size;
  }
  nlist->anum = num;
  nlist->array = narray;
  nlist->start = 0;
  nlist->num = num;
  return nlist;
}


/* Delete a list object. */
void tclistdel(TCLIST *list){
  assert(list);
  TCLISTDATUM *array = list->array;
  int end = list->start + list->num;
  for(int i = list->start; i < end; i++){
    TCFREE(array[i].ptr);
  }
  TCFREE(list->array);
  TCFREE(list);
}


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


/* Get the pointer to the region of an element of a list object. */
const void *tclistval(const TCLIST *list, int index, int *sp){
  assert(list && index >= 0 && sp);
  if(index >= list->num) return NULL;
  index += list->start;
  *sp = list->array[index].size;
  return list->array[index].ptr;
}


/* Get the string of an element of a list object. */
const char *tclistval2(const TCLIST *list, int index){
  assert(list && index >= 0);
  if(index >= list->num) return NULL;
  index += list->start;
  return list->array[index].ptr;
}


/* Add an element at the end of a list object. */
void tclistpush(TCLIST *list, const void *ptr, int size){
  assert(list && ptr && size >= 0);
  int index = list->start + list->num;
  if(index >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  TCLISTDATUM *array = list->array;
  TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  memcpy(array[index].ptr, ptr, size);
  array[index].ptr[size] = '\0';
  array[index].size = size;
  list->num++;
}


/* Add a string element at the end of a list object. */
void tclistpush2(TCLIST *list, const char *str){
  assert(list && str);
  int index = list->start + list->num;
  if(index >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  int size = strlen(str);
  TCLISTDATUM *array = list->array;
  TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  memcpy(array[index].ptr, str, size + 1);
  array[index].size = size;
  list->num++;
}


/* Remove an element of the end of a list object. */
void *tclistpop(TCLIST *list, int *sp){
  assert(list && sp);
  if(list->num < 1) return NULL;
  int index = list->start + list->num - 1;
  list->num--;
  *sp = list->array[index].size;
  return list->array[index].ptr;
}


/* Remove a string element of the end of a list object. */
char *tclistpop2(TCLIST *list){
  assert(list);
  if(list->num < 1) return NULL;
  int index = list->start + list->num - 1;
  list->num--;
  return list->array[index].ptr;
}


/* Add an element at the top of a list object. */
void tclistunshift(TCLIST *list, const void *ptr, int size){
  assert(list && ptr && size >= 0);
  if(list->start < 1){
    if(list->start + list->num >= list->anum){
      list->anum += list->num + 1;
      TCREALLOC(list->array, 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]));
  }
  int index = list->start - 1;
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  memcpy(list->array[index].ptr, ptr, size);
  list->array[index].ptr[size] = '\0';
  list->array[index].size = size;
  list->start--;
  list->num++;
}


/* Add a string element at the top of a list object. */
void tclistunshift2(TCLIST *list, const char *str){
  assert(list && str);
  if(list->start < 1){
    if(list->start + list->num >= list->anum){
      list->anum += list->num + 1;
      TCREALLOC(list->array, 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]));
  }
  int index = list->start - 1;
  int size = strlen(str);
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  memcpy(list->array[index].ptr, str, size + 1);
  list->array[index].size = size;
  list->start--;
  list->num++;
}


/* Remove an element of the top of a list object. */
void *tclistshift(TCLIST *list, int *sp){
  assert(list && sp);
  if(list->num < 1) return NULL;
  int index = list->start;
  list->start++;
  list->num--;
  *sp = list->array[index].size;
  void *rv = list->array[index].ptr;
  if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
    memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
    list->start = 0;
  }
  return rv;
}


/* Remove a string element of the top of a list object. */
char *tclistshift2(TCLIST *list){
  assert(list);
  if(list->num < 1) return NULL;
  int index = list->start;
  list->start++;
  list->num--;
  void *rv = list->array[index].ptr;
  if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
    memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
    list->start = 0;
  }
  return rv;
}


/* Add an element at the specified location of a list object. */
void tclistinsert(TCLIST *list, int index, const void *ptr, int size){
  assert(list && index >= 0 && ptr && size >= 0);
  if(index > list->num) return;
  index += list->start;
  if(list->start + list->num >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, 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));
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  memcpy(list->array[index].ptr, ptr, size);
  list->array[index].ptr[size] = '\0';
  list->array[index].size = size;
  list->num++;
}


/* Add a string element at the specified location of a list object. */
void tclistinsert2(TCLIST *list, int index, const char *str){
  assert(list && index >= 0 && str);
  if(index > list->num) return;
  index += list->start;
  if(list->start + list->num >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, 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));
  int size = strlen(str);
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  memcpy(list->array[index].ptr, str, size);
  list->array[index].ptr[size] = '\0';
  list->array[index].size = size;
  list->num++;
}


/* Remove an element at the specified location of a list object. */
void *tclistremove(TCLIST *list, int index, int *sp){
  assert(list && index >= 0 && sp);
  if(index >= list->num) return NULL;
  index += list->start;
  void *rv = list->array[index].ptr;
  *sp = list->array[index].size;
  list->num--;
  memmove(list->array + index, list->array + index + 1,
          sizeof(list->array[0]) * (list->start + list->num - index));
  return rv;
}


/* Remove a string element at the specified location of a list object. */
char *tclistremove2(TCLIST *list, int index){
  assert(list && index >= 0);
  if(index >= list->num) return NULL;
  index += list->start;
  void *rv = list->array[index].ptr;
  list->num--;
  memmove(list->array + index, list->array + index + 1,
          sizeof(list->array[0]) * (list->start + list->num - index));
  return rv;
}


/* Overwrite an element at the specified location of a list object. */
void tclistover(TCLIST *list, int index, const void *ptr, int size){
  assert(list && index >= 0 && ptr && size >= 0);
  if(index >= list->num) return;
  index += list->start;
  if(size > list->array[index].size)
    TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
  memcpy(list->array[index].ptr, ptr, size);
  list->array[index].size = size;
  list->array[index].ptr[size] = '\0';
}


/* Overwrite a string element at the specified location of a list object. */
void tclistover2(TCLIST *list, int index, const char *str){
  assert(list && index >= 0 && str);
  if(index >= list->num) return;
  index += list->start;
  int size = strlen(str);
  if(size > list->array[index].size)
    TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
  memcpy(list->array[index].ptr, str, size + 1);
  list->array[index].size = size;
}


/* Sort elements of a list object in lexical order. */
void tclistsort(TCLIST *list){
  assert(list);
  qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmp);
}


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


/* Search a list object for an element using binary search. */
int tclistbsearch(const TCLIST *list, const void *ptr, int size){
  assert(list && ptr && size >= 0);
  TCLISTDATUM key;
  key.ptr = (char *)ptr;
  key.size = size;
  TCLISTDATUM *res = bsearch(&key, list->array + list->start,
                             list->num, sizeof(list->array[0]), tclistelemcmp);
  return res ? res - list->array - list->start : -1;
}


/* Clear a list object. */
void tclistclear(TCLIST *list){
  assert(list);
  TCLISTDATUM *array = list->array;
  int end = list->start + list->num;
  for(int i = list->start; i < end; i++){
    TCFREE(array[i].ptr);
  }
  list->start = 0;
  list->num = 0;
}


/* Serialize a list object into a byte array. */
void *tclistdump(const TCLIST *list, int *sp){
  assert(list && sp);
  const TCLISTDATUM *array = list->array;
  int end = list->start + list->num;
  int tsiz = 0;
  for(int i = list->start; i < end; i++){
    tsiz += array[i].size + sizeof(int);
  }
  char *buf;
  TCMALLOC(buf, tsiz + 1);
  char *wp = buf;
  for(int i = list->start; i < end; i++){
    int step;
    TCSETVNUMBUF(step, wp, array[i].size);
    wp += step;
    memcpy(wp, array[i].ptr, array[i].size);
    wp += array[i].size;
  }
  *sp = wp - buf;
  return buf;
}


/* Create a list object from a serialized byte array. */
TCLIST *tclistload(const void *ptr, int size){
  assert(ptr && size >= 0);
  TCLIST *list;
  TCMALLOC(list, sizeof(*list));
  int anum = size / sizeof(int) + 1;
  TCLISTDATUM *array;
  TCMALLOC(array, sizeof(array[0]) * anum);
  int num = 0;
  const char *rp = ptr;
  const char *ep = (char *)ptr + size;
  while(rp < ep){
    int step, vsiz;
    TCREADVNUMBUF(rp, vsiz, step);
    rp += step;
    if(num >= anum){
      anum *= 2;
      TCREALLOC(array, array, anum * sizeof(array[0]));
    }
    TCMALLOC(array[num].ptr, tclmax(vsiz + 1, TCXSTRUNIT));
    memcpy(array[num].ptr, rp, vsiz);
    array[num].ptr[vsiz] = '\0';
    array[num].size = vsiz;
    num++;
    rp += vsiz;
  }
  list->anum = anum;
  list->array = array;
  list->start = 0;
  list->num = num;
  return list;
}


/* Compare two list elements in lexical order.
   `a' specifies the pointer to one element.
   `b' specifies the pointer to the other element.
   The return value is positive if the former is big, negative if the latter is big, 0 if both
   are equivalent. */
static int tclistelemcmp(const void *a, const void *b){
  assert(a && b);
  unsigned char *ao = (unsigned char *)((TCLISTDATUM *)a)->ptr;
  unsigned char *bo = (unsigned char *)((TCLISTDATUM *)b)->ptr;
  int size = (((TCLISTDATUM *)a)->size < ((TCLISTDATUM *)b)->size) ?
    ((TCLISTDATUM *)a)->size : ((TCLISTDATUM *)b)->size;
  for(int i = 0; i < size; i++){
    if(ao[i] > bo[i]) return 1;
    if(ao[i] < bo[i]) return -1;
  }
  return ((TCLISTDATUM *)a)->size - ((TCLISTDATUM *)b)->size;
}


/* Compare two list elements in case-insensitive lexical order..
   `a' specifies the pointer to one element.
   `b' specifies the pointer to the other element.
   The return value is positive if the former is big, negative if the latter is big, 0 if both
   are equivalent. */
static int tclistelemcmpci(const void *a, const void *b){
  assert(a && b);
  TCLISTDATUM *ap = (TCLISTDATUM *)a;
  TCLISTDATUM *bp = (TCLISTDATUM *)b;
  unsigned char *ao = (unsigned char *)ap->ptr;
  unsigned char *bo = (unsigned char *)bp->ptr;
  int size = (ap->size < bp->size) ? ap->size : bp->size;
  for(int i = 0; i < size; i++){
    int ac = ao[i];
    bool ab = false;
    if(ac >= 'A' && ac <= 'Z'){
      ac += 'a' - 'A';
      ab = true;
    }
    int bc = bo[i];
    bool bb = false;
    if(bc >= 'A' && bc <= 'Z'){
      bc += 'a' - 'A';
      bb = true;
    }
    if(ac > bc) return 1;
    if(ac < bc) return -1;
    if(!ab && bb) return 1;
    if(ab && !bb) return -1;
  }
  return ap->size - bp->size;
}



/*************************************************************************************************
 * array list (for experts)
 *************************************************************************************************/


/* Add an allocated element at the end of a list object. */
void tclistpushmalloc(TCLIST *list, void *ptr, int size){
  assert(list && ptr && size >= 0);
  int index = list->start + list->num;
  if(index >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  TCLISTDATUM *array = list->array;
  TCREALLOC(array[index].ptr, ptr, size + 1);
  array[index].ptr[size] = '\0';
  array[index].size = size;
  list->num++;
}


/* Sort elements of a list object in case-insensitive lexical order. */
void tclistsortci(TCLIST *list){
  assert(list);
  qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmpci);