X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/963238f713f02e538cf0f5851f3337173116ea39..4365e5b2d32798c168a8376fad891c0e5cccb4ec:/src/sds.c diff --git a/src/sds.c b/src/sds.c index 2d063c4a..e8491acf 100644 --- a/src/sds.c +++ b/src/sds.c @@ -1,6 +1,6 @@ /* SDSLib, A C dynamic strings library * - * Copyright (c) 2006-2010, Salvatore Sanfilippo + * Copyright (c) 2006-2012, Salvatore Sanfilippo * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -28,35 +28,27 @@ * POSSIBILITY OF SUCH DAMAGE. */ -#define SDS_ABORT_ON_OOM - -#include "sds.h" #include #include #include #include +#include +#include "sds.h" #include "zmalloc.h" -static void sdsOomAbort(void) { - fprintf(stderr,"SDS: Out Of Memory (SDS_ABORT_ON_OOM defined)\n"); - abort(); -} - sds sdsnewlen(const void *init, size_t initlen) { struct sdshdr *sh; - sh = zmalloc(sizeof(struct sdshdr)+initlen+1); -#ifdef SDS_ABORT_ON_OOM - if (sh == NULL) sdsOomAbort(); -#else + if (init) { + sh = zmalloc(sizeof(struct sdshdr)+initlen+1); + } else { + sh = zcalloc(sizeof(struct sdshdr)+initlen+1); + } if (sh == NULL) return NULL; -#endif sh->len = initlen; sh->free = 0; - if (initlen) { - if (init) memcpy(sh->buf, init, initlen); - else memset(sh->buf,0,initlen); - } + if (initlen && init) + memcpy(sh->buf, init, initlen); sh->buf[initlen] = '\0'; return (char*)sh->buf; } @@ -70,11 +62,6 @@ sds sdsnew(const char *init) { return sdsnewlen(init, initlen); } -size_t sdslen(const sds s) { - struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); - return sh->len; -} - sds sdsdup(const sds s) { return sdsnewlen(s, sdslen(s)); } @@ -84,11 +71,6 @@ void sdsfree(sds s) { zfree(s-sizeof(struct sdshdr)); } -size_t sdsavail(sds s) { - struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); - return sh->free; -} - void sdsupdatelen(sds s) { struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); int reallen = strlen(s); @@ -96,7 +78,20 @@ void sdsupdatelen(sds s) { sh->len = reallen; } -static sds sdsMakeRoomFor(sds s, size_t addlen) { +void sdsclear(sds s) { + struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); + sh->free += sh->len; + sh->len = 0; + sh->buf[0] = '\0'; +} + +/* Enlarge the free space at the end of the sds string so that the caller + * is sure that after calling this function can overwrite up to addlen + * bytes after the end of the string, plus one more byte for nul term. + * + * Note: this does not change the *size* of the sds string as returned + * by sdslen(), but only the free buffer space we have. */ +sds sdsMakeRoomFor(sds s, size_t addlen) { struct sdshdr *sh, *newsh; size_t free = sdsavail(s); size_t len, newlen; @@ -104,19 +99,87 @@ static sds sdsMakeRoomFor(sds s, size_t addlen) { if (free >= addlen) return s; len = sdslen(s); sh = (void*) (s-(sizeof(struct sdshdr))); - newlen = (len+addlen)*2; + newlen = (len+addlen); + if (newlen < SDS_MAX_PREALLOC) + newlen *= 2; + else + newlen += SDS_MAX_PREALLOC; newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); -#ifdef SDS_ABORT_ON_OOM - if (newsh == NULL) sdsOomAbort(); -#else if (newsh == NULL) return NULL; -#endif newsh->free = newlen - len; return newsh->buf; } -sds sdscatlen(sds s, void *t, size_t len) { +/* Reallocate the sds string so that it has no free space at the end. The + * contained string remains not altered, but next concatenation operations + * will require a reallocation. */ +sds sdsRemoveFreeSpace(sds s) { + struct sdshdr *sh; + + sh = (void*) (s-(sizeof(struct sdshdr))); + sh = zrealloc(sh, sizeof(struct sdshdr)+sh->len+1); + sh->free = 0; + return sh->buf; +} + +size_t sdsAllocSize(sds s) { + struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); + + return sizeof(*sh)+sh->len+sh->free+1; +} + +/* Increment the sds length and decrements the left free space at the + * end of the string accordingly to 'incr'. Also set the null term + * in the new end of the string. + * + * This function is used in order to fix the string length after the + * user calls sdsMakeRoomFor(), writes something after the end of + * the current string, and finally needs to set the new length. + * + * Note: it is possible to use a negative increment in order to + * right-trim the string. + * + * Using sdsIncrLen() and sdsMakeRoomFor() it is possible to mount the + * following schema to cat bytes coming from the kerenl to the end of an + * sds string new things without copying into an intermediate buffer: + * + * oldlen = sdslen(s); + * s = sdsMakeRoomFor(s, BUFFER_SIZE); + * nread = read(fd, s+oldlen, BUFFER_SIZE); + * ... check for nread <= 0 and handle it ... + * sdsIncrLen(s, nhread); + */ +void sdsIncrLen(sds s, int incr) { + struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); + + assert(sh->free >= incr); + sh->len += incr; + sh->free -= incr; + assert(sh->free >= 0); + s[sh->len] = '\0'; +} + +/* Grow the sds to have the specified length. Bytes that were not part of + * the original length of the sds will be set to zero. */ +sds sdsgrowzero(sds s, size_t len) { + struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); + size_t totlen, curlen = sh->len; + + if (len <= curlen) return s; + s = sdsMakeRoomFor(s,len-curlen); + if (s == NULL) return NULL; + + /* Make sure added region doesn't contain garbage */ + sh = (void*)(s-(sizeof(struct sdshdr))); + memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */ + totlen = sh->len+sh->free; + sh->len = len; + sh->free = totlen-sh->len; + return s; +} + +sds sdscatlen(sds s, const void *t, size_t len) { struct sdshdr *sh; size_t curlen = sdslen(s); @@ -130,11 +193,15 @@ sds sdscatlen(sds s, void *t, size_t len) { return s; } -sds sdscat(sds s, char *t) { +sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); } -sds sdscpylen(sds s, char *t, size_t len) { +sds sdscatsds(sds s, const sds t) { + return sdscatlen(s, t, sdslen(t)); +} + +sds sdscpylen(sds s, const char *t, size_t len) { struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); size_t totlen = sh->free+sh->len; @@ -151,7 +218,7 @@ sds sdscpylen(sds s, char *t, size_t len) { return s; } -sds sdscpy(sds s, char *t) { +sds sdscpy(sds s, const char *t) { return sdscpylen(s, t, strlen(t)); } @@ -162,11 +229,7 @@ sds sdscatvprintf(sds s, const char *fmt, va_list ap) { while(1) { buf = zmalloc(buflen); -#ifdef SDS_ABORT_ON_OOM - if (buf == NULL) sdsOomAbort(); -#else if (buf == NULL) return NULL; -#endif buf[buflen-2] = '\0'; va_copy(cpy,ap); vsnprintf(buf, buflen, fmt, cpy); @@ -251,7 +314,7 @@ void sdstoupper(sds s) { for (j = 0; j < len; j++) s[j] = toupper(s[j]); } -int sdscmp(sds s1, sds s2) { +int sdscmp(const sds s1, const sds s2) { size_t l1, l2, minlen; int cmp; @@ -279,14 +342,15 @@ int sdscmp(sds s1, sds s2) { * requires length arguments. sdssplit() is just the * same function but for zero-terminated strings. */ -sds *sdssplitlen(char *s, int len, char *sep, int seplen, int *count) { +sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count) { int elements = 0, slots = 5, start = 0, j; + sds *tokens; + + if (seplen < 1 || len < 0) return NULL; + + tokens = zmalloc(sizeof(sds)*slots); + if (tokens == NULL) return NULL; - sds *tokens = zmalloc(sizeof(sds)*slots); -#ifdef SDS_ABORT_ON_OOM - if (tokens == NULL) sdsOomAbort(); -#endif - if (seplen < 1 || len < 0 || tokens == NULL) return NULL; if (len == 0) { *count = 0; return tokens; @@ -298,25 +362,13 @@ sds *sdssplitlen(char *s, int len, char *sep, int seplen, int *count) { slots *= 2; newtokens = zrealloc(tokens,sizeof(sds)*slots); - if (newtokens == NULL) { -#ifdef SDS_ABORT_ON_OOM - sdsOomAbort(); -#else - goto cleanup; -#endif - } + if (newtokens == NULL) goto cleanup; tokens = newtokens; } /* search the separator */ if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) { tokens[elements] = sdsnewlen(s+start,j-start); - if (tokens[elements] == NULL) { -#ifdef SDS_ABORT_ON_OOM - sdsOomAbort(); -#else - goto cleanup; -#endif - } + if (tokens[elements] == NULL) goto cleanup; elements++; start = j+seplen; j = j+seplen-1; /* skip the separator */ @@ -324,26 +376,19 @@ sds *sdssplitlen(char *s, int len, char *sep, int seplen, int *count) { } /* Add the final element. We are sure there is room in the tokens array. */ tokens[elements] = sdsnewlen(s+start,len-start); - if (tokens[elements] == NULL) { -#ifdef SDS_ABORT_ON_OOM - sdsOomAbort(); -#else - goto cleanup; -#endif - } + if (tokens[elements] == NULL) goto cleanup; elements++; *count = elements; return tokens; -#ifndef SDS_ABORT_ON_OOM cleanup: { int i; for (i = 0; i < elements; i++) sdsfree(tokens[i]); zfree(tokens); + *count = 0; return NULL; } -#endif } void sdsfreesplitres(sds *tokens, int count) { @@ -368,7 +413,7 @@ sds sdsfromlonglong(long long value) { return sdsnewlen(p,32-(p-buf)); } -sds sdscatrepr(sds s, char *p, size_t len) { +sds sdscatrepr(sds s, const char *p, size_t len) { s = sdscatlen(s,"\"",1); while(len--) { switch(*p) { @@ -376,11 +421,11 @@ sds sdscatrepr(sds s, char *p, size_t len) { case '"': s = sdscatprintf(s,"\\%c",*p); break; - case '\n': s = sdscatlen(s,"\\n",1); break; - case '\r': s = sdscatlen(s,"\\r",1); break; - case '\t': s = sdscatlen(s,"\\t",1); break; - case '\a': s = sdscatlen(s,"\\a",1); break; - case '\b': s = sdscatlen(s,"\\b",1); break; + case '\n': s = sdscatlen(s,"\\n",2); break; + case '\r': s = sdscatlen(s,"\\r",2); break; + case '\t': s = sdscatlen(s,"\\t",2); break; + case '\a': s = sdscatlen(s,"\\a",2); break; + case '\b': s = sdscatlen(s,"\\b",2); break; default: if (isprint(*p)) s = sdscatprintf(s,"%c",*p); @@ -393,6 +438,37 @@ sds sdscatrepr(sds s, char *p, size_t len) { return sdscatlen(s,"\"",1); } +/* Helper function for sdssplitargs() that returns non zero if 'c' + * is a valid hex digit. */ +int is_hex_digit(char c) { + return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || + (c >= 'A' && c <= 'F'); +} + +/* Helper function for sdssplitargs() that converts an hex digit into an + * integer from 0 to 15 */ +int hex_digit_to_int(char c) { + switch(c) { + case '0': return 0; + case '1': return 1; + case '2': return 2; + case '3': return 3; + case '4': return 4; + case '5': return 5; + case '6': return 6; + case '7': return 7; + case '8': return 8; + case '9': return 9; + case 'a': case 'A': return 10; + case 'b': case 'B': return 11; + case 'c': case 'C': return 12; + case 'd': case 'D': return 13; + case 'e': case 'E': return 14; + case 'f': case 'F': return 15; + default: return 0; + } +} + /* Split a line into arguments, where every argument can be in the * following programming-language REPL-alike form: * @@ -405,8 +481,8 @@ sds sdscatrepr(sds s, char *p, size_t len) { * Note that sdscatrepr() is able to convert back a string into * a quoted string in the same format sdssplitargs() is able to parse. */ -sds *sdssplitargs(char *line, int *argc) { - char *p = line; +sds *sdssplitargs(const char *line, int *argc) { + const char *p = line; char *current = NULL; char **vector = NULL; @@ -416,13 +492,24 @@ sds *sdssplitargs(char *line, int *argc) { while(*p && isspace(*p)) p++; if (*p) { /* get a token */ - int inq=0; /* set to 1 if we are in "quotes" */ + int inq=0; /* set to 1 if we are in "quotes" */ + int insq=0; /* set to 1 if we are in 'single quotes' */ int done=0; if (current == NULL) current = sdsempty(); while(!done) { if (inq) { - if (*p == '\\' && *(p+1)) { + if (*p == '\\' && *(p+1) == 'x' && + is_hex_digit(*(p+2)) && + is_hex_digit(*(p+3))) + { + unsigned char byte; + + byte = (hex_digit_to_int(*(p+2))*16)+ + hex_digit_to_int(*(p+3)); + current = sdscatlen(current,(char*)&byte,1); + p += 3; + } else if (*p == '\\' && *(p+1)) { char c; p++; @@ -436,7 +523,23 @@ sds *sdssplitargs(char *line, int *argc) { } current = sdscatlen(current,&c,1); } else if (*p == '"') { - /* closing quote must be followed by a space */ + /* closing quote must be followed by a space or + * nothing at all. */ + if (*(p+1) && !isspace(*(p+1))) goto err; + done=1; + } else if (!*p) { + /* unterminated quotes */ + goto err; + } else { + current = sdscatlen(current,p,1); + } + } else if (insq) { + if (*p == '\\' && *(p+1) == '\'') { + p++; + current = sdscatlen(current,"'",1); + } else if (*p == '\'') { + /* closing quote must be followed by a space or + * nothing at all. */ if (*(p+1) && !isspace(*(p+1))) goto err; done=1; } else if (!*p) { @@ -457,6 +560,9 @@ sds *sdssplitargs(char *line, int *argc) { case '"': inq=1; break; + case '\'': + insq=1; + break; default: current = sdscatlen(current,p,1); break; @@ -482,12 +588,43 @@ err: return NULL; } +void sdssplitargs_free(sds *argv, int argc) { + int j; + + for (j = 0 ;j < argc; j++) sdsfree(argv[j]); + zfree(argv); +} + +/* Modify the string substituting all the occurrences of the set of + * characters specifed in the 'from' string to the corresponding character + * in the 'to' array. + * + * For instance: sdsmapchars(mystring, "ho", "01", 2) + * will have the effect of turning the string "hello" into "0ell1". + * + * The function returns the sds string pointer, that is always the same + * as the input pointer since no resize is needed. */ +sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen) { + size_t j, i, l = sdslen(s); + + for (j = 0; j < l; j++) { + for (i = 0; i < setlen; i++) { + if (s[j] == from[i]) { + s[j] = to[i]; + break; + } + } + } + return s; +} + #ifdef SDS_TEST_MAIN #include #include "testhelp.h" int main(void) { { + struct sdshdr *sh; sds x = sdsnew("foo"), y; test_cond("Create a string and obtain the length", @@ -567,7 +704,26 @@ int main(void) { x = sdsnew("aar"); y = sdsnew("bar"); test_cond("sdscmp(bar,bar)", sdscmp(x,y) < 0) + + { + int oldfree; + + sdsfree(x); + x = sdsnew("0"); + sh = (void*) (x-(sizeof(struct sdshdr))); + test_cond("sdsnew() free/len buffers", sh->len == 1 && sh->free == 0); + x = sdsMakeRoomFor(x,1); + sh = (void*) (x-(sizeof(struct sdshdr))); + test_cond("sdsMakeRoomFor()", sh->len == 1 && sh->free > 0); + oldfree = sh->free; + x[1] = '1'; + sdsIncrLen(x,1); + test_cond("sdsIncrLen() -- content", x[0] == '0' && x[1] == '1'); + test_cond("sdsIncrLen() -- len", sh->len == 2); + test_cond("sdsIncrLen() -- free", sh->free == oldfree-1); + } } test_report() + return 0; } #endif