diff options
Diffstat (limited to 'qdbm/cabin.c')
| -rw-r--r-- | qdbm/cabin.c | 3529 |
1 files changed, 3529 insertions, 0 deletions
diff --git a/qdbm/cabin.c b/qdbm/cabin.c new file mode 100644 index 00000000..262cb3eb --- /dev/null +++ b/qdbm/cabin.c @@ -0,0 +1,3529 @@ +/************************************************************************************************* + * Implementation of Cabin + * Copyright (C) 2000-2007 Mikio Hirabayashi + * This file is part of QDBM, Quick Database Manager. + * QDBM 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. QDBM 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 QDBM; if + * not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + * 02111-1307 USA. + *************************************************************************************************/ + + +#define QDBM_INTERNAL 1 + +#include "cabin.h" +#include "myconf.h" + +#define CB_GCUNIT 64 /* allocation unit size of a buffer in gc */ +#define CB_SPBUFSIZ 32 /* size of a buffer for sprintf */ +#define CB_SPMAXWIDTH 128 /* max width of a column for sprintf */ +#define CB_MAPPBNUM 251 /* bucket size of a petit map handle */ +#define CB_MAPCSUNIT 52 /* small allocation unit size of map concatenation */ +#define CB_MAPCBUNIT 252 /* big allocation unit size of map concatenation */ +#define CB_MSGBUFSIZ 256 /* size of a buffer for log message */ +#define CB_IOBUFSIZ 8192 /* size of an I/O buffer */ +#define CB_FILEMODE 00644 /* permission of a creating file */ +#define CB_NUMBUFSIZ 32 /* size of a buffer for a number */ +#define CB_ENCBUFSIZ 32 /* size of a buffer for encoding name */ +#define CB_DATEBUFSIZ 64 /* size of a buffer for date expression */ +#define CB_VNUMBUFSIZ 8 /* size of a buffer for variable length number */ + +/* set a buffer for a variable length number */ +#define CB_SETVNUMBUF(CB_len, CB_buf, CB_num) \ + do { \ + int _CB_num; \ + _CB_num = (CB_num); \ + if(_CB_num == 0){ \ + ((signed char *)(CB_buf))[0] = 0; \ + (CB_len) = 1; \ + } else { \ + (CB_len) = 0; \ + while(_CB_num > 0){ \ + int _CB_rem = _CB_num & 0x7f; \ + _CB_num >>= 7; \ + if(_CB_num > 0){ \ + ((signed char *)(CB_buf))[(CB_len)] = -_CB_rem - 1; \ + } else { \ + ((signed char *)(CB_buf))[(CB_len)] = _CB_rem; \ + } \ + (CB_len)++; \ + } \ + } \ + } while(FALSE) + +/* read a variable length buffer */ +#define CB_READVNUMBUF(CB_buf, CB_size, CB_num, CB_step) \ + do { \ + int _CB_i, _CB_base; \ + CB_num = 0; \ + _CB_base = 1; \ + if((size) < 2){ \ + CB_num = ((signed char *)(CB_buf))[0]; \ + (CB_step) = 1; \ + } else { \ + for(_CB_i = 0; _CB_i < (size); _CB_i++){ \ + if(((signed char *)(CB_buf))[_CB_i] >= 0){ \ + CB_num += ((signed char *)(CB_buf))[_CB_i] * _CB_base; \ + break; \ + } \ + CB_num += _CB_base * (((signed char *)(CB_buf))[_CB_i] + 1) * -1; \ + _CB_base *= 128; \ + } \ + (CB_step) = _CB_i + 1; \ + } \ + } while(FALSE) + +/* get the first hash value */ +#define CB_FIRSTHASH(CB_res, CB_kbuf, CB_ksiz) \ + do { \ + const unsigned char *_CB_p; \ + int _CB_ksiz; \ + _CB_p = (const unsigned char *)(CB_kbuf); \ + _CB_ksiz = CB_ksiz; \ + for((CB_res) = 19780211; _CB_ksiz--;){ \ + (CB_res) = (CB_res) * 37 + *(_CB_p)++; \ + } \ + (CB_res) &= INT_MAX; \ + } while(FALSE) + +/* get the second hash value */ +#define CB_SECONDHASH(CB_res, CB_kbuf, CB_ksiz) \ + do { \ + const unsigned char *_CB_p; \ + int _CB_ksiz; \ + _CB_p = (const unsigned char *)(CB_kbuf) + CB_ksiz - 1; \ + _CB_ksiz = CB_ksiz; \ + for((CB_res) = 0x13579bdf; _CB_ksiz--;){ \ + (CB_res) = (CB_res) * 31 + *(_CB_p)--; \ + } \ + (CB_res) &= INT_MAX; \ + } while(FALSE) + + +/* private function prototypes */ +static void cbggchandler(void); +static void cbggckeeper(void *ptr, void (*func)(void *)); +static void cbqsortsub(char *bp, int nmemb, int size, char *pswap, char *vswap, + int(*compar)(const void *, const void *)); +static int cblistelemcmp(const void *a, const void *b); +static int cbkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz); + + + +/************************************************************************************************* + * public objects + *************************************************************************************************/ + + +/* Call back function for handling a fatal error. */ +void (*cbfatalfunc)(const char *message) = NULL; + + +/* Allocate a region on memory. */ +void *cbmalloc(size_t size){ + char *p; + assert(size > 0 && size < INT_MAX); + if(!(p = malloc(size))) cbmyfatal("out of memory"); + return p; +} + + +/* Re-allocate a region on memory. */ +void *cbrealloc(void *ptr, size_t size){ + char *p; + assert(size > 0); + if(!(p = realloc(ptr, size))) cbmyfatal("out of memory"); + return p; +} + + +/* Duplicate a region on memory. */ +char *cbmemdup(const char *ptr, int size){ + char *p; + assert(ptr); + if(size < 0) size = strlen(ptr); + CB_MALLOC(p, size + 1); + memcpy(p, ptr, size); + p[size] = '\0'; + return p; +} + + +/* Free a region on memory. */ +void cbfree(void *ptr){ + free(ptr); +} + + +/* Register the pointer or handle of an object to the global garbage collector. */ +void cbglobalgc(void *ptr, void (*func)(void *)){ + assert(ptr && func); + cbggckeeper(ptr, func); +} + + +/* Exercise the global garbage collector explicitly. */ +void cbggcsweep(void){ + cbggckeeper(NULL, NULL); +} + + +/* Check availability of allocation of the virtual memory. */ +int cbvmemavail(size_t size){ + assert(size >= 0); + return _qdbm_vmemavail(size); +} + + +/* Sort an array using insert sort. */ +void cbisort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){ + char *bp, *swap; + int i, j; + assert(base && nmemb >= 0 && size > 0 && compar); + bp = (char *)base; + CB_MALLOC(swap, size); + for(i = 1; i < nmemb; i++){ + if(compar(bp + (i - 1) * size, bp + i * size) > 0){ + memcpy(swap, bp + i * size, size); + for(j = i; j > 0; j--){ + if(compar(bp + (j - 1) * size, swap) < 0) break; + memcpy(bp + j * size, bp + (j - 1) * size, size); + } + memcpy(bp + j * size, swap, size); + } + } + free(swap); +} + + +/* Sort an array using shell sort. */ +void cbssort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){ + char *bp, *swap; + int step, bottom, i, j; + assert(base && nmemb >= 0 && size > 0 && compar); + bp = (char *)base; + CB_MALLOC(swap, size); + for(step = (nmemb - 1) / 3; step >= 0; step = (step - 1) / 3){ + if(step < 5) step = 1; + for(bottom = 0; bottom < step; bottom++){ + for(i = bottom + step; i < nmemb; i += step){ + if(compar(bp + (i - step) * size, bp + i * size) > 0){ + memcpy(swap, bp + i * size, size); + for(j = i; j > step - 1; j -= step){ + if(compar(bp + (j - step) * size, swap) < 0) break; + memcpy(bp + j * size, bp + (j - step) * size, size); + } + memcpy(bp + j * size, swap, size); + } + } + } + if(step < 2) break; + } + free(swap); +} + + +/* Sort an array using heap sort. */ +void cbhsort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){ + char *bp, *swap; + int top, bottom, mybot, i; + assert(base && nmemb >= 0 && size > 0 && compar); + bp = (char *)base; + nmemb--; + bottom = nmemb / 2 + 1; + top = nmemb; + CB_MALLOC(swap, size); + while(bottom > 0){ + bottom--; + mybot = bottom; + i = 2 * mybot; + while(i <= top) { + if(i < top && compar(bp + (i + 1) * size, bp + i * size) > 0) i++; + if(compar(bp + mybot * size, bp + i * size) >= 0) break; + memcpy(swap, bp + mybot * size, size); + memcpy(bp + mybot * size, bp + i * size, size); + memcpy(bp + i * size, swap, size); + mybot = i; + i = 2 * mybot; + } + } + while(top > 0){ + memcpy(swap, bp, size); + memcpy(bp, bp + top * size, size); + memcpy(bp + top * size, swap, size); + top--; + mybot = bottom; + i = 2 * mybot; + while(i <= top){ + if(i < top && compar(bp + (i + 1) * size, bp + i * size) > 0) i++; + if(compar(bp + mybot * size, bp + i * size) >= 0) break; + memcpy(swap, bp + mybot * size, size); + memcpy(bp + mybot * size, bp + i * size, size); + memcpy(bp + i * size, swap, size); + mybot = i; + i = 2 * mybot; + } + } + free(swap); +} + + +/* Sort an array using quick sort. */ +void cbqsort(void *base, int nmemb, int size, int(*compar)(const void *, const void *)){ + char *pswap, *vswap; + assert(base && nmemb >= 0 && size > 0 && compar); + CB_MALLOC(pswap, size); + CB_MALLOC(vswap, size); + cbqsortsub(base, nmemb, size, pswap, vswap, compar); + free(vswap); + free(pswap); +} + + +/* Compare two strings with case insensitive evaluation. */ +int cbstricmp(const char *astr, const char *bstr){ + int ac, bc; + assert(astr && bstr); + while(*astr != '\0'){ + if(*bstr == '\0') return 1; + ac = (*astr >= 'A' && *astr <= 'Z') ? *astr + ('a' - 'A') : *(unsigned char *)astr; + bc = (*bstr >= 'A' && *bstr <= 'Z') ? *bstr + ('a' - 'A') : *(unsigned char *)bstr; + if(ac != bc) return ac - bc; + astr++; + bstr++; + } + return *bstr == '\0' ? 0 : -1; +} + + +/* Check whether a string begins with a key. */ +int cbstrfwmatch(const char *str, const char *key){ + assert(str && key); + while(*key != '\0'){ + if(*str != *key || *str == '\0') return FALSE; + key++; + str++; + } + return TRUE; +} + + +/* Check whether a string begins with a key, with case insensitive evaluation. */ +int cbstrfwimatch(const char *str, const char *key){ + int sc, kc; + assert(str && key); + while(*key != '\0'){ + if(*str == '\0') return FALSE; + sc = *str; + if(sc >= 'A' && sc <= 'Z') sc += 'a' - 'A'; + kc = *key; + if(kc >= 'A' && kc <= 'Z') kc += 'a' - 'A'; + if(sc != kc) return FALSE; + key++; + str++; + } + return TRUE; +} + + +/* Check whether a string ends with a key. */ +int cbstrbwmatch(const char *str, const char *key){ + int slen, klen, i; + assert(str && key); + slen = strlen(str); + klen = strlen(key); + for(i = 1; i <= klen; i++){ + if(i > slen || str[slen-i] != key[klen-i]) return FALSE; + } + return TRUE; +} + + +/* Check whether a string ends with a key, with case insensitive evaluation. */ +int cbstrbwimatch(const char *str, const char *key){ + int slen, klen, i, sc, kc; + assert(str && key); + slen = strlen(str); + klen = strlen(key); + for(i = 1; i <= klen; i++){ + if(i > slen) return FALSE; + sc = str[slen-i]; + if(sc >= 'A' && sc <= 'Z') sc += 'a' - 'A'; + kc = key[klen-i]; + if(kc >= 'A' && kc <= 'Z') kc += 'a' - 'A'; + if(sc != kc) return FALSE; + } + return TRUE; +} + + +/* Locate a substring in a string using KMP method. */ +char *cbstrstrkmp(const char *haystack, const char *needle){ + int i, j, hlen, nlen; + signed char tbl[0x100]; + assert(haystack && needle); + nlen = strlen(needle); + if(nlen >= 0x100) return strstr(haystack, needle); + tbl[0] = -1; + i = 0; + j = -1; + while(i < nlen){ + while((j >= 0) && (needle[i] != needle[j])){ + j = tbl[j]; + } + i++; + j++; + tbl[i] = j; + } + hlen = strlen(haystack); + i = 0; + j = 0; + while(i < hlen && j < nlen){ + while((j >= 0) && (haystack[i] != needle[j])){ + j = tbl[j]; + } + i++; + j++; + } + if(j == nlen) return (char *)(haystack + i - nlen); + return NULL; +} + + +/* Locate a substring in a string using BM method. */ +char *cbstrstrbm(const char *haystack, const char *needle){ + const unsigned char *rp; + const char *ep; + unsigned char tbl[0x100]; + int i, j, nlen, len, idx; + assert(haystack && needle); + nlen = strlen(needle); + if(nlen < 3 || nlen >= 0x100) return strstr(haystack, needle); + for(i = 0; i < 0x100; i++){ + tbl[i] = nlen; + } + len = nlen; + rp = (const unsigned char *)needle; + while(len > 0){ + tbl[*rp++] = --len; + } + nlen--; + ep = haystack + strlen(haystack) - nlen; + while(haystack < ep){ + for(i = nlen; haystack[i] == needle[i]; i--){ + if(i == 0) return (char *)haystack; + } + idx = ((unsigned char *)haystack)[i]; + j = tbl[idx] - nlen + i; + haystack += j > 0 ? j : 2; + } + return NULL; +} + + +/* Convert the letters of a string to upper case. */ +char *cbstrtoupper(char *str){ + int i; + assert(str); + for(i = 0; str[i] != '\0'; i++){ + if(str[i] >= 'a' && str[i] <= 'z') str[i] -= 'a' - 'A'; + } + return str; +} + + +/* Convert the letters of a string to lower case. */ +char *cbstrtolower(char *str){ + int i; + assert(str); + for(i = 0; str[i] != '\0'; i++){ + if(str[i] >= 'A' && str[i] <= 'Z') str[i] += 'a' - 'A'; + } + return str; +} + + +/* Cut space characters at head or tail of a string. */ +char *cbstrtrim(char *str){ + char *wp; + int i, head; + assert(str); + wp = str; + head = TRUE; + for(i = 0; str[i] != '\0'; i++){ + if((str[i] >= 0x07 && str[i] <= 0x0d) || str[i] == 0x20){ + if(!head) *(wp++) = str[i]; + } else { + *(wp++) = str[i]; + head = FALSE; + } + } + *wp = '\0'; + while(wp > str && ((wp[-1] >= 0x07 && wp[-1] <= 0x0d) || wp[-1] == 0x20)){ + *(--wp) = '\0'; + } + return str; +} + + +/* Squeeze space characters in a string and trim it. */ +char *cbstrsqzspc(char *str){ + char *wp; + int i, spc; + assert(str); + wp = str; + spc = TRUE; + for(i = 0; str[i] != '\0'; i++){ + if(str[i] > 0 && str[i] <= ' '){ + if(!spc) *(wp++) = str[i]; + spc = TRUE; + } else { + *(wp++) = str[i]; + spc = FALSE; + } + } + *wp = '\0'; + for(wp--; wp >= str; wp--){ + if(*wp > 0 && *wp <= ' '){ + *wp = '\0'; + } else { + break; + } + } + return str; +} + + +/* Count the number of characters in a string of UTF-8. */ +int cbstrcountutf(const char *str){ + const unsigned char *rp; + int cnt; + assert(str); + rp = (unsigned char *)str; + cnt = 0; + while(*rp != '\0'){ + if((*rp & 0x80) == 0x00 || (*rp & 0xe0) == 0xc0 || + (*rp & 0xf0) == 0xe0 || (*rp & 0xf8) == 0xf0) cnt++; + rp++; + } + return cnt; +} + + +/* Cut a string of UTF-8 at the specified number of characters. */ +char *cbstrcututf(char *str, int num){ + unsigned char *wp; + int cnt; + assert(str && num >= 0); + wp = (unsigned char *)str; + cnt = 0; + while(*wp != '\0'){ + if((*wp & 0x80) == 0x00 || (*wp & 0xe0) == 0xc0 || + (*wp & 0xf0) == 0xe0 || (*wp & 0xf8) == 0xf0){ + cnt++; + if(cnt > num){ + *wp = '\0'; + break; + } + } + wp++; + } + return str; +} + + +/* Get a datum handle. */ +CBDATUM *cbdatumopen(const char *ptr, int size){ + CBDATUM *datum; + CB_MALLOC(datum, sizeof(*datum)); + CB_MALLOC(datum->dptr, CB_DATUMUNIT); + datum->dptr[0] = '\0'; + datum->dsize = 0; + datum->asize = CB_DATUMUNIT; + if(ptr) CB_DATUMCAT(datum, ptr, (size >= 0 ? size : strlen(ptr))); + return datum; +} + + +/* Copy a datum. */ +CBDATUM *cbdatumdup(const CBDATUM *datum){ + assert(datum); + return cbdatumopen(datum->dptr, datum->dsize); +} + + +/* Free a datum handle. */ +void cbdatumclose(CBDATUM *datum){ + assert(datum); + free(datum->dptr); + free(datum); +} + + +/* Concatenate a datum and a region. */ +void cbdatumcat(CBDATUM *datum, const char *ptr, int size){ + assert(datum && ptr); + if(size < 0) size = strlen(ptr); + if(datum->dsize + size >= datum->asize){ + datum->asize = datum->asize * 2 + size + 1; + CB_REALLOC(datum->dptr, datum->asize); + } + memcpy(datum->dptr + datum->dsize, ptr, size); + datum->dsize += size; + datum->dptr[datum->dsize] = '\0'; +} + + +/* Get the pointer of the region of a datum. */ +const char *cbdatumptr(const CBDATUM *datum){ + assert(datum); + return datum->dptr; +} + + +/* Get the size of the region of a datum. */ +int cbdatumsize(const CBDATUM *datum){ + assert(datum); + return datum->dsize; +} + + +/* Set the size of the region of a datum. */ +void cbdatumsetsize(CBDATUM *datum, int size){ + assert(datum && size >= 0); + if(size <= datum->dsize){ + datum->dsize = size; + datum->dptr[size] = '\0'; + } else { + if(size >= datum->asize){ + datum->asize = datum->asize * 2 + size + 1; + CB_REALLOC(datum->dptr, datum->asize); + } + memset(datum->dptr + datum->dsize, 0, (size - datum->dsize) + 1); + datum->dsize = size; + } +} + + +/* Perform formatted output into a datum. */ +void cbdatumprintf(CBDATUM *datum, const char *format, ...){ + va_list ap; + char *tmp, cbuf[CB_NUMBUFSIZ], tbuf[CB_NUMBUFSIZ*2]; + unsigned char c; + int cblen, tlen; + assert(datum && format); + va_start(ap, format); + while(*format != '\0'){ + if(*format == '%'){ + cbuf[0] = '%'; + cblen = 1; + format++; + while(strchr("0123456789 .+-", *format) && *format != '\0' && cblen < CB_NUMBUFSIZ - 1){ + cbuf[cblen++] = *format; + format++; + } + cbuf[cblen++] = *format; + cbuf[cblen] = '\0'; + switch(*format){ + case 's': + tmp = va_arg(ap, char *); + if(!tmp) tmp = "(null)"; + cbdatumcat(datum, tmp, -1); + break; + case 'd': + tlen = sprintf(tbuf, cbuf, va_arg(ap, int)); + cbdatumcat(datum, tbuf, tlen); + break; + case 'o': case 'u': case 'x': case 'X': case 'c': + tlen = sprintf(tbuf, cbuf, va_arg(ap, unsigned int)); + cbdatumcat(datum, tbuf, tlen); + break; + case 'e': case 'E': case 'f': case 'g': case 'G': + tlen = sprintf(tbuf, cbuf, va_arg(ap, double)); + cbdatumcat(datum, tbuf, tlen); + break; + case '@': + tmp = va_arg(ap, char *); + if(!tmp) tmp = "(null)"; + while(*tmp){ + switch(*tmp){ + case '&': cbdatumcat(datum, "&", 5); break; + case '<': cbdatumcat(datum, "<", 4); break; + case '>': cbdatumcat(datum, ">", 4); break; + case '"': cbdatumcat(datum, """, 6); break; + default: + if(!((*tmp >= 0 && *tmp <= 0x8) || (*tmp >= 0x0e && *tmp <= 0x1f))) + cbdatumcat(datum, tmp, 1); + break; + } + tmp++; + } + break; + case '?': + tmp = va_arg(ap, char *); + if(!tmp) tmp = "(null)"; + while(*tmp){ + c = *(unsigned char *)tmp; + if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || + (c >= '0' && c <= '9') || (c != '\0' && strchr("_-.", c))){ + cbdatumcat(datum, tmp, 1); + } else { + tlen = sprintf(tbuf, "%%%02X", c); + cbdatumcat(datum, tbuf, tlen); + } + tmp++; + } + break; + case ':': + tmp = va_arg(ap, char *); + if(!tmp) tmp = ""; + tmp = cbmimeencode(tmp, "UTF-8", TRUE); + cbdatumcat(datum, tmp, -1); + free(tmp); + break; + case '%': + cbdatumcat(datum, "%", 1); + break; + } + } else { + cbdatumcat(datum, format, 1); + } + format++; + } + va_end(ap); +} + + +/* Convert a datum to an allocated region. */ +char *cbdatumtomalloc(CBDATUM *datum, int *sp){ + char *ptr; + assert(datum); + ptr = datum->dptr; + if(sp) *sp = datum->dsize; + free(datum); + return ptr; +} + + +/* Get a list handle. */ +CBLIST *cblistopen(void){ + CBLIST *list; + CB_MALLOC(list, sizeof(*list)); + list->anum = CB_LISTUNIT; + CB_MALLOC(list->array, sizeof(list->array[0]) * list->anum); + list->start = 0; + list->num = 0; + return list; +} + + +/* Copy a list. */ +CBLIST *cblistdup(const CBLIST *list){ + CBLIST *newlist; + int i, size; + const char *val; + assert(list); + CB_LISTOPEN2(newlist, CB_LISTNUM(list)); + for(i = 0; i < CB_LISTNUM(list); i++){ + val = CB_LISTVAL2(list, i, size); + CB_LISTPUSH(newlist, val, size); + } + return newlist; +} + + +/* Close a list handle. */ +void cblistclose(CBLIST *list){ + int i, end; + assert(list); + end = list->start + list->num; + for(i = list->start; i < end; i++){ + free(list->array[i].dptr); + } + free(list->array); + free(list); +} + + +/* Get the number of elements of a list. */ +int cblistnum(const CBLIST *list){ + assert(list); + return list->num; +} + + +/* Get the pointer to the region of an element. */ +const char *cblistval(const CBLIST *list, int index, int *sp){ + assert(list && index >= 0); + if(index >= list->num) return NULL; + index += list->start; + if(sp) *sp = list->array[index].dsize; + return list->array[index].dptr; +} + + +/* Add an element at the end of a list. */ +void cblistpush(CBLIST *list, const char *ptr, int size){ + int index; + assert(list && ptr); + if(size < 0) size = strlen(ptr); + index = list->start + list->num; + if(index >= list->anum){ + list->anum *= 2; + CB_REALLOC(list->array, list->anum * sizeof(list->array[0])); + } + CB_MALLOC(list->array[index].dptr, (size < CB_DATUMUNIT ? CB_DATUMUNIT : size) + 1); + memcpy(list->array[index].dptr, ptr, size); + list->array[index].dptr[size] = '\0'; + list->array[index].dsize = size; + list->num++; +} + + +/* Remove an element of the end of a list. */ +char *cblistpop(CBLIST *list, int *sp){ + int index; + assert(list); + if(list->num < 1) return NULL; + index = list->start + list->num - 1; + list->num--; + if(sp) *sp = list->array[index].dsize; + return list->array[index].dptr; +} + + +/* Add an element at the top of a list. */ +void cblistunshift(CBLIST *list, const char *ptr, int size){ + int index; + assert(list && ptr); + if(size < 0) size = strlen(ptr); + if(list->start < 1){ + if(list->start + list->num >= list->anum){ + list->anum *= 2; + CB_REALLOC(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])); + } + index = list->start - 1; + CB_MALLOC(list->array[index].dptr, (size < CB_DATUMUNIT ? CB_DATUMUNIT : size) + 1); + memcpy(list->array[index].dptr, ptr, size); + list->array[index].dptr[size] = '\0'; + list->array[index].dsize = size; + list->start--; + list->num++; +} + + +/* Remove an element of the top of a list. */ +char *cblistshift(CBLIST *list, int *sp){ + int index; + assert(list); + if(list->num < 1) return NULL; + index = list->start; + list->start++; + list->num--; + if(sp) *sp = list->array[index].dsize; + return list->array[index].dptr; +} + + +/* Add an element at the specified location of a list. */ +void cblistinsert(CBLIST *list, int index, const char *ptr, int size){ + assert(list && index >= 0); + if(index > list->num) return; + if(size < 0) size = strlen(ptr); + index += list->start; + if(list->start + list->num >= list->anum){ + list->anum *= 2; + CB_REALLOC(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)); + CB_MEMDUP(list->array[index].dptr, ptr, size); + list->array[index].dsize = size; + list->num++; +} + + +/* Remove an element at the specified location of a list. */ +char *cblistremove(CBLIST *list, int index, int *sp){ + char *dptr; + assert(list && index >= 0); + if(index >= list->num) return NULL; + index += list->start; + dptr = list->array[index].dptr; + if(sp) *sp = list->array[index].dsize; + list->num--; + memmove(list->array + index, list->array + index + 1, + sizeof(list->array[0]) * (list->start + list->num - index)); + return dptr; +} + + +/* Overwrite an element at the specified location of a list. */ +void cblistover(CBLIST *list, int index, const char *ptr, int size){ + assert(list && index >= 0); + if(index >= list->num) return; + if(size < 0) size = strlen(ptr); + index += list->start; + if(size > list->array[index].dsize) + CB_REALLOC(list->array[index].dptr, size + 1); + memcpy(list->array[index].dptr, ptr, size); + list->array[index].dsize = size; + list->array[index].dptr[size] = '\0'; +} + + +/* Sort elements of a list in lexical order. */ +void cblistsort(CBLIST *list){ + assert(list); + qsort(list->array + list->start, list->num, sizeof(list->array[0]), cblistelemcmp); +} + + +/* Search a list for an element using liner search. */ +int cblistlsearch(const CBLIST *list, const char *ptr, int size){ + int i, end; + assert(list && ptr); + if(size < 0) size = strlen(ptr); + end = list->start + list->num; + for(i = list->start; i < end; i++){ + if(list->array[i].dsize == size && !memcmp(list->array[i].dptr, ptr, size)) + return i - list->start; + } + return -1; +} + + +/* Search a list for an element using binary search. */ +int cblistbsearch(const CBLIST *list, const char *ptr, int size){ + CBLISTDATUM key, *res; + assert(list && ptr); + if(size < 0) size = strlen(ptr); + CB_MEMDUP(key.dptr, ptr, size); + key.dsize = size; + res = bsearch(&key, list->array + list->start, list->num, sizeof(list->array[0]), cblistelemcmp); + free(key.dptr); + return res ? (res - list->array - list->start) : -1; +} + + +/* Serialize a list into a byte array. */ +char *cblistdump(const CBLIST *list, int *sp){ + char *buf, vnumbuf[CB_VNUMBUFSIZ]; + const char *vbuf; + int i, bsiz, vnumsiz, ln, vsiz; + assert(list && sp); + ln = CB_LISTNUM(list); + CB_SETVNUMBUF(vnumsiz, vnumbuf, ln); + CB_MALLOC(buf, vnumsiz + 1); + memcpy(buf, vnumbuf, vnumsiz); + bsiz = vnumsiz; + for(i = 0; i < ln; i++){ + vbuf = CB_LISTVAL2(list, i, vsiz); + CB_SETVNUMBUF(vnumsiz, vnumbuf, vsiz); + CB_REALLOC(buf, bsiz + vnumsiz + vsiz + 1); + memcpy(buf + bsiz, vnumbuf, vnumsiz); + bsiz += vnumsiz; + memcpy(buf + bsiz, vbuf, vsiz); + bsiz += vsiz; + } + *sp = bsiz; + return buf; +} + + +/* Redintegrate a serialized list. */ +CBLIST *cblistload(const char *ptr, int size){ + CBLIST *list; + const char *rp; + int i, anum, step, ln, vsiz; + assert(ptr && size >= 0); + anum = size / (sizeof(CBLISTDATUM) + 1); + CB_LISTOPEN2(list, anum); + rp = ptr; + CB_READVNUMBUF(rp, size, ln, step); + rp += step; + size -= step; + if(ln > size) return list; + for(i = 0; i < ln; i++){ + if(size < 1) break; + CB_READVNUMBUF(rp, size, vsiz, step); + rp += step; + size -= step; + if(vsiz > size) break; + CB_LISTPUSH(list, rp, vsiz); + rp += vsiz; + } + return list; +} + + +/* Get a map handle. */ +CBMAP *cbmapopen(void){ + return cbmapopenex(CB_MAPBNUM); +} + + +/* Copy a map. */ +CBMAP *cbmapdup(CBMAP *map){ + CBMAP *newmap; + const char *kbuf, *vbuf; + int ksiz, vsiz; + assert(map); + cbmapiterinit(map); + newmap = map->rnum > CB_MAPPBNUM ? cbmapopen() : cbmapopenex(CB_MAPPBNUM); + while((kbuf = cbmapiternext(map, &ksiz)) != NULL){ + CB_MAPITERVAL(vbuf, kbuf, vsiz); + cbmapput(newmap, kbuf, ksiz, vbuf, vsiz, FALSE); + } + cbmapiterinit(map); + return newmap; +} + + +/* Close a map handle. */ +void cbmapclose(CBMAP *map){ + CBMAPDATUM *datum, *next; + datum = map->first; + while(datum){ + next = datum->next; + free(datum); + datum = next; + } + free(map->buckets); + free(map); +} + + +/* Store a record. */ +int cbmapput(CBMAP *map, const char *kbuf, int ksiz, const char *vbuf, int vsiz, int over){ + CBMAPDATUM *datum, **entp, *old; + char *dbuf; + int bidx, hash, kcmp, psiz; + assert(map && kbuf && vbuf); + if(ksiz < 0) ksiz = strlen(kbuf); + if(vsiz < 0) vsiz = strlen(vbuf); + CB_FIRSTHASH(hash, kbuf, ksiz); + bidx = hash % map->bnum; + datum = map->buckets[bidx]; + entp = map->buckets + bidx; + CB_SECONDHASH(hash, kbuf, ksiz); + while(datum){ + if(hash > datum->hash){ + entp = &(datum->left); + datum = datum->left; + } else if(hash < datum->hash){ + entp = &(datum->right); + datum = datum->right; + } else { + dbuf = (char *)datum + sizeof(*datum); + kcmp = cbkeycmp(kbuf, ksiz, dbuf, datum->ksiz); + if(kcmp < 0){ + entp = &(datum->left); + datum = datum->left; + } else if(kcmp > 0){ + entp = &(datum->right); + datum = datum->right; + } else { + if(!over) return FALSE; + psiz = CB_ALIGNPAD(ksiz); + if(vsiz > datum->vsiz){ + old = datum; + CB_REALLOC(datum, sizeof(*datum) + ksiz + psiz + vsiz + 1); + if(datum != old){ + if(map->first == old) map->first = datum; + if(map->last == old) map->last = datum; + if(*entp == old) *entp = datum; + if(datum->prev) datum->prev->next = datum; + if(datum->next) datum->next->prev = datum; + dbuf = (char *)datum + sizeof(*datum); + } + } + memcpy(dbuf + ksiz + psiz, vbuf, vsiz); + dbuf[ksiz+psiz+vsiz] = '\0'; + datum->vsiz = vsiz; + return TRUE; + } + } + } + psiz = CB_ALIGNPAD(ksiz); + CB_MALLOC(datum, sizeof(*datum) + ksiz + psiz + vsiz + 1); + dbuf = (char *)datum + sizeof(*datum); + memcpy(dbuf, kbuf, ksiz); + dbuf[ksiz] = '\0'; + datum->ksiz = ksiz; + memcpy(dbuf + ksiz + psiz, vbuf, vsiz); + dbuf[ksiz+psiz+vsiz] = '\0'; + datum->vsiz = vsiz; + datum->hash = hash; + datum->left = NULL; + datum->right = NULL; + datum->prev = map->last; + datum->next = NULL; + *entp = datum; + if(!map->first) map->first = datum; + if(map->last) map->last->next = datum; + map->last = datum; + map->rnum++; + return TRUE; +} + + +/* Concatenate a value at the end of the value of the existing record. */ +void cbmapputcat(CBMAP *map, const char *kbuf, int ksiz, const char *vbuf, int vsiz){ + CBMAPDATUM *datum, **entp, *old; + char *dbuf; + int bidx, hash, kcmp, psiz, asiz, unit; + assert(map && kbuf && vbuf); + if(ksiz < 0) ksiz = strlen(kbuf); + if(vsiz < 0) vsiz = strlen(vbuf); + CB_FIRSTHASH(hash, kbuf, ksiz); + bidx = hash % map->bnum; + datum = map->buckets[bidx]; + entp = map->buckets + bidx; + CB_SECONDHASH(hash, kbuf, ksiz); + while(datum){ + if(hash > datum->hash){ + entp = &(datum->left); + datum = datum->left; + } else if(hash < datum->hash){ + entp = &(datum->right); + datum = datum->right; + } else { + dbuf = (char *)datum + sizeof(*datum); + kcmp = cbkeycmp(kbuf, ksiz, dbuf, datum->ksiz); + if(kcmp < 0){ + entp = &(datum->left); + datum = datum->left; + } else if(kcmp > 0){ + entp = &(datum->right); + datum = datum->right; + } else { + psiz = CB_ALIGNPAD(ksiz); + asiz = sizeof(*datum) + ksiz + psiz + datum->vsiz + vsiz + 1; + unit = asiz <= CB_MAPCSUNIT ? CB_MAPCSUNIT : CB_MAPCBUNIT; + asiz = (asiz - 1) + unit - (asiz - 1) % unit; + old = datum; + CB_REALLOC(datum, asiz); + if(datum != old){ + if(map->first == old) map->first = datum; + if(map->last == old) map->last = datum; + if(*entp == old) *entp = datum; + if(datum->prev) datum->prev->next = datum; + if(datum->next) datum->next->prev = datum; + dbuf = (char *)datum + sizeof(*datum); + } + memcpy(dbuf + ksiz + psiz + datum->vsiz, vbuf, vsiz); + dbuf[ksiz+psiz+datum->vsiz+vsiz] = '\0'; + datum->vsiz += vsiz; + return; + } + } + } + psiz = CB_ALIGNPAD(ksiz); + asiz = sizeof(*datum) + ksiz + psiz + vsiz + 1; + unit = asiz <= CB_MAPCSUNIT ? CB_MAPCSUNIT : CB_MAPCBUNIT; + asiz = (asiz - 1) + unit - (asiz - 1) % unit; + CB_MALLOC(datum, asiz); + dbuf = (char *)datum + sizeof(*datum); + memcpy(dbuf, kbuf, ksiz); + dbuf[ksiz] = '\0'; + datum->ksiz = ksiz; + memcpy(dbuf + ksiz + psiz, vbuf, vsiz); + dbuf[ksiz+psiz+vsiz] = '\0'; + datum->vsiz = vsiz; + datum->hash = hash; + datum->left = NULL; + datum->right = NULL; + datum->prev = map->last; + datum->next = NULL; + *entp = datum; + if(!map->first) map->first = datum; + if(map->last) map->last->next = datum; + map->last = datum; + map->rnum++; +} + + +/* Delete a record. */ +int cbmapout(CBMAP *map, const char *kbuf, int ksiz){ + CBMAPDATUM *datum, **entp, *tmp; + char *dbuf; + int bidx, hash, kcmp; + assert(map && kbuf); + if(ksiz < 0) ksiz = strlen(kbuf); + CB_FIRSTHASH(hash, kbuf, ksiz); + bidx = hash % map->bnum; + datum = map->buckets[bidx]; + entp = map->buckets + bidx; + CB_SECONDHASH(hash, kbuf, ksiz); + while(datum){ + if(hash > datum->hash){ + entp = &(datum->left); + datum = datum->left; + } else if(hash < datum->hash){ + entp = &(datum->right); + datum = datum->right; + } else { + dbuf = (char *)datum + sizeof(*datum); + kcmp = cbkeycmp(kbuf, ksiz, dbuf, datum->ksiz); + if(kcmp < 0){ + entp = &(datum->left); + datum = datum->left; + } else if(kcmp > 0){ + entp = &(datum->right); + datum = datum->right; + } else { + if(datum->prev) datum->prev->next = datum->next; + if(datum->next) datum->next->prev = datum->prev; + if(datum == map->first) map->first = datum->next; + if(datum == map->last) map->last = datum->prev; + if(datum->left && !datum->right){ + *entp = datum->left; + } else if(!datum->left && datum->right){ + *entp = datum->right; + } else if(!datum->left && !datum->left){ + *entp = NULL; + } else { + *entp = datum->left; + tmp = *entp; + while(TRUE){ + if(hash > tmp->hash){ + if(tmp->left){ + tmp = tmp->left; + } else { + tmp->left = datum->right; + break; + } + } else if(hash < tmp->hash){ + if(tmp->right){ + tmp = tmp->right; + } else { + tmp->right = datum->right; + break; + } + } else { + kcmp = cbkeycmp(kbuf, ksiz, dbuf, datum->ksiz); + if(kcmp < 0){ + if(tmp->left){ + tmp = tmp->left; + } else { + tmp->left = datum->right; + break; + } + } else { + if(tmp->right){ + tmp = tmp->right; + } else { + tmp->right = datum->right; + break; + } + } + } + } + } + free(datum); + map->rnum--; + return TRUE; + } + } + } + return FALSE; +} + + +/* Retrieve a record. */ +const char *cbmapget(const CBMAP *map, const char *kbuf, int ksiz, int *sp){ + CBMAPDATUM *datum; + char *dbuf; + int hash, kcmp; + assert(map && kbuf); + if(ksiz < 0) ksiz = strlen(kbuf); + CB_FIRSTHASH(hash, kbuf, ksiz); + datum = map->buckets[hash%map->bnum]; + CB_SECONDHASH(hash, kbuf, ksiz); + while(datum){ + if(hash > datum->hash){ + datum = datum->left; + } else if(hash < datum->hash){ + datum = datum->right; + } else { + dbuf = (char *)datum + sizeof(*datum); + kcmp = cbkeycmp(kbuf, ksiz, dbuf, datum->ksiz); + if(kcmp < 0){ + datum = datum->left; + } else if(kcmp > 0){ + datum = datum->right; + } else { + if(sp) *sp = datum->vsiz; + return dbuf + datum->ksiz + CB_ALIGNPAD(datum->ksiz); + } + } + } + return NULL; +} + + +/* Move a record to the edge. */ +int cbmapmove(CBMAP *map, const char *kbuf, int ksiz, int head){ + CBMAPDATUM *datum; + char *dbuf; + int hash, kcmp; + assert(map && kbuf); + if(ksiz < 0) ksiz = strlen(kbuf); + CB_FIRSTHASH(hash, kbuf, ksiz); + datum = map->buckets[hash%map->bnum]; + CB_SECONDHASH(hash, kbuf, ksiz); + while(datum){ + if(hash > datum->hash){ + datum = datum->left; + } else if(hash < datum->hash){ + datum = datum->right; + } else { + dbuf = (char *)datum + sizeof(*datum); + kcmp = cbkeycmp(kbuf, ksiz, dbuf, datum->ksiz); + if(kcmp < 0){ + datum = datum->left; + } else if(kcmp > 0){ + datum = datum->right; + } else { + if(head){ + if(map->first == datum) return TRUE; + if(map->last == datum) map->last = datum->prev; + if(datum->prev) datum->prev->next = datum->next; + if(datum->next) datum->next->prev = datum->prev; + datum->prev = NULL; + datum->next = map->first; + map->first->prev = datum; + map->first = datum; + } else { + if(map->last == datum) return TRUE; + if(map->first == datum) map->first = datum->next; + if(datum->prev) datum->prev->next = datum->next; + if(datum->next) datum->next->prev = datum->prev; + datum->prev = map->last; + datum->next = NULL; + map->last->next = datum; + map->last = datum; + } + return TRUE; + } + } + } + return FALSE; +} + + +/* Initialize the iterator of a map handle. */ +void cbmapiterinit(CBMAP *map){ + assert(map); + map->cur = map->first; +} + + +/* Get the next key of the iterator. */ +const char *cbmapiternext(CBMAP *map, int *sp){ + CBMAPDATUM *datum; + assert(map); + if(!map->cur) return NULL; + datum = map->cur; + map->cur = datum->next; + if(sp) *sp = datum->ksiz; + return (char *)datum + sizeof(*datum); +} + + +/* Get the value binded to the key fetched from the iterator. */ +const char *cbmapiterval(const char *kbuf, int *sp){ + CBMAPDATUM *datum; + assert(kbuf); + datum = (CBMAPDATUM *)(kbuf - sizeof(*datum)); + if(sp) *sp = datum->vsiz; + return (char *)datum + sizeof(*datum) + datum->ksiz + CB_ALIGNPAD(datum->ksiz); +} + + +/* Get the number of the records stored in a map. */ +int cbmaprnum(const CBMAP *map){ + assert(map); + return map->rnum; +} + + +/* Get the list handle contains all keys in a map. */ +CBLIST *cbmapkeys(CBMAP *map){ + CBLIST *list; + const char *kbuf; + int anum, ksiz; + assert(map); + anum = cbmaprnum(map); + CB_LISTOPEN2(list, anum); + cbmapiterinit(map); + while((kbuf = cbmapiternext(map, &ksiz)) != NULL){ + CB_LISTPUSH(list, kbuf, ksiz); + } + return list; +} + + +/* Get the list handle contains all values in a map. */ +CBLIST *cbmapvals(CBMAP *map){ + CBLIST *list; + const char *kbuf, *vbuf; + int anum, ksiz, vsiz; + assert(map); + anum = cbmaprnum(map); + CB_LISTOPEN2(list, anum); + cbmapiterinit(map); + while((kbuf = cbmapiternext(map, &ksiz)) != NULL){ + CB_MAPITERVAL(vbuf, kbuf, vsiz); + CB_LISTPUSH(list, vbuf, vsiz); + } + return list; +} + + +/* Serialize a map into a byte array. */ +char *cbmapdump(CBMAP *map, int *sp){ + char *buf, vnumbuf[CB_VNUMBUFSIZ]; + const char *kbuf, *vbuf; + int bsiz, vnumsiz, rn, ksiz, vsiz; + assert(map && sp); + rn = cbmaprnum(map); + CB_SETVNUMBUF(vnumsiz, vnumbuf, rn); + CB_MALLOC(buf, vnumsiz + 1); + memcpy(buf, vnumbuf, vnumsiz); + bsiz = vnumsiz; + cbmapiterinit(map); + while((kbuf = cbmapiternext(map, &ksiz)) != NULL){ + CB_MAPITERVAL(vbuf, kbuf, vsiz); + CB_SETVNUMBUF(vnumsiz, vnumbuf, ksiz); + CB_REALLOC(buf, bsiz + vnumsiz + ksiz + 1); + memcpy(buf + bsiz, vnumbuf, vnumsiz); + bsiz += vnumsiz; + memcpy(buf + bsiz, kbuf, ksiz); + bsiz += ksiz; + CB_SETVNUMBUF(vnumsiz, vnumbuf, vsiz); + CB_REALLOC(buf, bsiz + vnumsiz + vsiz + 1); + memcpy(buf + bsiz, vnumbuf, vnumsiz); + bsiz += vnumsiz; + memcpy(buf + bsiz, vbuf, vsiz); + bsiz += vsiz; + } + *sp = bsiz; + return buf; +} + + +/* Redintegrate a serialized map. */ +CBMAP *cbmapload(const char *ptr, int size){ + CBMAP *map; + const char *rp, *kbuf, *vbuf; + int i, step, rn, ksiz, vsiz; + assert(ptr && size >= 0); + map = cbmapopenex(CB_MAPPBNUM); + rp = ptr; + CB_READVNUMBUF(rp, size, rn, step); + rp += step; + size -= step; + if(rn > size) return map; + for(i = 0; i < rn; i++){ + if(size < 1) break; + CB_READVNUMBUF(rp, size, ksiz, step); + rp += step; + size -= step; + if(ksiz > size) break; + kbuf = rp; + rp += ksiz; + if(size < 1) break; + CB_READVNUMBUF(rp, size, vsiz, step); + rp += step; + size -= step; + if(vsiz > size) break; + vbuf = rp; + rp += vsiz; + cbmapput(map, kbuf, ksiz, vbuf, vsiz, TRUE); + } + return map; +} + + +/* Redintegrate a serialized map and get one of the records. */ +char *cbmaploadone(const char *ptr, int size, const char *kbuf, int ksiz, int *sp){ + const char *rp, *tkbuf, *vbuf; + char *rv; + int i, step, rn, tksiz, vsiz; + assert(ptr && size >= 0 && kbuf); + if(ksiz < 0) ksiz = strlen(kbuf); + rp = ptr; + CB_READVNUMBUF(rp, size, rn, step); + rp += step; + size -= step; + if(rn > size) return NULL; + for(i = 0; i < rn; i++){ + if(size < 1) break; + CB_READVNUMBUF(rp, size, tksiz, step); + rp += step; + size -= step; + if(tksiz > size) break; + tkbuf = rp; + rp += tksiz; + if(size < 1) break; + CB_READVNUMBUF(rp, size, vsiz, step); + rp += step; + size -= step; + if(vsiz > size) break; + vbuf = rp; + rp += vsiz; + if(tksiz == ksiz && !memcmp(tkbuf, kbuf, ksiz)){ + if(sp) *sp = vsiz; + CB_MEMDUP(rv, vbuf, vsiz); + return rv; + } + } + return NULL; +} + + +/* Get a heap handle. */ +CBHEAP *cbheapopen(int size, int max, int(*compar)(const void *, const void *)){ + CBHEAP *heap; + assert(size > 0 && max >= 0 && compar); + CB_MALLOC(heap, sizeof(*heap)); + CB_MALLOC(heap->base, size * max + 1); + CB_MALLOC(heap->swap, size); + heap->size = size; + heap->num = 0; + heap->max = max; + heap->compar = compar; + return heap; +} + + +/* Copy a heap. */ +CBHEAP *cbheapdup(CBHEAP *heap){ + CBHEAP *newheap; + assert(heap); + CB_MALLOC(newheap, sizeof(*newheap)); + CB_MEMDUP(newheap->base, heap->base, heap->size * heap->max); + CB_MALLOC(newheap->swap, heap->size); + newheap->size = heap->size; + newheap->num = heap->num; + newheap->max = heap->max; + newheap->compar = heap->compar; + return newheap; +} + + +/* Close a heap handle. */ +void cbheapclose(CBHEAP *heap){ + assert(heap); + free(heap->swap); + free(heap->base); + free(heap); +} + + +/* Get the number of the records stored in a heap. */ +int cbheapnum(CBHEAP *heap){ + assert(heap); + return heap->num; +} + + +/* Insert a record into a heap. */ +int cbheapinsert(CBHEAP *heap, const void *ptr){ + char *base; + int size, pidx, cidx, bot; + assert(heap && ptr); + if(heap->max < 1) return FALSE; + base = heap->base; + size = heap->size; + if(heap->num >= heap->max){ + if(heap->compar(ptr, base) > 0) return FALSE; + memcpy(base, ptr, size); + pidx = 0; + bot = heap->num / 2; + while(pidx < bot){ + cidx = pidx * 2 + 1; + if(cidx < heap->num - 1 && heap->compar(base + cidx * size, base + (cidx + 1) * size) < 0) + cidx++; + if(heap->compar(base + pidx * size, base + cidx * size) > 0) break; + memcpy(heap->swap, base + pidx * size, size); + memcpy(base + pidx * size, base + cidx * size, size); + memcpy(base + cidx * size, heap->swap, size); + pidx = cidx; + } + } else { + memcpy(base + size * heap->num, ptr, size); + cidx = heap->num; + while(cidx > 0){ + pidx = (cidx - 1) / 2; + if(heap->compar(base + cidx * size, base + pidx * size) <= 0) break; + memcpy(heap->swap, base + cidx * size, size); + memcpy(base + cidx * size, base + pidx * size, size); + memcpy(base + pidx * size, heap->swap, size); + cidx = pidx; + } + heap->num++; + } + return TRUE; +} + + +/* Get the pointer to the region of a record in a heap. */ +const void *cbheapval(CBHEAP *heap, int index){ + assert(heap && index >= 0); + if(index >= heap->num) return NULL; + return heap->base + index * heap->size; +} + + +/* Convert a heap to an allocated region. */ +void *cbheaptomalloc(CBHEAP *heap, int *np){ + char *ptr; + assert(heap); + qsort(heap->base, heap->num, heap->size, heap->compar); + ptr = heap->base; + if(np) *np = heap->num; + free(heap->swap); + free(heap); + return ptr; +} + + +/* Allocate a formatted string on memory. */ +char *cbsprintf(const char *format, ...){ + va_list ap; + char *buf, cbuf[CB_SPBUFSIZ], *str; + int len, cblen, num, slen; + unsigned int unum; + double dnum; + va_start(ap, format); + assert(format); + CB_MALLOC(buf, 1); + len = 0; + while(*format != '\0'){ + if(*format == '%'){ + cbuf[0] = '%'; + cblen = 1; + format++; + while(strchr("0123456789 .+-", *format) && *format != '\0' && cblen < CB_SPBUFSIZ - 1){ + cbuf[cblen++] = *format; + format++; + } + cbuf[cblen] = '\0'; + if(atoi(cbuf + 1) > CB_SPMAXWIDTH - 16){ + sprintf(cbuf, "(err)"); + } else { + cbuf[cblen++] = *format; + cbuf[cblen] = '\0'; + } + switch(*format){ + case 'd': + num = va_arg(ap, int); + CB_REALLOC(buf, len + CB_SPMAXWIDTH + 2); + len += sprintf(buf + len, cbuf, num); + break; + case 'o': case 'u': case 'x': case 'X': case 'c': + unum = va_arg(ap, unsigned int); + CB_REALLOC(buf, len + CB_SPMAXWIDTH + 2); + len += sprintf(buf + len, cbuf, unum); + break; + case 'e': case 'E': case 'f': case 'g': case 'G': + dnum = va_arg(ap, double); + CB_REALLOC(buf, len + CB_SPMAXWIDTH + 2); + len += sprintf(buf + len, cbuf, dnum); + break; + case 's': + str = va_arg(ap, char *); + slen = strlen(str); + CB_REALLOC(buf, len + slen + 2); + memcpy(buf + len, str, slen); + len += slen; + break; + case '%': + CB_REALLOC(buf, len + 2); + buf[len++] = '%'; + break; + default: + break; + } + } else { + CB_REALLOC(buf, len + 2); + buf[len++] = *format; + } + format++; + } + buf[len] = '\0'; + va_end(ap); + return buf; +} + + +/* Replace some patterns in a string. */ +char *cbreplace(const char *str, CBMAP *pairs){ + int i, bsiz, wi, rep, ksiz, vsiz; + char *buf; + const char *key, *val; + assert(str && pairs); + bsiz = CB_DATUMUNIT; + CB_MALLOC(buf, bsiz); + wi = 0; + while(*str != '\0'){ + rep = FALSE; + cbmapiterinit(pairs); + while((key = cbmapiternext(pairs, &ksiz)) != NULL){ + for(i = 0; i < ksiz; i++){ + if(str[i] == '\0' || str[i] != key[i]) break; + } + if(i == ksiz){ + CB_MAPITERVAL(val, key, vsiz); + if(wi + vsiz >= bsiz){ + bsiz = bsiz * 2 + vsiz; + CB_REALLOC(buf, bsiz); + } + memcpy(buf + wi, val, vsiz); + wi += vsiz; + str += ksiz; + rep = TRUE; + break; + } + } + if(!rep){ + if(wi + 1 >= bsiz){ + bsiz = bsiz * 2 + 1; + CB_REALLOC(buf, bsiz); + } + buf[wi++] = *str; + str++; + } + } + CB_REALLOC(buf, wi + 1); + buf[wi] = '\0'; + return buf; +} + + +/* Make a list by split a serial datum. */ +CBLIST *cbsplit(const char *ptr, int size, const char *delim){ + CBLIST *list; + int bi, step; + assert(ptr); + CB_LISTOPEN(list); + if(size < 0) size = strlen(ptr); + if(delim){ + for(bi = 0; bi < size; bi += step){ + step = 0; + while(bi + step < size && !strchr(delim, ptr[bi+step])){ + step++; + } + cblistpush(list, ptr + bi, step); + step++; + } + if(size > 0 && strchr(delim, ptr[size-1])) cblistpush(list, "", 0); + } else { + for(bi = 0; bi < size; bi += step){ + step = 0; + while(bi + step < size && ptr[bi+step]){ + step++; + } + cblistpush(list, ptr + bi, step); + step++; + } + if(size > 0 && ptr[size-1] == 0) cblistpush(list, "", 0); + } + return list; +} + + +/* Read whole data of a file. */ +char *cbreadfile(const char *name, int *sp){ + struct stat sbuf; + char iobuf[CB_IOBUFSIZ], *buf; + int fd, size, asiz, rv; + asiz = CB_IOBUFSIZ * 2; + if(name){ + if((fd = open(name, O_RDONLY, 0)) == -1) return NULL; + if(fstat(fd, &sbuf) != -1) asiz = sbuf.st_size + 1; + } else { + fd = 0; + } + CB_MALLOC(buf, asiz + 1); + size = 0; + while((rv = read(fd, iobuf, CB_IOBUFSIZ)) > 0){ + if(size + rv >= asiz){ + asiz = asiz * 2 + size; + CB_REALLOC(buf, asiz + 1); + } + memcpy(buf + size, iobuf, rv); + size += rv; + } + buf[size] = '\0'; + if(close(fd) == -1 || rv == -1){ + free(buf); + return NULL; + } + if(sp) *sp = size; + return buf; +} + + +/* Write data of a region into a file. */ +int cbwritefile(const char *name, const char *ptr, int size){ + int fd, err, wb; + assert(ptr); + if(size < 0) size = strlen(ptr); + if(name){ + if((fd = open(name, O_WRONLY | O_CREAT | O_TRUNC, CB_FILEMODE)) == -1) return FALSE; + } else { + fd = 1; + } + err = FALSE; + wb = 0; + do { + wb = write(fd, ptr, size); + switch(wb){ + case -1: err = errno != EINTR ? TRUE : FALSE; break; + case 0: break; + default: + ptr += wb; + size -= wb; + break; + } + } while(size > 0); + if(close(fd) == -1) err = TRUE; + return err ? FALSE : TRUE; +} + + +/* Read every line of a file. */ +CBLIST *cbreadlines(const char *name){ + char *buf, *tmp; + int vsiz; + CBMAP *pairs; + CBLIST *list; + if(!(buf = cbreadfile(name, NULL))) return NULL; + pairs = cbmapopenex(3); + cbmapput(pairs, "\r\n", 2, "\n", 1, TRUE); + cbmapput(pairs, "\r", 1, "\n", 1, TRUE); + tmp = cbreplace(buf, pairs); + list = cbsplit(tmp, strlen(tmp), "\n"); + free(tmp); + cbmapclose(pairs); + free(buf); + if(CB_LISTNUM(list) > 0){ + cblistval(list, CB_LISTNUM(list) - 1, &vsiz); + if(vsiz < 1) CB_LISTDROP(list); + } + return list; +} + + +/* Read names of files in a directory. */ +CBLIST *cbdirlist(const char *name){ + DIR *DD; + struct dirent *dp; + CBLIST *list; + assert(name); + if(!(DD = opendir(name))) return NULL; + CB_LISTOPEN(list); + while((dp = readdir(DD)) != NULL){ + CB_LISTPUSH(list, dp->d_name, strlen(dp->d_name)); + } + if(closedir(DD) == -1){ + CB_LISTCLOSE(list); + return NULL; + } + return list; +} + + +/* Get the status of a file or a directory. */ +int cbfilestat(const char *name, int *isdirp, int *sizep, time_t *mtimep){ + struct stat sbuf; + assert(name); + if(lstat(name, &sbuf) == -1) return FALSE; + if(isdirp) *isdirp = S_ISDIR(sbuf.st_mode); + if(sizep) *sizep = (int)sbuf.st_size; + if(mtimep) *mtimep = sbuf.st_mtime; + return TRUE; +} + + +/* Remove a file or a directory and its sub ones recursively. */ +int cbremove(const char *name){ + CBLIST *list; + const char *elem; + char *path; + int i, err, tail; + struct stat sbuf; + assert(name); + if(lstat(name, &sbuf) == -1) return FALSE; + if(unlink(name) == 0) return TRUE; + if(!S_ISDIR(sbuf.st_mode) || !(list = cbdirlist(name))) return FALSE; + err = FALSE; + tail = name[0] != '\0' && name[strlen(name)-1] == MYPATHCHR; + for(i = 0; i < CB_LISTNUM(list); i++){ + elem = CB_LISTVAL(list, i); + if(!strcmp(MYCDIRSTR, elem) || !strcmp(MYPDIRSTR, elem)) continue; + if(tail){ + path = cbsprintf("%s%s", name, elem); + } else { + path = cbsprintf("%s%c%s", name, MYPATHCHR, elem); + } + if(!cbremove(path)) err = TRUE; + free(path); + } + CB_LISTCLOSE(list); + return rmdir(name) == 0 ? TRUE : FALSE; +} + + +/* Break up a URL into elements. */ +CBMAP *cburlbreak(const char *str){ + CBMAP *map; + char *tmp, *ep; + const char *rp; + int serv; + assert(str); + map = cbmapopenex(CB_MAPPBNUM); + CB_MEMDUP(tmp, str, strlen(str)); + rp = cbstrtrim(tmp); + cbmapput(map, "self", -1, rp, -1, TRUE); + serv = FALSE; + if(cbstrfwimatch(rp, "http://")){ + cbmapput(map, "scheme", -1, "http", -1, TRUE); + rp += 7; + serv = TRUE; + } else if(cbstrfwimatch(rp, "https://")){ + cbmapput(map, "scheme", -1, "https", -1, TRUE); + rp += 8; + serv = TRUE; + } else if(cbstrfwimatch(rp, "ftp://")){ + cbmapput(map, "scheme", -1, "ftp", -1, TRUE); + rp += 6; + serv = TRUE; + } else if(cbstrfwimatch(rp, "sftp://")){ + cbmapput(map, "scheme", -1, "sftp", -1, TRUE); + rp += 7; + serv = TRUE; + } else if(cbstrfwimatch(rp, "ftps://")){ + cbmapput(map, "scheme", -1, "ftps", -1, TRUE); + rp += 7; + serv = TRUE; + } else if(cbstrfwimatch(rp, "tftp://")){ + cbmapput(map, "scheme", -1, "tftp", -1, TRUE); + rp += 7; + serv = TRUE; + } else if(cbstrfwimatch(rp, "ldap://")){ + cbmapput(map, "scheme", -1, "ldap", -1, TRUE); + rp += 7; + serv = TRUE; + } else if(cbstrfwimatch(rp, "ldaps://")){ + cbmapput(map, "scheme", -1, "ldaps", -1, TRUE); + rp += 8; + serv = TRUE; + } else if(cbstrfwimatch(rp, "file://")){ + cbmapput(map, "scheme", -1, "file", -1, TRUE); + rp += 7; + serv = TRUE; + } + if((ep = strchr(rp, '#')) != NULL){ + cbmapput(map, "fragment", -1, ep + 1, -1, TRUE); + *ep = '\0'; + } + if((ep = strchr(rp, '?')) != NULL){ + cbmapput(map, "query", -1, ep + 1, -1, TRUE); + *ep = '\0'; + } + if(serv){ + if((ep = strchr(rp, '/')) != NULL){ + cbmapput(map, "path", -1, ep, -1, TRUE); + *ep = '\0'; + } else { + cbmapput(map, "path", -1, "/", -1, TRUE); + } + if((ep = strchr(rp, '@')) != NULL){ + *ep = '\0'; + if(rp[0] != '\0') cbmapput(map, "authority", -1, rp, -1, TRUE); + rp = ep + 1; + } + if((ep = strchr(rp, ':')) != NULL){ + if(ep[1] != '\0') cbmapput(map, "port", -1, ep + 1, -1, TRUE); + *ep = '\0'; + } + if(rp[0] != '\0') cbmapput(map, "host", -1, rp, -1, TRUE); + } else { + cbmapput(map, "path", -1, rp, -1, TRUE); + } + free(tmp); + if((rp = cbmapget(map, "path", -1, NULL)) != NULL){ + if((ep = strrchr(rp, '/')) != NULL){ + if(ep[1] != '\0') cbmapput(map, "file", -1, ep + 1, -1, TRUE); + } else { + cbmapput(map, "file", -1, rp, -1, TRUE); + } + } + if((rp = cbmapget(map, "file", -1, NULL)) != NULL && (!strcmp(rp, ".") || !strcmp(rp, ".."))) + cbmapout(map, "file", -1); + return map; +} + + +/* Resolve a relative URL with another absolute URL. */ +char *cburlresolve(const char *base, const char *target){ + CBMAP *telems, *belems; + CBLIST *bpaths, *opaths, *qelems; + CBDATUM *rbuf; + const char *vbuf, *path; + char *tmp, *wp, *enc, numbuf[CB_NUMBUFSIZ]; + int i, vsiz, port, num; + assert(base && target); + while(*base > '\0' && *base <= ' '){ + base++; + } + while(*target > '\0' && *target <= ' '){ + target++; + } + if(*target == '\0') target = base; + CB_DATUMOPEN(rbuf); + telems = cburlbreak(target); + port = 80; + belems = cburlbreak(cbmapget(telems, "scheme", -1, &vsiz) ? target : base); + if((vbuf = cbmapget(belems, "scheme", -1, &vsiz)) != NULL){ + CB_DATUMCAT(rbuf, vbuf, vsiz); + CB_DATUMCAT(rbuf, "://", 3); + if(!cbstricmp(vbuf, "https")){ + port = 443; + } else if(!cbstricmp(vbuf, "ftp")){ + port = 21; + } else if(!cbstricmp(vbuf, "sftp")){ + port = 115; + } else if(!cbstricmp(vbuf, "ftps")){ + port = 22; + } else if(!cbstricmp(vbuf, "tftp")){ + port = 69; + } else if(!cbstricmp(vbuf, "ldap")){ + port = 389; + } else if(!cbstricmp(vbuf, "ldaps")){ + port = 636; + } + } else { + CB_DATUMCAT(rbuf, "http://", 7); + } + if((vbuf = cbmapget(belems, "authority", -1, &vsiz)) != NULL){ + if((wp = strchr(vbuf, ':')) != NULL){ + *wp = '\0'; + tmp = cburldecode(vbuf, NULL); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + CB_DATUMCAT(rbuf, ":", 1); + wp++; + tmp = cburldecode(wp, NULL); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + } else { + tmp = cburldecode(vbuf, NULL); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + } + CB_DATUMCAT(rbuf, "@", 1); + } + if((vbuf = cbmapget(belems, "host", -1, &vsiz)) != NULL){ + tmp = cburldecode(vbuf, NULL); + cbstrtolower(tmp); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + } else { + CB_DATUMCAT(rbuf, "localhost", 9); + } + if((vbuf = cbmapget(belems, "port", -1, &vsiz)) != NULL && + (num = atoi(vbuf)) != port && num > 1){ + sprintf(numbuf, ":%d", num); + CB_DATUMCAT(rbuf, numbuf, strlen(numbuf)); + } + if(!(path = cbmapget(telems, "path", -1, NULL))) path = "/"; + if(path[0] == '\0' && (vbuf = cbmapget(belems, "path", -1, NULL)) != NULL) path = vbuf; + if(path[0] == '\0') path = "/"; + CB_LISTOPEN(bpaths); + if(path[0] != '/' && (vbuf = cbmapget(belems, "path", -1, &vsiz)) != NULL){ + opaths = cbsplit(vbuf, vsiz, "/"); + } else { + opaths = cbsplit("/", 1, "/"); + } + CB_LISTDROP(opaths); + for(i = 0; i < CB_LISTNUM(opaths); i++){ + vbuf = CB_LISTVAL2(opaths, i, vsiz); + if(vsiz < 1 || !strcmp(vbuf, ".")) continue; + if(!strcmp(vbuf, "..")){ + CB_LISTDROP(bpaths); + } else { + CB_LISTPUSH(bpaths, vbuf, vsiz); + } + } + CB_LISTCLOSE(opaths); + opaths = cbsplit(path, -1, "/"); + for(i = 0; i < CB_LISTNUM(opaths); i++){ + vbuf = CB_LISTVAL2(opaths, i, vsiz); + if(vsiz < 1 || !strcmp(vbuf, ".")) continue; + if(!strcmp(vbuf, "..")){ + CB_LISTDROP(bpaths); + } else { + CB_LISTPUSH(bpaths, vbuf, vsiz); + } + } + CB_LISTCLOSE(opaths); + for(i = 0; i < CB_LISTNUM(bpaths); i++){ + vbuf = CB_LISTVAL(bpaths, i); + if(strchr(vbuf, '%')){ + tmp = cburldecode(vbuf, NULL); + } else { + CB_MEMDUP(tmp, vbuf, strlen(vbuf)); + } + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, "/", 1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + } + if(cbstrbwmatch(path, "/")) CB_DATUMCAT(rbuf, "/", 1); + CB_LISTCLOSE(bpaths); + if((vbuf = cbmapget(telems, "query", -1, &vsiz)) != NULL){ + CB_DATUMCAT(rbuf, "?", 1); + qelems = cbsplit(vbuf, vsiz, "&;"); + for(i = 0; i < CB_LISTNUM(qelems); i++){ + vbuf = CB_LISTVAL(qelems, i); + if(i > 0) CB_DATUMCAT(rbuf, "&", 1); + if((wp = strchr(vbuf, '=')) != NULL){ + *wp = '\0'; + tmp = cburldecode(vbuf, NULL); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + CB_DATUMCAT(rbuf, "=", 1); + wp++; + tmp = cburldecode(wp, NULL); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + } else { + tmp = cburldecode(vbuf, NULL); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + } + } + CB_LISTCLOSE(qelems); + } + if((vbuf = cbmapget(telems, "fragment", -1, &vsiz)) != NULL){ + tmp = cburldecode(vbuf, NULL); + enc = cburlencode(tmp, -1); + CB_DATUMCAT(rbuf, "#", 1); + CB_DATUMCAT(rbuf, enc, strlen(enc)); + free(enc); + free(tmp); + } + cbmapclose(belems); + cbmapclose(telems); + return cbdatumtomalloc(rbuf, NULL); +} + + +/* Encode a serial object with URL encoding. */ +char *cburlencode(const char *ptr, int size){ + char *buf, *wp; + int i, c; + assert(ptr); + if(size < 0) size = strlen(ptr); + CB_MALLOC(buf, size * 3 + 1); + wp = buf; + for(i = 0; i < size; i++){ + c = ((unsigned char *)ptr)[i]; + if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || + (c >= '0' && c <= '9') || (c != '\0' && strchr("_-.!~*'()", c))){ + *(wp++) = c; + } else { + wp += sprintf(wp, "%%%02X", c); + } + } + *wp = '\0'; + return buf; +} + + +/* Decode a string encoded with URL encoding. */ +char *cburldecode(const char *str, int *sp){ + char *buf, *wp; + unsigned char c; + CB_MEMDUP(buf, str, strlen(str)); + wp = buf; + while(*str != '\0'){ + if(*str == '%'){ + str++; + if(((str[0] >= '0' && str[0] <= '9') || (str[0] >= 'A' && str[0] <= 'F') || + (str[0] >= 'a' && str[0] <= 'f')) && + ((str[1] >= '0' && str[1] <= '9') || (str[1] >= 'A' && str[1] <= 'F') || + (str[1] >= 'a' && str[1] <= 'f'))){ + c = *str; + if(c >= 'A' && c <= 'Z') c += 'a' - 'A'; + if(c >= 'a' && c <= 'z'){ + *wp = c - 'a' + 10; + } else { + *wp = c - '0'; + } + *wp *= 0x10; + str++; + c = *str; + if(c >= 'A' && c <= 'Z') c += 'a' - 'A'; + if(c >= 'a' && c <= 'z'){ + *wp += c - 'a' + 10; + } else { + *wp += c - '0'; + } + str++; + wp++; + } else { + break; + } + } else if(*str == '+'){ + *wp = ' '; + str++; + wp++; + } else { + *wp = *str; + str++; + wp++; + } + } + *wp = '\0'; + if(sp) *sp = wp - buf; + return buf; +} + + +/* Encode a serial object with Base64 encoding. */ +char *cbbaseencode(const char *ptr, int size){ + char *tbl = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; + char *buf, *wp; + const unsigned char *obj; + int i; + assert(ptr); + if(size < 0) size = strlen(ptr); + CB_MALLOC(buf, 4 * (size + 2) / 3 + 1); + obj = (const unsigned char *)ptr; + wp = buf; + for(i = 0; i < size; i += 3){ + switch(size - i){ + case 1: + *wp++ = tbl[obj[0] >> 2]; + *wp++ = tbl[(obj[0] & 3) << 4]; + *wp++ = '='; + *wp++ = '='; + break; + case 2: + *wp++ = tbl[obj[0] >> 2]; + *wp++ = tbl[((obj[0] & 3) << 4) + (obj[1] >> 4)]; + *wp++ = tbl[(obj[1] & 0xf) << 2]; + *wp++ = '='; + break; + default: + *wp++ = tbl[obj[0] >> 2]; + *wp++ = tbl[((obj[0] & 3) << 4) + (obj[1] >> 4)]; + *wp++ = tbl[((obj[1] & 0xf) << 2) + (obj[2] >> 6)]; + *wp++ = tbl[obj[2] & 0x3f]; + break; + } + obj += 3; + } + *wp = '\0'; + return buf; +} + + +/* Decode a string encoded with Base64 encoding. */ +char *cbbasedecode(const char *str, int *sp){ + unsigned char *obj, *wp; + int len, cnt, bpos, i, bits, eqcnt; + assert(str); + cnt = 0; + bpos = 0; + eqcnt = 0; + len = strlen(str); + CB_MALLOC(obj, len + 4); + wp = obj; + while(bpos < len && eqcnt == 0){ + bits = 0; + for(i = 0; bpos < len && i < 4; bpos++){ + if(str[bpos] >= 'A' && str[bpos] <= 'Z'){ + bits = (bits << 6) | (str[bpos] - 'A'); + i++; + } else if(str[bpos] >= 'a' && str[bpos] <= 'z'){ + bits = (bits << 6) | (str[bpos] - 'a' + 26); + i++; + } else if(str[bpos] >= '0' && str[bpos] <= '9'){ + bits = (bits << 6) | (str[bpos] - '0' + 52); + i++; + } else if(str[bpos] == '+'){ + bits = (bits << 6) | 62; + i++; + } else if(str[bpos] == '/'){ + bits = (bits << 6) | 63; + i++; + } else if(str[bpos] == '='){ + bits <<= 6; + i++; + eqcnt++; + } + } + if(i == 0 && bpos >= len) continue; + switch(eqcnt){ + case 0: + *wp++ = (bits >> 16) & 0xff; + *wp++ = (bits >> 8) & 0xff; + *wp++ = bits & 0xff; + cnt += 3; + break; + case 1: + *wp++ = (bits >> 16) & 0xff; + *wp++ = (bits >> 8) & 0xff; + cnt += 2; + break; + case 2: + *wp++ = (bits >> 16) & 0xff; + cnt += 1; + break; + } + } + obj[cnt] = '\0'; + if(sp) *sp = cnt; + return (char *)obj; +} + + +/* Encode a serial object with quoted-printable encoding. */ +char *cbquoteencode(const char *ptr, int size){ + const unsigned char *rp; + char *buf, *wp; + int i, cols; + assert(ptr); + if(size < 0) size = strlen(ptr); + rp = (const unsigned char *)ptr; + CB_MALLOC(buf, size * 3 + 1); + wp = buf; + cols = 0; + for(i = 0; i < size; i++){ + if(rp[i] == '=' || (rp[i] < 0x20 && rp[i] != '\r' && rp[i] != '\n' && rp[i] != '\t') || + rp[i] > 0x7e){ + wp += sprintf(wp, "=%02X", rp[i]); + cols += 3; + } else { + *(wp++) = rp[i]; + cols++; + } + } + *wp = '\0'; + return buf; +} + + +/* Decode a string encoded with quoted-printable encoding. */ +char *cbquotedecode(const char *str, int *sp){ + char *buf, *wp; + assert(str); + CB_MALLOC(buf, strlen(str) + 1); + wp = buf; + for(; *str != '\0'; str++){ + if(*str == '='){ + str++; + if(*str == '\0'){ + break; + } else if(str[0] == '\r' && str[1] == '\n'){ + str++; + } else if(str[0] != '\n' && str[0] != '\r'){ + if(*str >= 'A' && *str <= 'Z'){ + *wp = (*str - 'A' + 10) * 16; + } else if(*str >= 'a' && *str <= 'z'){ + *wp = (*str - 'a' + 10) * 16; + } else { + *wp = (*str - '0') * 16; + } + str++; + if(*str == '\0') break; + if(*str >= 'A' && *str <= 'Z'){ + *wp += *str - 'A' + 10; + } else if(*str >= 'a' && *str <= 'z'){ + *wp += *str - 'a' + 10; + } else { + *wp += *str - '0'; + } + wp++; + } + } else { + *wp = *str; + wp++; + } + } + *wp = '\0'; + if(sp) *sp = wp - buf; + return buf; +} + + +/* Split a string of MIME into headers and the body. */ +char *cbmimebreak(const char *ptr, int size, CBMAP *attrs, int *sp){ + CBLIST *list; + const char *head, *line, *pv, *ep; + char *hbuf, *name, *rv; + int i, j, wi, hlen; + assert(ptr); + if(size < 0) size = strlen(ptr); + head = NULL; + hlen = 0; + for(i = 0; i < size; i++){ + if(i < size - 4 && ptr[i] == '\r' && ptr[i+1] == '\n' && + ptr[i+2] == '\r' && ptr[i+3] == '\n'){ + head = ptr; + hlen = i; + ptr += i + 4; + size -= i + 4; + break; + } else if(i < size - 2 && ptr[i] == '\n' && ptr[i+1] == '\n'){ + head = ptr; + hlen = i; + ptr += i + 2; + size -= i + 2; + break; + } + } + if(head && attrs){ + CB_MALLOC(hbuf, hlen + 1); + wi = 0; + for(i = 0; i < hlen; i++){ + if(head[i] == '\r') continue; + if(i < hlen - 1 && head[i] == '\n' && (head[i+1] == ' ' || head[i+1] == '\t')){ + hbuf[wi++] = ' '; + i++; + } else { + hbuf[wi++] = head[i]; + } + } + list = cbsplit(hbuf, wi, "\n"); + for(i = 0; i < CB_LISTNUM(list); i++){ + line = CB_LISTVAL(list, i); + if((pv = strchr(line, ':')) != NULL){ + CB_MEMDUP(name, line, pv - line); + for(j = 0; name[j] != '\0'; j++){ + if(name[j] >= 'A' && name[j] <= 'Z') name[j] -= 'A' - 'a'; + } + pv++; + while(*pv == ' ' || *pv == '\t'){ + pv++; + } + cbmapput(attrs, name, -1, pv, -1, TRUE); + free(name); + } + + } + CB_LISTCLOSE(list); + free(hbuf); + if((pv = cbmapget(attrs, "content-type", -1, NULL)) != NULL){ + if((ep = strchr(pv, ';')) != NULL){ + cbmapput(attrs, "TYPE", -1, pv, ep - pv, TRUE); + do { + ep++; + while(ep[0] == ' '){ + ep++; + } + if(cbstrfwimatch(ep, "charset=")){ + ep += 8; + while(*ep > '\0' && *ep <= ' '){ + ep++; + } + if(ep[0] == '"') ep++; + pv = ep; + while(ep[0] != '\0' && ep[0] != ' ' && ep[0] != '"' && ep[0] != ';'){ + ep++; + } + cbmapput(attrs, "CHARSET", -1, pv, ep - pv, TRUE); + } else if(cbstrfwimatch(ep, "boundary=")){ + ep += 9; + while(*ep > '\0' && *ep <= ' '){ + ep++; + } + if(ep[0] == '"'){ + ep++; + pv = ep; + while(ep[0] != '\0' && ep[0] != '"'){ + ep++; + } + } else { + pv = ep; + while(ep[0] != '\0' && ep[0] != ' ' && ep[0] != '"' && ep[0] != ';'){ + ep++; + } + } + cbmapput(attrs, "BOUNDARY", -1, pv, ep - pv, TRUE); + } + } while((ep = strchr(ep, ';')) != NULL); + } else { + cbmapput(attrs, "TYPE", -1, pv, -1, TRUE); + } + } + if((pv = cbmapget(attrs, "content-disposition", -1, NULL)) != NULL){ + if((ep = strchr(pv, ';')) != NULL){ + cbmapput(attrs, "DISPOSITION", -1, pv, ep - pv, TRUE); + do { + ep++; + while(ep[0] == ' '){ + ep++; + } + if(cbstrfwimatch(ep, "filename=")){ + ep += 9; + if(ep[0] == '"') ep++; + pv = ep; + while(ep[0] != '\0' && ep[0] != '"'){ + ep++; + } + cbmapput(attrs, "FILENAME", -1, pv, ep - pv, TRUE); + } else if(cbstrfwimatch(ep, "name=")){ + ep += 5; + if(ep[0] == '"') ep++; + pv = ep; + while(ep[0] != '\0' && ep[0] != '"'){ + ep++; + } + cbmapput(attrs, "NAME", -1, pv, ep - pv, TRUE); + } + } while((ep = strchr(ep, ';')) != NULL); + } else { + cbmapput(attrs, "DISPOSITION", -1, pv, -1, TRUE); + } + } + } + if(sp) *sp = size; + CB_MEMDUP(rv, ptr, size); + return rv; +} + + +/* Split multipart data in MIME into its parts. */ +CBLIST *cbmimeparts(const char *ptr, int size, const char *boundary){ + CBLIST *list; + const char *pv, *ep; + int i, blen; + assert(ptr && boundary); + if(size < 0) size = strlen(ptr); + CB_LISTOPEN(list); + if((blen = strlen(boundary)) < 1) return list; + pv = NULL; + for(i = 0; i < size; i++){ + if(ptr[i] == '-' && ptr[i+1] == '-' && i + 2 + blen < size && + cbstrfwmatch(ptr + i + 2, boundary) && strchr("\t\n\v\f\r ", ptr[i+2+blen])){ + pv = ptr + i + 2 + blen; + if(*pv == '\r') pv++; + if(*pv == '\n') pv++; + size -= pv - ptr; + ptr = pv; + break; + } + } + if(!pv) return list; + for(i = 0; i < size; i++){ + if(ptr[i] == '-' && ptr[i+1] == '-' && i + 2 + blen < size && + cbstrfwmatch(ptr + i + 2, boundary) && strchr("\t\n\v\f\r -", ptr[i+2+blen])){ + ep = ptr + i; + if(ep > ptr && ep[-1] == '\n') ep--; + if(ep > ptr && ep[-1] == '\r') ep--; + if(ep > pv) CB_LISTPUSH(list, pv, ep - pv); + pv = ptr + i + 2 + blen; + if(*pv == '\r') pv++; + if(*pv == '\n') pv++; + } + } + return list; +} + + +/* Encode a string with MIME encoding. */ +char *cbmimeencode(const char *str, const char *encname, int base){ + char *buf, *wp, *enc; + int len; + assert(str && encname); + len = strlen(str); + CB_MALLOC(buf, len * 3 + strlen(encname) + 16); + wp = buf; + wp += sprintf(wp, "=?%s?%c?", encname, base ? 'B' : 'Q'); + enc = base ? cbbaseencode(str, len) : cbquoteencode(str, len); + wp += sprintf(wp, "%s?=", enc); + free(enc); + return buf; +} + + +/* Decode a string encoded with MIME encoding. */ +char *cbmimedecode(const char *str, char *enp){ + char *buf, *wp, *tmp, *dec; + const char *pv, *ep; + int quoted; + assert(str); + if(enp) sprintf(enp, "US-ASCII"); + CB_MALLOC(buf, strlen(str) + 1); + wp = buf; + while(*str != '\0'){ + if(cbstrfwmatch(str, "=?")){ + str += 2; + pv = str; + if(!(ep = strchr(str, '?'))) continue; + if(enp && ep - pv < CB_ENCBUFSIZ){ + memcpy(enp, pv, ep - pv); + enp[ep-pv] = '\0'; + } + pv = ep + 1; + quoted = (*pv == 'Q' || *pv == 'q'); + if(*pv != '\0') pv++; + if(*pv != '\0') pv++; + if(!(ep = strchr(pv, '?'))) continue; + CB_MEMDUP(tmp, pv, ep - pv); + dec = quoted ? cbquotedecode(tmp, NULL) : cbbasedecode(tmp, NULL); + wp += sprintf(wp, "%s", dec); + free(dec); + free(tmp); + str = ep + 1; + if(*str != '\0') str++; + } else { + *(wp++) = *str; + str++; + } + } + *wp = '\0'; + return buf; +} + + +/* Split a string of CSV into rows. */ +CBLIST *cbcsvrows(const char *str){ + CBLIST *list; + const char *pv; + int quoted; + assert(str); + CB_LISTOPEN(list); + pv = str; + quoted = FALSE; + while(TRUE){ + if(*str == '"') quoted = !quoted; + if(!quoted && (*str == '\r' || *str == '\n')){ + CB_LISTPUSH(list, pv, str - pv); + if(str[0] == '\r' && str[1] == '\n') str++; + str++; + pv = str; + } else if(*str == '\0'){ + if(str > pv) CB_LISTPUSH(list, pv, str - pv); + break; + } else { + str++; + } + } + return list; +} + + +/* Split a string of a row of CSV into cells. */ +CBLIST *cbcsvcells(const char *str){ + CBLIST *list, *uelist; + const char *pv; + char *tmp; + int i, quoted; + assert(str); + CB_LISTOPEN(list); + pv = str; + quoted = FALSE; + while(TRUE){ + if(*str == '"') quoted = !quoted; + if(!quoted && *str == ','){ + CB_LISTPUSH(list, pv, str - pv); + str++; + pv = str; + } else if(*str == '\0'){ + CB_LISTPUSH(list, pv, str - pv); + break; + } else { + str++; + } + } + CB_LISTOPEN(uelist); + for(i = 0; i < CB_LISTNUM(list); i++){ + tmp = cbcsvunescape(CB_LISTVAL(list, i)); + CB_LISTPUSH(uelist, tmp, strlen(tmp)); + free(tmp); + } + CB_LISTCLOSE(list); + return uelist; +} + + +/* Escape a string with the meta characters of CSV. */ +char *cbcsvescape(const char *str){ + char *buf, *wp; + int i; + assert(str); + CB_MALLOC(buf, strlen(str) * 2 + 3); + wp = buf; + *(wp++) = '"'; + for(i = 0; str[i] != '\0'; i++){ + if(str[i] == '"') *(wp++) = '"'; + *(wp++) = str[i]; + } + *(wp++) = '"'; + *wp = '\0'; + return buf; +} + + +/* Unescape a string with the escaped meta characters of CSV. */ +char *cbcsvunescape(const char *str){ + char *buf, *wp; + int i, len; + assert(str); + len = strlen(str); + if(str[0] == '"'){ + str++; + len--; + if(str[len-1] == '"') len--; + } + CB_MALLOC(buf, len + 1); + wp = buf; + for(i = 0; i < len; i++){ + if(str[i] == '"'){ + if(str[i+1] == '"') *(wp++) = str[i++]; + } else { + *(wp++) = str[i]; + } + } + *wp = '\0'; + return buf; +} + + +/* Split a string of XML into tags and text sections. */ +CBLIST *cbxmlbreak(const char *str, int cr){ + CBLIST *list; + CBDATUM *datum; + int i, pv, tag; + char *ep; + assert(str); + CB_LISTOPEN(list); + i = 0; + pv = 0; + tag = FALSE; + while(TRUE){ + if(str[i] == '\0'){ + if(i > pv) CB_LISTPUSH(list, str + pv, i - pv); + break; + } else if(!tag && str[i] == '<'){ + if(str[i+1] == '!' && str[i+2] == '-' && str[i+3] == '-'){ + if(i > pv) CB_LISTPUSH(list, str + pv, i - pv); + if((ep = strstr(str + i, "-->")) != NULL){ + if(!cr) CB_LISTPUSH(list, str + i, ep - str - i + 3); + i = ep - str + 2; + pv = i + 1; + } + } else if(str[i+1] == '!' && str[i+2] == '[' && cbstrfwimatch(str + i, "<![CDATA[")){ + if(i > pv) CB_LISTPUSH(list, str + pv, i - pv); + if((ep = strstr(str + i, "]]>")) != NULL){ + i += 9; + CB_DATUMOPEN(datum); + while(str + i < ep){ + if(str[i] == '&'){ + CB_DATUMCAT(datum, "&", 5); + } else if(str[i] == '<'){ + CB_DATUMCAT(datum, "<", 4); + } else if(str[i] == '>'){ + CB_DATUMCAT(datum, ">", 4); + } else { + CB_DATUMCAT(datum, str + i, 1); + } + i++; + } + if(CB_DATUMSIZE(datum) > 0) CB_LISTPUSH(list, CB_DATUMPTR(datum), CB_DATUMSIZE(datum)); + CB_DATUMCLOSE(datum); + i = ep - str + 2; + pv = i + 1; + } + } else { + if(i > pv) CB_LISTPUSH(list, str + pv, i - pv); + tag = TRUE; + pv = i; + } + } else if(tag && str[i] == '>'){ + if(i > pv) CB_LISTPUSH(list, str + pv, i - pv + 1); + tag = FALSE; + pv = i + 1; + } + i++; + } + return list; +} + + +/* Get the map of attributes of a XML tag. */ +CBMAP *cbxmlattrs(const char *str){ + CBMAP *map; + const unsigned char *rp, *key, *val; + char *copy, *raw; + int ksiz, vsiz; + assert(str); + map = cbmapopenex(CB_MAPPBNUM); + rp = (unsigned char *)str; + while(*rp == '<' || *rp == '/' || *rp == '?' || *rp == '!' || *rp == ' '){ + rp++; + } + key = rp; + while(*rp > 0x20 && *rp != '/' && *rp != '>'){ + rp++; + } + cbmapput(map, "", -1, (char *)key, rp - key, FALSE); + while(*rp != '\0'){ + while(*rp != '\0' && (*rp <= 0x20 || *rp == '/' || *rp == '?' || *rp == '>')){ + rp++; + } + key = rp; + while(*rp > 0x20 && *rp != '/' && *rp != '>' && *rp != '='){ + rp++; + } + ksiz = rp - key; + while(*rp != '\0' && (*rp == '=' || *rp <= 0x20)){ + rp++; + } + if(*rp == '"'){ + rp++; + val = rp; + while(*rp != '\0' && *rp != '"'){ + rp++; + } + vsiz = rp - val; + } else if(*rp == '\''){ + rp++; + val = rp; + while(*rp != '\0' && *rp != '\''){ + rp++; + } + vsiz = rp - val; + } else { + val = rp; + while(*rp > 0x20 && *rp != '"' && *rp != '\'' && *rp != '>'){ + rp++; + } + vsiz = rp - val; + } + if(*rp != '\0') rp++; + if(ksiz > 0){ + CB_MEMDUP(copy, (char *)val, vsiz); + raw = cbxmlunescape(copy); + cbmapput(map, (char *)key, ksiz, raw, -1, FALSE); + free(raw); + free(copy); + } + } + return map; +} + + +/* Escape a string with the meta characters of XML. */ +char *cbxmlescape(const char *str){ + CBDATUM *datum; + assert(str); + CB_DATUMOPEN(datum); + while(*str != '\0'){ + switch(*str){ + case '&': + CB_DATUMCAT(datum, "&", 5); + break; + case '<': + CB_DATUMCAT(datum, "<", 4); + break; + case '>': + CB_DATUMCAT(datum, ">", 4); + break; + case '"': + CB_DATUMCAT(datum, """, 6); + break; + case '\'': + CB_DATUMCAT(datum, "'", 6); + break; + default: + CB_DATUMCAT(datum, str, 1); + break; + } + str++; + } + return cbdatumtomalloc(datum, NULL); +} + + +/* Unescape a string with the entity references of XML. */ +char *cbxmlunescape(const char *str){ + CBDATUM *datum; + assert(str); + CB_DATUMOPEN(datum); + while(*str != '\0'){ + if(*str == '&'){ + if(cbstrfwmatch(str, "&")){ + CB_DATUMCAT(datum, "&", 1); + str += 5; + } else if(cbstrfwmatch(str, "<")){ + CB_DATUMCAT(datum, "<", 1); + str += 4; + } else if(cbstrfwmatch(str, ">")){ + CB_DATUMCAT(datum, ">", 1); + str += 4; + } else if(cbstrfwmatch(str, """)){ + CB_DATUMCAT(datum, "\"", 1); + str += 6; + } else if(cbstrfwmatch(str, "'")){ + CB_DATUMCAT(datum, "'", 1); + str += 6; + } else { + CB_DATUMCAT(datum, str, 1); + str++; + } + } else { + CB_DATUMCAT(datum, str, 1); + str++; + } + } + return cbdatumtomalloc(datum, NULL); +} + + +/* Compress a serial object with ZLIB. */ +char *cbdeflate(const char *ptr, int size, int *sp){ + assert(ptr && sp); + if(!_qdbm_deflate) return NULL; + return _qdbm_deflate(ptr, size, sp, _QDBM_ZMZLIB); +} + + +/* Decompress a serial object compressed with ZLIB. */ +char *cbinflate(const char *ptr, int size, int *sp){ + assert(ptr && size >= 0); + if(!_qdbm_inflate) return NULL; + return _qdbm_inflate(ptr, size, sp, _QDBM_ZMZLIB); +} + + +/* Compress a serial object with GZIP. */ +char *cbgzencode(const char *ptr, int size, int *sp){ + assert(ptr && sp); + if(!_qdbm_deflate) return NULL; + return _qdbm_deflate(ptr, size, sp, _QDBM_ZMGZIP); +} + + +/* Decompress a serial object compressed with GZIP. */ +char *cbgzdecode(const char *ptr, int size, int *sp){ + assert(ptr && size >= 0); + if(!_qdbm_inflate) return NULL; + return _qdbm_inflate(ptr, size, sp, _QDBM_ZMGZIP); +} + + +/* Get the CRC32 checksum of a serial object. */ +unsigned int cbgetcrc(const char *ptr, int size){ + assert(ptr); + if(!_qdbm_inflate) return 0; + return _qdbm_getcrc(ptr, size); +} + + +/* Compress a serial object with LZO. */ +char *cblzoencode(const char *ptr, int size, int *sp){ + assert(ptr && sp); + if(!_qdbm_lzoencode) return NULL; + return _qdbm_lzoencode(ptr, size, sp); +} + + +/* Decompress a serial object compressed with LZO. */ +char *cblzodecode(const char *ptr, int size, int *sp){ + assert(ptr && size >= 0); + if(!_qdbm_lzodecode) return NULL; + return _qdbm_lzodecode(ptr, size, sp); +} + + +/* Compress a serial object with BZIP2. */ +char *cbbzencode(const char *ptr, int size, int *sp){ + assert(ptr && sp); + if(!_qdbm_bzencode) return NULL; + return _qdbm_bzencode(ptr, size, sp); +} + + +/* Decompress a serial object compressed with BZIP2. */ +char *cbbzdecode(const char *ptr, int size, int *sp){ + assert(ptr && size >= 0); + if(!_qdbm_bzdecode) return NULL; + return _qdbm_bzdecode(ptr, size, sp); +} + + +/* Convert the character encoding of a string. */ +char *cbiconv(const char *ptr, int size, const char *icode, const char *ocode, int *sp, int *mp){ + char *res; + assert(ptr && icode && ocode); + if(!_qdbm_iconv) return NULL; + if((res = _qdbm_iconv(ptr, size, icode, ocode, sp, mp)) != NULL) return res; + if(!cbstricmp(icode, ocode)){ + if(sp) *sp = size; + if(mp) *mp = 0; + CB_MEMDUP(res, ptr, size < 0 ? strlen(ptr) : size); + return res; + } + return NULL; +} + + +/* Detect the encoding of a string automatically. */ +const char *cbencname(const char *ptr, int size){ + assert(ptr); + if(!_qdbm_encname) return "ISO-8859-1"; + return _qdbm_encname(ptr, size); +} + + +/* Get the jet lag of the local time in seconds. */ +int cbjetlag(void){ + struct tm ts, *tp; + time_t t, gt, lt; + if((t = time(NULL)) < 0) return 0; + if(!(tp = _qdbm_gmtime(&t, &ts))) return 0; + if((gt = mktime(tp)) < 0) return 0; + if(!(tp = _qdbm_localtime(&t, &ts))) return 0; + if((lt = mktime(tp)) < 0) return 0; + return lt - gt; +} + + +/* Get the Gregorian calendar of a time. */ +void cbcalendar(time_t t, int jl, int *yearp, int *monp, int *dayp, + int *hourp, int *minp, int *secp){ + struct tm ts, *tp; + if(t < 0) t = time(NULL); + t += jl; + if(!(tp = _qdbm_gmtime(&t, &ts))) return; + if(yearp) *yearp = tp->tm_year + 1900; + if(monp) *monp = tp->tm_mon + 1; + if(dayp) *dayp = tp->tm_mday; + if(hourp) *hourp = tp->tm_hour; + if(minp) *minp = tp->tm_min; + if(secp) *secp = tp->tm_sec; +} + + +/* Get the day of week of a date. */ +int cbdayofweek(int year, int mon, int day){ + if(mon < 3){ + year--; + mon += 12; + } + return (day + ((8 + (13 * mon)) / 5) + (year + (year / 4) - (year / 100) + (year / 400))) % 7; +} + + +/* Get the string for a date in W3CDTF. */ +char *cbdatestrwww(time_t t, int jl){ + char date[CB_DATEBUFSIZ], tzone[CB_DATEBUFSIZ], *rv; + int year, mon, day, hour, min, sec; + cbcalendar(t, jl, &year, &mon, &day, &hour, &min, &sec); + jl /= 60; + if(jl == 0){ + sprintf(tzone, "Z"); + } else if(jl < 0){ + jl *= -1; + sprintf(tzone, "-%02d:%02d", jl / 60, jl % 60); + } else { + sprintf(tzone, "+%02d:%02d", jl / 60, jl % 60); + } + sprintf(date, "%04d-%02d-%02dT%02d:%02d:%02d%s", year, mon, day, hour, min, sec, tzone); + CB_MEMDUP(rv, date, strlen(date)); + return rv; +} + + +/* Get the string for a date in RFC 1123 format. */ +char *cbdatestrhttp(time_t t, int jl){ + char date[CB_DATEBUFSIZ], *wp, *rv; + int year, mon, day, hour, min, sec; + cbcalendar(t, jl, &year, &mon, &day, &hour, &min, &sec); + jl /= 60; + wp = date; + switch(cbdayofweek(year, mon, day)){ + case 0: wp += sprintf(wp, "Sun, "); break; + case 1: wp += sprintf(wp, "Mon, "); break; + case 2: wp += sprintf(wp, "Tue, "); break; + case 3: wp += sprintf(wp, "Wed, "); break; + case 4: wp += sprintf(wp, "Thu, "); break; + case 5: wp += sprintf(wp, "Fri, "); break; + case 6: wp += sprintf(wp, "Sat, "); break; + } + wp += sprintf(wp, "%02d ", day); + switch(mon){ + case 1: wp += sprintf(wp, "Jan "); break; + case 2: wp += sprintf(wp, "Feb "); break; + case 3: wp += sprintf(wp, "Mar "); break; + case 4: wp += sprintf(wp, "Apr "); break; + case 5: wp += sprintf(wp, "May "); break; + case 6: wp += sprintf(wp, "Jun "); break; + case 7: wp += sprintf(wp, "Jul "); break; + case 8: wp += sprintf(wp, "Aug "); break; + case 9: wp += sprintf(wp, "Sep "); break; + case 10: wp += sprintf(wp, "Oct "); break; + case 11: wp += sprintf(wp, "Nov "); break; + case 12: wp += sprintf(wp, "Dec "); break; + } + wp += sprintf(wp, "%04d %02d:%02d:%02d ", year, hour, min, sec); + if(jl == 0){ + wp += sprintf(wp, "GMT"); + } else if(jl < 0){ + jl *= -1; + wp += sprintf(wp, "-%02d%02d", jl / 60, jl % 60); + } else { + wp += sprintf(wp, "+%02d%02d", jl / 60, jl % 60); + } + CB_MEMDUP(rv, date, strlen(date)); + return rv; +} + + +/* Get the time value of a date string in decimal, W3CDTF, or RFC 1123. */ +time_t cbstrmktime(const char *str){ + const char *crp; + char *pv, *rp; + int len, clen; + time_t t; + struct tm ts; + assert(str); + while(*str > '\0' && *str <= ' '){ + str++; + } + if(*str == '\0') return -1; + if(str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) return (time_t)strtol(str + 2, NULL, 16); + memset(&ts, 0, sizeof(struct tm)); + ts.tm_year = 70; + ts.tm_mon = 0; + ts.tm_mday = 1; + ts.tm_hour = 0; + ts.tm_min = 0; + ts.tm_sec = 0; + ts.tm_isdst = 0; + len = strlen(str); + t = (time_t)strtol(str, &pv, 10); + if(*(signed char *)pv >= '\0' && *pv <= ' '){ + while(*pv > '\0' && *pv <= ' '){ + pv++; + } + if(*pv == '\0') return t; + } + if((pv[0] == 's' || pv[0] == 'S') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ') + return t; + if((pv[0] == 'm' || pv[0] == 'M') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ') + return t * 60; + if((pv[0] == 'h' || pv[0] == 'H') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ') + return t * 60 * 60; + if((pv[0] == 'd' || pv[0] == 'D') && ((signed char *)pv)[1] >= '\0' && pv[1] <= ' ') + return t * 60 * 60 * 24; + if(len > 4 && str[4] == '-'){ + ts.tm_year = atoi(str) - 1900; + if((pv = strchr(str, '-')) != NULL && pv - str == 4){ + rp = pv + 1; + ts.tm_mon = atoi(rp) - 1; + if((pv = strchr(rp, '-')) != NULL && pv - str == 7){ + rp = pv + 1; + ts.tm_mday = atoi(rp); + if((pv = strchr(rp, 'T')) != NULL && pv - str == 10){ + rp = pv + 1; + ts.tm_hour = atoi(rp); + if((pv = strchr(rp, ':')) != NULL && pv - str == 13){ + rp = pv + 1; + ts.tm_min = atoi(rp); + } + if((pv = strchr(rp, ':')) != NULL && pv - str == 16){ + rp = pv + 1; + ts.tm_sec = atoi(rp); + } + if((pv = strchr(rp, '.')) != NULL && pv - str >= 19) rp = pv + 1; + strtol(rp, &pv, 10); + if((*pv == '+' || *pv == '-') && strlen(pv) >= 6 && pv[3] == ':') + ts.tm_sec -= (atoi(pv + 1) * 3600 + atoi(pv + 4) * 60) * (pv[0] == '+' ? 1 : -1); + } + } + } + ts.tm_sec += cbjetlag(); + return mktime(&ts); + } + if(len > 4 && str[4] == '/'){ + ts.tm_year = atoi(str) - 1900; + if((pv = strchr(str, '/')) != NULL && pv - str == 4){ + rp = pv + 1; + ts.tm_mon = atoi(rp) - 1; + if((pv = strchr(rp, '/')) != NULL && pv - str == 7){ + rp = pv + 1; + ts.tm_mday = atoi(rp); + if((pv = strchr(rp, ' ')) != NULL && pv - str == 10){ + rp = pv + 1; + ts.tm_hour = atoi(rp); + if((pv = strchr(rp, ':')) != NULL && pv - str == 13){ + rp = pv + 1; + ts.tm_min = atoi(rp); + } + if((pv = strchr(rp, ':')) != NULL && pv - str == 16){ + rp = pv + 1; + ts.tm_sec = atoi(rp); + } + if((pv = strchr(rp, '.')) != NULL && pv - str >= 19) rp = pv + 1; + strtol(rp, &pv, 10); + if((*pv == '+' || *pv == '-') && strlen(pv) >= 6 && pv[3] == ':') + ts.tm_sec -= (atoi(pv + 1) * 3600 + atoi(pv + 4) * 60) * (pv[0] == '+' ? 1 : -1); + } + } + } + ts.tm_sec += cbjetlag(); + return mktime(&ts); + } + crp = str; + if(len >= 4 && str[3] == ',') crp = str + 4; + while(*crp == ' '){ + crp++; + } + ts.tm_mday = atoi(crp); + while((*crp >= '0' && *crp <= '9') || *crp == ' '){ + crp++; + } + if(cbstrfwimatch(crp, "Jan")){ + ts.tm_mon = 0; + } else if(cbstrfwimatch(crp, "Feb")){ + ts.tm_mon = 1; + } else if(cbstrfwimatch(crp, "Mar")){ + ts.tm_mon = 2; + } else if(cbstrfwimatch(crp, "Apr")){ + ts.tm_mon = 3; + } else if(cbstrfwimatch(crp, "May")){ + ts.tm_mon = 4; + } else if(cbstrfwimatch(crp, "Jun")){ + ts.tm_mon = 5; + } else if(cbstrfwimatch(crp, "Jul")){ + ts.tm_mon = 6; + } else if(cbstrfwimatch(crp, "Aug")){ + ts.tm_mon = 7; + } else if(cbstrfwimatch(crp, "Sep")){ + ts.tm_mon = 8; + } else if(cbstrfwimatch(crp, "Oct")){ + ts.tm_mon = 9; + } else if(cbstrfwimatch(crp, "Nov")){ + ts.tm_mon = 10; + } else if(cbstrfwimatch(crp, "Dec")){ + ts.tm_mon = 11; + } else { + ts.tm_mon = -1; + } + if(ts.tm_mon >= 0) crp += 3; + while(*crp == ' '){ + crp++; + } + ts.tm_year = atoi(crp); + if(ts.tm_year >= 1969) ts.tm_year -= 1900; + while(*crp >= '0' && *crp <= '9'){ + crp++; + } + while(*crp == ' '){ + crp++; + } + if(ts.tm_mday > 0 && ts.tm_mon >= 0 && ts.tm_year >= 0){ + clen = strlen(crp); + if(clen >= 8 && crp[2] == ':' && crp[5] == ':'){ + ts.tm_hour = atoi(crp + 0); + ts.tm_min = atoi(crp + 3); + ts.tm_sec = atoi(crp + 6); + if(clen >= 14 && crp[8] == ' ' && (crp[9] == '+' || crp[9] == '-')){ + ts.tm_sec -= ((crp[10] - '0') * 36000 + (crp[11] - '0') * 3600 + + (crp[12] - '0') * 600 + (crp[13] - '0') * 60) * (crp[9] == '+' ? 1 : -1); + } else if(clen > 9){ + if(!strcmp(crp + 9, "JST")){ + ts.tm_sec -= 9 * 3600; + } else if(!strcmp(crp + 9, "CCT")){ + ts.tm_sec -= 8 * 3600; + } else if(!strcmp(crp + 9, "KST")){ + ts.tm_sec -= 9 * 3600; + } else if(!strcmp(crp + 9, "EDT")){ + ts.tm_sec -= -4 * 3600; + } else if(!strcmp(crp + 9, "EST")){ + ts.tm_sec -= -5 * 3600; + } else if(!strcmp(crp + 9, "CDT")){ + ts.tm_sec -= -5 * 3600; + } else if(!strcmp(crp + 9, "CST")){ + ts.tm_sec -= -6 * 3600; + } else if(!strcmp(crp + 9, "MDT")){ + ts.tm_sec -= -6 * 3600; + } else if(!strcmp(crp + 9, "MST")){ + ts.tm_sec -= -7 * 3600; + } else if(!strcmp(crp + 9, "PDT")){ + ts.tm_sec -= -7 * 3600; + } else if(!strcmp(crp + 9, "PST")){ + ts.tm_sec -= -8 * 3600; + } else if(!strcmp(crp + 9, "HDT")){ + ts.tm_sec -= -9 * 3600; + } else if(!strcmp(crp + 9, "HST")){ + ts.tm_sec -= -10 * 3600; + } + } + } + ts.tm_sec += cbjetlag(); + return mktime(&ts); + } + return -1; +} + + +/* Get user and system processing times. */ +void cbproctime(double *usrp, double *sysp){ + struct tms buf; + times(&buf); + if(usrp) *usrp = (double)buf.tms_utime / sysconf(_SC_CLK_TCK); + if(sysp) *sysp = (double)buf.tms_stime / sysconf(_SC_CLK_TCK); +} + + +/* Ensure that the standard I/O is binary mode. */ +void cbstdiobin(void){ + if(setmode(0, O_BINARY) == -1 || setmode(1, O_BINARY) == -1 || setmode(2, O_BINARY) == -1) + cbmyfatal("setmode failed"); +} + + + +/************************************************************************************************* + * features for experts + *************************************************************************************************/ + + +/* Show error message on the standard error output and exit. */ +void *cbmyfatal(const char *message){ + char buf[CB_MSGBUFSIZ]; + assert(message); + if(cbfatalfunc){ + cbfatalfunc(message); + } else { + sprintf(buf, "fatal error: %s\n", message); + write(2, buf, strlen(buf)); + } + exit(1); + return NULL; +} + + +/* Create a datum handle from an allocated region. */ +CBDATUM *cbdatumopenbuf(char *ptr, int size){ + CBDATUM *datum; + assert(ptr && size >= 0); + CB_REALLOC(ptr, size + 1); + CB_MALLOC(datum, sizeof(*datum)); + datum->dptr = ptr; + datum->dptr[size] = '\0'; + datum->dsize = size; + datum->asize = size; + return datum; +} + + +/* Set a buffer to a datum handle. */ +void cbdatumsetbuf(CBDATUM *datum, char *ptr, int size){ + assert(datum && ptr && size >= 0); + free(datum->dptr); + CB_REALLOC(ptr, size + 1); + datum->dptr = ptr; + datum->dptr[size] = '\0'; + datum->dsize = size; + datum->asize = size; +} + + +/* Add an allocated element at the end of a list. */ +void cblistpushbuf(CBLIST *list, char *ptr, int size){ + int index; + assert(list && ptr && size >= 0); + index = list->start + list->num; + if(index >= list->anum){ + list->anum *= 2; + CB_REALLOC(list->array, list->anum * sizeof(list->array[0])); + } + list->array[index].dptr = ptr; + list->array[index].dsize = size; + list->num++; +} + + +/* Get a map handle with specifying the number of buckets. */ +CBMAP *cbmapopenex(int bnum){ + CBMAP *map; + int i; + assert(bnum > 0); + CB_MALLOC(map, sizeof(*map)); + CB_MALLOC(map->buckets, sizeof(map->buckets[0]) * bnum); + for(i = 0; i < bnum; i++){ + map->buckets[i] = NULL; + } + map->first = NULL; + map->last = NULL; + map->cur = NULL; + map->bnum = bnum; + map->rnum = 0; + return map; +} + + + +/************************************************************************************************* + * private objects + *************************************************************************************************/ + + +/* Handler to invoke the global garbage collector. */ +static void cbggchandler(void){ + cbggckeeper(NULL, NULL); +} + + +/* Manage resources of the global garbage collector. + `ptr' specifies the pointer to add to the collection. If it is `NULL', all resources are + released. + `func' specifies the pointer to the function to release the resources. */ +static void cbggckeeper(void *ptr, void (*func)(void *)){ + static void **parray = NULL; + static void (**farray)(void *) = NULL; + static int onum = 0; + static int asiz = CB_GCUNIT; + int i; + if(!ptr){ + if(!parray) return; + for(i = onum - 1; i >= 0; i--){ + farray[i](parray[i]); + } + free(parray); + free(farray); + parray = NULL; + farray = NULL; + onum = 0; + asiz = CB_GCUNIT; + return; + } + if(!parray){ + CB_MALLOC(parray, sizeof(void *) * asiz); + CB_MALLOC(farray, sizeof(void *) * asiz); + if(atexit(cbggchandler) != 0) cbmyfatal("gc failed"); + } + if(onum >= asiz){ + asiz *= 2; + CB_REALLOC(parray, sizeof(void *) * asiz); + CB_REALLOC(farray, sizeof(void *) * asiz); + } + parray[onum] = ptr; + farray[onum] = func; + onum++; +} + + +/* Utility function for quick sort. + `bp' specifies the pointer to the pointer to an array. + `nmemb' specifies the number of elements of the array. + `size' specifies the size of each element. + `pswap' specifies the pointer to the swap region for a pivot. + `vswap' specifies the pointer to the swap region for elements. + `compar' specifies the pointer to comparing function. */ +static void cbqsortsub(char *bp, int nmemb, int size, char *pswap, char *vswap, + int(*compar)(const void *, const void *)){ + int top, bottom; + assert(bp && nmemb >= 0 && size > 0 && pswap && vswap && compar); + if(nmemb < 10){ + if(nmemb > 1) cbisort(bp, nmemb, size, compar); + return; + } + top = 0; + bottom = nmemb - 1; + memcpy(pswap, bp + (nmemb / 2) * size, size); + while(top - 1 < bottom){ + if(compar(bp + top * size, pswap) < 0){ + top++; + } else if(compar(bp + bottom * size, pswap) > 0){ + bottom--; + } else { + if(top != bottom){ + memcpy(vswap, bp + top * size, size); + memcpy(bp + top * size, bp + bottom * size, size); + memcpy(bp + bottom * size, vswap, size); + } + top++; + bottom--; + } + } + cbqsortsub(bp, top, size, pswap, vswap, compar); + cbqsortsub(bp + (bottom + 1) * size, nmemb - bottom - 1, size, pswap, vswap, compar); +} + + +/* Compare two list elements. + `a' specifies the pointer to one element. + `b' specifies the pointer to the other element. + The return value is positive if a is big, negative if b is big, else, it is 0. */ +static int cblistelemcmp(const void *a, const void *b){ + int i, size; + CBLISTDATUM *ap, *bp; + char *ao, *bo; + assert(a && b); + ap = (CBLISTDATUM *)a; + bp = (CBLISTDATUM *)b; + ao = ap->dptr; + bo = bp->dptr; + size = ap->dsize < bp->dsize ? ap->dsize : bp->dsize; + for(i = 0; i < size; i++){ + if(ao[i] > bo[i]) return 1; + if(ao[i] < bo[i]) return -1; + } + return ap->dsize - bp->dsize; +} + + +/* Compare two keys. + `abuf' specifies the pointer to the region of the former. + `asiz' specifies the size of the region. + `bbuf' specifies the pointer to the region of the latter. + `bsiz' specifies the size of the region. + The return value is 0 if two equals, positive if the formar is big, else, negative. */ +static int cbkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz){ + assert(abuf && asiz >= 0 && bbuf && bsiz >= 0); + if(asiz > bsiz) return 1; + if(asiz < bsiz) return -1; + return memcmp(abuf, bbuf, asiz); +} + + + +/* END OF FILE */ |