/src/duckdb/third_party/hyperloglog/sds.hpp

Source (jump to first uncovered line)
/* SDSLib 2.0 -- A C dynamic strings library
 *
 * Copyright (c) 2006-2015, Salvatore Sanfilippo <antirez at gmail dot com>
 * Copyright (c) 2015, Oran Agra
 * Copyright (c) 2015, Redis Labs, Inc
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef __SDS_H
#define __SDS_H


#ifdef _MSC_VER
#define __attribute__(A)
#define ssize_t int64_t
#endif

#define SDS_MAX_PREALLOC (1024*1024)

#include <sys/types.h>
#include <stdarg.h>
#include <stdint.h>

namespace duckdb_hll {


typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[1];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[1];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[1];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[1];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[1];
};

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

/* sdsalloc() = sdsavail() + sdslen() */
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t len);
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);

sds sdscatvprintf(sds s, const char *fmt, va_list ap);
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
    __attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif

sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, ssize_t start, ssize_t end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, ssize_t incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);

/* Export the allocator used by SDS to the program using SDS.
 * Sometimes the program SDS is linked to, may use a different set of
 * allocators, but may want to allocate or free things that SDS will
 * respectively free or allocate. */
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

#ifdef REDIS_TEST
int sdsTest(int argc, char *argv[]);
#endif
}


#endif

Coverage Report

Created: 2025-06-12 07:25

Line	Count	Source (jump to first uncovered line)
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		#ifndef __SDS_H
34		#define __SDS_H
35
36
37		#ifdef _MSC_VER
38		#define __attribute__(A)
39		#define ssize_t int64_t
40		#endif
41
42	0	#define SDS_MAX_PREALLOC (1024*1024)
43
44		#include <sys/types.h>
45		#include <stdarg.h>
46		#include <stdint.h>
47
48		namespace duckdb_hll {
49
50
51		typedef char *sds;
52
53		/* Note: sdshdr5 is never used, we just access the flags byte directly.
54		* However is here to document the layout of type 5 SDS strings. */
55		struct __attribute__ ((__packed__)) sdshdr5 {
56		unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
57		char buf[1];
58		};
59		struct __attribute__ ((__packed__)) sdshdr8 {
60		uint8_t len; /* used */
61		uint8_t alloc; /* excluding the header and null terminator */
62		unsigned char flags; /* 3 lsb of type, 5 unused bits */
63		char buf[1];
64		};
65		struct __attribute__ ((__packed__)) sdshdr16 {
66		uint16_t len; /* used */
67		uint16_t alloc; /* excluding the header and null terminator */
68		unsigned char flags; /* 3 lsb of type, 5 unused bits */
69		char buf[1];
70		};
71		struct __attribute__ ((__packed__)) sdshdr32 {
72		uint32_t len; /* used */
73		uint32_t alloc; /* excluding the header and null terminator */
74		unsigned char flags; /* 3 lsb of type, 5 unused bits */
75		char buf[1];
76		};
77		struct __attribute__ ((__packed__)) sdshdr64 {
78		uint64_t len; /* used */
79		uint64_t alloc; /* excluding the header and null terminator */
80		unsigned char flags; /* 3 lsb of type, 5 unused bits */
81		char buf[1];
82		};
83
84	0	#define SDS_TYPE_5 0
85	0	#define SDS_TYPE_8 1
86	0	#define SDS_TYPE_16 2
87	0	#define SDS_TYPE_32 3
88	0	#define SDS_TYPE_64 4
89	0	#define SDS_TYPE_MASK 7
90	0	#define SDS_TYPE_BITS 3
91	0	#define SDS_HDR_VAR(T,s) struct sdshdr##T sh = (struct sdshdr##T )((s)-(sizeof(struct sdshdr##T)));
92	0	#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
93	0	#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
94
95	0	static inline size_t sdslen(const sds s) {
96	0	unsigned char flags = s[-1];
97	0	switch(flags&SDS_TYPE_MASK) {
98	0	case SDS_TYPE_5:
99	0	return SDS_TYPE_5_LEN(flags);
100	0	case SDS_TYPE_8:
101	0	return SDS_HDR(8,s)->len;
102	0	case SDS_TYPE_16:
103	0	return SDS_HDR(16,s)->len;
104	0	case SDS_TYPE_32:
105	0	return SDS_HDR(32,s)->len;
106	0	case SDS_TYPE_64:
107	0	return SDS_HDR(64,s)->len;
108	0	}
109	0	return 0;
110	0	} Unexecuted instantiation: hyperloglog.cpp:duckdb_hll::sdslen(char) Unexecuted instantiation: sds.cpp:duckdb_hll::sdslen(char)
111
112	0	static inline size_t sdsavail(const sds s) {
113	0	unsigned char flags = s[-1];
114	0	switch(flags&SDS_TYPE_MASK) {
115	0	case SDS_TYPE_5: {
116	0	return 0;
117	0	}
118	0	case SDS_TYPE_8: {
119	0	SDS_HDR_VAR(8,s);
120	0	return sh->alloc - sh->len;
121	0	}
122	0	case SDS_TYPE_16: {
123	0	SDS_HDR_VAR(16,s);
124	0	return sh->alloc - sh->len;
125	0	}
126	0	case SDS_TYPE_32: {
127	0	SDS_HDR_VAR(32,s);
128	0	return sh->alloc - sh->len;
129	0	}
130	0	case SDS_TYPE_64: {
131	0	SDS_HDR_VAR(64,s);
132	0	return sh->alloc - sh->len;
133	0	}
134	0	}
135	0	return 0;
136	0	} Unexecuted instantiation: hyperloglog.cpp:duckdb_hll::sdsavail(char) Unexecuted instantiation: sds.cpp:duckdb_hll::sdsavail(char)
137
138	0	static inline void sdssetlen(sds s, size_t newlen) {
139	0	unsigned char flags = s[-1];
140	0	switch(flags&SDS_TYPE_MASK) {
141	0	case SDS_TYPE_5:
142	0	{
143	0	unsigned char fp = ((unsigned char)s)-1;
144	0	*fp = SDS_TYPE_5 \| (newlen << SDS_TYPE_BITS);
145	0	}
146	0	break;
147	0	case SDS_TYPE_8:
148	0	SDS_HDR(8,s)->len = newlen;
149	0	break;
150	0	case SDS_TYPE_16:
151	0	SDS_HDR(16,s)->len = newlen;
152	0	break;
153	0	case SDS_TYPE_32:
154	0	SDS_HDR(32,s)->len = newlen;
155	0	break;
156	0	case SDS_TYPE_64:
157	0	SDS_HDR(64,s)->len = newlen;
158	0	break;
159	0	}
160	0	} Unexecuted instantiation: hyperloglog.cpp:duckdb_hll::sdssetlen(char, unsigned long) Unexecuted instantiation: sds.cpp:duckdb_hll::sdssetlen(char, unsigned long)
161
162	0	static inline void sdsinclen(sds s, size_t inc) {
163	0	unsigned char flags = s[-1];
164	0	switch(flags&SDS_TYPE_MASK) {
165	0	case SDS_TYPE_5:
166	0	{
167	0	unsigned char fp = ((unsigned char)s)-1;
168	0	unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
169	0	*fp = SDS_TYPE_5 \| (newlen << SDS_TYPE_BITS);
170	0	}
171	0	break;
172	0	case SDS_TYPE_8:
173	0	SDS_HDR(8,s)->len += inc;
174	0	break;
175	0	case SDS_TYPE_16:
176	0	SDS_HDR(16,s)->len += inc;
177	0	break;
178	0	case SDS_TYPE_32:
179	0	SDS_HDR(32,s)->len += inc;
180	0	break;
181	0	case SDS_TYPE_64:
182	0	SDS_HDR(64,s)->len += inc;
183	0	break;
184	0	}
185	0	} Unexecuted instantiation: hyperloglog.cpp:duckdb_hll::sdsinclen(char, unsigned long) Unexecuted instantiation: sds.cpp:duckdb_hll::sdsinclen(char, unsigned long)
186
187		/* sdsalloc() = sdsavail() + sdslen() */
188	0	static inline size_t sdsalloc(const sds s) {
189	0	unsigned char flags = s[-1];
190	0	switch(flags&SDS_TYPE_MASK) {
191	0	case SDS_TYPE_5:
192	0	return SDS_TYPE_5_LEN(flags);
193	0	case SDS_TYPE_8:
194	0	return SDS_HDR(8,s)->alloc;
195	0	case SDS_TYPE_16:
196	0	return SDS_HDR(16,s)->alloc;
197	0	case SDS_TYPE_32:
198	0	return SDS_HDR(32,s)->alloc;
199	0	case SDS_TYPE_64:
200	0	return SDS_HDR(64,s)->alloc;
201	0	}
202	0	return 0;
203	0	} Unexecuted instantiation: hyperloglog.cpp:duckdb_hll::sdsalloc(char) Unexecuted instantiation: sds.cpp:duckdb_hll::sdsalloc(char)
204
205	0	static inline void sdssetalloc(sds s, size_t newlen) {
206	0	unsigned char flags = s[-1];
207	0	switch(flags&SDS_TYPE_MASK) {
208	0	case SDS_TYPE_5:
209		/* Nothing to do, this type has no total allocation info. */
210	0	break;
211	0	case SDS_TYPE_8:
212	0	SDS_HDR(8,s)->alloc = newlen;
213	0	break;
214	0	case SDS_TYPE_16:
215	0	SDS_HDR(16,s)->alloc = newlen;
216	0	break;
217	0	case SDS_TYPE_32:
218	0	SDS_HDR(32,s)->alloc = newlen;
219	0	break;
220	0	case SDS_TYPE_64:
221	0	SDS_HDR(64,s)->alloc = newlen;
222	0	break;
223	0	}
224	0	} Unexecuted instantiation: hyperloglog.cpp:duckdb_hll::sdssetalloc(char, unsigned long) Unexecuted instantiation: sds.cpp:duckdb_hll::sdssetalloc(char, unsigned long)
225
226		sds sdsnewlen(const void *init, size_t initlen);
227		sds sdsnew(const char *init);
228		sds sdsempty(void);
229		sds sdsdup(const sds s);
230		void sdsfree(sds s);
231		sds sdsgrowzero(sds s, size_t len);
232		sds sdscatlen(sds s, const void *t, size_t len);
233		sds sdscat(sds s, const char *t);
234		sds sdscatsds(sds s, const sds t);
235		sds sdscpylen(sds s, const char *t, size_t len);
236		sds sdscpy(sds s, const char *t);
237
238		sds sdscatvprintf(sds s, const char *fmt, va_list ap);
239		#ifdef __GNUC__
240		sds sdscatprintf(sds s, const char *fmt, ...)
241		__attribute__((format(printf, 2, 3)));
242		#else
243		sds sdscatprintf(sds s, const char *fmt, ...);
244		#endif
245
246		sds sdscatfmt(sds s, char const *fmt, ...);
247		sds sdstrim(sds s, const char *cset);
248		void sdsrange(sds s, ssize_t start, ssize_t end);
249		void sdsupdatelen(sds s);
250		void sdsclear(sds s);
251		int sdscmp(const sds s1, const sds s2);
252		sds sdssplitlen(const char s, ssize_t len, const char sep, int seplen, int count);
253		void sdsfreesplitres(sds *tokens, int count);
254		void sdstolower(sds s);
255		void sdstoupper(sds s);
256		sds sdsfromlonglong(long long value);
257		sds sdscatrepr(sds s, const char *p, size_t len);
258		sds sdssplitargs(const char line, int *argc);
259		sds sdsmapchars(sds s, const char from, const char to, size_t setlen);
260		sds sdsjoin(char *argv, int argc, char sep);
261		sds sdsjoinsds(sds argv, int argc, const char sep, size_t seplen);
262
263		/* Low level functions exposed to the user API */
264		sds sdsMakeRoomFor(sds s, size_t addlen);
265		void sdsIncrLen(sds s, ssize_t incr);
266		sds sdsRemoveFreeSpace(sds s);
267		size_t sdsAllocSize(sds s);
268		void *sdsAllocPtr(sds s);
269
270		/* Export the allocator used by SDS to the program using SDS.
271		* Sometimes the program SDS is linked to, may use a different set of
272		* allocators, but may want to allocate or free things that SDS will
273		* respectively free or allocate. */
274		void *sds_malloc(size_t size);
275		void sds_realloc(void ptr, size_t size);
276		void sds_free(void *ptr);
277
278		#ifdef REDIS_TEST
279		int sdsTest(int argc, char *argv[]);
280		#endif
281		}
282
283
284		#endif