tcutil.c

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

}


/* Sort elements of a list object by an arbitrary comparison function. */
void tclistsortex(TCLIST *list, int (*cmp)(const TCLISTDATUM *, const TCLISTDATUM *)){
  assert(list && cmp);
  qsort(list->array + list->start, list->num, sizeof(list->array[0]),
        (int (*)(const void *, const void *))cmp);
}


/* Invert elements of a list object. */
void tclistinvert(TCLIST *list){
  assert(list);
  TCLISTDATUM *top = list->array + list->start;
  TCLISTDATUM *bot = top + list->num - 1;
  while(top < bot){
    TCLISTDATUM swap = *top;
    *top = *bot;
    *bot = swap;
    top++;
    bot--;
  }
}



/*************************************************************************************************
 * hash map
 *************************************************************************************************/


#define TCMAPKMAXSIZ   0xfffff           // maximum size of each key
#define TCMAPDEFBNUM   4093              // default bucket number
#define TCMAPZMMINSIZ  131072            // minimum memory size to use nullified region
#define TCMAPCSUNIT    52                // small allocation unit size of map concatenation
#define TCMAPCBUNIT    252               // big allocation unit size of map concatenation
#define TCMAPTINYBNUM  31                // bucket number of a tiny map

/* get the first hash value */
#define TCMAPHASH1(TC_res, TC_kbuf, TC_ksiz) \
  do { \
    const unsigned char *_TC_p = (const unsigned char *)(TC_kbuf); \
    int _TC_ksiz = TC_ksiz; \
    for((TC_res) = 19780211; _TC_ksiz--;){ \
      (TC_res) = (TC_res) * 37 + *(_TC_p)++; \
    } \
  } while(false)

/* get the second hash value */
#define TCMAPHASH2(TC_res, TC_kbuf, TC_ksiz) \
  do { \
    const unsigned char *_TC_p = (const unsigned char *)(TC_kbuf) + TC_ksiz - 1; \
    int _TC_ksiz = TC_ksiz; \
    for((TC_res) = 0x13579bdf; _TC_ksiz--;){ \
      (TC_res) = (TC_res) * 31 + *(_TC_p)--; \
    } \
  } while(false)

/* compare two keys */
#define TCKEYCMP(TC_abuf, TC_asiz, TC_bbuf, TC_bsiz) \
  ((TC_asiz > TC_bsiz) ? 1 : (TC_asiz < TC_bsiz) ? -1 : memcmp(TC_abuf, TC_bbuf, TC_asiz))


/* Create a map object. */
TCMAP *tcmapnew(void){
  return tcmapnew2(TCMAPDEFBNUM);
}


/* Create a map object with specifying the number of the buckets. */
TCMAP *tcmapnew2(uint32_t bnum){
  if(bnum < 1) bnum = 1;
  TCMAP *map;
  TCMALLOC(map, sizeof(*map));
  TCMAPREC **buckets;
  if(bnum >= TCMAPZMMINSIZ / sizeof(*buckets)){
    buckets = tczeromap(bnum * sizeof(*buckets));
  } else {
    TCCALLOC(buckets, bnum, sizeof(*buckets));
  }
  map->buckets = buckets;
  map->first = NULL;
  map->last = NULL;
  map->cur = NULL;
  map->bnum = bnum;
  map->rnum = 0;
  map->msiz = 0;
  return map;
}


/* Create a map object with initial string elements. */
TCMAP *tcmapnew3(const char *str, ...){
  TCMAP *map = tcmapnew2(TCMAPTINYBNUM);
  if(str){
    va_list ap;
    va_start(ap, str);
    const char *key = str;
    const char *elem;
    while((elem = va_arg(ap, char *)) != NULL){
      if(key){
        tcmapput2(map, key, elem);
        key = NULL;
      } else {
        key = elem;
      }
    }
    va_end(ap);
  }
  return map;
}


/* Copy a map object. */
TCMAP *tcmapdup(const TCMAP *map){
  assert(map);
  TCMAP *nmap = tcmapnew2(tclmax(tclmax(map->bnum, map->rnum), TCMAPDEFBNUM));
  TCMAPREC *rec = map->first;
  while(rec){
    char *dbuf = (char *)rec + sizeof(*rec);
    uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
    tcmapput(nmap, dbuf, rksiz, dbuf + rksiz + TCALIGNPAD(rksiz), rec->vsiz);
    rec = rec->next;
  }
  return nmap;
}


/* Close a map object. */
void tcmapdel(TCMAP *map){
  assert(map);
  TCMAPREC *rec = map->first;
  while(rec){
    TCMAPREC *next = rec->next;
    TCFREE(rec);
    rec = next;
  }
  if(map->bnum >= TCMAPZMMINSIZ / sizeof(map->buckets[0])){
    tczerounmap(map->buckets);
  } else {
    TCFREE(map->buckets);
  }
  TCFREE(map);
}


/* Store a record into a map object. */
void tcmapput(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
  if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
  uint32_t hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  int bidx = hash % map->bnum;
  TCMAPREC *rec = map->buckets[bidx];
  TCMAPREC **entp = map->buckets + bidx;
  TCMAPHASH2(hash, kbuf, ksiz);
  hash &= ~TCMAPKMAXSIZ;
  while(rec){
    uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
    uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
    if(hash > rhash){
      entp = &(rec->left);
      rec = rec->left;
    } else if(hash < rhash){
      entp = &(rec->right);
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
      if(kcmp < 0){
        entp = &(rec->left);
        rec = rec->left;
      } else if(kcmp > 0){
        entp = &(rec->right);
        rec = rec->right;
      } else {
        map->msiz += vsiz - rec->vsiz;
        int psiz = TCALIGNPAD(ksiz);
        if(vsiz > rec->vsiz){
          TCMAPREC *old = rec;
          TCREALLOC(rec, rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
          if(rec != old){
            if(map->first == old) map->first = rec;
            if(map->last == old) map->last = rec;
            if(map->cur == old) map->cur = rec;
            *entp = rec;
            if(rec->prev) rec->prev->next = rec;
            if(rec->next) rec->next->prev = rec;
            dbuf = (char *)rec + sizeof(*rec);
          }
        }
        memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
        dbuf[ksiz+psiz+vsiz] = '\0';
        rec->vsiz = vsiz;
        return;
      }
    }
  }
  int psiz = TCALIGNPAD(ksiz);
  map->msiz += ksiz + vsiz;
  TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
  char *dbuf = (char *)rec + sizeof(*rec);
  memcpy(dbuf, kbuf, ksiz);
  dbuf[ksiz] = '\0';
  rec->ksiz = ksiz | hash;
  memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
  dbuf[ksiz+psiz+vsiz] = '\0';
  rec->vsiz = vsiz;
  rec->left = NULL;
  rec->right = NULL;
  rec->prev = map->last;
  rec->next = NULL;
  *entp = rec;
  if(!map->first) map->first = rec;
  if(map->last) map->last->next = rec;
  map->last = rec;
  map->rnum++;
}


/* Store a string record into a map object. */
void tcmapput2(TCMAP *map, const char *kstr, const char *vstr){
  assert(map && kstr && vstr);
  tcmapput(map, kstr, strlen(kstr), vstr, strlen(vstr));
}


/* Store a new record into a map object. */
bool tcmapputkeep(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
  if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
  uint32_t hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  int bidx = hash % map->bnum;
  TCMAPREC *rec = map->buckets[bidx];
  TCMAPREC **entp = map->buckets + bidx;
  TCMAPHASH2(hash, kbuf, ksiz);
  hash &= ~TCMAPKMAXSIZ;
  while(rec){
    uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
    uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
    if(hash > rhash){
      entp = &(rec->left);
      rec = rec->left;
    } else if(hash < rhash){
      entp = &(rec->right);
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
      if(kcmp < 0){
        entp = &(rec->left);
        rec = rec->left;
      } else if(kcmp > 0){
        entp = &(rec->right);
        rec = rec->right;
      } else {
        return false;
      }
    }
  }
  int psiz = TCALIGNPAD(ksiz);
  map->msiz += ksiz + vsiz;
  TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
  char *dbuf = (char *)rec + sizeof(*rec);
  memcpy(dbuf, kbuf, ksiz);
  dbuf[ksiz] = '\0';
  rec->ksiz = ksiz | hash;
  memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
  dbuf[ksiz+psiz+vsiz] = '\0';
  rec->vsiz = vsiz;
  rec->left = NULL;
  rec->right = NULL;
  rec->prev = map->last;
  rec->next = NULL;
  *entp = rec;
  if(!map->first) map->first = rec;
  if(map->last) map->last->next = rec;
  map->last = rec;
  map->rnum++;
  return true;
}


/* Store a new string record into a map object. */
bool tcmapputkeep2(TCMAP *map, const char *kstr, const char *vstr){
  assert(map && kstr && vstr);
  return tcmapputkeep(map, kstr, strlen(kstr), vstr, strlen(vstr));
}


/* Concatenate a value at the end of the value of the existing record in a map object. */
void tcmapputcat(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
  if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
  uint32_t hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  int bidx = hash % map->bnum;
  TCMAPREC *rec = map->buckets[bidx];
  TCMAPREC **entp = map->buckets + bidx;
  TCMAPHASH2(hash, kbuf, ksiz);
  hash &= ~TCMAPKMAXSIZ;
  while(rec){
    uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
    uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
    if(hash > rhash){
      entp = &(rec->left);
      rec = rec->left;
    } else if(hash < rhash){
      entp = &(rec->right);
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
      if(kcmp < 0){
        entp = &(rec->left);
        rec = rec->left;
      } else if(kcmp > 0){
        entp = &(rec->right);
        rec = rec->right;
      } else {
        map->msiz += vsiz;
        int psiz = TCALIGNPAD(ksiz);
        int asiz = sizeof(*rec) + ksiz + psiz + rec->vsiz + vsiz + 1;
        int unit = (asiz <= TCMAPCSUNIT) ? TCMAPCSUNIT : TCMAPCBUNIT;
        asiz = (asiz - 1) + unit - (asiz - 1) % unit;
        TCMAPREC *old = rec;
        TCREALLOC(rec, rec, asiz);
        if(rec != old){
          if(map->first == old) map->first = rec;
          if(map->last == old) map->last = rec;
          if(map->cur == old) map->cur = rec;
          *entp = rec;
          if(rec->prev) rec->prev->next = rec;
          if(rec->next) rec->next->prev = rec;
          dbuf = (char *)rec + sizeof(*rec);
        }
        memcpy(dbuf + ksiz + psiz + rec->vsiz, vbuf, vsiz);
        rec->vsiz += vsiz;
        dbuf[ksiz+psiz+rec->vsiz] = '\0';
        return;
      }
    }
  }
  int psiz = TCALIGNPAD(ksiz);
  int asiz = sizeof(*rec) + ksiz + psiz + vsiz + 1;
  int unit = (asiz <= TCMAPCSUNIT) ? TCMAPCSUNIT : TCMAPCBUNIT;
  asiz = (asiz - 1) + unit - (asiz - 1) % unit;
  map->msiz += ksiz + vsiz;
  TCMALLOC(rec, asiz);
  char *dbuf = (char *)rec + sizeof(*rec);
  memcpy(dbuf, kbuf, ksiz);
  dbuf[ksiz] = '\0';
  rec->ksiz = ksiz | hash;
  memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
  dbuf[ksiz+psiz+vsiz] = '\0';
  rec->vsiz = vsiz;
  rec->left = NULL;
  rec->right = NULL;
  rec->prev = map->last;
  rec->next = NULL;
  *entp = rec;
  if(!map->first) map->first = rec;
  if(map->last) map->last->next = rec;
  map->last = rec;
  map->rnum++;
}


/* Concatenate a string value at the end of the value of the existing record in a map object. */
void tcmapputcat2(TCMAP *map, const char *kstr, const char *vstr){
  assert(map && kstr && vstr);
  tcmapputcat(map, kstr, strlen(kstr), vstr, strlen(vstr));
}


/* Remove a record of a map object. */
bool tcmapout(TCMAP *map, const void *kbuf, int ksiz){
  assert(map && kbuf && ksiz >= 0);
  if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
  uint32_t hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  int bidx = hash % map->bnum;
  TCMAPREC *rec = map->buckets[bidx];
  TCMAPREC **entp = map->buckets + bidx;
  TCMAPHASH2(hash, kbuf, ksiz);
  hash &= ~TCMAPKMAXSIZ;
  while(rec){
    uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
    uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
    if(hash > rhash){
      entp = &(rec->left);
      rec = rec->left;
    } else if(hash < rhash){
      entp = &(rec->right);
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
      if(kcmp < 0){
        entp = &(rec->left);
        rec = rec->left;
      } else if(kcmp > 0){
        entp = &(rec->right);
        rec = rec->right;
      } else {
        map->rnum--;
        map->msiz -= rksiz + rec->vsiz;
        if(rec->prev) rec->prev->next = rec->next;
        if(rec->next) rec->next->prev = rec->prev;
        if(rec == map->first) map->first = rec->next;
        if(rec == map->last) map->last = rec->prev;
        if(rec == map->cur) map->cur = rec->next;
        if(rec->left && !rec->right){
          *entp = rec->left;
        } else if(!rec->left && rec->right){
          *entp = rec->right;
        } else if(!rec->left && !rec->left){
          *entp = NULL;
        } else {
          *entp = rec->left;
          TCMAPREC *tmp = *entp;
          while(tmp->right){
            tmp = tmp->right;
          }
          tmp->right = rec->right;
        }
        TCFREE(rec);
        return true;
      }
    }
  }
  return false;
}


/* Remove a string record of a map object. */
bool tcmapout2(TCMAP *map, const char *kstr){
  assert(map && kstr);
  return tcmapout(map, kstr, strlen(kstr));
}


/* Retrieve a record in a map object. */
const void *tcmapget(const TCMAP *map, const void *kbuf, int ksiz, int *sp){
  assert(map && kbuf && ksiz >= 0 && sp);
  if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
  uint32_t hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  TCMAPREC *rec = map->buckets[hash%map->bnum];
  TCMAPHASH2(hash, kbuf, ksiz);
  hash &= ~TCMAPKMAXSIZ;
  while(rec){