1/* SDSLib 2.0 -- A C dynamic strings library
2 *
3 * Copyright (c) 2006-2015, Salvatore Sanfilippo <antirez at gmail dot com>
4 * Copyright (c) 2015, Oran Agra
5 * Copyright (c) 2015, Redis Labs, Inc
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright notice,
12 * this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * * Neither the name of Redis nor the names of its contributors may be used
17 * to endorse or promote products derived from this software without
18 * specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 * POSSIBILITY OF SUCH DAMAGE.
31 */
32
33#include <stdio.h>
34#include <stdlib.h>
35#include <string.h>
36#include <ctype.h>
37#include <assert.h>
38#include <limits.h>
39#include "sds.hpp"
40
41static inline int sdsHdrSize(char type) {
42 switch(type&SDS_TYPE_MASK) {
43 case SDS_TYPE_5:
44 return sizeof(struct sdshdr5);
45 case SDS_TYPE_8:
46 return sizeof(struct sdshdr8);
47 case SDS_TYPE_16:
48 return sizeof(struct sdshdr16);
49 case SDS_TYPE_32:
50 return sizeof(struct sdshdr32);
51 case SDS_TYPE_64:
52 return sizeof(struct sdshdr64);
53 }
54 return 0;
55}
56
57static inline char sdsReqType(size_t string_size) {
58 if (string_size < 1<<5)
59 return SDS_TYPE_5;
60 if (string_size < 1<<8)
61 return SDS_TYPE_8;
62 if (string_size < 1<<16)
63 return SDS_TYPE_16;
64#if (LONG_MAX == LLONG_MAX)
65 if (string_size < 1ll<<32)
66 return SDS_TYPE_32;
67 return SDS_TYPE_64;
68#else
69 return SDS_TYPE_32;
70#endif
71}
72
73/* Create a new sds string with the content specified by the 'init' pointer
74 * and 'initlen'.
75 * If NULL is used for 'init' the string is initialized with zero bytes.
76 * If SDS_NOINIT is used, the buffer is left uninitialized;
77 *
78 * The string is always null-termined (all the sds strings are, always) so
79 * even if you create an sds string with:
80 *
81 * mystring = sdsnewlen("abc",3);
82 *
83 * You can print the string with printf() as there is an implicit \0 at the
84 * end of the string. However the string is binary safe and can contain
85 * \0 characters in the middle, as the length is stored in the sds header. */
86sds sdsnewlen(const void *init, size_t initlen) {
87 void *sh;
88 sds s;
89 char type = sdsReqType(initlen);
90 /* Empty strings are usually created in order to append. Use type 8
91 * since type 5 is not good at this. */
92 if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
93 int hdrlen = sdsHdrSize(type);
94 unsigned char *fp; /* flags pointer. */
95
96 sh = malloc(hdrlen+initlen+1);
97 if (!init)
98 memset(sh, 0, hdrlen+initlen+1);
99 if (sh == NULL) return NULL;
100 s = (char*)sh+hdrlen;
101 fp = ((unsigned char*)s)-1;
102 switch(type) {
103 case SDS_TYPE_5: {
104 *fp = type | (initlen << SDS_TYPE_BITS);
105 break;
106 }
107 case SDS_TYPE_8: {
108 SDS_HDR_VAR(8,s);
109 sh->len = initlen;
110 sh->alloc = initlen;
111 *fp = type;
112 break;
113 }
114 case SDS_TYPE_16: {
115 SDS_HDR_VAR(16,s);
116 sh->len = initlen;
117 sh->alloc = initlen;
118 *fp = type;
119 break;
120 }
121 case SDS_TYPE_32: {
122 SDS_HDR_VAR(32,s);
123 sh->len = initlen;
124 sh->alloc = initlen;
125 *fp = type;
126 break;
127 }
128 case SDS_TYPE_64: {
129 SDS_HDR_VAR(64,s);
130 sh->len = initlen;
131 sh->alloc = initlen;
132 *fp = type;
133 break;
134 }
135 }
136 if (initlen && init)
137 memcpy(s, init, initlen);
138 s[initlen] = '\0';
139 return s;
140}
141
142/* Create an empty (zero length) sds string. Even in this case the string
143 * always has an implicit null term. */
144sds sdsempty(void) {
145 return sdsnewlen("",0);
146}
147
148/* Create a new sds string starting from a null terminated C string. */
149sds sdsnew(const char *init) {
150 size_t initlen = (init == NULL) ? 0 : strlen(init);
151 return sdsnewlen(init, initlen);
152}
153
154/* Duplicate an sds string. */
155sds sdsdup(const sds s) {
156 return sdsnewlen(s, sdslen(s));
157}
158
159/* Free an sds string. No operation is performed if 's' is NULL. */
160void sdsfree(sds s) {
161 if (s == NULL) return;
162 free((char*)s-sdsHdrSize(s[-1]));
163}
164
165/* Set the sds string length to the length as obtained with strlen(), so
166 * considering as content only up to the first null term character.
167 *
168 * This function is useful when the sds string is hacked manually in some
169 * way, like in the following example:
170 *
171 * s = sdsnew("foobar");
172 * s[2] = '\0';
173 * sdsupdatelen(s);
174 * printf("%d\n", sdslen(s));
175 *
176 * The output will be "2", but if we comment out the call to sdsupdatelen()
177 * the output will be "6" as the string was modified but the logical length
178 * remains 6 bytes. */
179void sdsupdatelen(sds s) {
180 size_t reallen = strlen(s);
181 sdssetlen(s, reallen);
182}
183
184/* Modify an sds string in-place to make it empty (zero length).
185 * However all the existing buffer is not discarded but set as free space
186 * so that next append operations will not require allocations up to the
187 * number of bytes previously available. */
188void sdsclear(sds s) {
189 sdssetlen(s, 0);
190 s[0] = '\0';
191}
192
193/* Enlarge the free space at the end of the sds string so that the caller
194 * is sure that after calling this function can overwrite up to addlen
195 * bytes after the end of the string, plus one more byte for nul term.
196 *
197 * Note: this does not change the *length* of the sds string as returned
198 * by sdslen(), but only the free buffer space we have. */
199sds sdsMakeRoomFor(sds s, size_t addlen) {
200 void *sh, *newsh;
201 size_t avail = sdsavail(s);
202 size_t len, newlen;
203 char type, oldtype = s[-1] & SDS_TYPE_MASK;
204 int hdrlen;
205
206 /* Return ASAP if there is enough space left. */
207 if (avail >= addlen) return s;
208
209 len = sdslen(s);
210 sh = (char*)s-sdsHdrSize(oldtype);
211 newlen = (len+addlen);
212 if (newlen < SDS_MAX_PREALLOC)
213 newlen *= 2;
214 else
215 newlen += SDS_MAX_PREALLOC;
216
217 type = sdsReqType(newlen);
218
219 /* Don't use type 5: the user is appending to the string and type 5 is
220 * not able to remember empty space, so sdsMakeRoomFor() must be called
221 * at every appending operation. */
222 if (type == SDS_TYPE_5) type = SDS_TYPE_8;
223
224 hdrlen = sdsHdrSize(type);
225 if (oldtype==type) {
226 newsh = realloc(sh, hdrlen+newlen+1);
227 if (newsh == NULL) return NULL;
228 s = (char*)newsh+hdrlen;
229 } else {
230 /* Since the header size changes, need to move the string forward,
231 * and can't use realloc */
232 newsh = malloc(hdrlen+newlen+1);
233 if (newsh == NULL) return NULL;
234 memcpy((char*)newsh+hdrlen, s, len+1);
235 free(sh);
236 s = (char*)newsh+hdrlen;
237 s[-1] = type;
238 sdssetlen(s, len);
239 }
240 sdssetalloc(s, newlen);
241 return s;
242}
243
244/* Reallocate the sds string so that it has no free space at the end. The
245 * contained string remains not altered, but next concatenation operations
246 * will require a reallocation.
247 *
248 * After the call, the passed sds string is no longer valid and all the
249 * references must be substituted with the new pointer returned by the call. */
250sds sdsRemoveFreeSpace(sds s) {
251 void *sh, *newsh;
252 char type, oldtype = s[-1] & SDS_TYPE_MASK;
253 int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
254 size_t len = sdslen(s);
255 sh = (char*)s-oldhdrlen;
256
257 /* Check what would be the minimum SDS header that is just good enough to
258 * fit this string. */
259 type = sdsReqType(len);
260 hdrlen = sdsHdrSize(type);
261
262 /* If the type is the same, or at least a large enough type is still
263 * required, we just realloc(), letting the allocator to do the copy
264 * only if really needed. Otherwise if the change is huge, we manually
265 * reallocate the string to use the different header type. */
266 if (oldtype==type || type > SDS_TYPE_8) {
267 newsh = realloc(sh, oldhdrlen+len+1);
268 if (newsh == NULL) return NULL;
269 s = (char*)newsh+oldhdrlen;
270 } else {
271 newsh = malloc(hdrlen+len+1);
272 if (newsh == NULL) return NULL;
273 memcpy((char*)newsh+hdrlen, s, len+1);
274 free(sh);
275 s = (char*)newsh+hdrlen;
276 s[-1] = type;
277 sdssetlen(s, len);
278 }
279 sdssetalloc(s, len);
280 return s;
281}
282
283/* Return the total size of the allocation of the specified sds string,
284 * including:
285 * 1) The sds header before the pointer.
286 * 2) The string.
287 * 3) The free buffer at the end if any.
288 * 4) The implicit null term.
289 */
290size_t sdsAllocSize(sds s) {
291 size_t alloc = sdsalloc(s);
292 return sdsHdrSize(s[-1])+alloc+1;
293}
294
295/* Return the pointer of the actual SDS allocation (normally SDS strings
296 * are referenced by the start of the string buffer). */
297void *sdsAllocPtr(sds s) {
298 return (void*) (s-sdsHdrSize(s[-1]));
299}
300
301/* Increment the sds length and decrements the left free space at the
302 * end of the string according to 'incr'. Also set the null term
303 * in the new end of the string.
304 *
305 * This function is used in order to fix the string length after the
306 * user calls sdsMakeRoomFor(), writes something after the end of
307 * the current string, and finally needs to set the new length.
308 *
309 * Note: it is possible to use a negative increment in order to
310 * right-trim the string.
311 *
312 * Usage example:
313 *
314 * Using sdsIncrLen() and sdsMakeRoomFor() it is possible to mount the
315 * following schema, to cat bytes coming from the kernel to the end of an
316 * sds string without copying into an intermediate buffer:
317 *
318 * oldlen = sdslen(s);
319 * s = sdsMakeRoomFor(s, BUFFER_SIZE);
320 * nread = read(fd, s+oldlen, BUFFER_SIZE);
321 * ... check for nread <= 0 and handle it ...
322 * sdsIncrLen(s, nread);
323 */
324void sdsIncrLen(sds s, ssize_t incr) {
325 unsigned char flags = s[-1];
326 size_t len;
327 switch(flags&SDS_TYPE_MASK) {
328 case SDS_TYPE_5: {
329 unsigned char *fp = ((unsigned char*)s)-1;
330 unsigned char oldlen = SDS_TYPE_5_LEN(flags);
331 assert((incr > 0 && oldlen+incr < 32) || (incr < 0 && oldlen >= (unsigned int)(-incr)));
332 *fp = SDS_TYPE_5 | ((oldlen+incr) << SDS_TYPE_BITS);
333 len = oldlen+incr;
334 break;
335 }
336 case SDS_TYPE_8: {
337 SDS_HDR_VAR(8,s);
338 assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
339 len = (sh->len += incr);
340 break;
341 }
342 case SDS_TYPE_16: {
343 SDS_HDR_VAR(16,s);
344 assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
345 len = (sh->len += incr);
346 break;
347 }
348 case SDS_TYPE_32: {
349 SDS_HDR_VAR(32,s);
350 assert((incr >= 0 && sh->alloc-sh->len >= (unsigned int)incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
351 len = (sh->len += incr);
352 break;
353 }
354 case SDS_TYPE_64: {
355 SDS_HDR_VAR(64,s);
356 assert((incr >= 0 && sh->alloc-sh->len >= (uint64_t)incr) || (incr < 0 && sh->len >= (uint64_t)(-incr)));
357 len = (sh->len += incr);
358 break;
359 }
360 default: len = 0; /* Just to avoid compilation warnings. */
361 }
362 s[len] = '\0';
363}
364
365/* Grow the sds to have the specified length. Bytes that were not part of
366 * the original length of the sds will be set to zero.
367 *
368 * if the specified length is smaller than the current length, no operation
369 * is performed. */
370sds sdsgrowzero(sds s, size_t len) {
371 size_t curlen = sdslen(s);
372
373 if (len <= curlen) return s;
374 s = sdsMakeRoomFor(s,len-curlen);
375 if (s == NULL) return NULL;
376
377 /* Make sure added region doesn't contain garbage */
378 memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
379 sdssetlen(s, len);
380 return s;
381}
382
383/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
384 * end of the specified sds string 's'.
385 *
386 * After the call, the passed sds string is no longer valid and all the
387 * references must be substituted with the new pointer returned by the call. */
388sds sdscatlen(sds s, const void *t, size_t len) {
389 size_t curlen = sdslen(s);
390
391 s = sdsMakeRoomFor(s,len);
392 if (s == NULL) return NULL;
393 memcpy(s+curlen, t, len);
394 sdssetlen(s, curlen+len);
395 s[curlen+len] = '\0';
396 return s;
397}
398
399/* Append the specified null termianted C string to the sds string 's'.
400 *
401 * After the call, the passed sds string is no longer valid and all the
402 * references must be substituted with the new pointer returned by the call. */
403sds sdscat(sds s, const char *t) {
404 return sdscatlen(s, t, strlen(t));
405}
406
407/* Append the specified sds 't' to the existing sds 's'.
408 *
409 * After the call, the modified sds string is no longer valid and all the
410 * references must be substituted with the new pointer returned by the call. */
411sds sdscatsds(sds s, const sds t) {
412 return sdscatlen(s, t, sdslen(t));
413}
414
415/* Destructively modify the sds string 's' to hold the specified binary
416 * safe string pointed by 't' of length 'len' bytes. */
417sds sdscpylen(sds s, const char *t, size_t len) {
418 if (sdsalloc(s) < len) {
419 s = sdsMakeRoomFor(s,len-sdslen(s));
420 if (s == NULL) return NULL;
421 }
422 memcpy(s, t, len);
423 s[len] = '\0';
424 sdssetlen(s, len);
425 return s;
426}
427
428/* Like sdscpylen() but 't' must be a null-termined string so that the length
429 * of the string is obtained with strlen(). */
430sds sdscpy(sds s, const char *t) {
431 return sdscpylen(s, t, strlen(t));
432}
433
434/* Helper for sdscatlonglong() doing the actual number -> string
435 * conversion. 's' must point to a string with room for at least
436 * SDS_LLSTR_SIZE bytes.
437 *
438 * The function returns the length of the null-terminated string
439 * representation stored at 's'. */
440#define SDS_LLSTR_SIZE 21
441int sdsll2str(char *s, long long value) {
442 char *p, aux;
443 unsigned long long v;
444 size_t l;
445
446 /* Generate the string representation, this method produces
447 * an reversed string. */
448 v = (value < 0) ? -value : value;
449 p = s;
450 do {
451 *p++ = '0'+(v%10);
452 v /= 10;
453 } while(v);
454 if (value < 0) *p++ = '-';
455
456 /* Compute length and add null term. */
457 l = p-s;
458 *p = '\0';
459
460 /* Reverse the string. */
461 p--;
462 while(s < p) {
463 aux = *s;
464 *s = *p;
465 *p = aux;
466 s++;
467 p--;
468 }
469 return l;
470}
471
472/* Identical sdsll2str(), but for unsigned long long type. */
473int sdsull2str(char *s, unsigned long long v) {
474 char *p, aux;
475 size_t l;
476
477 /* Generate the string representation, this method produces
478 * an reversed string. */
479 p = s;
480 do {
481 *p++ = '0'+(v%10);
482 v /= 10;
483 } while(v);
484
485 /* Compute length and add null term. */
486 l = p-s;
487 *p = '\0';
488
489 /* Reverse the string. */
490 p--;
491 while(s < p) {
492 aux = *s;
493 *s = *p;
494 *p = aux;
495 s++;
496 p--;
497 }
498 return l;
499}
500
501/* Create an sds string from a long long value. It is much faster than:
502 *
503 * sdscatprintf(sdsempty(),"%lld\n", value);
504 */
505sds sdsfromlonglong(long long value) {
506 char buf[SDS_LLSTR_SIZE];
507 int len = sdsll2str(buf,value);
508
509 return sdsnewlen(buf,len);
510}
511
512/* Like sdscatprintf() but gets va_list instead of being variadic. */
513sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
514 va_list cpy;
515 char staticbuf[1024], *buf = staticbuf, *t;
516 size_t buflen = strlen(fmt)*2;
517
518 /* We try to start using a static buffer for speed.
519 * If not possible we revert to heap allocation. */
520 if (buflen > sizeof(staticbuf)) {
521 buf = (char*) malloc(buflen);
522 if (buf == NULL) return NULL;
523 } else {
524 buflen = sizeof(staticbuf);
525 }
526
527 /* Try with buffers two times bigger every time we fail to
528 * fit the string in the current buffer size. */
529 while(1) {
530 buf[buflen-2] = '\0';
531 va_copy(cpy,ap);
532 vsnprintf(buf, buflen, fmt, cpy);
533 va_end(cpy);
534 if (buf[buflen-2] != '\0') {
535 if (buf != staticbuf) free(buf);
536 buflen *= 2;
537 buf = (char*) malloc(buflen);
538 if (buf == NULL) return NULL;
539 continue;
540 }
541 break;
542 }
543
544 /* Finally concat the obtained string to the SDS string and return it. */
545 t = sdscat(s, buf);
546 if (buf != staticbuf) free(buf);
547 return t;
548}
549
550/* Append to the sds string 's' a string obtained using printf-alike format
551 * specifier.
552 *
553 * After the call, the modified sds string is no longer valid and all the
554 * references must be substituted with the new pointer returned by the call.
555 *
556 * Example:
557 *
558 * s = sdsnew("Sum is: ");
559 * s = sdscatprintf(s,"%d+%d = %d",a,b,a+b).
560 *
561 * Often you need to create a string from scratch with the printf-alike
562 * format. When this is the need, just use sdsempty() as the target string:
563 *
564 * s = sdscatprintf(sdsempty(), "... your format ...", args);
565 */
566sds sdscatprintf(sds s, const char *fmt, ...) {
567 va_list ap;
568 char *t;
569 va_start(ap, fmt);
570 t = sdscatvprintf(s,fmt,ap);
571 va_end(ap);
572 return t;
573}
574
575/* This function is similar to sdscatprintf, but much faster as it does
576 * not rely on sprintf() family functions implemented by the libc that
577 * are often very slow. Moreover directly handling the sds string as
578 * new data is concatenated provides a performance improvement.
579 *
580 * However this function only handles an incompatible subset of printf-alike
581 * format specifiers:
582 *
583 * %s - C String
584 * %S - SDS string
585 * %i - signed int
586 * %I - 64 bit signed integer (long long, int64_t)
587 * %u - unsigned int
588 * %U - 64 bit unsigned integer (unsigned long long, uint64_t)
589 * %% - Verbatim "%" character.
590 */
591sds sdscatfmt(sds s, char const *fmt, ...) {
592 size_t initlen = sdslen(s);
593 const char *f = fmt;
594 long i;
595 va_list ap;
596
597 va_start(ap,fmt);
598 f = fmt; /* Next format specifier byte to process. */
599 i = initlen; /* Position of the next byte to write to dest str. */
600 while(*f) {
601 char next, *str;
602 size_t l;
603 long long num;
604 unsigned long long unum;
605
606 /* Make sure there is always space for at least 1 char. */
607 if (sdsavail(s)==0) {
608 s = sdsMakeRoomFor(s,1);
609 }
610
611 switch(*f) {
612 case '%':
613 next = *(f+1);
614 f++;
615 switch(next) {
616 case 's':
617 case 'S':
618 str = va_arg(ap,char*);
619 l = (next == 's') ? strlen(str) : sdslen(str);
620 if (sdsavail(s) < l) {
621 s = sdsMakeRoomFor(s,l);
622 }
623 memcpy(s+i,str,l);
624 sdsinclen(s,l);
625 i += l;
626 break;
627 case 'i':
628 case 'I':
629 if (next == 'i')
630 num = va_arg(ap,int);
631 else
632 num = va_arg(ap,long long);
633 {
634 char buf[SDS_LLSTR_SIZE];
635 l = sdsll2str(buf,num);
636 if (sdsavail(s) < l) {
637 s = sdsMakeRoomFor(s,l);
638 }
639 memcpy(s+i,buf,l);
640 sdsinclen(s,l);
641 i += l;
642 }
643 break;
644 case 'u':
645 case 'U':
646 if (next == 'u')
647 unum = va_arg(ap,unsigned int);
648 else
649 unum = va_arg(ap,unsigned long long);
650 {
651 char buf[SDS_LLSTR_SIZE];
652 l = sdsull2str(buf,unum);
653 if (sdsavail(s) < l) {
654 s = sdsMakeRoomFor(s,l);
655 }
656 memcpy(s+i,buf,l);
657 sdsinclen(s,l);
658 i += l;
659 }
660 break;
661 default: /* Handle %% and generally %<unknown>. */
662 s[i++] = next;
663 sdsinclen(s,1);
664 break;
665 }
666 break;
667 default:
668 s[i++] = *f;
669 sdsinclen(s,1);
670 break;
671 }
672 f++;
673 }
674 va_end(ap);
675
676 /* Add null-term */
677 s[i] = '\0';
678 return s;
679}
680
681/* Remove the part of the string from left and from right composed just of
682 * contiguous characters found in 'cset', that is a null terminted C string.
683 *
684 * After the call, the modified sds string is no longer valid and all the
685 * references must be substituted with the new pointer returned by the call.
686 *
687 * Example:
688 *
689 * s = sdsnew("AA...AA.a.aa.aHelloWorld :::");
690 * s = sdstrim(s,"Aa. :");
691 * printf("%s\n", s);
692 *
693 * Output will be just "Hello World".
694 */
695sds sdstrim(sds s, const char *cset) {
696 char *start, *end, *sp, *ep;
697 size_t len;
698
699 sp = start = s;
700 ep = end = s+sdslen(s)-1;
701 while(sp <= end && strchr(cset, *sp)) sp++;
702 while(ep > sp && strchr(cset, *ep)) ep--;
703 len = (sp > ep) ? 0 : ((ep-sp)+1);
704 if (s != sp) memmove(s, sp, len);
705 s[len] = '\0';
706 sdssetlen(s,len);
707 return s;
708}
709
710/* Turn the string into a smaller (or equal) string containing only the
711 * substring specified by the 'start' and 'end' indexes.
712 *
713 * start and end can be negative, where -1 means the last character of the
714 * string, -2 the penultimate character, and so forth.
715 *
716 * The interval is inclusive, so the start and end characters will be part
717 * of the resulting string.
718 *
719 * The string is modified in-place.
720 *
721 * Example:
722 *
723 * s = sdsnew("Hello World");
724 * sdsrange(s,1,-1); => "ello World"
725 */
726void sdsrange(sds s, ssize_t start, ssize_t end) {
727 size_t newlen, len = sdslen(s);
728
729 if (len == 0) return;
730 if (start < 0) {
731 start = len+start;
732 if (start < 0) start = 0;
733 }
734 if (end < 0) {
735 end = len+end;
736 if (end < 0) end = 0;
737 }
738 newlen = (start > end) ? 0 : (end-start)+1;
739 if (newlen != 0) {
740 if (start >= (ssize_t)len) {
741 newlen = 0;
742 } else if (end >= (ssize_t)len) {
743 end = len-1;
744 newlen = (start > end) ? 0 : (end-start)+1;
745 }
746 } else {
747 start = 0;
748 }
749 if (start && newlen) memmove(s, s+start, newlen);
750 s[newlen] = 0;
751 sdssetlen(s,newlen);
752}
753
754/* Apply tolower() to every character of the sds string 's'. */
755void sdstolower(sds s) {
756 size_t len = sdslen(s), j;
757
758 for (j = 0; j < len; j++) s[j] = tolower(s[j]);
759}
760
761/* Apply toupper() to every character of the sds string 's'. */
762void sdstoupper(sds s) {
763 size_t len = sdslen(s), j;
764
765 for (j = 0; j < len; j++) s[j] = toupper(s[j]);
766}
767
768/* Compare two sds strings s1 and s2 with memcmp().
769 *
770 * Return value:
771 *
772 * positive if s1 > s2.
773 * negative if s1 < s2.
774 * 0 if s1 and s2 are exactly the same binary string.
775 *
776 * If two strings share exactly the same prefix, but one of the two has
777 * additional characters, the longer string is considered to be greater than
778 * the smaller one. */
779int sdscmp(const sds s1, const sds s2) {
780 size_t l1, l2, minlen;
781 int cmp;
782
783 l1 = sdslen(s1);
784 l2 = sdslen(s2);
785 minlen = (l1 < l2) ? l1 : l2;
786 cmp = memcmp(s1,s2,minlen);
787 if (cmp == 0) return l1>l2? 1: (l1<l2? -1: 0);
788 return cmp;
789}
790
791/* Split 's' with separator in 'sep'. An array
792 * of sds strings is returned. *count will be set
793 * by reference to the number of tokens returned.
794 *
795 * On out of memory, zero length string, zero length
796 * separator, NULL is returned.
797 *
798 * Note that 'sep' is able to split a string using
799 * a multi-character separator. For example
800 * sdssplit("foo_-_bar","_-_"); will return two
801 * elements "foo" and "bar".
802 *
803 * This version of the function is binary-safe but
804 * requires length arguments. sdssplit() is just the
805 * same function but for zero-terminated strings.
806 */
807sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count) {
808 int elements = 0, slots = 5;
809 long start = 0, j;
810 sds *tokens;
811
812 if (seplen < 1 || len < 0) return NULL;
813
814 tokens = (sds*) malloc(sizeof(sds)*slots);
815 if (tokens == NULL) return NULL;
816
817 if (len == 0) {
818 *count = 0;
819 return tokens;
820 }
821 for (j = 0; j < (len-(seplen-1)); j++) {
822 /* make sure there is room for the next element and the final one */
823 if (slots < elements+2) {
824 sds *newtokens;
825
826 slots *= 2;
827 newtokens = (sds*) realloc(tokens,sizeof(sds)*slots);
828 if (newtokens == NULL) goto cleanup;
829 tokens = newtokens;
830 }
831 /* search the separator */
832 if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) {
833 tokens[elements] = sdsnewlen(s+start,j-start);
834 if (tokens[elements] == NULL) goto cleanup;
835 elements++;
836 start = j+seplen;
837 j = j+seplen-1; /* skip the separator */
838 }
839 }
840 /* Add the final element. We are sure there is room in the tokens array. */
841 tokens[elements] = sdsnewlen(s+start,len-start);
842 if (tokens[elements] == NULL) goto cleanup;
843 elements++;
844 *count = elements;
845 return tokens;
846
847cleanup:
848 {
849 int i;
850 for (i = 0; i < elements; i++) sdsfree(tokens[i]);
851 free(tokens);
852 *count = 0;
853 return NULL;
854 }
855}
856
857/* Free the result returned by sdssplitlen(), or do nothing if 'tokens' is NULL. */
858void sdsfreesplitres(sds *tokens, int count) {
859 if (!tokens) return;
860 while(count--)
861 sdsfree(tokens[count]);
862 free(tokens);
863}
864
865/* Append to the sds string "s" an escaped string representation where
866 * all the non-printable characters (tested with isprint()) are turned into
867 * escapes in the form "\n\r\a...." or "\x<hex-number>".
868 *
869 * After the call, the modified sds string is no longer valid and all the
870 * references must be substituted with the new pointer returned by the call. */
871sds sdscatrepr(sds s, const char *p, size_t len) {
872 s = sdscatlen(s,"\"",1);
873 while(len--) {
874 switch(*p) {
875 case '\\':
876 case '"':
877 s = sdscatprintf(s,"\\%c",*p);
878 break;
879 case '\n': s = sdscatlen(s,"\\n",2); break;
880 case '\r': s = sdscatlen(s,"\\r",2); break;
881 case '\t': s = sdscatlen(s,"\\t",2); break;
882 case '\a': s = sdscatlen(s,"\\a",2); break;
883 case '\b': s = sdscatlen(s,"\\b",2); break;
884 default:
885 if (isprint(*p))
886 s = sdscatprintf(s,"%c",*p);
887 else
888 s = sdscatprintf(s,"\\x%02x",(unsigned char)*p);
889 break;
890 }
891 p++;
892 }
893 return sdscatlen(s,"\"",1);
894}
895
896/* Helper function for sdssplitargs() that returns non zero if 'c'
897 * is a valid hex digit. */
898int is_hex_digit(char c) {
899 return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') ||
900 (c >= 'A' && c <= 'F');
901}
902
903/* Helper function for sdssplitargs() that converts a hex digit into an
904 * integer from 0 to 15 */
905int hex_digit_to_int(char c) {
906 switch(c) {
907 case '0': return 0;
908 case '1': return 1;
909 case '2': return 2;
910 case '3': return 3;
911 case '4': return 4;
912 case '5': return 5;
913 case '6': return 6;
914 case '7': return 7;
915 case '8': return 8;
916 case '9': return 9;
917 case 'a': case 'A': return 10;
918 case 'b': case 'B': return 11;
919 case 'c': case 'C': return 12;
920 case 'd': case 'D': return 13;
921 case 'e': case 'E': return 14;
922 case 'f': case 'F': return 15;
923 default: return 0;
924 }
925}
926
927/* Split a line into arguments, where every argument can be in the
928 * following programming-language REPL-alike form:
929 *
930 * foo bar "newline are supported\n" and "\xff\x00otherstuff"
931 *
932 * The number of arguments is stored into *argc, and an array
933 * of sds is returned.
934 *
935 * The caller should free the resulting array of sds strings with
936 * sdsfreesplitres().
937 *
938 * Note that sdscatrepr() is able to convert back a string into
939 * a quoted string in the same format sdssplitargs() is able to parse.
940 *
941 * The function returns the allocated tokens on success, even when the
942 * input string is empty, or NULL if the input contains unbalanced
943 * quotes or closed quotes followed by non space characters
944 * as in: "foo"bar or "foo'
945 */
946sds *sdssplitargs(const char *line, int *argc) {
947 const char *p = line;
948 char *current = NULL;
949 char **vector = NULL;
950
951 *argc = 0;
952 while(1) {
953 /* skip blanks */
954 while(*p && isspace(*p)) p++;
955 if (*p) {
956 /* get a token */
957 int inq=0; /* set to 1 if we are in "quotes" */
958 int insq=0; /* set to 1 if we are in 'single quotes' */
959 int done=0;
960
961 if (current == NULL) current = sdsempty();
962 while(!done) {
963 if (inq) {
964 if (*p == '\\' && *(p+1) == 'x' &&
965 is_hex_digit(*(p+2)) &&
966 is_hex_digit(*(p+3)))
967 {
968 unsigned char byte;
969
970 byte = (hex_digit_to_int(*(p+2))*16)+
971 hex_digit_to_int(*(p+3));
972 current = sdscatlen(current,(char*)&byte,1);
973 p += 3;
974 } else if (*p == '\\' && *(p+1)) {
975 char c;
976
977 p++;
978 switch(*p) {
979 case 'n': c = '\n'; break;
980 case 'r': c = '\r'; break;
981 case 't': c = '\t'; break;
982 case 'b': c = '\b'; break;
983 case 'a': c = '\a'; break;
984 default: c = *p; break;
985 }
986 current = sdscatlen(current,&c,1);
987 } else if (*p == '"') {
988 /* closing quote must be followed by a space or
989 * nothing at all. */
990 if (*(p+1) && !isspace(*(p+1))) goto err;
991 done=1;
992 } else if (!*p) {
993 /* unterminated quotes */
994 goto err;
995 } else {
996 current = sdscatlen(current,p,1);
997 }
998 } else if (insq) {
999 if (*p == '\\' && *(p+1) == '\'') {
1000 p++;
1001 current = sdscatlen(current,"'",1);
1002 } else if (*p == '\'') {
1003 /* closing quote must be followed by a space or
1004 * nothing at all. */
1005 if (*(p+1) && !isspace(*(p+1))) goto err;
1006 done=1;
1007 } else if (!*p) {
1008 /* unterminated quotes */
1009 goto err;
1010 } else {
1011 current = sdscatlen(current,p,1);
1012 }
1013 } else {
1014 switch(*p) {
1015 case ' ':
1016 case '\n':
1017 case '\r':
1018 case '\t':
1019 case '\0':
1020 done=1;
1021 break;
1022 case '"':
1023 inq=1;
1024 break;
1025 case '\'':
1026 insq=1;
1027 break;
1028 default:
1029 current = sdscatlen(current,p,1);
1030 break;
1031 }
1032 }
1033 if (*p) p++;
1034 }
1035 /* add the token to the vector */
1036 vector = (char**) realloc(vector,((*argc)+1)*sizeof(char*));
1037 vector[*argc] = current;
1038 (*argc)++;
1039 current = NULL;
1040 } else {
1041 /* Even on empty input string return something not NULL. */
1042 if (vector == NULL) vector = (char**) malloc(sizeof(void*));
1043 return vector;
1044 }
1045 }
1046
1047err:
1048 while((*argc)--)
1049 sdsfree(vector[*argc]);
1050 free(vector);
1051 if (current) sdsfree(current);
1052 *argc = 0;
1053 return NULL;
1054}
1055
1056/* Modify the string substituting all the occurrences of the set of
1057 * characters specified in the 'from' string to the corresponding character
1058 * in the 'to' array.
1059 *
1060 * For instance: sdsmapchars(mystring, "ho", "01", 2)
1061 * will have the effect of turning the string "hello" into "0ell1".
1062 *
1063 * The function returns the sds string pointer, that is always the same
1064 * as the input pointer since no resize is needed. */
1065sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen) {
1066 size_t j, i, l = sdslen(s);
1067
1068 for (j = 0; j < l; j++) {
1069 for (i = 0; i < setlen; i++) {
1070 if (s[j] == from[i]) {
1071 s[j] = to[i];
1072 break;
1073 }
1074 }
1075 }
1076 return s;
1077}
1078
1079/* Join an array of C strings using the specified separator (also a C string).
1080 * Returns the result as an sds string. */
1081sds sdsjoin(char **argv, int argc, char *sep) {
1082 sds join = sdsempty();
1083 int j;
1084
1085 for (j = 0; j < argc; j++) {
1086 join = sdscat(join, argv[j]);
1087 if (j != argc-1) join = sdscat(join,sep);
1088 }
1089 return join;
1090}
1091
1092/* Like sdsjoin, but joins an array of SDS strings. */
1093sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen) {
1094 sds join = sdsempty();
1095 int j;
1096
1097 for (j = 0; j < argc; j++) {
1098 join = sdscatsds(join, argv[j]);
1099 if (j != argc-1) join = sdscatlen(join,sep,seplen);
1100 }
1101 return join;
1102}
1103
1104/* Wrappers to the allocators used by SDS. Note that SDS will actually
1105 * just use the macros defined into sdsalloc.h in order to avoid to pay
1106 * the overhead of function calls. Here we define these wrappers only for
1107 * the programs SDS is linked to, if they want to touch the SDS internals
1108 * even if they use a different allocator. */
1109void *sdmalloc(size_t size) { return malloc(size); }
1110void *sdrealloc(void *ptr, size_t size) { return realloc(ptr,size); }
1111void sdfree(void *ptr) { free(ptr); }
1112