tcutil.c

高性能嵌入式数据库在高并发的环境下使用最好是64位系统比较好

  return tctreenew2(tctreecmplexical, NULL);
}


/* Create a tree object with specifying the custom comparison function. */
TCTREE *tctreenew2(TREECMP cmp, void *cmpop){
  assert(cmp);
  TCTREE *tree;
  TCMALLOC(tree, sizeof(*tree));
  tree->root = NULL;
  tree->cur = NULL;
  tree->rnum = 0;
  tree->msiz = 0;
  tree->cmp = cmp;
  tree->cmpop = cmpop;
  return tree;
}


/* Copy a tree object. */
TCTREE *tctreedup(const TCTREE *tree){
  assert(tree);
  TCTREE *ntree = tctreenew2(tree->cmp, tree->cmpop);
  if(tree->root){
    TCTREEREC *histbuf[TREESTACKNUM];
    TCTREEREC **history = histbuf;
    int hnum = 0;
    history[hnum++] = tree->root;
    while(hnum > 0){
      TCTREEREC *rec = history[--hnum];
      if(hnum >= TREESTACKNUM - 2 && history == histbuf){
        TCMALLOC(history, sizeof(*history) * tree->rnum);
        memcpy(history, histbuf, sizeof(*history) * hnum);
      }
      if(rec->left) history[hnum++] = rec->left;
      if(rec->right) history[hnum++] = rec->right;
      char *dbuf = (char *)rec + sizeof(*rec);
      tctreeput(ntree, dbuf, rec->ksiz, dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz), rec->vsiz);
    }
    if(history != histbuf) TCFREE(history);
  }
  return ntree;
}


/* Delete a tree object. */
void tctreedel(TCTREE *tree){
  assert(tree);
  if(tree->root){
    TCTREEREC *histbuf[TREESTACKNUM];
    TCTREEREC **history = histbuf;
    int hnum = 0;
    history[hnum++] = tree->root;
    while(hnum > 0){
      TCTREEREC *rec = history[--hnum];
      if(hnum >= TREESTACKNUM - 2 && history == histbuf){
        TCMALLOC(history, sizeof(*history) * tree->rnum);
        memcpy(history, histbuf, sizeof(*history) * hnum);
      }
      if(rec->left) history[hnum++] = rec->left;
      if(rec->right) history[hnum++] = rec->right;
      TCFREE(rec);
    }
    if(history != histbuf) TCFREE(history);
  }
  TCFREE(tree);
}


/* Store a record into a tree object. */
void tctreeput(TCTREE *tree, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  assert(tree && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
  TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
  if(!top){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    char *dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = NULL;
    rec->right = NULL;
    tree->root = rec;
    tree->rnum = 1;
    tree->msiz = ksiz + vsiz;
    return;
  }
  char *dbuf = (char *)top + sizeof(*top);
  int cv = tree->cmp(kbuf, ksiz, dbuf, top->ksiz, tree->cmpop);
  if(cv < 0){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = top->left;
    rec->right = top;
    top->left = NULL;
    tree->rnum++;
    tree->msiz += ksiz + vsiz;
    tree->root = rec;
  } else if(cv > 0){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = top;
    rec->right = top->right;
    top->right = NULL;
    tree->rnum++;
    tree->msiz += ksiz + vsiz;
    tree->root = rec;
  } else {
    int psiz = TCALIGNPAD(ksiz);
    if(vsiz > top->vsiz){
      TCTREEREC *old = top;
      TCREALLOC(top, top, sizeof(*top) + ksiz + psiz + vsiz + 1);
      if(top != old){
        if(tree->cur == old) tree->cur = top;
        dbuf = (char *)top + sizeof(*top);
      }
    }
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    top->vsiz = vsiz;
    tree->root = top;
  }
}


/* Store a string record into a tree object. */
void tctreeput2(TCTREE *tree, const char *kstr, const char *vstr){
  assert(tree && kstr && vstr);
  tctreeput(tree, kstr, strlen(kstr), vstr, strlen(vstr));
}


/* Store a new record into a tree object. */
bool tctreeputkeep(TCTREE *tree, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  assert(tree && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
  TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
  if(!top){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    char *dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = NULL;
    rec->right = NULL;
    tree->root = rec;
    tree->rnum = 1;
    tree->msiz = ksiz + vsiz;
    return true;
  }
  char *dbuf = (char *)top + sizeof(*top);
  int cv = tree->cmp(kbuf, ksiz, dbuf, top->ksiz, tree->cmpop);
  if(cv < 0){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = top->left;
    rec->right = top;
    top->left = NULL;
    tree->rnum++;
    tree->msiz += ksiz + vsiz;
    tree->root = rec;
  } else if(cv > 0){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = top;
    rec->right = top->right;
    top->right = NULL;
    tree->rnum++;
    tree->msiz += ksiz + vsiz;
    tree->root = rec;
  } else {
    tree->root = top;
    return false;
  }
  return true;
}


/* Store a new string record into a tree object. */
bool tctreeputkeep2(TCTREE *tree, const char *kstr, const char *vstr){
  assert(tree && kstr && vstr);
  return tctreeputkeep(tree, kstr, strlen(kstr), vstr, strlen(vstr));
}


/* Concatenate a value at the end of the value of the existing record in a tree object. */
void tctreeputcat(TCTREE *tree, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  assert(tree && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
  TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
  if(!top){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    char *dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = NULL;
    rec->right = NULL;
    tree->root = rec;
    tree->rnum = 1;
    tree->msiz = ksiz + vsiz;
    return;
  }
  char *dbuf = (char *)top + sizeof(*top);
  int cv = tree->cmp(kbuf, ksiz, dbuf, top->ksiz, tree->cmpop);
  if(cv < 0){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = top->left;
    rec->right = top;
    top->left = NULL;
    tree->rnum++;
    tree->msiz += ksiz + vsiz;
    tree->root = rec;
  } else if(cv > 0){
    int psiz = TCALIGNPAD(ksiz);
    TCTREEREC *rec;
    TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
    dbuf = (char *)rec + sizeof(*rec);
    memcpy(dbuf, kbuf, ksiz);
    dbuf[ksiz] = '\0';
    rec->ksiz = ksiz;
    memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
    dbuf[ksiz+psiz+vsiz] = '\0';
    rec->vsiz = vsiz;
    rec->left = top;
    rec->right = top->right;
    top->right = NULL;
    tree->rnum++;
    tree->msiz += ksiz + vsiz;
    tree->root = rec;
  } else {
    tree->msiz += vsiz;
    int psiz = TCALIGNPAD(ksiz);
    int asiz = sizeof(*top) + ksiz + psiz + top->vsiz + vsiz + 1;
    int unit = (asiz <= TCTREECSUNIT) ? TCTREECSUNIT : TCTREECBUNIT;
    asiz = (asiz - 1) + unit - (asiz - 1) % unit;
    TCTREEREC *old = top;
    TCREALLOC(top, top, asiz);
    if(top != old){
      if(tree->cur == old) tree->cur = top;
      dbuf = (char *)top + sizeof(*top);
    }
    memcpy(dbuf + ksiz + psiz + top->vsiz, vbuf, vsiz);
    top->vsiz += vsiz;
    dbuf[ksiz+psiz+top->vsiz] = '\0';
    tree->root = top;
  }
}


/* Concatenate a string value at the end of the value of the existing record in a tree object. */
void tctreeputcat2(TCTREE *tree, const char *kstr, const char *vstr){
  assert(tree && kstr && vstr);
  tctreeputcat(tree, kstr, strlen(kstr), vstr, strlen(vstr));
}


/* Remove a record of a tree object. */
bool tctreeout(TCTREE *tree, const void *kbuf, int ksiz){
  assert(tree && kbuf && ksiz >= 0);
  TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
  if(!top) return false;
  if(tree->cur == top){
    TCTREEREC *rec = top->right;
    if(rec){
      while(rec->left){
        rec = rec->left;
      }
    }
    tree->cur = rec;
  }
  char *dbuf = (char *)top + sizeof(*top);
  int cv = tree->cmp(kbuf, ksiz, dbuf, top->ksiz, tree->cmpop);
  if(cv != 0){
    tree->root = top;
    return false;
  }
  tree->rnum--;
  tree->msiz -= top->ksiz + top->vsiz;
  if(!top->left){
    tree->root = top->right;
  } else if(!top->right){
    tree->root = top->left;
  } else {
    tree->root = top->left;
    TCTREEREC *rec = tctreesplay(tree, kbuf, ksiz);
    rec->right = top->right;
    tree->root = rec;
  }
  TCFREE(top);
  return true;
}


/* Remove a string record of a tree object. */
bool tctreeout2(TCTREE *tree, const char *kstr){
  assert(tree && kstr);
  return tctreeout(tree, kstr, strlen(kstr));
}


/* Retrieve a record in a tree object. */
const void *tctreeget(TCTREE *tree, const void *kbuf, int ksiz, int *sp){
  assert(tree && kbuf && ksiz >= 0 && sp);
  TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
  if(!top) return NULL;
  char *dbuf = (char *)top + sizeof(*top);
  int cv = tree->cmp(kbuf, ksiz, dbuf, top->ksiz, tree->cmpop);
  if(cv != 0){
    tree->root = top;
    return NULL;
  }
  tree->root = top;
  *sp = top->vsiz;
  return dbuf + top->ksiz + TCALIGNPAD(top->ksiz);
}


/* Retrieve a string record in a tree object. */
const char *tctreeget2(TCTREE *tree, const char *kstr){
  assert(tree && kstr);
  int vsiz;
  return tctreeget(tree, kstr, strlen(kstr), &vsiz);
}


/* Retrieve a record in a tree object without balancing nodes. */
const void *tctreeget3(const TCTREE *tree, const void *kbuf, int ksiz, int *sp){
  assert(tree && kbuf && ksiz >= 0 && sp);
  TCTREEREC *rec = tree->root;
  while(rec){
    char *dbuf = (char *)rec + sizeof(*rec);
    int cv = tree->cmp(kbuf, ksiz, dbuf, rec->ksiz, tree->cmpop);
    if(cv < 0){
      rec = rec->left;
    } else if(cv > 0){
      rec = rec->right;
    } else {
      *sp = rec->vsiz;
      return dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz);
    }
  }
  return NULL;
}


/* Initialize the iterator of a tree object. */
void tctreeiterinit(TCTREE *tree){
  assert(tree);
  TCTREEREC *rec = tree->root;
  if(!rec) return;
  while(rec->left){
    rec = rec->left;
  }
  tree->cur = rec;
}


/* Initialize the iterator of a tree object in front of records corresponding a key. */
void tctreeiterinit2(TCTREE *tree, const void *kbuf, int ksiz){
  assert(tree && kbuf && ksiz >= 0);
  TCTREEREC *rec = tree->root;
  while(rec){
    char *dbuf = (char *)rec + sizeof(*rec);
    int cv = tree->cmp(kbuf, ksiz, dbuf, rec->ksiz, tree->cmpop);
    if(cv < 0){
      tree->cur = rec;
      rec = rec->left;
    } else if(cv > 0){
      rec = rec->right;
    } else {
      tree->cur = rec;
      return;
    }
  }
}


/* Initialize the iterator of a tree object in front of records corresponding a key string. */
void tctreeiterinit3(TCTREE *tree, const char *kstr){
  assert(tree);
  tctreeiterinit2(tree, kstr, strlen(kstr));
}


/* Get the next key of the iterator of a tree object. */
const void *tctreeiternext(TCTREE *tree, int *sp){
  assert(tree && sp);
  if(!tree->cur) return NULL;
  TCTREEREC *rec = tree->cur;
  const char *kbuf = (char *)rec + sizeof(*rec);
  int ksiz = rec->ksiz;
  rec = tctreesplay(tree, kbuf, ksiz);
  if(!rec) return NULL;
  tree->root = rec;
  rec = rec->right;
  if(rec){
    while(rec->left){
      rec = rec->left;
    }
  }
  tree->cur = rec;
  *sp = ksiz;
  return kbuf;
}


/* Get the next key string of the iterator of a tree object. */
const char *tctreeiternext2(T