cabin.c

harvest是一个下载html网页得机器人

/*************************************************************************************************
 * 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_GCUNIT      64                /* allocation unit size of a buffer in gc */
#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 cbggchandler(void);
static void cbggckeeper(void *ptr, void *func);
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;
}


/* Register the pointer or handle of an object to the global garbage collector. */
void cbglobalgc(void *ptr, void (*func)(void *)){
  assert(ptr && func);
  cbggckeeper(ptr, (void *)func);
}


/* 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;
  assert(ptr && size >= 0);
  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;
}