tcutil.c

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

        return dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz);
      }
    }
  }
  return NULL;
}


/* 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);
  unsigned int hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  TCMAPREC *rec = map->buckets[hash%map->bnum];
  TCMAPHASH2(hash, kbuf, ksiz);
  while(rec){
    if(hash > rec->hash){
      rec = rec->left;
    } else if(hash < rec->hash){
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
      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 + rec->ksiz + TCALIGNPAD(rec->ksiz);
      }
    }
  }
  return NULL;
}


/* Move a record to the edge of a map object. */
bool tcmapmove(TCMAP *map, const void *kbuf, int ksiz, bool head){
  assert(map && kbuf && ksiz >= 0);
  unsigned int hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  TCMAPREC *rec = map->buckets[hash%map->bnum];
  TCMAPHASH2(hash, kbuf, ksiz);
  while(rec){
    if(hash > rec->hash){
      rec = rec->left;
    } else if(hash < rec->hash){
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
      if(kcmp < 0){
        rec = rec->left;
      } else if(kcmp > 0){
        rec = rec->right;
      } else {
        if(head){
          if(map->first == rec) return true;
          if(map->last == rec) map->last = rec->prev;
          if(rec->prev) rec->prev->next = rec->next;
          if(rec->next) rec->next->prev = rec->prev;
          rec->prev = NULL;
          rec->next = map->first;
          map->first->prev = rec;
          map->first = rec;
        } else {
          if(map->last == rec) return true;
          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 true;
      }
    }
  }
  return false;
}


/* Move a string record to the edge of a map object. */
bool tcmapmove2(TCMAP *map, const char *kstr, bool head){
  assert(map && kstr);
  return tcmapmove(map, kstr, strlen(kstr), head);
}


/* Initialize the iterator of a map object. */
void tcmapiterinit(TCMAP *map){
  assert(map);
  map->cur = map->first;
}


/* Get the next key of the iterator of a map object. */
const void *tcmapiternext(TCMAP *map, int *sp){
  assert(map && sp);
  TCMAPREC *rec;
  if(!map->cur) return NULL;
  rec = map->cur;
  map->cur = rec->next;
  *sp = rec->ksiz;
  return (char *)rec + sizeof(*rec);
}


/* Get the next key string of the iterator of a map object. */
const char *tcmapiternext2(TCMAP *map){
  assert(map);
  TCMAPREC *rec;
  if(!map->cur) return NULL;
  rec = map->cur;
  map->cur = rec->next;
  return (char *)rec + sizeof(*rec);
}


/* 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));
  *sp = rec->vsiz;
  return (char *)kbuf + rec->ksiz + TCALIGNPAD(rec->ksiz);
}


/* 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));
  return kstr + rec->ksiz + TCALIGNPAD(rec->ksiz);
}


/* Get the number of records stored in a map object. */
uint64_t tcmaprnum(const TCMAP *map){
  assert(map);
  return map->rnum;
}


/* Get the total size of memory used in a map object. */
uint64_t tcmapmsiz(const TCMAP *map){
  assert(map);
  return map->msiz + map->rnum * (sizeof(*map->first) + sizeof(void *)) +
    map->bnum * sizeof(void *);
}


/* Create a list object containing all keys in a map object. */
TCLIST *tcmapkeys(const TCMAP *map){
  assert(map);
  TCLIST *list = tclistnew2(map->rnum);
  TCMAPREC *rec = map->first;
  while(rec){
    char *dbuf = (char *)rec + sizeof(*rec);
    TCLISTPUSH(list, dbuf, rec->ksiz);
    rec = rec->next;
  }
  return list;
}


/* 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 a list object containing all values in a map object. */
TCLIST *tcmapvals(const TCMAP *map){
  assert(map);
  TCLIST *list = tclistnew2(map->rnum);
  TCMAPREC *rec = map->first;
  while(rec){
    char *dbuf = (char *)rec + sizeof(*rec);
    TCLISTPUSH(list, dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz), rec->vsiz);
    rec = rec->next;
  }
  return list;
}


/* 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){
    ary[(anum++)] = (char *)rec + sizeof(*rec) + rec->ksiz + TCALIGNPAD(rec->ksiz);
    rec = rec->next;
  }
  *np = anum;
  return ary;
}


/* Add an integer to a record in a map object. */
int tcmapaddint(TCMAP *map, const void *kbuf, int ksiz, int num){
  assert(map && kbuf && ksiz >= 0);
  unsigned int hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  int bidx = hash % map->bnum;
  TCMAPREC *rec = map->buckets[bidx];
  TCMAPREC **entp = map->buckets + bidx;
  TCMAPHASH2(hash, kbuf, ksiz);
  while(rec){
    if(hash > rec->hash){
      entp = &(rec->left);
      rec = rec->left;
    } else if(hash < rec->hash){
      entp = &(rec->right);
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
      if(kcmp < 0){
        entp = &(rec->left);
        rec = rec->left;
      } else if(kcmp > 0){
        entp = &(rec->right);
        rec = rec->right;
      } else {
        if(rec->vsiz != sizeof(num)) return INT_MIN;
        int *resp = (int *)(dbuf + ksiz + TCALIGNPAD(ksiz));
        return *resp += num;
      }
    }
  }
  int psiz = TCALIGNPAD(ksiz);
  TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + sizeof(num) + 1);
  char *dbuf = (char *)rec + sizeof(*rec);
  memcpy(dbuf, kbuf, ksiz);
  dbuf[ksiz] = '\0';
  rec->ksiz = ksiz;
  memcpy(dbuf + ksiz + psiz, &num, sizeof(num));
  dbuf[ksiz+psiz+sizeof(num)] = '\0';
  rec->vsiz = sizeof(num);
  rec->hash = hash;
  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 num;
}


/* Add a real number to a record in a map object. */
double tcmapadddouble(TCMAP *map, const void *kbuf, int ksiz, double num){
  assert(map && kbuf && ksiz >= 0);
  unsigned int hash;
  TCMAPHASH1(hash, kbuf, ksiz);
  int bidx = hash % map->bnum;
  TCMAPREC *rec = map->buckets[bidx];
  TCMAPREC **entp = map->buckets + bidx;
  TCMAPHASH2(hash, kbuf, ksiz);
  while(rec){
    if(hash > rec->hash){
      entp = &(rec->left);
      rec = rec->left;
    } else if(hash < rec->hash){
      entp = &(rec->right);
      rec = rec->right;
    } else {
      char *dbuf = (char *)rec + sizeof(*rec);
      int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rec->ksiz);
      if(kcmp < 0){
        entp = &(rec->left);
        rec = rec->left;
      } else if(kcmp > 0){
        entp = &(rec->right);
        rec = rec->right;
      } else {
        if(rec->vsiz != sizeof(num)) return nan("");
        double *resp = (double *)(dbuf + ksiz + TCALIGNPAD(ksiz));
        return *resp += num;
      }
    }
  }
  int psiz = TCALIGNPAD(ksiz);
  TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + sizeof(num) + 1);
  char *dbuf = (char *)rec + sizeof(*rec);
  memcpy(dbuf, kbuf, ksiz);
  dbuf[ksiz] = '\0';
  rec->ksiz = ksiz;
  memcpy(dbuf + ksiz + psiz, &num, sizeof(num));
  dbuf[ksiz+psiz+sizeof(num)] = '\0';
  rec->vsiz = sizeof(num);
  rec->hash = hash;
  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 num;
}


/* Clear a map object. */
void tcmapclear(TCMAP *map){
  assert(map);
  TCMAPREC *rec = map->first;
  while(rec){
    TCMAPREC *next = rec->next;
    TCFREE(rec);
    rec = next;
  }
  TCMAPREC **buckets = map->buckets;
  int bnum = map->bnum;
  for(int i = 0; i < bnum; i++){
    buckets[i] = NULL;
  }
  map->first = NULL;
  map->last = NULL;
  map->cur = NULL;
  map->rnum = 0;
  map->msiz = 0;
}


/* Remove front records of a map object. */
void tcmapcutfront(TCMAP *map, int num){
  assert(map && num >= 0);
  tcmapiterinit(map);
  while(num-- > 0){
    int ksiz;
    const char *kbuf = tcmapiternext(map, &ksiz);
    if(!kbuf) break;
    tcmapout(map, kbuf, ksiz);
  }
}


/* Serialize a map object into a byte array. */
void *tcmapdump(const TCMAP *map, int *sp){
  assert(map && sp);
  int tsiz = 0;
  TCMAPREC *rec = map->first;
  while(rec){
    tsiz += rec->ksiz + rec->vsiz + sizeof(int) * 2;
    rec = rec->next;
  }
  char *buf;
  TCMALLOC(buf, tsiz + 1);
  char *wp = buf;
  rec = map->first;
  while(rec){
    const char *kbuf = (char *)rec + sizeof(*rec);
    int ksiz = rec->ksiz;
    const char *vbuf = kbuf + ksiz + TCALIGNPAD(ksiz);
    int vsiz = rec->vsiz;
    int step;
    TCSETVNUMBUF(step, wp, ksiz);
    wp += step;
    memcpy(wp, kbuf, ksiz);
    wp += ksiz;
    TCSETVNUMBUF(step, wp, vsiz);
    wp += step;
    memcpy(wp, vbuf, vsiz);
    wp += vsiz;
    rec = rec->next;
  }
  *sp = wp - buf;
  return buf;
}


/* Create a map object from a serialized byte array. */
TCMAP *tcmapload(const void *ptr, int size){
  assert(ptr && size >= 0);
  TCMAP *map = tcmapnew();
  const char *rp = ptr;
  const char *ep = (char *)ptr + size;
  while(rp < ep){
    int step, ksiz, vsiz;
    TCREADVNUMBUF(rp, ksiz, step);
    rp += step;
    const char *kbuf = rp;
    rp += ksiz;
    TCREADVNUMBUF(rp, vsiz, step);
    rp += step;
    tcmapputkeep(map, kbuf, ksiz, rp, vsiz);
    rp += vsiz;
  }
  return map;
}


/* 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){