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 "fmacros.h"
34#include <stdio.h>
35#include <stdlib.h>
36#include <string.h>
37#include <ctype.h>
38#include <assert.h>
39#include <limits.h>
40#include "sds.h"
41#include "sdsalloc.h"
42
43static inline int hi_sdsHdrSize(char type) {
44 switch(type&HI_SDS_TYPE_MASK) {
45 case HI_SDS_TYPE_5:
46 return sizeof(struct hisdshdr5);
47 case HI_SDS_TYPE_8:
48 return sizeof(struct hisdshdr8);
49 case HI_SDS_TYPE_16:
50 return sizeof(struct hisdshdr16);
51 case HI_SDS_TYPE_32:
52 return sizeof(struct hisdshdr32);
53 case HI_SDS_TYPE_64:
54 return sizeof(struct hisdshdr64);
55 }
56 return 0;
57}
58
59static inline char hi_sdsReqType(size_t string_size) {
60 if (string_size < 32)
61 return HI_SDS_TYPE_5;
62 if (string_size < 0xff)
63 return HI_SDS_TYPE_8;
64 if (string_size < 0xffff)
65 return HI_SDS_TYPE_16;
66 if (string_size < 0xffffffff)
67 return HI_SDS_TYPE_32;
68 return HI_SDS_TYPE_64;
69}
70
71/* Create a new hisds string with the content specified by the 'init' pointer
72 * and 'initlen'.
73 * If NULL is used for 'init' the string is initialized with zero bytes.
74 *
75 * The string is always null-terminated (all the hisds strings are, always) so
76 * even if you create an hisds string with:
77 *
78 * mystring = hi_sdsnewlen("abc",3);
79 *
80 * You can print the string with printf() as there is an implicit \0 at the
81 * end of the string. However the string is binary safe and can contain
82 * \0 characters in the middle, as the length is stored in the hisds header. */
83hisds hi_sdsnewlen(const void *init, size_t initlen) {
84 void *sh;
85 hisds s;
86 char type = hi_sdsReqType(initlen);
87 /* Empty strings are usually created in order to append. Use type 8
88 * since type 5 is not good at this. */
89 if (type == HI_SDS_TYPE_5 && initlen == 0) type = HI_SDS_TYPE_8;
90 int hdrlen = hi_sdsHdrSize(type);
91 unsigned char *fp; /* flags pointer. */
92
93 sh = hi_s_malloc(hdrlen+initlen+1);
94 if (sh == NULL) return NULL;
95 if (!init)
96 memset(sh, 0, hdrlen+initlen+1);
97 s = (char*)sh+hdrlen;
98 fp = ((unsigned char*)s)-1;
99 switch(type) {
100 case HI_SDS_TYPE_5: {
101 *fp = type | (initlen << HI_SDS_TYPE_BITS);
102 break;
103 }
104 case HI_SDS_TYPE_8: {
105 HI_SDS_HDR_VAR(8,s);
106 sh->len = initlen;
107 sh->alloc = initlen;
108 *fp = type;
109 break;
110 }
111 case HI_SDS_TYPE_16: {
112 HI_SDS_HDR_VAR(16,s);
113 sh->len = initlen;
114 sh->alloc = initlen;
115 *fp = type;
116 break;
117 }
118 case HI_SDS_TYPE_32: {
119 HI_SDS_HDR_VAR(32,s);
120 sh->len = initlen;
121 sh->alloc = initlen;
122 *fp = type;
123 break;
124 }
125 case HI_SDS_TYPE_64: {
126 HI_SDS_HDR_VAR(64,s);
127 sh->len = initlen;
128 sh->alloc = initlen;
129 *fp = type;
130 break;
131 }
132 }
133 if (initlen && init)
134 memcpy(s, init, initlen);
135 s[initlen] = '\0';
136 return s;
137}
138
139/* Create an empty (zero length) hisds string. Even in this case the string
140 * always has an implicit null term. */
141hisds hi_sdsempty(void) {
142 return hi_sdsnewlen("",0);
143}
144
145/* Create a new hisds string starting from a null terminated C string. */
146hisds hi_sdsnew(const char *init) {
147 size_t initlen = (init == NULL) ? 0 : strlen(init);
148 return hi_sdsnewlen(init, initlen);
149}
150
151/* Duplicate an hisds string. */
152hisds hi_sdsdup(const hisds s) {
153 return hi_sdsnewlen(s, hi_sdslen(s));
154}
155
156/* Free an hisds string. No operation is performed if 's' is NULL. */
157void hi_sdsfree(hisds s) {
158 if (s == NULL) return;
159 hi_s_free((char*)s-hi_sdsHdrSize(s[-1]));
160}
161
162/* Set the hisds string length to the length as obtained with strlen(), so
163 * considering as content only up to the first null term character.
164 *
165 * This function is useful when the hisds string is hacked manually in some
166 * way, like in the following example:
167 *
168 * s = hi_sdsnew("foobar");
169 * s[2] = '\0';
170 * hi_sdsupdatelen(s);
171 * printf("%d\n", hi_sdslen(s));
172 *
173 * The output will be "2", but if we comment out the call to hi_sdsupdatelen()
174 * the output will be "6" as the string was modified but the logical length
175 * remains 6 bytes. */
176void hi_sdsupdatelen(hisds s) {
177 int reallen = strlen(s);
178 hi_sdssetlen(s, reallen);
179}
180
181/* Modify an hisds string in-place to make it empty (zero length).
182 * However all the existing buffer is not discarded but set as free space
183 * so that next append operations will not require allocations up to the
184 * number of bytes previously available. */
185void hi_sdsclear(hisds s) {
186 hi_sdssetlen(s, 0);
187 s[0] = '\0';
188}
189
190/* Enlarge the free space at the end of the hisds string so that the caller
191 * is sure that after calling this function can overwrite up to addlen
192 * bytes after the end of the string, plus one more byte for nul term.
193 *
194 * Note: this does not change the *length* of the hisds string as returned
195 * by hi_sdslen(), but only the free buffer space we have. */
196hisds hi_sdsMakeRoomFor(hisds s, size_t addlen) {
197 void *sh, *newsh;
198 size_t avail = hi_sdsavail(s);
199 size_t len, newlen;
200 char type, oldtype = s[-1] & HI_SDS_TYPE_MASK;
201 int hdrlen;
202
203 /* Return ASAP if there is enough space left. */
204 if (avail >= addlen) return s;
205
206 len = hi_sdslen(s);
207 sh = (char*)s-hi_sdsHdrSize(oldtype);
208 newlen = (len+addlen);
209 if (newlen < HI_SDS_MAX_PREALLOC)
210 newlen *= 2;
211 else
212 newlen += HI_SDS_MAX_PREALLOC;
213
214 type = hi_sdsReqType(newlen);
215
216 /* Don't use type 5: the user is appending to the string and type 5 is
217 * not able to remember empty space, so hi_sdsMakeRoomFor() must be called
218 * at every appending operation. */
219 if (type == HI_SDS_TYPE_5) type = HI_SDS_TYPE_8;
220
221 hdrlen = hi_sdsHdrSize(type);
222 if (oldtype==type) {
223 newsh = hi_s_realloc(sh, hdrlen+newlen+1);
224 if (newsh == NULL) return NULL;
225 s = (char*)newsh+hdrlen;
226 } else {
227 /* Since the header size changes, need to move the string forward,
228 * and can't use realloc */
229 newsh = hi_s_malloc(hdrlen+newlen+1);
230 if (newsh == NULL) return NULL;
231 memcpy((char*)newsh+hdrlen, s, len+1);
232 hi_s_free(sh);
233 s = (char*)newsh+hdrlen;
234 s[-1] = type;
235 hi_sdssetlen(s, len);
236 }
237 hi_sdssetalloc(s, newlen);
238 return s;
239}
240
241/* Reallocate the hisds string so that it has no free space at the end. The
242 * contained string remains not altered, but next concatenation operations
243 * will require a reallocation.
244 *
245 * After the call, the passed hisds string is no longer valid and all the
246 * references must be substituted with the new pointer returned by the call. */
247hisds hi_sdsRemoveFreeSpace(hisds s) {
248 void *sh, *newsh;
249 char type, oldtype = s[-1] & HI_SDS_TYPE_MASK;
250 int hdrlen;
251 size_t len = hi_sdslen(s);
252 sh = (char*)s-hi_sdsHdrSize(oldtype);
253
254 type = hi_sdsReqType(len);
255 hdrlen = hi_sdsHdrSize(type);
256 if (oldtype==type) {
257 newsh = hi_s_realloc(sh, hdrlen+len+1);
258 if (newsh == NULL) return NULL;
259 s = (char*)newsh+hdrlen;
260 } else {
261 newsh = hi_s_malloc(hdrlen+len+1);
262 if (newsh == NULL) return NULL;
263 memcpy((char*)newsh+hdrlen, s, len+1);
264 hi_s_free(sh);
265 s = (char*)newsh+hdrlen;
266 s[-1] = type;
267 hi_sdssetlen(s, len);
268 }
269 hi_sdssetalloc(s, len);
270 return s;
271}
272
273/* Return the total size of the allocation of the specifed hisds string,
274 * including:
275 * 1) The hisds header before the pointer.
276 * 2) The string.
277 * 3) The free buffer at the end if any.
278 * 4) The implicit null term.
279 */
280size_t hi_sdsAllocSize(hisds s) {
281 size_t alloc = hi_sdsalloc(s);
282 return hi_sdsHdrSize(s[-1])+alloc+1;
283}
284
285/* Return the pointer of the actual SDS allocation (normally SDS strings
286 * are referenced by the start of the string buffer). */
287void *hi_sdsAllocPtr(hisds s) {
288 return (void*) (s-hi_sdsHdrSize(s[-1]));
289}
290
291/* Increment the hisds length and decrements the left free space at the
292 * end of the string according to 'incr'. Also set the null term
293 * in the new end of the string.
294 *
295 * This function is used in order to fix the string length after the
296 * user calls hi_sdsMakeRoomFor(), writes something after the end of
297 * the current string, and finally needs to set the new length.
298 *
299 * Note: it is possible to use a negative increment in order to
300 * right-trim the string.
301 *
302 * Usage example:
303 *
304 * Using hi_sdsIncrLen() and hi_sdsMakeRoomFor() it is possible to mount the
305 * following schema, to cat bytes coming from the kernel to the end of an
306 * hisds string without copying into an intermediate buffer:
307 *
308 * oldlen = hi_hi_sdslen(s);
309 * s = hi_sdsMakeRoomFor(s, BUFFER_SIZE);
310 * nread = read(fd, s+oldlen, BUFFER_SIZE);
311 * ... check for nread <= 0 and handle it ...
312 * hi_sdsIncrLen(s, nread);
313 */
314void hi_sdsIncrLen(hisds s, int incr) {
315 unsigned char flags = s[-1];
316 size_t len;
317 switch(flags&HI_SDS_TYPE_MASK) {
318 case HI_SDS_TYPE_5: {
319 unsigned char *fp = ((unsigned char*)s)-1;
320 unsigned char oldlen = HI_SDS_TYPE_5_LEN(flags);
321 assert((incr > 0 && oldlen+incr < 32) || (incr < 0 && oldlen >= (unsigned int)(-incr)));
322 *fp = HI_SDS_TYPE_5 | ((oldlen+incr) << HI_SDS_TYPE_BITS);
323 len = oldlen+incr;
324 break;
325 }
326 case HI_SDS_TYPE_8: {
327 HI_SDS_HDR_VAR(8,s);
328 assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
329 len = (sh->len += incr);
330 break;
331 }
332 case HI_SDS_TYPE_16: {
333 HI_SDS_HDR_VAR(16,s);
334 assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
335 len = (sh->len += incr);
336 break;
337 }
338 case HI_SDS_TYPE_32: {
339 HI_SDS_HDR_VAR(32,s);
340 assert((incr >= 0 && sh->alloc-sh->len >= (unsigned int)incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
341 len = (sh->len += incr);
342 break;
343 }
344 case HI_SDS_TYPE_64: {
345 HI_SDS_HDR_VAR(64,s);
346 assert((incr >= 0 && sh->alloc-sh->len >= (uint64_t)incr) || (incr < 0 && sh->len >= (uint64_t)(-incr)));
347 len = (sh->len += incr);
348 break;
349 }
350 default: len = 0; /* Just to avoid compilation warnings. */
351 }
352 s[len] = '\0';
353}
354
355/* Grow the hisds to have the specified length. Bytes that were not part of
356 * the original length of the hisds will be set to zero.
357 *
358 * if the specified length is smaller than the current length, no operation
359 * is performed. */
360hisds hi_sdsgrowzero(hisds s, size_t len) {
361 size_t curlen = hi_sdslen(s);
362
363 if (len <= curlen) return s;
364 s = hi_sdsMakeRoomFor(s,len-curlen);
365 if (s == NULL) return NULL;
366
367 /* Make sure added region doesn't contain garbage */
368 memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
369 hi_sdssetlen(s, len);
370 return s;
371}
372
373/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
374 * end of the specified hisds string 's'.
375 *
376 * After the call, the passed hisds string is no longer valid and all the
377 * references must be substituted with the new pointer returned by the call. */
378hisds hi_sdscatlen(hisds s, const void *t, size_t len) {
379 size_t curlen = hi_sdslen(s);
380
381 s = hi_sdsMakeRoomFor(s,len);
382 if (s == NULL) return NULL;
383 memcpy(s+curlen, t, len);
384 hi_sdssetlen(s, curlen+len);
385 s[curlen+len] = '\0';
386 return s;
387}
388
389/* Append the specified null termianted C string to the hisds string 's'.
390 *
391 * After the call, the passed hisds string is no longer valid and all the
392 * references must be substituted with the new pointer returned by the call. */
393hisds hi_sdscat(hisds s, const char *t) {
394 return hi_sdscatlen(s, t, strlen(t));
395}
396
397/* Append the specified hisds 't' to the existing hisds 's'.
398 *
399 * After the call, the modified hisds string is no longer valid and all the
400 * references must be substituted with the new pointer returned by the call. */
401hisds hi_sdscatsds(hisds s, const hisds t) {
402 return hi_sdscatlen(s, t, hi_sdslen(t));
403}
404
405/* Destructively modify the hisds string 's' to hold the specified binary
406 * safe string pointed by 't' of length 'len' bytes. */
407hisds hi_sdscpylen(hisds s, const char *t, size_t len) {
408 if (hi_sdsalloc(s) < len) {
409 s = hi_sdsMakeRoomFor(s,len-hi_sdslen(s));
410 if (s == NULL) return NULL;
411 }
412 memcpy(s, t, len);
413 s[len] = '\0';
414 hi_sdssetlen(s, len);
415 return s;
416}
417
418/* Like hi_sdscpylen() but 't' must be a null-terminated string so that the length
419 * of the string is obtained with strlen(). */
420hisds hi_sdscpy(hisds s, const char *t) {
421 return hi_sdscpylen(s, t, strlen(t));
422}
423
424/* Helper for hi_sdscatlonglong() doing the actual number -> string
425 * conversion. 's' must point to a string with room for at least
426 * HI_SDS_LLSTR_SIZE bytes.
427 *
428 * The function returns the length of the null-terminated string
429 * representation stored at 's'. */
430#define HI_SDS_LLSTR_SIZE 21
431int hi_sdsll2str(char *s, long long value) {
432 char *p, aux;
433 unsigned long long v;
434 size_t l;
435
436 /* Generate the string representation, this method produces
437 * an reversed string. */
438 v = (value < 0) ? -value : value;
439 p = s;
440 do {
441 *p++ = '0'+(v%10);
442 v /= 10;
443 } while(v);
444 if (value < 0) *p++ = '-';
445
446 /* Compute length and add null term. */
447 l = p-s;
448 *p = '\0';
449
450 /* Reverse the string. */
451 p--;
452 while(s < p) {
453 aux = *s;
454 *s = *p;
455 *p = aux;
456 s++;
457 p--;
458 }
459 return l;
460}
461
462/* Identical hi_sdsll2str(), but for unsigned long long type. */
463int hi_sdsull2str(char *s, unsigned long long v) {
464 char *p, aux;
465 size_t l;
466
467 /* Generate the string representation, this method produces
468 * an reversed string. */
469 p = s;
470 do {
471 *p++ = '0'+(v%10);
472 v /= 10;
473 } while(v);
474
475 /* Compute length and add null term. */
476 l = p-s;
477 *p = '\0';
478
479 /* Reverse the string. */
480 p--;
481 while(s < p) {
482 aux = *s;
483 *s = *p;
484 *p = aux;
485 s++;
486 p--;
487 }
488 return l;
489}
490
491/* Create an hisds string from a long long value. It is much faster than:
492 *
493 * hi_sdscatprintf(hi_sdsempty(),"%lld\n", value);
494 */
495hisds hi_sdsfromlonglong(long long value) {
496 char buf[HI_SDS_LLSTR_SIZE];
497 int len = hi_sdsll2str(buf,value);
498
499 return hi_sdsnewlen(buf,len);
500}
501
502/* Like hi_sdscatprintf() but gets va_list instead of being variadic. */
503hisds hi_sdscatvprintf(hisds s, const char *fmt, va_list ap) {
504 va_list cpy;
505 char staticbuf[1024], *buf = staticbuf, *t;
506 size_t buflen = strlen(fmt)*2;
507
508 /* We try to start using a static buffer for speed.
509 * If not possible we revert to heap allocation. */
510 if (buflen > sizeof(staticbuf)) {
511 buf = hi_s_malloc(buflen);
512 if (buf == NULL) return NULL;
513 } else {
514 buflen = sizeof(staticbuf);
515 }
516
517 /* Try with buffers two times bigger every time we fail to
518 * fit the string in the current buffer size. */
519 while(1) {
520 buf[buflen-2] = '\0';
521 va_copy(cpy,ap);
522 vsnprintf(buf, buflen, fmt, cpy);
523 va_end(cpy);
524 if (buf[buflen-2] != '\0') {
525 if (buf != staticbuf) hi_s_free(buf);
526 buflen *= 2;
527 buf = hi_s_malloc(buflen);
528 if (buf == NULL) return NULL;
529 continue;
530 }
531 break;
532 }
533
534 /* Finally concat the obtained string to the SDS string and return it. */
535 t = hi_sdscat(s, buf);
536 if (buf != staticbuf) hi_s_free(buf);
537 return t;
538}
539
540/* Append to the hisds string 's' a string obtained using printf-alike format
541 * specifier.
542 *
543 * After the call, the modified hisds string is no longer valid and all the
544 * references must be substituted with the new pointer returned by the call.
545 *
546 * Example:
547 *
548 * s = hi_sdsnew("Sum is: ");
549 * s = hi_sdscatprintf(s,"%d+%d = %d",a,b,a+b).
550 *
551 * Often you need to create a string from scratch with the printf-alike
552 * format. When this is the need, just use hi_sdsempty() as the target string:
553 *
554 * s = hi_sdscatprintf(hi_sdsempty(), "... your format ...", args);
555 */
556hisds hi_sdscatprintf(hisds s, const char *fmt, ...) {
557 va_list ap;
558 char *t;
559 va_start(ap, fmt);
560 t = hi_sdscatvprintf(s,fmt,ap);
561 va_end(ap);
562 return t;
563}
564
565/* This function is similar to hi_sdscatprintf, but much faster as it does
566 * not rely on sprintf() family functions implemented by the libc that
567 * are often very slow. Moreover directly handling the hisds string as
568 * new data is concatenated provides a performance improvement.
569 *
570 * However this function only handles an incompatible subset of printf-alike
571 * format specifiers:
572 *
573 * %s - C String
574 * %S - SDS string
575 * %i - signed int
576 * %I - 64 bit signed integer (long long, int64_t)
577 * %u - unsigned int
578 * %U - 64 bit unsigned integer (unsigned long long, uint64_t)
579 * %% - Verbatim "%" character.
580 */
581hisds hi_sdscatfmt(hisds s, char const *fmt, ...) {
582 const char *f = fmt;
583 int i;
584 va_list ap;
585
586 va_start(ap,fmt);
587 i = hi_sdslen(s); /* Position of the next byte to write to dest str. */
588 while(*f) {
589 char next, *str;
590 size_t l;
591 long long num;
592 unsigned long long unum;
593
594 /* Make sure there is always space for at least 1 char. */
595 if (hi_sdsavail(s)==0) {
596 s = hi_sdsMakeRoomFor(s,1);
597 if (s == NULL) goto fmt_error;
598 }
599
600 switch(*f) {
601 case '%':
602 next = *(f+1);
603 f++;
604 switch(next) {
605 case 's':
606 case 'S':
607 str = va_arg(ap,char*);
608 l = (next == 's') ? strlen(str) : hi_sdslen(str);
609 if (hi_sdsavail(s) < l) {
610 s = hi_sdsMakeRoomFor(s,l);
611 if (s == NULL) goto fmt_error;
612 }
613 memcpy(s+i,str,l);
614 hi_sdsinclen(s,l);
615 i += l;
616 break;
617 case 'i':
618 case 'I':
619 if (next == 'i')
620 num = va_arg(ap,int);
621 else
622 num = va_arg(ap,long long);
623 {
624 char buf[HI_SDS_LLSTR_SIZE];
625 l = hi_sdsll2str(buf,num);
626 if (hi_sdsavail(s) < l) {
627 s = hi_sdsMakeRoomFor(s,l);
628 if (s == NULL) goto fmt_error;
629 }
630 memcpy(s+i,buf,l);
631 hi_sdsinclen(s,l);
632 i += l;
633 }
634 break;
635 case 'u':
636 case 'U':
637 if (next == 'u')
638 unum = va_arg(ap,unsigned int);
639 else
640 unum = va_arg(ap,unsigned long long);
641 {
642 char buf[HI_SDS_LLSTR_SIZE];
643 l = hi_sdsull2str(buf,unum);
644 if (hi_sdsavail(s) < l) {
645 s = hi_sdsMakeRoomFor(s,l);
646 if (s == NULL) goto fmt_error;
647 }
648 memcpy(s+i,buf,l);
649 hi_sdsinclen(s,l);
650 i += l;
651 }
652 break;
653 default: /* Handle %% and generally %<unknown>. */
654 s[i++] = next;
655 hi_sdsinclen(s,1);
656 break;
657 }
658 break;
659 default:
660 s[i++] = *f;
661 hi_sdsinclen(s,1);
662 break;
663 }
664 f++;
665 }
666 va_end(ap);
667
668 /* Add null-term */
669 s[i] = '\0';
670 return s;
671
672fmt_error:
673 va_end(ap);
674 return NULL;
675}
676
677/* Remove the part of the string from left and from right composed just of
678 * contiguous characters found in 'cset', that is a null terminted C string.
679 *
680 * After the call, the modified hisds string is no longer valid and all the
681 * references must be substituted with the new pointer returned by the call.
682 *
683 * Example:
684 *
685 * s = hi_sdsnew("AA...AA.a.aa.aHelloWorld :::");
686 * s = hi_sdstrim(s,"Aa. :");
687 * printf("%s\n", s);
688 *
689 * Output will be just "Hello World".
690 */
691hisds hi_sdstrim(hisds s, const char *cset) {
692 char *start, *end, *sp, *ep;
693 size_t len;
694
695 sp = start = s;
696 ep = end = s+hi_sdslen(s)-1;
697 while(sp <= end && strchr(cset, *sp)) sp++;
698 while(ep > sp && strchr(cset, *ep)) ep--;
699 len = (sp > ep) ? 0 : ((ep-sp)+1);
700 if (s != sp) memmove(s, sp, len);
701 s[len] = '\0';
702 hi_sdssetlen(s,len);
703 return s;
704}
705
706/* Turn the string into a smaller (or equal) string containing only the
707 * substring specified by the 'start' and 'end' indexes.
708 *
709 * start and end can be negative, where -1 means the last character of the
710 * string, -2 the penultimate character, and so forth.
711 *
712 * The interval is inclusive, so the start and end characters will be part
713 * of the resulting string.
714 *
715 * The string is modified in-place.
716 *
717 * Return value:
718 * -1 (error) if hi_sdslen(s) is larger than maximum positive ssize_t value.
719 * 0 on success.
720 *
721 * Example:
722 *
723 * s = hi_sdsnew("Hello World");
724 * hi_sdsrange(s,1,-1); => "ello World"
725 */
726int hi_sdsrange(hisds s, ssize_t start, ssize_t end) {
727 size_t newlen, len = hi_sdslen(s);
728 if (len > SSIZE_MAX) return -1;
729
730 if (len == 0) return 0;
731 if (start < 0) {
732 start = len+start;
733 if (start < 0) start = 0;
734 }
735 if (end < 0) {
736 end = len+end;
737 if (end < 0) end = 0;
738 }
739 newlen = (start > end) ? 0 : (end-start)+1;
740 if (newlen != 0) {
741 if (start >= (ssize_t)len) {
742 newlen = 0;
743 } else if (end >= (ssize_t)len) {
744 end = len-1;
745 newlen = (start > end) ? 0 : (end-start)+1;
746 }
747 } else {
748 start = 0;
749 }
750 if (start && newlen) memmove(s, s+start, newlen);
751 s[newlen] = 0;
752 hi_sdssetlen(s,newlen);
753 return 0;
754}
755
756/* Apply tolower() to every character of the hisds string 's'. */
757void hi_sdstolower(hisds s) {
758 int len = hi_sdslen(s), j;
759
760 for (j = 0; j < len; j++) s[j] = tolower(s[j]);
761}
762
763/* Apply toupper() to every character of the hisds string 's'. */
764void hi_sdstoupper(hisds s) {
765 int len = hi_sdslen(s), j;
766
767 for (j = 0; j < len; j++) s[j] = toupper(s[j]);
768}
769
770/* Compare two hisds strings s1 and s2 with memcmp().
771 *
772 * Return value:
773 *
774 * positive if s1 > s2.
775 * negative if s1 < s2.
776 * 0 if s1 and s2 are exactly the same binary string.
777 *
778 * If two strings share exactly the same prefix, but one of the two has
779 * additional characters, the longer string is considered to be greater than
780 * the smaller one. */
781int hi_sdscmp(const hisds s1, const hisds s2) {
782 size_t l1, l2, minlen;
783 int cmp;
784
785 l1 = hi_sdslen(s1);
786 l2 = hi_sdslen(s2);
787 minlen = (l1 < l2) ? l1 : l2;
788 cmp = memcmp(s1,s2,minlen);
789 if (cmp == 0) return l1-l2;
790 return cmp;
791}
792
793/* Split 's' with separator in 'sep'. An array
794 * of hisds strings is returned. *count will be set
795 * by reference to the number of tokens returned.
796 *
797 * On out of memory, zero length string, zero length
798 * separator, NULL is returned.
799 *
800 * Note that 'sep' is able to split a string using
801 * a multi-character separator. For example
802 * hi_sdssplit("foo_-_bar","_-_"); will return two
803 * elements "foo" and "bar".
804 *
805 * This version of the function is binary-safe but
806 * requires length arguments. hi_sdssplit() is just the
807 * same function but for zero-terminated strings.
808 */
809hisds *hi_sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count) {
810 int elements = 0, slots = 5, start = 0, j;
811 hisds *tokens;
812
813 if (seplen < 1 || len < 0) return NULL;
814
815 tokens = hi_s_malloc(sizeof(hisds)*slots);
816 if (tokens == NULL) return NULL;
817
818 if (len == 0) {
819 *count = 0;
820 return tokens;
821 }
822 for (j = 0; j < (len-(seplen-1)); j++) {
823 /* make sure there is room for the next element and the final one */
824 if (slots < elements+2) {
825 hisds *newtokens;
826
827 slots *= 2;
828 newtokens = hi_s_realloc(tokens,sizeof(hisds)*slots);
829 if (newtokens == NULL) goto cleanup;
830 tokens = newtokens;
831 }
832 /* search the separator */
833 if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) {
834 tokens[elements] = hi_sdsnewlen(s+start,j-start);
835 if (tokens[elements] == NULL) goto cleanup;
836 elements++;
837 start = j+seplen;
838 j = j+seplen-1; /* skip the separator */
839 }
840 }
841 /* Add the final element. We are sure there is room in the tokens array. */
842 tokens[elements] = hi_sdsnewlen(s+start,len-start);
843 if (tokens[elements] == NULL) goto cleanup;
844 elements++;
845 *count = elements;
846 return tokens;
847
848cleanup:
849 {
850 int i;
851 for (i = 0; i < elements; i++) hi_sdsfree(tokens[i]);
852 hi_s_free(tokens);
853 *count = 0;
854 return NULL;
855 }
856}
857
858/* Free the result returned by hi_sdssplitlen(), or do nothing if 'tokens' is NULL. */
859void hi_sdsfreesplitres(hisds *tokens, int count) {
860 if (!tokens) return;
861 while(count--)
862 hi_sdsfree(tokens[count]);
863 hi_s_free(tokens);
864}
865
866/* Append to the hisds string "s" an escaped string representation where
867 * all the non-printable characters (tested with isprint()) are turned into
868 * escapes in the form "\n\r\a...." or "\x<hex-number>".
869 *
870 * After the call, the modified hisds string is no longer valid and all the
871 * references must be substituted with the new pointer returned by the call. */
872hisds hi_sdscatrepr(hisds s, const char *p, size_t len) {
873 s = hi_sdscatlen(s,"\"",1);
874 while(len--) {
875 switch(*p) {
876 case '\\':
877 case '"':
878 s = hi_sdscatprintf(s,"\\%c",*p);
879 break;
880 case '\n': s = hi_sdscatlen(s,"\\n",2); break;
881 case '\r': s = hi_sdscatlen(s,"\\r",2); break;
882 case '\t': s = hi_sdscatlen(s,"\\t",2); break;
883 case '\a': s = hi_sdscatlen(s,"\\a",2); break;
884 case '\b': s = hi_sdscatlen(s,"\\b",2); break;
885 default:
886 if (isprint(*p))
887 s = hi_sdscatprintf(s,"%c",*p);
888 else
889 s = hi_sdscatprintf(s,"\\x%02x",(unsigned char)*p);
890 break;
891 }
892 p++;
893 }
894 return hi_sdscatlen(s,"\"",1);
895}
896
897/* Helper function for hi_sdssplitargs() that converts a hex digit into an
898 * integer from 0 to 15 */
899static int hi_hex_digit_to_int(char c) {
900 switch(c) {
901 case '0': return 0;
902 case '1': return 1;
903 case '2': return 2;
904 case '3': return 3;
905 case '4': return 4;
906 case '5': return 5;
907 case '6': return 6;
908 case '7': return 7;
909 case '8': return 8;
910 case '9': return 9;
911 case 'a': case 'A': return 10;
912 case 'b': case 'B': return 11;
913 case 'c': case 'C': return 12;
914 case 'd': case 'D': return 13;
915 case 'e': case 'E': return 14;
916 case 'f': case 'F': return 15;
917 default: return 0;
918 }
919}
920
921/* Split a line into arguments, where every argument can be in the
922 * following programming-language REPL-alike form:
923 *
924 * foo bar "newline are supported\n" and "\xff\x00otherstuff"
925 *
926 * The number of arguments is stored into *argc, and an array
927 * of hisds is returned.
928 *
929 * The caller should free the resulting array of hisds strings with
930 * hi_sdsfreesplitres().
931 *
932 * Note that hi_sdscatrepr() is able to convert back a string into
933 * a quoted string in the same format hi_sdssplitargs() is able to parse.
934 *
935 * The function returns the allocated tokens on success, even when the
936 * input string is empty, or NULL if the input contains unbalanced
937 * quotes or closed quotes followed by non space characters
938 * as in: "foo"bar or "foo'
939 */
940hisds *hi_sdssplitargs(const char *line, int *argc) {
941 const char *p = line;
942 char *current = NULL;
943 char **vector = NULL;
944
945 *argc = 0;
946 while(1) {
947 /* skip blanks */
948 while(*p && isspace(*p)) p++;
949 if (*p) {
950 /* get a token */
951 int inq=0; /* set to 1 if we are in "quotes" */
952 int insq=0; /* set to 1 if we are in 'single quotes' */
953 int done=0;
954
955 if (current == NULL) current = hi_sdsempty();
956 while(!done) {
957 if (inq) {
958 if (*p == '\\' && *(p+1) == 'x' &&
959 isxdigit(*(p+2)) &&
960 isxdigit(*(p+3)))
961 {
962 unsigned char byte;
963
964 byte = (hi_hex_digit_to_int(*(p+2))*16)+
965 hi_hex_digit_to_int(*(p+3));
966 current = hi_sdscatlen(current,(char*)&byte,1);
967 p += 3;
968 } else if (*p == '\\' && *(p+1)) {
969 char c;
970
971 p++;
972 switch(*p) {
973 case 'n': c = '\n'; break;
974 case 'r': c = '\r'; break;
975 case 't': c = '\t'; break;
976 case 'b': c = '\b'; break;
977 case 'a': c = '\a'; break;
978 default: c = *p; break;
979 }
980 current = hi_sdscatlen(current,&c,1);
981 } else if (*p == '"') {
982 /* closing quote must be followed by a space or
983 * nothing at all. */
984 if (*(p+1) && !isspace(*(p+1))) goto err;
985 done=1;
986 } else if (!*p) {
987 /* unterminated quotes */
988 goto err;
989 } else {
990 current = hi_sdscatlen(current,p,1);
991 }
992 } else if (insq) {
993 if (*p == '\\' && *(p+1) == '\'') {
994 p++;
995 current = hi_sdscatlen(current,"'",1);
996 } else if (*p == '\'') {
997 /* closing quote must be followed by a space or
998 * nothing at all. */
999 if (*(p+1) && !isspace(*(p+1))) goto err;
1000 done=1;
1001 } else if (!*p) {
1002 /* unterminated quotes */
1003 goto err;
1004 } else {
1005 current = hi_sdscatlen(current,p,1);
1006 }
1007 } else {
1008 switch(*p) {
1009 case ' ':
1010 case '\n':
1011 case '\r':
1012 case '\t':
1013 case '\0':
1014 done=1;
1015 break;
1016 case '"':
1017 inq=1;
1018 break;
1019 case '\'':
1020 insq=1;
1021 break;
1022 default:
1023 current = hi_sdscatlen(current,p,1);
1024 break;
1025 }
1026 }
1027 if (*p) p++;
1028 }
1029 /* add the token to the vector */
1030 {
1031 char **new_vector = hi_s_realloc(vector,((*argc)+1)*sizeof(char*));
1032 if (new_vector == NULL) {
1033 hi_s_free(vector);
1034 return NULL;
1035 }
1036
1037 vector = new_vector;
1038 vector[*argc] = current;
1039 (*argc)++;
1040 current = NULL;
1041 }
1042 } else {
1043 /* Even on empty input string return something not NULL. */
1044 if (vector == NULL) vector = hi_s_malloc(sizeof(void*));
1045 return vector;
1046 }
1047 }
1048
1049err:
1050 while((*argc)--)
1051 hi_sdsfree(vector[*argc]);
1052 hi_s_free(vector);
1053 if (current) hi_sdsfree(current);
1054 *argc = 0;
1055 return NULL;
1056}
1057
1058/* Modify the string substituting all the occurrences of the set of
1059 * characters specified in the 'from' string to the corresponding character
1060 * in the 'to' array.
1061 *
1062 * For instance: hi_sdsmapchars(mystring, "ho", "01", 2)
1063 * will have the effect of turning the string "hello" into "0ell1".
1064 *
1065 * The function returns the hisds string pointer, that is always the same
1066 * as the input pointer since no resize is needed. */
1067hisds hi_sdsmapchars(hisds s, const char *from, const char *to, size_t setlen) {
1068 size_t j, i, l = hi_sdslen(s);
1069
1070 for (j = 0; j < l; j++) {
1071 for (i = 0; i < setlen; i++) {
1072 if (s[j] == from[i]) {
1073 s[j] = to[i];
1074 break;
1075 }
1076 }
1077 }
1078 return s;
1079}
1080
1081/* Join an array of C strings using the specified separator (also a C string).
1082 * Returns the result as an hisds string. */
1083hisds hi_sdsjoin(char **argv, int argc, char *sep) {
1084 hisds join = hi_sdsempty();
1085 int j;
1086
1087 for (j = 0; j < argc; j++) {
1088 join = hi_sdscat(join, argv[j]);
1089 if (j != argc-1) join = hi_sdscat(join,sep);
1090 }
1091 return join;
1092}
1093
1094/* Like hi_sdsjoin, but joins an array of SDS strings. */
1095hisds hi_sdsjoinsds(hisds *argv, int argc, const char *sep, size_t seplen) {
1096 hisds join = hi_sdsempty();
1097 int j;
1098
1099 for (j = 0; j < argc; j++) {
1100 join = hi_sdscatsds(join, argv[j]);
1101 if (j != argc-1) join = hi_sdscatlen(join,sep,seplen);
1102 }
1103 return join;
1104}
1105
1106/* Wrappers to the allocators used by SDS. Note that SDS will actually
1107 * just use the macros defined into sdsalloc.h in order to avoid to pay
1108 * the overhead of function calls. Here we define these wrappers only for
1109 * the programs SDS is linked to, if they want to touch the SDS internals
1110 * even if they use a different allocator. */
1111void *hi_sds_malloc(size_t size) { return hi_s_malloc(size); }
1112void *hi_sds_realloc(void *ptr, size_t size) { return hi_s_realloc(ptr,size); }
1113void hi_sds_free(void *ptr) { hi_s_free(ptr); }
1114
1115#if defined(HI_SDS_TEST_MAIN)
1116#include <stdio.h>
1117#include "testhelp.h"
1118#include "limits.h"
1119
1120#define UNUSED(x) (void)(x)
1121int hi_sdsTest(void) {
1122 {
1123 hisds x = hi_sdsnew("foo"), y;
1124
1125 test_cond("Create a string and obtain the length",
1126 hi_sdslen(x) == 3 && memcmp(x,"foo\0",4) == 0)
1127
1128 hi_sdsfree(x);
1129 x = hi_sdsnewlen("foo",2);
1130 test_cond("Create a string with specified length",
1131 hi_sdslen(x) == 2 && memcmp(x,"fo\0",3) == 0)
1132
1133 x = hi_sdscat(x,"bar");
1134 test_cond("Strings concatenation",
1135 hi_sdslen(x) == 5 && memcmp(x,"fobar\0",6) == 0);
1136
1137 x = hi_sdscpy(x,"a");
1138 test_cond("hi_sdscpy() against an originally longer string",
1139 hi_sdslen(x) == 1 && memcmp(x,"a\0",2) == 0)
1140
1141 x = hi_sdscpy(x,"xyzxxxxxxxxxxyyyyyyyyyykkkkkkkkkk");
1142 test_cond("hi_sdscpy() against an originally shorter string",
1143 hi_sdslen(x) == 33 &&
1144 memcmp(x,"xyzxxxxxxxxxxyyyyyyyyyykkkkkkkkkk\0",33) == 0)
1145
1146 hi_sdsfree(x);
1147 x = hi_sdscatprintf(hi_sdsempty(),"%d",123);
1148 test_cond("hi_sdscatprintf() seems working in the base case",
1149 hi_sdslen(x) == 3 && memcmp(x,"123\0",4) == 0)
1150
1151 hi_sdsfree(x);
1152 x = hi_sdsnew("--");
1153 x = hi_sdscatfmt(x, "Hello %s World %I,%I--", "Hi!", LLONG_MIN,LLONG_MAX);
1154 test_cond("hi_sdscatfmt() seems working in the base case",
1155 hi_sdslen(x) == 60 &&
1156 memcmp(x,"--Hello Hi! World -9223372036854775808,"
1157 "9223372036854775807--",60) == 0)
1158 printf("[%s]\n",x);
1159
1160 hi_sdsfree(x);
1161 x = hi_sdsnew("--");
1162 x = hi_sdscatfmt(x, "%u,%U--", UINT_MAX, ULLONG_MAX);
1163 test_cond("hi_sdscatfmt() seems working with unsigned numbers",
1164 hi_sdslen(x) == 35 &&
1165 memcmp(x,"--4294967295,18446744073709551615--",35) == 0)
1166
1167 hi_sdsfree(x);
1168 x = hi_sdsnew(" x ");
1169 hi_sdstrim(x," x");
1170 test_cond("hi_sdstrim() works when all chars match",
1171 hi_sdslen(x) == 0)
1172
1173 hi_sdsfree(x);
1174 x = hi_sdsnew(" x ");
1175 hi_sdstrim(x," ");
1176 test_cond("hi_sdstrim() works when a single char remains",
1177 hi_sdslen(x) == 1 && x[0] == 'x')
1178
1179 hi_sdsfree(x);
1180 x = hi_sdsnew("xxciaoyyy");
1181 hi_sdstrim(x,"xy");
1182 test_cond("hi_sdstrim() correctly trims characters",
1183 hi_sdslen(x) == 4 && memcmp(x,"ciao\0",5) == 0)
1184
1185 y = hi_sdsdup(x);
1186 hi_sdsrange(y,1,1);
1187 test_cond("hi_sdsrange(...,1,1)",
1188 hi_sdslen(y) == 1 && memcmp(y,"i\0",2) == 0)
1189
1190 hi_sdsfree(y);
1191 y = hi_sdsdup(x);
1192 hi_sdsrange(y,1,-1);
1193 test_cond("hi_sdsrange(...,1,-1)",
1194 hi_sdslen(y) == 3 && memcmp(y,"iao\0",4) == 0)
1195
1196 hi_sdsfree(y);
1197 y = hi_sdsdup(x);
1198 hi_sdsrange(y,-2,-1);
1199 test_cond("hi_sdsrange(...,-2,-1)",
1200 hi_sdslen(y) == 2 && memcmp(y,"ao\0",3) == 0)
1201
1202 hi_sdsfree(y);
1203 y = hi_sdsdup(x);
1204 hi_sdsrange(y,2,1);
1205 test_cond("hi_sdsrange(...,2,1)",
1206 hi_sdslen(y) == 0 && memcmp(y,"\0",1) == 0)
1207
1208 hi_sdsfree(y);
1209 y = hi_sdsdup(x);
1210 hi_sdsrange(y,1,100);
1211 test_cond("hi_sdsrange(...,1,100)",
1212 hi_sdslen(y) == 3 && memcmp(y,"iao\0",4) == 0)
1213
1214 hi_sdsfree(y);
1215 y = hi_sdsdup(x);
1216 hi_sdsrange(y,100,100);
1217 test_cond("hi_sdsrange(...,100,100)",
1218 hi_sdslen(y) == 0 && memcmp(y,"\0",1) == 0)
1219
1220 hi_sdsfree(y);
1221 hi_sdsfree(x);
1222 x = hi_sdsnew("foo");
1223 y = hi_sdsnew("foa");
1224 test_cond("hi_sdscmp(foo,foa)", hi_sdscmp(x,y) > 0)
1225
1226 hi_sdsfree(y);
1227 hi_sdsfree(x);
1228 x = hi_sdsnew("bar");
1229 y = hi_sdsnew("bar");
1230 test_cond("hi_sdscmp(bar,bar)", hi_sdscmp(x,y) == 0)
1231
1232 hi_sdsfree(y);
1233 hi_sdsfree(x);
1234 x = hi_sdsnew("aar");
1235 y = hi_sdsnew("bar");
1236 test_cond("hi_sdscmp(bar,bar)", hi_sdscmp(x,y) < 0)
1237
1238 hi_sdsfree(y);
1239 hi_sdsfree(x);
1240 x = hi_sdsnewlen("\a\n\0foo\r",7);
1241 y = hi_sdscatrepr(hi_sdsempty(),x,hi_sdslen(x));
1242 test_cond("hi_sdscatrepr(...data...)",
1243 memcmp(y,"\"\\a\\n\\x00foo\\r\"",15) == 0)
1244
1245 {
1246 unsigned int oldfree;
1247 char *p;
1248 int step = 10, j, i;
1249
1250 hi_sdsfree(x);
1251 hi_sdsfree(y);
1252 x = hi_sdsnew("0");
1253 test_cond("hi_sdsnew() free/len buffers", hi_sdslen(x) == 1 && hi_sdsavail(x) == 0);
1254
1255 /* Run the test a few times in order to hit the first two
1256 * SDS header types. */
1257 for (i = 0; i < 10; i++) {
1258 int oldlen = hi_sdslen(x);
1259 x = hi_sdsMakeRoomFor(x,step);
1260 int type = x[-1]&HI_SDS_TYPE_MASK;
1261
1262 test_cond("sdsMakeRoomFor() len", hi_sdslen(x) == oldlen);
1263 if (type != HI_SDS_TYPE_5) {
1264 test_cond("hi_sdsMakeRoomFor() free", hi_sdsavail(x) >= step);
1265 oldfree = hi_sdsavail(x);
1266 }
1267 p = x+oldlen;
1268 for (j = 0; j < step; j++) {
1269 p[j] = 'A'+j;
1270 }
1271 hi_sdsIncrLen(x,step);
1272 }
1273 test_cond("hi_sdsMakeRoomFor() content",
1274 memcmp("0ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ",x,101) == 0);
1275 test_cond("sdsMakeRoomFor() final length",hi_sdslen(x)==101);
1276
1277 hi_sdsfree(x);
1278 }
1279 }
1280 test_report();
1281 return 0;
1282}
1283#endif
1284
1285#ifdef HI_SDS_TEST_MAIN
1286int main(void) {
1287 return hi_sdsTest();
1288}
1289#endif
1290