tcutil.c

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

          map->last->next = rec;
          map->last = rec;
        }
        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 record of the value of two regions into a map object. */
void tcmapput4(TCMAP *map, const void *kbuf, int ksiz,
               const void *fvbuf, int fvsiz, const void *lvbuf, int lvsiz){
  assert(map && kbuf && ksiz >= 0 && fvbuf && fvsiz >= 0 && lvbuf && lvsiz >= 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 {
        int vsiz = fvsiz + lvsiz;
        map->msiz += vsiz - rec->vsiz;
        int psiz = TCALIGNPAD(ksiz);
        ksiz += psiz;
        if(vsiz > rec->vsiz){
          TCMAPREC *old = rec;
          TCREALLOC(rec, rec, sizeof(*rec) + ksiz + 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, fvbuf, fvsiz);
        memcpy(dbuf + ksiz + fvsiz, lvbuf, lvsiz);
        dbuf[ksiz+vsiz] = '\0';
        rec->vsiz = vsiz;
        return;
      }
    }
  }
  int vsiz = fvsiz + lvsiz;
  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;
  ksiz += psiz;
  memcpy(dbuf + ksiz, fvbuf, fvsiz);
  memcpy(dbuf + ksiz + fvsiz, lvbuf, lvsiz);
  dbuf[ksiz+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 value at the existing record and make it semivolatile in a map object. */
void tcmapputcat3(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';
        if(map->last != rec){
          if(map->first == rec) map->first = rec->next;
          if(rec->prev) rec->prev->next = rec->next;
          if(rec->next) rec->next->prev = rec->prev;
          rec->prev = map->last;
          rec->next = NULL;
          map->last->next = rec;
          map->last = rec;
        }
        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++;
}


/* Store a record into a map object with a duplication handler. */
bool tcmapputproc(TCMAP *map, const void *kbuf, int ksiz, const char *vbuf, int vsiz,
                  TCPDPROC proc, void *op){
  assert(map && kbuf && ksiz >= 0 && proc);
  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 {
        int psiz = TCALIGNPAD(ksiz);
        int nvsiz;
        char *nvbuf = proc(dbuf + ksiz + psiz, rec->vsiz, &nvsiz, op);
        if(nvbuf == (void *)-1){
          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;
        }
        if(!nvbuf) return false;
        map->msiz += nvsiz - rec->vsiz;
        if(nvsiz > rec->vsiz){
          TCMAPREC *old = rec;
          TCREALLOC(rec, rec, sizeof(*rec) + ksiz + psiz + nvsiz + 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, nvbuf, nvsiz);
        dbuf[ksiz+psiz+nvsiz] = '\0';
        rec->vsiz = nvsiz;
        TCFREE(nvbuf);
        return true;
      }
    }
  }
  if(!vbuf) return false;
  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++;
  return true;
}


/* Retrieve a semivolatile record in a map object. */
const void *tcmapget3(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){
    uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
    uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
    if(hash > rhash){
      rec = rec->left;
    } else if(hash < rhash){
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
      if(kcmp < 0){
        rec = rec->left;
      } else if(kcmp > 0){
        rec = rec->right;
      } else {
        if(map->last != rec){
          if(map->first == rec) map->first = rec->next;
          if(rec->prev) rec->prev->next = rec->next;
          if(rec->next) rec->next->prev = rec->prev;
          rec->prev = map->last;
          rec->next = NULL;
          map->last->next = rec;
          map->last = rec;
        }
        *sp = rec->vsiz;
        return dbuf + rksiz + TCALIGNPAD(rksiz);
      }
    }
  }
  return NULL;
}


/* Get the value bound to the key fetched from the iterator of a map object. */
const void *tcmapiterval(const void *kbuf, int *sp){
  assert(kbuf && sp);
  TCMAPREC *rec = (TCMAPREC *)((char *)kbuf - sizeof(*rec));
  uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
  *sp = rec->vsiz;
  return (char *)kbuf + rksiz + TCALIGNPAD(rksiz);
}


/* Get the value string bound to the key fetched from the iterator of a map object. */
const char *tcmapiterval2(const char *kstr){
  assert(kstr);
  TCMAPREC *rec = (TCMAPREC *)(kstr - sizeof(*rec));
  uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
  return kstr + rksiz + TCALIGNPAD(rksiz);
}


/* Create an array of strings of all keys in a map object. */
const char **tcmapkeys2(const TCMAP *map, int *np){
  assert(map && np);
  const char **ary;
  TCMALLOC(ary, sizeof(*ary) * map->rnum + 1);
  int anum = 0;
  TCMAPREC *rec = map->first;
  while(rec){
    ary[(anum++)] = (char *)rec + sizeof(*rec);
    rec = rec->next;
  }
  *np = anum;
  return ary;
}


/* Create an array of strings of all values in a map object. */
const char **tcmapvals2(const TCMAP *map, int *np){
  assert(map && np);
  const char **ary;
  TCMALLOC(ary, sizeof(*ary) * map->rnum + 1);
  int anum = 0;
  TCMAPREC *rec = map->first;
  while(rec){
    uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
    ary[(anum++)] = (char *)rec + sizeof(*rec) + rksiz + TCALIGNPAD(rksiz);
    rec = rec->next;
  }
  *np = anum;
  return ary;
}


/* Extract a map record from a serialized byte array. */
void *tcmaploadone(const void *ptr, int size, const void *kbuf, int ksiz, int *sp){
  assert(ptr && size >= 0 && kbuf && ksiz >= 0 && sp);
  const char *rp = ptr;
  const char *ep = (char *)ptr + size;
  while(rp < ep){
    int step, rsiz;
    TCREADVNUMBUF(rp, rsiz, step);
    rp += step;
    if(rsiz == ksiz && !memcmp(kbuf, rp, rsiz)){
      rp += rsiz;
      TCREADVNUMBUF(rp, rsiz, step);
      rp += step;
      *sp = rsiz;
      char *rv;
      TCMEMDUP(rv, rp, rsiz);
      return rv;
    }
    rp += rsiz;
    TCREADVNUMBUF(rp, rsiz, step);
    rp += step;
    rp += rsiz;
  }
  return NULL;
}



/*************************************************************************************************
 * ordered tree
 *************************************************************************************************/


#define TREESTACKNUM   2048              // capacity of the stack of ordered tree
#define TCTREECSUNIT   52                // small allocation unit size of map concatenation
#define TCTREECBUNIT   252               // big allocation unit size of map concatenation


/* private function prototypes */
static TCTREEREC* tctreesplay(TCTREE *tree, const void *kbuf, int ksiz);


/* Create a tree object. */
TCTREE *tctreenew(void){
  return tctreenew2(tccmplexical, NULL);
}


/* Create a tree object with specifying the custom comparison function. */
TCTREE *tctreenew2(TCCMP cmp, void *cmpop){
  assert(cmp);
  TCTREE *t