Permalink
Fetching contributors…
Cannot retrieve contributors at this time
10223 lines (9305 sloc) 280 KB
/*************************************************************************************************
* The utility API of Tokyo Cabinet
* Copyright (C) 2006-2009 Mikio Hirabayashi
* This file is part of Tokyo Cabinet.
* Tokyo Cabinet 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. Tokyo Cabinet 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 Tokyo
* Cabinet; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
* Boston, MA 02111-1307 USA.
*************************************************************************************************/
#include "tcutil.h"
#include "myconf.h"
#include "md5.h"
/*************************************************************************************************
* basic utilities
*************************************************************************************************/
/* String containing the version information. */
const char *tcversion = _TC_VERSION;
/* Call back function for handling a fatal error. */
void (*tcfatalfunc)(const char *message) = NULL;
/* Allocate a region on memory. */
void *tcmalloc(size_t size){
assert(size > 0 && size < INT_MAX);
char *p;
TCMALLOC(p, size);
return p;
}
/* Allocate a nullified region on memory. */
void *tccalloc(size_t nmemb, size_t size){
assert(nmemb > 0 && size < INT_MAX && size > 0 && size < INT_MAX);
char *p;
TCCALLOC(p, nmemb, size);
return p;
}
/* Re-allocate a region on memory. */
void *tcrealloc(void *ptr, size_t size){
assert(size >= 0 && size < INT_MAX);
char *p;
TCREALLOC(p, ptr, size);
return p;
}
/* Duplicate a region on memory. */
void *tcmemdup(const void *ptr, size_t size){
assert(ptr && size >= 0);
char *p;
TCMALLOC(p, size + 1);
memcpy(p, ptr, size);
p[size] = '\0';
return p;
}
/* Duplicate a string on memory. */
char *tcstrdup(const void *str){
assert(str);
int size = strlen(str);
char *p;
TCMALLOC(p, size + 1);
memcpy(p, str, size);
p[size] = '\0';
return p;
}
/* Free a region on memory. */
void tcfree(void *ptr){
TCFREE(ptr);
}
/*************************************************************************************************
* extensible string
*************************************************************************************************/
#define TCXSTRUNIT 12 // allocation unit size of an extensible string
/* private function prototypes */
static void tcvxstrprintf(TCXSTR *xstr, const char *format, va_list ap);
/* Create an extensible string object. */
TCXSTR *tcxstrnew(void){
TCXSTR *xstr;
TCMALLOC(xstr, sizeof(*xstr));
TCMALLOC(xstr->ptr, TCXSTRUNIT);
xstr->size = 0;
xstr->asize = TCXSTRUNIT;
xstr->ptr[0] = '\0';
return xstr;
}
/* Create an extensible string object from a character string. */
TCXSTR *tcxstrnew2(const char *str){
assert(str);
TCXSTR *xstr;
TCMALLOC(xstr, sizeof(*xstr));
int size = strlen(str);
int asize = tclmax(size + 1, TCXSTRUNIT);
TCMALLOC(xstr->ptr, asize);
xstr->size = size;
xstr->asize = asize;
memcpy(xstr->ptr, str, size + 1);
return xstr;
}
/* Create an extensible string object with the initial allocation size. */
TCXSTR *tcxstrnew3(int asiz){
assert(asiz >= 0);
asiz = tclmax(asiz, TCXSTRUNIT);
TCXSTR *xstr;
TCMALLOC(xstr, sizeof(*xstr));
TCMALLOC(xstr->ptr, asiz);
xstr->size = 0;
xstr->asize = asiz;
xstr->ptr[0] = '\0';
return xstr;
}
/* Copy an extensible string object. */
TCXSTR *tcxstrdup(const TCXSTR *xstr){
assert(xstr);
TCXSTR *nxstr;
TCMALLOC(nxstr, sizeof(*nxstr));
int asize = tclmax(xstr->size + 1, TCXSTRUNIT);
TCMALLOC(nxstr->ptr, asize);
nxstr->size = xstr->size;
nxstr->asize = asize;
memcpy(nxstr->ptr, xstr->ptr, xstr->size + 1);
return nxstr;
}
/* Delete an extensible string object. */
void tcxstrdel(TCXSTR *xstr){
assert(xstr);
TCFREE(xstr->ptr);
TCFREE(xstr);
}
/* Concatenate a region to the end of an extensible string object. */
void tcxstrcat(TCXSTR *xstr, const void *ptr, int size){
assert(xstr && ptr && size >= 0);
int nsize = xstr->size + size + 1;
if(xstr->asize < nsize){
while(xstr->asize < nsize){
xstr->asize *= 2;
if(xstr->asize < nsize) xstr->asize = nsize;
}
TCREALLOC(xstr->ptr, xstr->ptr, xstr->asize);
}
memcpy(xstr->ptr + xstr->size, ptr, size);
xstr->size += size;
xstr->ptr[xstr->size] = '\0';
}
/* Concatenate a character string to the end of an extensible string object. */
void tcxstrcat2(TCXSTR *xstr, const char *str){
assert(xstr && str);
int size = strlen(str);
int nsize = xstr->size + size + 1;
if(xstr->asize < nsize){
while(xstr->asize < nsize){
xstr->asize *= 2;
if(xstr->asize < nsize) xstr->asize = nsize;
}
TCREALLOC(xstr->ptr, xstr->ptr, xstr->asize);
}
memcpy(xstr->ptr + xstr->size, str, size + 1);
xstr->size += size;
}
/* Get the pointer of the region of an extensible string object. */
const void *tcxstrptr(const TCXSTR *xstr){
assert(xstr);
return xstr->ptr;
}
/* Get the size of the region of an extensible string object. */
int tcxstrsize(const TCXSTR *xstr){
assert(xstr);
return xstr->size;
}
/* Clear an extensible string object. */
void tcxstrclear(TCXSTR *xstr){
assert(xstr);
xstr->size = 0;
xstr->ptr[0] = '\0';
}
/* Perform formatted output into an extensible string object. */
void tcxstrprintf(TCXSTR *xstr, const char *format, ...){
assert(xstr && format);
va_list ap;
va_start(ap, format);
tcvxstrprintf(xstr, format, ap);
va_end(ap);
}
/* Allocate a formatted string on memory. */
char *tcsprintf(const char *format, ...){
assert(format);
TCXSTR *xstr = tcxstrnew();
va_list ap;
va_start(ap, format);
tcvxstrprintf(xstr, format, ap);
va_end(ap);
return tcxstrtomalloc(xstr);
}
/* Perform formatted output into an extensible string object. */
static void tcvxstrprintf(TCXSTR *xstr, const char *format, va_list ap){
assert(xstr && format);
while(*format != '\0'){
if(*format == '%'){
char cbuf[TCNUMBUFSIZ];
cbuf[0] = '%';
int cblen = 1;
int lnum = 0;
format++;
while(strchr("0123456789 .+-hlLz", *format) && *format != '\0' &&
cblen < TCNUMBUFSIZ - 1){
if(*format == 'l' || *format == 'L') lnum++;
cbuf[cblen++] = *(format++);
}
cbuf[cblen++] = *format;
cbuf[cblen] = '\0';
int tlen;
char *tmp, tbuf[TCNUMBUFSIZ*4];
switch(*format){
case 's':
tmp = va_arg(ap, char *);
if(!tmp) tmp = "(null)";
tcxstrcat2(xstr, tmp);
break;
case 'd':
if(lnum >= 2){
tlen = sprintf(tbuf, cbuf, va_arg(ap, long long));
} else if(lnum >= 1){
tlen = sprintf(tbuf, cbuf, va_arg(ap, long));
} else {
tlen = sprintf(tbuf, cbuf, va_arg(ap, int));
}
TCXSTRCAT(xstr, tbuf, tlen);
break;
case 'o': case 'u': case 'x': case 'X': case 'c':
if(lnum >= 2){
tlen = sprintf(tbuf, cbuf, va_arg(ap, unsigned long long));
} else if(lnum >= 1){
tlen = sprintf(tbuf, cbuf, va_arg(ap, unsigned long));
} else {
tlen = sprintf(tbuf, cbuf, va_arg(ap, unsigned int));
}
TCXSTRCAT(xstr, tbuf, tlen);
break;
case 'e': case 'E': case 'f': case 'g': case 'G':
if(lnum >= 1){
tlen = snprintf(tbuf, sizeof(tbuf), cbuf, va_arg(ap, long double));
} else {
tlen = snprintf(tbuf, sizeof(tbuf), cbuf, va_arg(ap, double));
}
if(tlen < 0 || tlen > sizeof(tbuf)){
tbuf[sizeof(tbuf)-1] = '*';
tlen = sizeof(tbuf);
}
TCXSTRCAT(xstr, tbuf, tlen);
break;
case '@':
tmp = va_arg(ap, char *);
if(!tmp) tmp = "(null)";
while(*tmp){
switch(*tmp){
case '&': TCXSTRCAT(xstr, "&amp;", 5); break;
case '<': TCXSTRCAT(xstr, "&lt;", 4); break;
case '>': TCXSTRCAT(xstr, "&gt;", 4); break;
case '"': TCXSTRCAT(xstr, "&quot;", 6); break;
default:
if(!((*tmp >= 0 && *tmp <= 0x8) || (*tmp >= 0x0e && *tmp <= 0x1f)))
TCXSTRCAT(xstr, tmp, 1);
break;
}
tmp++;
}
break;
case '?':
tmp = va_arg(ap, char *);
if(!tmp) tmp = "(null)";
while(*tmp){
unsigned char c = *(unsigned char *)tmp;
if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
(c >= '0' && c <= '9') || (c != '\0' && strchr("_-.", c))){
TCXSTRCAT(xstr, tmp, 1);
} else {
tlen = sprintf(tbuf, "%%%02X", c);
TCXSTRCAT(xstr, tbuf, tlen);
}
tmp++;
}
break;
case 'b':
if(lnum >= 2){
tlen = tcnumtostrbin(va_arg(ap, unsigned long long), tbuf,
tcatoi(cbuf + 1), (cbuf[1] == '0') ? '0' : ' ');
} else if(lnum >= 1){
tlen = tcnumtostrbin(va_arg(ap, unsigned long), tbuf,
tcatoi(cbuf + 1), (cbuf[1] == '0') ? '0' : ' ');
} else {
tlen = tcnumtostrbin(va_arg(ap, unsigned int), tbuf,
tcatoi(cbuf + 1), (cbuf[1] == '0') ? '0' : ' ');
}
TCXSTRCAT(xstr, tbuf, tlen);
break;
case '%':
TCXSTRCAT(xstr, "%", 1);
break;
}
} else {
TCXSTRCAT(xstr, format, 1);
}
format++;
}
}
/*************************************************************************************************
* extensible string (for experts)
*************************************************************************************************/
/* Convert an extensible string object into a usual allocated region. */
void *tcxstrtomalloc(TCXSTR *xstr){
assert(xstr);
char *ptr;
ptr = xstr->ptr;
TCFREE(xstr);
return ptr;
}
/* Create an extensible string object from an allocated region. */
TCXSTR *tcxstrfrommalloc(void *ptr, int size){
TCXSTR *xstr;
TCMALLOC(xstr, sizeof(*xstr));
TCREALLOC(xstr->ptr, ptr, size + 1);
xstr->ptr[size] = '\0';
xstr->size = size;
xstr->asize = size;
return xstr;
}
/*************************************************************************************************
* array list
*************************************************************************************************/
#define TCLISTUNIT 64 // allocation unit number of a list handle
/* private function prototypes */
static int tclistelemcmp(const void *a, const void *b);
static int tclistelemcmpci(const void *a, const void *b);
/* Create a list object. */
TCLIST *tclistnew(void){
TCLIST *list;
TCMALLOC(list, sizeof(*list));
list->anum = TCLISTUNIT;
TCMALLOC(list->array, sizeof(list->array[0]) * list->anum);
list->start = 0;
list->num = 0;
return list;
}
/* Create a list object. */
TCLIST *tclistnew2(int anum){
TCLIST *list;
TCMALLOC(list, sizeof(*list));
if(anum < 1) anum = 1;
list->anum = anum;
TCMALLOC(list->array, sizeof(list->array[0]) * list->anum);
list->start = 0;
list->num = 0;
return list;
}
/* Create a list object with initial string elements. */
TCLIST *tclistnew3(const char *str, ...){
TCLIST *list = tclistnew();
if(str){
tclistpush2(list, str);
va_list ap;
va_start(ap, str);
const char *elem;
while((elem = va_arg(ap, char *)) != NULL){
tclistpush2(list, elem);
}
va_end(ap);
}
return list;
}
/* Copy a list object. */
TCLIST *tclistdup(const TCLIST *list){
assert(list);
int num = list->num;
if(num < 1) return tclistnew();
const TCLISTDATUM *array = list->array + list->start;
TCLIST *nlist;
TCMALLOC(nlist, sizeof(*nlist));
TCLISTDATUM *narray;
TCMALLOC(narray, sizeof(list->array[0]) * num);
for(int i = 0; i < num; i++){
int size = array[i].size;
TCMALLOC(narray[i].ptr, tclmax(size + 1, TCXSTRUNIT));
memcpy(narray[i].ptr, array[i].ptr, size + 1);
narray[i].size = array[i].size;
}
nlist->anum = num;
nlist->array = narray;
nlist->start = 0;
nlist->num = num;
return nlist;
}
/* Delete a list object. */
void tclistdel(TCLIST *list){
assert(list);
TCLISTDATUM *array = list->array;
int end = list->start + list->num;
for(int i = list->start; i < end; i++){
TCFREE(array[i].ptr);
}
TCFREE(list->array);
TCFREE(list);
}
/* Get the number of elements of a list object. */
int tclistnum(const TCLIST *list){
assert(list);
return list->num;
}
/* Get the pointer to the region of an element of a list object. */
const void *tclistval(const TCLIST *list, int index, int *sp){
assert(list && index >= 0 && sp);
if(index >= list->num) return NULL;
index += list->start;
*sp = list->array[index].size;
return list->array[index].ptr;
}
/* Get the string of an element of a list object. */
const char *tclistval2(const TCLIST *list, int index){
assert(list && index >= 0);
if(index >= list->num) return NULL;
index += list->start;
return list->array[index].ptr;
}
/* Add an element at the end of a list object. */
void tclistpush(TCLIST *list, const void *ptr, int size){
assert(list && ptr && size >= 0);
int index = list->start + list->num;
if(index >= list->anum){
list->anum += list->num + 1;
TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
}
TCLISTDATUM *array = list->array;
TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
memcpy(array[index].ptr, ptr, size);
array[index].ptr[size] = '\0';
array[index].size = size;
list->num++;
}
/* Add a string element at the end of a list object. */
void tclistpush2(TCLIST *list, const char *str){
assert(list && str);
int index = list->start + list->num;
if(index >= list->anum){
list->anum += list->num + 1;
TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
}
int size = strlen(str);
TCLISTDATUM *array = list->array;
TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
memcpy(array[index].ptr, str, size + 1);
array[index].size = size;
list->num++;
}
/* Remove an element of the end of a list object. */
void *tclistpop(TCLIST *list, int *sp){
assert(list && sp);
if(list->num < 1) return NULL;
int index = list->start + list->num - 1;
list->num--;
*sp = list->array[index].size;
return list->array[index].ptr;
}
/* Remove a string element of the end of a list object. */
char *tclistpop2(TCLIST *list){
assert(list);
if(list->num < 1) return NULL;
int index = list->start + list->num - 1;
list->num--;
return list->array[index].ptr;
}
/* Add an element at the top of a list object. */
void tclistunshift(TCLIST *list, const void *ptr, int size){
assert(list && ptr && size >= 0);
if(list->start < 1){
if(list->start + list->num >= list->anum){
list->anum += list->num + 1;
TCREALLOC(list->array, 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]));
}
int index = list->start - 1;
TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
memcpy(list->array[index].ptr, ptr, size);
list->array[index].ptr[size] = '\0';
list->array[index].size = size;
list->start--;
list->num++;
}
/* Add a string element at the top of a list object. */
void tclistunshift2(TCLIST *list, const char *str){
assert(list && str);
if(list->start < 1){
if(list->start + list->num >= list->anum){
list->anum += list->num + 1;
TCREALLOC(list->array, 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]));
}
int index = list->start - 1;
int size = strlen(str);
TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
memcpy(list->array[index].ptr, str, size + 1);
list->array[index].size = size;
list->start--;
list->num++;
}
/* Remove an element of the top of a list object. */
void *tclistshift(TCLIST *list, int *sp){
assert(list && sp);
if(list->num < 1) return NULL;
int index = list->start;
list->start++;
list->num--;
*sp = list->array[index].size;
void *rv = list->array[index].ptr;
if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
list->start = 0;
}
return rv;
}
/* Remove a string element of the top of a list object. */
char *tclistshift2(TCLIST *list){
assert(list);
if(list->num < 1) return NULL;
int index = list->start;
list->start++;
list->num--;
void *rv = list->array[index].ptr;
if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
list->start = 0;
}
return rv;
}
/* Add an element at the specified location of a list object. */
void tclistinsert(TCLIST *list, int index, const void *ptr, int size){
assert(list && index >= 0 && ptr && size >= 0);
if(index > list->num) return;
index += list->start;
if(list->start + list->num >= list->anum){
list->anum += list->num + 1;
TCREALLOC(list->array, 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));
TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
memcpy(list->array[index].ptr, ptr, size);
list->array[index].ptr[size] = '\0';
list->array[index].size = size;
list->num++;
}
/* Add a string element at the specified location of a list object. */
void tclistinsert2(TCLIST *list, int index, const char *str){
assert(list && index >= 0 && str);
if(index > list->num) return;
index += list->start;
if(list->start + list->num >= list->anum){
list->anum += list->num + 1;
TCREALLOC(list->array, 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));
int size = strlen(str);
TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
memcpy(list->array[index].ptr, str, size);
list->array[index].ptr[size] = '\0';
list->array[index].size = size;
list->num++;
}
/* Remove an element at the specified location of a list object. */
void *tclistremove(TCLIST *list, int index, int *sp){
assert(list && index >= 0 && sp);
if(index >= list->num) return NULL;
index += list->start;
void *rv = list->array[index].ptr;
*sp = list->array[index].size;
list->num--;
memmove(list->array + index, list->array + index + 1,
sizeof(list->array[0]) * (list->start + list->num - index));
return rv;
}
/* Remove a string element at the specified location of a list object. */
char *tclistremove2(TCLIST *list, int index){
assert(list && index >= 0);
if(index >= list->num) return NULL;
index += list->start;
void *rv = list->array[index].ptr;
list->num--;
memmove(list->array + index, list->array + index + 1,
sizeof(list->array[0]) * (list->start + list->num - index));
return rv;
}
/* Overwrite an element at the specified location of a list object. */
void tclistover(TCLIST *list, int index, const void *ptr, int size){
assert(list && index >= 0 && ptr && size >= 0);
if(index >= list->num) return;
index += list->start;
if(size > list->array[index].size)
TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
memcpy(list->array[index].ptr, ptr, size);
list->array[index].size = size;
list->array[index].ptr[size] = '\0';
}
/* Overwrite a string element at the specified location of a list object. */
void tclistover2(TCLIST *list, int index, const char *str){
assert(list && index >= 0 && str);
if(index >= list->num) return;
index += list->start;
int size = strlen(str);
if(size > list->array[index].size)
TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
memcpy(list->array[index].ptr, str, size + 1);
list->array[index].size = size;
}
/* Sort elements of a list object in lexical order. */
void tclistsort(TCLIST *list){
assert(list);
qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmp);
}
/* Search a list object for an element using liner search. */
int tclistlsearch(const TCLIST *list, const void *ptr, int size){
assert(list && ptr && size >= 0);
int end = list->start + list->num;
for(int i = list->start; i < end; i++){
if(list->array[i].size == size && !memcmp(list->array[i].ptr, ptr, size))
return i - list->start;
}
return -1;
}
/* Search a list object for an element using binary search. */
int tclistbsearch(const TCLIST *list, const void *ptr, int size){
assert(list && ptr && size >= 0);
TCLISTDATUM key;
key.ptr = (char *)ptr;
key.size = size;
TCLISTDATUM *res = bsearch(&key, list->array + list->start,
list->num, sizeof(list->array[0]), tclistelemcmp);
return res ? res - list->array - list->start : -1;
}
/* Clear a list object. */
void tclistclear(TCLIST *list){
assert(list);
TCLISTDATUM *array = list->array;
int end = list->start + list->num;
for(int i = list->start; i < end; i++){
TCFREE(array[i].ptr);
}
list->start = 0;
list->num = 0;
}
/* Serialize a list object into a byte array. */
void *tclistdump(const TCLIST *list, int *sp){
assert(list && sp);
const TCLISTDATUM *array = list->array;
int end = list->start + list->num;
int tsiz = 0;
for(int i = list->start; i < end; i++){
tsiz += array[i].size + sizeof(int);
}
char *buf;
TCMALLOC(buf, tsiz + 1);
char *wp = buf;
for(int i = list->start; i < end; i++){
int step;
TCSETVNUMBUF(step, wp, array[i].size);
wp += step;
memcpy(wp, array[i].ptr, array[i].size);
wp += array[i].size;
}
*sp = wp - buf;
return buf;
}
/* Create a list object from a serialized byte array. */
TCLIST *tclistload(const void *ptr, int size){
assert(ptr && size >= 0);
TCLIST *list;
TCMALLOC(list, sizeof(*list));
int anum = size / sizeof(int) + 1;
TCLISTDATUM *array;
TCMALLOC(array, sizeof(array[0]) * anum);
int num = 0;
const char *rp = ptr;
const char *ep = (char *)ptr + size;
while(rp < ep){
int step, vsiz;
TCREADVNUMBUF(rp, vsiz, step);
rp += step;
if(num >= anum){
anum *= 2;
TCREALLOC(array, array, anum * sizeof(array[0]));
}
TCMALLOC(array[num].ptr, tclmax(vsiz + 1, TCXSTRUNIT));
memcpy(array[num].ptr, rp, vsiz);
array[num].ptr[vsiz] = '\0';
array[num].size = vsiz;
num++;
rp += vsiz;
}
list->anum = anum;
list->array = array;
list->start = 0;
list->num = num;
return list;
}
/* Compare two list elements in lexical order.
`a' specifies the pointer to one element.
`b' specifies the pointer to the other element.
The return value is positive if the former is big, negative if the latter is big, 0 if both
are equivalent. */
static int tclistelemcmp(const void *a, const void *b){
assert(a && b);
unsigned char *ao = (unsigned char *)((TCLISTDATUM *)a)->ptr;
unsigned char *bo = (unsigned char *)((TCLISTDATUM *)b)->ptr;
int size = (((TCLISTDATUM *)a)->size < ((TCLISTDATUM *)b)->size) ?
((TCLISTDATUM *)a)->size : ((TCLISTDATUM *)b)->size;
for(int i = 0; i < size; i++){
if(ao[i] > bo[i]) return 1;
if(ao[i] < bo[i]) return -1;
}
return ((TCLISTDATUM *)a)->size - ((TCLISTDATUM *)b)->size;
}
/* Compare two list elements in case-insensitive lexical order..
`a' specifies the pointer to one element.
`b' specifies the pointer to the other element.
The return value is positive if the former is big, negative if the latter is big, 0 if both
are equivalent. */
static int tclistelemcmpci(const void *a, const void *b){
assert(a && b);
TCLISTDATUM *ap = (TCLISTDATUM *)a;
TCLISTDATUM *bp = (TCLISTDATUM *)b;
unsigned char *ao = (unsigned char *)ap->ptr;
unsigned char *bo = (unsigned char *)bp->ptr;
int size = (ap->size < bp->size) ? ap->size : bp->size;
for(int i = 0; i < size; i++){
int ac = ao[i];
bool ab = false;
if(ac >= 'A' && ac <= 'Z'){
ac += 'a' - 'A';
ab = true;
}
int bc = bo[i];
bool bb = false;
if(bc >= 'A' && bc <= 'Z'){
bc += 'a' - 'A';
bb = true;
}
if(ac > bc) return 1;
if(ac < bc) return -1;
if(!ab && bb) return 1;
if(ab && !bb) return -1;
}
return ap->size - bp->size;
}
/*************************************************************************************************
* array list (for experts)
*************************************************************************************************/
/* Add an allocated element at the end of a list object. */
void tclistpushmalloc(TCLIST *list, void *ptr, int size){
assert(list && ptr && size >= 0);
int index = list->start + list->num;
if(index >= list->anum){
list->anum += list->num + 1;
TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
}
TCLISTDATUM *array = list->array;
TCREALLOC(array[index].ptr, ptr, size + 1);
array[index].ptr[size] = '\0';
array[index].size = size;
list->num++;
}
/* Sort elements of a list object in case-insensitive lexical order. */
void tclistsortci(TCLIST *list){
assert(list);
qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmpci);
}
/* 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--;
}
}
/* Perform formatted output into a list object. */
void tclistprintf(TCLIST *list, const char *format, ...){
assert(list && format);
TCXSTR *xstr = tcxstrnew();
va_list ap;
va_start(ap, format);
tcvxstrprintf(xstr, format, ap);
va_end(ap);
int size = TCXSTRSIZE(xstr);
char *ptr = tcxstrtomalloc(xstr);
tclistpushmalloc(list, ptr, size);
}
/*************************************************************************************************
* 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){
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 {
*sp = rec->vsiz;
return dbuf + rksiz + TCALIGNPAD(rksiz);
}
}
}
return NULL;
}
/* Retrieve a string record in a map object. */
const char *tcmapget2(const TCMAP *map, const char *kstr){
assert(map && kstr);
int ksiz = strlen(kstr);
if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
uint32_t hash;
TCMAPHASH1(hash, kstr, ksiz);
TCMAPREC *rec = map->buckets[hash%map->bnum];
TCMAPHASH2(hash, kstr, 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(kstr, ksiz, dbuf, rksiz);
if(kcmp < 0){
rec = rec->left;
} else if(kcmp > 0){
rec = rec->right;
} else {
return dbuf + rksiz + TCALIGNPAD(rksiz);
}
}
}
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);
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(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 & TCMAPKMAXSIZ;
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 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 & TCMAPKMAXSIZ);
rec = rec->next;
}
return list;
}
/* 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);
uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
TCLISTPUSH(list, dbuf + rksiz + TCALIGNPAD(rksiz), rec->vsiz);
rec = rec->next;
}
return list;
}
/* 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);
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 {
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 | hash;
memcpy(dbuf + ksiz + psiz, &num, sizeof(num));
dbuf[ksiz+psiz+sizeof(num)] = '\0';
rec->vsiz = sizeof(num);
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);
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 {
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 | hash;
memcpy(dbuf + ksiz + psiz, &num, sizeof(num));
dbuf[ksiz+psiz+sizeof(num)] = '\0';
rec->vsiz = sizeof(num);
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 & TCMAPKMAXSIZ) + 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 & TCMAPKMAXSIZ;
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 = tcmapnew2(tclmin(size / 6 + 1, TCMAPDEFBNUM));
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;
}
/*************************************************************************************************
* hash map (for experts)
*************************************************************************************************/
/* Store a record and make it semivolatile in a map object. */
void tcmapput3(TCMAP *map, const void *kbuf, int ksiz, const char *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;
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);
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 void *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;
}
/* Retrieve a string record in a map object with specifying the default value string. */
const char *tcmapget4(TCMAP *map, const char *kstr, const char *dstr){
assert(map && kstr && dstr);
int vsiz;
const char *vbuf = tcmapget(map, kstr, strlen(kstr), &vsiz);
return vbuf ? vbuf : dstr;
}
/* Initialize the iterator of a map object at the record corresponding a key. */
void tcmapiterinit2(TCMAP *map, const void *kbuf, int ksiz){
assert(map && kbuf && ksiz >= 0);
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 {
map->cur = rec;
return;
}
}
}
}
/* Initialize the iterator of a map object at the record corresponding a key string. */
void tcmapiterinit3(TCMAP *map, const char *kstr){
assert(map && kstr);
tcmapiterinit2(map, kstr, strlen(kstr));
}
/* 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;
}
/* Perform formatted output into a map object. */
void tcmapprintf(TCMAP *map, const char *kstr, const char *format, ...){
assert(map && kstr && format);
TCXSTR *xstr = tcxstrnew();
va_list ap;
va_start(ap, format);
tcvxstrprintf(xstr, format, ap);
va_end(ap);
tcmapput(map, kstr, strlen(kstr), TCXSTRPTR(xstr), TCXSTRSIZE(xstr));
tcxstrdel(xstr);
}
/*************************************************************************************************
* 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 *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 {
tree->msiz += vsiz - top->vsiz;
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));
}
/* Store a record into a tree object with a duplication handler. */
bool tctreeputproc(TCTREE *tree, const void *kbuf, int ksiz, const void *vbuf, int vsiz,
TCPDPROC proc, void *op){
assert(tree && kbuf && ksiz >= 0 && proc);
TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
if(!top){
if(!vbuf) return false;
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){
if(!vbuf){
tree->root = top;
return false;
}
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){
if(!vbuf){
tree->root = top;
return false;
}
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);
int nvsiz;
char *nvbuf = proc(dbuf + ksiz + psiz, top->vsiz, &nvsiz, op);
if(nvbuf == (void *)-1){
tree->rnum--;
tree->msiz -= top->ksiz + top->vsiz;
if(tree->cur == top){
TCTREEREC *rec = top->right;
if(rec){
while(rec->left){
rec = rec->left;
}
}
tree->cur = rec;
}
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;
}
if(!nvbuf){
tree->root = top;
return false;
}
tree->msiz += nvsiz - top->vsiz;
if(nvsiz > top->vsiz){
TCTREEREC *old = top;
TCREALLOC(top, top, sizeof(*top) + ksiz + psiz + nvsiz + 1);
if(top != old){
if(tree->cur == old) tree->cur = top;
dbuf = (char *)top + sizeof(*top);
}
}
memcpy(dbuf + ksiz + psiz, nvbuf, nvsiz);
dbuf[ksiz+psiz+nvsiz] = '\0';
top->vsiz = nvsiz;
TCFREE(nvbuf);
tree->root = top;
}
return true;
}
/* 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;
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(tree->cur == top){
TCTREEREC *rec = top->right;
if(rec){
while(rec->left){
rec = rec->left;
}
}
tree->cur = rec;
}
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);
}
/* 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;
}
/* 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(TCTREE *tree){
assert(tree);
int ksiz;
return tctreeiternext(tree, &ksiz);
}
/* Get the number of records stored in a tree object. */
uint64_t tctreernum(const TCTREE *tree){
assert(tree);
return tree->rnum;
}
/* Get the total size of memory used in a tree object. */
uint64_t tctreemsiz(const TCTREE *tree){
assert(tree);
return tree->msiz + tree->rnum * (sizeof(*tree->root) + sizeof(void *));
}
/* Create a list object containing all keys in a tree object. */
TCLIST *tctreekeys(const TCTREE *tree){
assert(tree);
TCLIST *list = tclistnew2(tree->rnum);
if(tree->root){
TCTREEREC **history;
TCMALLOC(history, sizeof(*history) * tree->rnum);
TCTREEREC **result;
TCMALLOC(result, sizeof(*history) * tree->rnum);
int hnum = 0;
history[hnum++] = tree->root;
while(hnum > 0){
TCTREEREC *rec = history[--hnum];
if(!rec){
rec = result[hnum];
char *dbuf = (char *)rec + sizeof(*rec);
TCLISTPUSH(list, dbuf, rec->ksiz);
continue;
}
if(rec->right) history[hnum++] = rec->right;
history[hnum] = NULL;
result[hnum] = rec;
hnum++;
if(rec->left) history[hnum++] = rec->left;
}
TCFREE(result);
TCFREE(history);
}
return list;
}
/* Create a list object containing all values in a tree object. */
TCLIST *tctreevals(const TCTREE *tree){
assert(tree);
TCLIST *list = tclistnew2(tree->rnum);
if(tree->root){
TCTREEREC **history;
TCMALLOC(history, sizeof(*history) * tree->rnum);
TCTREEREC **result;
TCMALLOC(result, sizeof(*history) * tree->rnum);
int hnum = 0;
history[hnum++] = tree->root;
while(hnum > 0){
TCTREEREC *rec = history[--hnum];
if(!rec){
rec = result[hnum];
char *dbuf = (char *)rec + sizeof(*rec);
TCLISTPUSH(list, dbuf + rec->ksiz + TCALIGNPAD(rec->ksiz), rec->vsiz);
continue;
}
if(rec->right) history[hnum++] = rec->right;
history[hnum] = NULL;
result[hnum] = rec;
hnum++;
if(rec->left) history[hnum++] = rec->left;
}
TCFREE(result);
TCFREE(history);
}
return list;
}
/* Add an integer to a record in a tree object. */
int tctreeaddint(TCTREE *tree, const void *kbuf, int ksiz, int num){
assert(tree && kbuf && ksiz >= 0);
TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
if(!top){
int psiz = TCALIGNPAD(ksiz);
TCTREEREC *rec;
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->left = NULL;
rec->right = NULL;
tree->root = rec;
tree->rnum = 1;
tree->msiz = ksiz + sizeof(num);
return num;
}
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 + sizeof(num) + 1);
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->left = top->left;
rec->right = top;
top->left = NULL;
tree->rnum++;
tree->msiz += ksiz + sizeof(num);
tree->root = rec;
} else if(cv > 0){
int psiz = TCALIGNPAD(ksiz);
TCTREEREC *rec;
TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + sizeof(num) + 1);
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->left = top;
rec->right = top->right;
top->right = NULL;
tree->rnum++;
tree->msiz += ksiz + sizeof(num);
tree->root = rec;
} else {
tree->root = top;
if(top->vsiz != sizeof(num)) return INT_MIN;
int *resp = (int *)(dbuf + ksiz + TCALIGNPAD(ksiz));
return *resp += num;
}
return num;
}
/* Add a real number to a record in a tree object. */
double tctreeadddouble(TCTREE *tree, const void *kbuf, int ksiz, double num){
assert(tree && kbuf && ksiz >= 0);
TCTREEREC *top = tctreesplay(tree, kbuf, ksiz);
if(!top){
int psiz = TCALIGNPAD(ksiz);
TCTREEREC *rec;
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->left = NULL;
rec->right = NULL;
tree->root = rec;
tree->rnum = 1;
tree->msiz = ksiz + sizeof(num);
return num;
}
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 + sizeof(num) + 1);
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->left = top->left;
rec->right = top;
top->left = NULL;
tree->rnum++;
tree->msiz += ksiz + sizeof(num);
tree->root = rec;
} else if(cv > 0){
int psiz = TCALIGNPAD(ksiz);
TCTREEREC *rec;
TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + sizeof(num) + 1);
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->left = top;
rec->right = top->right;
top->right = NULL;
tree->rnum++;
tree->msiz += ksiz + sizeof(num);
tree->root = rec;
} else {
tree->root = top;
if(top->vsiz != sizeof(num)) return nan("");
double *resp = (double *)(dbuf + ksiz + TCALIGNPAD(ksiz));
return *resp += num;
}
return num;
}
/* Clear a tree object. */
void tctreeclear(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);
}
tree->root = NULL;
tree->cur = NULL;
tree->rnum = 0;
tree->msiz = 0;
}
/* Remove fringe records of a tree object. */
void tctreecutfringe(TCTREE *tree, int num){
assert(tree && num >= 0);
if(!tree->root || num < 1) return;
TCTREEREC **history;
TCMALLOC(history, sizeof(*history) * tree->rnum);
int hnum = 0;
history[hnum++] = tree->root;
for(int i = 0; i < hnum; i++){
TCTREEREC *rec = history[i];
if(rec->left) history[hnum++] = rec->left;
if(rec->right) history[hnum++] = rec->right;
}
TCTREEREC *cur = NULL;
for(int i = hnum - 1; i >= 0; i--){
TCTREEREC *rec = history[i];
if(rec->left){
TCTREEREC *child = rec->left;
tree->rnum--;
tree->msiz -= child->ksiz + child->vsiz;
rec->left = NULL;
if(tree->cur == child){
tree->cur = NULL;
cur = child;
} else {
TCFREE(child);
}
if(--num < 1) break;
}
if(rec->right){
TCTREEREC *child = rec->right;
tree->rnum--;
tree->msiz -= child->ksiz + child->vsiz;
rec->right = NULL;
if(tree->cur == child){
tree->cur = NULL;
cur = child;
} else {
TCFREE(child);
}
if(--num < 1) break;
}
}
if(num > 0){
TCFREE(tree->root);
tree->root = NULL;
tree->cur = NULL;
tree->rnum = 0;
tree->msiz = 0;
}
if(cur){
char *dbuf = (char *)cur + sizeof(*cur);
tctreeiterinit2(tree, dbuf, cur->ksiz);
TCFREE(cur);
}
TCFREE(history);
}
/* Serialize a tree object into a byte array. */
void *tctreedump(const TCTREE *tree, int *sp){
assert(tree && sp);
int tsiz = 0;
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;
tsiz += rec->ksiz + rec->vsiz + sizeof(int) * 2;
}
if(history != histbuf) TCFREE(history);
}
char *buf;
TCMALLOC(buf, tsiz + 1);
char *wp = buf;
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;
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;
}
if(history != histbuf) TCFREE(history);
}
*sp = wp - buf;
return buf;
}
/* Create a tree object from a serialized byte array. */
TCTREE *tctreeload(const void *ptr, int size, TCCMP cmp, void *cmpop){
assert(ptr && size >= 0 && cmp);
TCTREE *tree = tctreenew2(cmp, cmpop);
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;
tctreeputkeep(tree, kbuf, ksiz, rp, vsiz);
rp += vsiz;
}
return tree;
}
/* Perform the splay operation of a tree object.
`tree' specifies the tree object.
`kbuf' specifies the pointer to the region of the key.
`ksiz' specifies the size of the region of the key.
The return value is the pointer to the record corresponding the key. */
static TCTREEREC* tctreesplay(TCTREE *tree, const void *kbuf, int ksiz){
assert(tree && kbuf && ksiz >= 0);
TCTREEREC *top = tree->root;
if(!top) return NULL;
TCCMP cmp = tree->cmp;
void *cmpop = tree->cmpop;
TCTREEREC ent;
ent.left = NULL;
ent.right = NULL;
TCTREEREC *lrec = &ent;
TCTREEREC *rrec = &ent;
while(true){
char *dbuf = (char *)top + sizeof(*top);
int cv = cmp(kbuf, ksiz, dbuf, top->ksiz, cmpop);
if(cv < 0){
if(!top->left) break;
dbuf = (char *)top->left + sizeof(*top);
cv = cmp(kbuf, ksiz, dbuf, top->left->ksiz, cmpop);
if(cv < 0){
TCTREEREC *swap = top->left;
top->left = swap->right;
swap->right = top;
top = swap;
if(!top->left) break;
}
rrec->left = top;
rrec = top;
top = top->left;
} else if(cv > 0){
if(!top->right) break;
dbuf = (char *)top->right + sizeof(*top);
cv = cmp(kbuf, ksiz, dbuf, top->right->ksiz, cmpop);
if(cv > 0){
TCTREEREC *swap = top->right;
top->right = swap->left;
swap->left = top;
top = swap;
if(!top->right) break;
}
lrec->right = top;
lrec = top;
top = top->right;
} else {
break;
}
}
lrec->right = top->left;
rrec->left = top->right;
top->left = ent.right;
top->right = ent.left;
return top;
}
/*************************************************************************************************
* ordered tree (for experts)
*************************************************************************************************/
/* Store a record into a tree object without balancing nodes. */
void tctreeput3(TCTREE *tree, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
assert(tree && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
TCTREEREC *rec = tree->root;
TCTREEREC **entp = NULL;
while(rec){
char *dbuf = (char *)rec + sizeof(*rec);
int cv = tree->cmp(kbuf, ksiz, dbuf, rec->ksiz, tree->cmpop);
if(cv < 0){
entp = &(rec->left);
rec = rec->left;
} else if(cv > 0){
entp = &(rec->right);
rec = rec->right;
} else {
tree->msiz += vsiz - rec->vsiz;
int psiz = TCALIGNPAD(ksiz);
if(vsiz > rec->vsiz){
TCTREEREC *old = rec;
TCREALLOC(rec, rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
if(rec != old){
if(tree->root == old) tree->root = rec;
if(tree->cur == old) tree->cur = rec;
if(entp) *entp = 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);
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;
if(entp){
*entp = rec;
} else {
tree->root = rec;
}
tree->rnum++;
tree->msiz += ksiz + vsiz;
}
/* Store a new record into a map object without balancing nodes. */
bool tctreeputkeep3(TCTREE *tree, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
assert(tree && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
TCTREEREC *rec = tree->root;
TCTREEREC **entp = NULL;
while(rec){
char *dbuf = (char *)rec + sizeof(*rec);
int cv = tree->cmp(kbuf, ksiz, dbuf, rec->ksiz, tree->cmpop);
if(cv < 0){
entp = &(rec->left);
rec = rec->left;
} else if(cv > 0){
entp = &(rec->right);
rec = rec->right;
} else {
return false;
}
}
int psiz = TCALIGNPAD(ksiz);
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;
if(entp){
*entp = rec;
} else {
tree->root = rec;
}
tree->rnum++;
tree->msiz += ksiz + vsiz;
return true;
}
/* Concatenate a value at the existing record in a tree object without balancing nodes. */
void tctreeputcat3(TCTREE *tree, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
assert(tree && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
TCTREEREC *rec = tree->root;
TCTREEREC **entp = NULL;
while(rec){
char *dbuf = (char *)rec + sizeof(*rec);
int cv = tree->cmp(kbuf, ksiz, dbuf, rec->ksiz, tree->cmpop);
if(cv < 0){
entp = &(rec->left);
rec = rec->left;
} else if(cv > 0){
entp = &(rec->right);
rec = rec->right;
} else {
tree->msiz += vsiz;
int psiz = TCALIGNPAD(ksiz);
int asiz = sizeof(*rec) + ksiz + psiz + rec->vsiz + vsiz + 1;
int unit = (asiz <= TCTREECSUNIT) ? TCTREECSUNIT : TCTREECBUNIT;
asiz = (asiz - 1) + unit - (asiz - 1) % unit;
TCTREEREC *old = rec;
TCREALLOC(rec, rec, asiz);
if(rec != old){
if(tree->root == old) tree->root = rec;
if(tree->cur == old) tree->cur = rec;
if(entp) *entp = 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);
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;
if(entp){
*entp = rec;
} else {
tree->root = rec;
}
tree->rnum++;
tree->msiz += ksiz + 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;
}
/* Retrieve a string record in a tree object with specifying the default value string. */
const char *tctreeget4(TCTREE *tree, const char *kstr, const char *dstr){
assert(tree && kstr && dstr);
int vsiz;
const char *vbuf = tctreeget(tree, kstr, strlen(kstr), &vsiz);
return vbuf ? vbuf : dstr;
}
/* 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 value bound to the key fetched from the iterator of a tree object. */
const void *tctreeiterval(const void *kbuf, int *sp){
assert(kbuf && sp);
TCTREEREC *rec = (TCTREEREC *)((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 tree object. */
const char *tctreeiterval2(const char *kstr){
assert(kstr);
TCTREEREC *rec = (TCTREEREC *)(kstr - sizeof(*rec));
return kstr + rec->ksiz + TCALIGNPAD(rec->ksiz);
}
/* Create an array of strings of all keys in a tree object. */
const char **tctreekeys2(const TCTREE *tree, int *np){
assert(tree && np);
const char **ary;
TCMALLOC(ary, sizeof(*ary) * tree->rnum + 1);
int anum = 0;
if(tree->root){
TCTREEREC **history;
TCMALLOC(history, sizeof(*history) * tree->rnum);
TCTREEREC **result;
TCMALLOC(result, sizeof(*history) * tree->rnum);
int hnum = 0;
history[hnum++] = tree->root;
while(hnum > 0){
TCTREEREC *rec = history[--hnum];
if(!rec){
rec = result[hnum];
ary[(anum++)] = (char *)rec + sizeof(*rec);
continue;
}
if(rec->right) history[hnum++] = rec->right;
history[hnum] = NULL;
result[hnum] = rec;
hnum++;
if(rec->left) history[hnum++] = rec->left;
}
TCFREE(result);
TCFREE(history);
}
*np = anum;
return ary;
}
/* Create an array of strings of all values in a tree object. */
const char **tctreevals2(const TCTREE *tree, int *np){
assert(tree && np);
const char **ary;
TCMALLOC(ary, sizeof(*ary) * tree->rnum + 1);
int anum = 0;
if(tree->root){
TCTREEREC **history;
TCMALLOC(history, sizeof(*history) * tree->rnum);
TCTREEREC **result;
TCMALLOC(result, sizeof(*history) * tree->rnum);
int hnum = 0;
history[hnum++] = tree->root;
while(hnum > 0){
TCTREEREC *rec = history[--hnum];
if(!rec){
rec = result[hnum];
ary[(anum++)] = (char *)rec + sizeof(*rec);
continue;
}
if(rec->right) history[hnum++] = rec->right;
history[hnum] = NULL;
result[hnum] = rec;
hnum++;
if(rec->left) history[hnum++] = rec->left;
}
TCFREE(result);
TCFREE(history);
}
*np = anum;
return ary;
}
/* Extract a tree record from a serialized byte array. */
void *tctreeloadone(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;
}
/* Perform formatted output into a tree object. */
void tctreeprintf(TCTREE *tree, const char *kstr, const char *format, ...){
assert(tree && kstr && format);
TCXSTR *xstr = tcxstrnew();
va_list ap;
va_start(ap, format);
tcvxstrprintf(xstr, format, ap);
va_end(ap);
tctreeput(tree, kstr, strlen(kstr), TCXSTRPTR(xstr), TCXSTRSIZE(xstr));
tcxstrdel(xstr);
}
/*************************************************************************************************
* on-memory hash database
*************************************************************************************************/
#define TCMDBMNUM 8 // number of internal maps
#define TCMDBDEFBNUM 65536 // default bucket number
/* get the first hash value */
#define TCMDBHASH(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) = 0x20071123; _TC_ksiz--;){ \
(TC_res) = (TC_res) * 33 + *(_TC_p)--; \
} \
(TC_res) &= TCMDBMNUM - 1; \
} while(false)
/* Create an on-memory hash database object. */
TCMDB *tcmdbnew(void){
return tcmdbnew2(TCMDBDEFBNUM);
}
/* Create an on-memory hash database with specifying the number of the buckets. */
TCMDB *tcmdbnew2(uint32_t bnum){
TCMDB *mdb;
if(bnum < 1) bnum = TCMDBDEFBNUM;
bnum = bnum / TCMDBMNUM + 17;
TCMALLOC(mdb, sizeof(*mdb));
TCMALLOC(mdb->mmtxs, sizeof(pthread_rwlock_t) * TCMDBMNUM);
TCMALLOC(mdb->imtx, sizeof(pthread_mutex_t));
TCMALLOC(mdb->maps, sizeof(TCMAP *) * TCMDBMNUM);
if(pthread_mutex_init(mdb->imtx, NULL) != 0) tcmyfatal("mutex error");
for(int i = 0; i < TCMDBMNUM; i++){
if(pthread_rwlock_init((pthread_rwlock_t *)mdb->mmtxs + i, NULL) != 0)
tcmyfatal("rwlock error");
mdb->maps[i] = tcmapnew2(bnum);
}
mdb->iter = -1;
return mdb;
}
/* Delete an on-memory hash database object. */
void tcmdbdel(TCMDB *mdb){
assert(mdb);
for(int i = TCMDBMNUM - 1; i >= 0; i--){
tcmapdel(mdb->maps[i]);
pthread_rwlock_destroy((pthread_rwlock_t *)mdb->mmtxs + i);
}
pthread_mutex_destroy(mdb->imtx);
TCFREE(mdb->maps);
TCFREE(mdb->imtx);
TCFREE(mdb->mmtxs);
TCFREE(mdb);
}
/* Store a record into an on-memory hash database. */
void tcmdbput(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;
tcmapput(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
}
/* Store a string record into an on-memory hash database. */
void tcmdbput2(TCMDB *mdb, const char *kstr, const char *vstr){
assert(mdb && kstr && vstr);
tcmdbput(mdb, kstr, strlen(kstr), vstr, strlen(vstr));
}
/* Store a new record into an on-memory hash database. */
bool tcmdbputkeep(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return false;
bool rv = tcmapputkeep(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
return rv;
}
/* Store a new string record into an on-memory hash database. */
bool tcmdbputkeep2(TCMDB *mdb, const char *kstr, const char *vstr){
assert(mdb && kstr && vstr);
return tcmdbputkeep(mdb, kstr, strlen(kstr), vstr, strlen(vstr));
}
/* Concatenate a value at the end of the existing record in an on-memory hash database. */
void tcmdbputcat(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;
tcmapputcat(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
}
/* Concatenate a string at the end of the existing record in an on-memory hash database. */
void tcmdbputcat2(TCMDB *mdb, const char *kstr, const char *vstr){
assert(mdb && kstr && vstr);
tcmdbputcat(mdb, kstr, strlen(kstr), vstr, strlen(vstr));
}
/* Remove a record of an on-memory hash database. */
bool tcmdbout(TCMDB *mdb, const void *kbuf, int ksiz){
assert(mdb && kbuf && ksiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return false;
bool rv = tcmapout(mdb->maps[mi], kbuf, ksiz);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
return rv;
}
/* Remove a string record of an on-memory hash database. */
bool tcmdbout2(TCMDB *mdb, const char *kstr){
assert(mdb && kstr);
return tcmdbout(mdb, kstr, strlen(kstr));
}
/* Retrieve a record in an on-memory hash database. */
void *tcmdbget(TCMDB *mdb, const void *kbuf, int ksiz, int *sp){
assert(mdb && kbuf && ksiz >= 0 && sp);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return NULL;
int vsiz;
const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);
char *rv;
if(vbuf){
TCMEMDUP(rv, vbuf, vsiz);
*sp = vsiz;
} else {
rv = NULL;
}
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
return rv;
}
/* Retrieve a string record in an on-memory hash database. */
char *tcmdbget2(TCMDB *mdb, const char *kstr){
assert(mdb && kstr);
int vsiz;
return tcmdbget(mdb, kstr, strlen(kstr), &vsiz);
}
/* Get the size of the value of a record in an on-memory hash database object. */
int tcmdbvsiz(TCMDB *mdb, const void *kbuf, int ksiz){
assert(mdb && kbuf && ksiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return -1;
int vsiz;
const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);
if(!vbuf) vsiz = -1;
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
return vsiz;
}
/* Get the size of the value of a string record in an on-memory hash database object. */
int tcmdbvsiz2(TCMDB *mdb, const char *kstr){
assert(mdb && kstr);
return tcmdbvsiz(mdb, kstr, strlen(kstr));
}
/* Initialize the iterator of an on-memory hash database. */
void tcmdbiterinit(TCMDB *mdb){
assert(mdb);
if(pthread_mutex_lock(mdb->imtx) != 0) return;
for(int i = 0; i < TCMDBMNUM; i++){
tcmapiterinit(mdb->maps[i]);
}
mdb->iter = 0;
pthread_mutex_unlock(mdb->imtx);
}
/* Get the next key of the iterator of an on-memory hash database. */
void *tcmdbiternext(TCMDB *mdb, int *sp){
assert(mdb && sp);
if(pthread_mutex_lock(mdb->imtx) != 0) return NULL;
if(mdb->iter < 0 || mdb->iter >= TCMDBMNUM){
pthread_mutex_unlock(mdb->imtx);
return NULL;
}
int mi = mdb->iter;
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0){
pthread_mutex_unlock(mdb->imtx);
return NULL;
}
int ksiz;
const char *kbuf;
while(!(kbuf = tcmapiternext(mdb->maps[mi], &ksiz)) && mi < TCMDBMNUM - 1){
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
mi = ++mdb->iter;
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0){
pthread_mutex_unlock(mdb->imtx);
return NULL;
}
}
char *rv;
if(kbuf){
TCMEMDUP(rv, kbuf, ksiz);
*sp = ksiz;
} else {
rv = NULL;
}
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
pthread_mutex_unlock(mdb->imtx);
return rv;
}
/* Get the next key string of the iterator of an on-memory hash database. */
char *tcmdbiternext2(TCMDB *mdb){
assert(mdb);
int ksiz;
return tcmdbiternext(mdb, &ksiz);
}
/* Get forward matching keys in an on-memory hash database object. */
TCLIST *tcmdbfwmkeys(TCMDB *mdb, const void *pbuf, int psiz, int max){
assert(mdb && pbuf && psiz >= 0);
TCLIST* keys = tclistnew();
if(pthread_mutex_lock(mdb->imtx) != 0) return keys;
if(max < 0) max = INT_MAX;
for(int i = 0; i < TCMDBMNUM && TCLISTNUM(keys) < max; i++){
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + i) == 0){
TCMAP *map = mdb->maps[i];
TCMAPREC *cur = map->cur;
tcmapiterinit(map);
const char *kbuf;
int ksiz;
while(TCLISTNUM(keys) < max && (kbuf = tcmapiternext(map, &ksiz)) != NULL){
if(ksiz >= psiz && !memcmp(kbuf, pbuf, psiz)) TCLISTPUSH(keys, kbuf, ksiz);
}
map->cur = cur;
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + i);
}
}
pthread_mutex_unlock(mdb->imtx);
return keys;
}
/* Get forward matching string keys in an on-memory hash database object. */
TCLIST *tcmdbfwmkeys2(TCMDB *mdb, const char *pstr, int max){
assert(mdb && pstr);
return tcmdbfwmkeys(mdb, pstr, strlen(pstr), max);
}
/* Get the number of records stored in an on-memory hash database. */
uint64_t tcmdbrnum(TCMDB *mdb){
assert(mdb);
uint64_t rnum = 0;
for(int i = 0; i < TCMDBMNUM; i++){
rnum += tcmaprnum(mdb->maps[i]);
}
return rnum;
}
/* Get the total size of memory used in an on-memory hash database object. */
uint64_t tcmdbmsiz(TCMDB *mdb){
assert(mdb);
uint64_t msiz = 0;
for(int i = 0; i < TCMDBMNUM; i++){
msiz += tcmapmsiz(mdb->maps[i]);
}
return msiz;
}
/* Add an integer to a record in an on-memory hash database object. */
int tcmdbaddint(TCMDB *mdb, const void *kbuf, int ksiz, int num){
assert(mdb && kbuf && ksiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return INT_MIN;
int rv = tcmapaddint(mdb->maps[mi], kbuf, ksiz, num);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
return rv;
}
/* Add a real number to a record in an on-memory hash database object. */
double tcmdbadddouble(TCMDB *mdb, const void *kbuf, int ksiz, double num){
assert(mdb && kbuf && ksiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return nan("");
double rv = tcmapadddouble(mdb->maps[mi], kbuf, ksiz, num);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
return rv;
}
/* Clear an on-memory hash database object. */
void tcmdbvanish(TCMDB *mdb){
assert(mdb);
for(int i = 0; i < TCMDBMNUM; i++){
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + i) == 0){
tcmapclear(mdb->maps[i]);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + i);
}
}
}
/* Remove front records of a map object. */
void tcmdbcutfront(TCMDB *mdb, int num){
assert(mdb && num >= 0);
num = num / TCMDBMNUM + 1;
for(int i = 0; i < TCMDBMNUM; i++){
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + i) == 0){
tcmapcutfront(mdb->maps[i], num);
pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + i);
}
}
}
/*************************************************************************************************
* on-memory hash database (for experts)
*************************************************************************************************/
/* Store a record and make it semivolatile in an on-memory hash database object. */
void tcmdbput3(TCMDB *mdb, const void *kbuf, int ksiz, const char *vbuf, int vsiz){
assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
unsigned int mi;
TCMDBHASH(mi, kbuf, ksiz);
if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;
tcmapput3(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);