Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of "what is the source code related to Redis SDS". The editor shows you the operation process through an actual case. The method of operation is simple and fast, and it is practical. I hope that this article "what is the source code related to Redis SDS" can help you solve the problem.

The source codes related to sds in Redis are all in src/sds.c and src/sds.h, in which sds.h defines all the api of SDS, of course, it also implements some api, such as sds length, sds remaining free space. In no hurry to look at the code, let's first take a look at the data structure of sds, and then you can see at a glance why the code is written that way.

Sdshdr data structure

Redis provides several sds implementations of sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64, of which except sdshdr5 is special, the other sdshdr is not only the difference in the type of the two fields. I'll take sdshdr8 and sdshdr16 as an example, and their struct definitions are as follows.

Struct _ _ attribute__ ((_ _ packed__)) sdshdr8 {uint8_t len; / * Space used * / uint8_t alloc; / * the total available character space should be the size of the actual buf minus 1 (because the c string must end with\ 0, not counted) * / unsigned char flags / * flag bit, mainly to identify the number of sdshdr, currently only 3 digits are used, and there are still 5 spare bits * / char buf []; / * where the string is really stored * /}; 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 [];}

Sdshdr32 sdshdr64 is also consistent with the above structure, except that len and alloc have different data types. Compared with the c native string, sds has three more fields: len, alloc and flag to store some additional information. Redis takes into account the huge loss caused by string concatenation, so every time you create a new sds, you will pre-allocate some space to cope with future growth. Friends who are familiar with the relationship between sds and C string may decide that it is just like the relationship between String and StringBuffer in java. It is precisely because of the mechanism of reserving space that redis needs to record the allocated and total space size, and of course the available space is calculated directly.

Next question, why does redis bother to provide five SDS from sdshdr5 to sdshdr64? I think this can only show that the Redis author scratches the memory mechanism at the expense of the simplicity of the code in exchange for a few bytes of memory saved by each sds. We can see from the sds initialization methods sdsnew and sdsnewlen that when creating a new sds, redis needs to pass the initialization length, and then determine which kind of sdshdr to use according to the initialization length, and then use sdshdr8 if the length of the initialization is less than 2 ^ 8. In this way, len and alloc only occupy two bytes, and the relatively short string may be very large, so the memory saved is still very considerable. Knowing the data structure and design principle of sds, the code of sdsnewlen is very easy to understand as follows:

Sds sdsnewlen (const void * init, size_t initlen) {void * sh; sds s; / / determines which sdshdr char type = sdsReqType (initlen) to use based on the initialization length; / * the empty string will append later, but sdshdr5 is not suitable for append, so it is directly replaced with sdshdr8 * / if (type = SDS_TYPE_5 & & initlen = 0) type = SDS_TYPE_8; int hdrlen = sdsHdrSize (type); unsigned char * fp / * flags pointer. * / sh = s_malloc (hdrlen+initlen+1); if (sh = = NULL) return NULL; if (init==SDS_NOINIT) init= NULL; else if (! init) memset (sh, 0, hdrlen+initlen+1); / * Note: the returned s is not a pointer directly to sds, but a pointer to a string in sds. The pointer to sds also needs to be * calculated based on s and hdrlen * / s = (char*) sh+hdrlen Fp = ((unsigned char*) s)-1; switch (type) {case SDS_TYPE_5: {* fp = type | (initlen len = initlen; sh- > alloc = initlen; * fp = type; break;} case SDS_TYPE_16: {SDS_HDR_VAR (16); sh- > len = initlen Sh- > alloc = initlen; * fp = type; break;} case SDS_TYPE_32: {SDS_HDR_VAR (32 cores); sh- > len = initlen; sh- > alloc = initlen; * fp = type; break } case SDS_TYPE_64: {SDS_HDR_VAR (64 init s); sh- > len = initlen; sh- > alloc = initlen; * fp = type; break;}} if (initlen & & init) memcpy (s, init, initlen); s [initlen] ='\ 0wow; return s;} use of SDS

I specifically noted in the above code that the sds pointer returned by sdsnewlen () does not point directly to the address of sdshdr, but directly to the address of buf in sdshdr. What's the advantage of doing this? The advantage is that it is compatible with c native strings. Buf is actually a C native string + part of the free space, separated by the special symbol'\ 0', and'\ 0' is a symbol that identifies the end of the C string, so it is compatible with the C native string, and the API of some C strings can be used directly. Of course, this also has disadvantages, so it is impossible to get the specific values of len and alloc directly, but it is not impossible.

When we get a sds, let's say the sds is called S. in fact, we don't know anything about this sds at first, even if he is sdshdr. At this time, we can look at the first byte of s. We already know the data structure of sdshdr. The first byte is flag. According to the specific value of flag, we can infer which sdshdr s is, and we can also infer the real address of sds. Knowing its len and alloc accordingly, the following somewhat obscure code is easy to understand.

Oldtype = s [- 1] & SDS_TYPE_MASK; / / SDS_TYPE_MASK = 7 calculate the type of sdshdr by looking at the byte before s (flag). / / this macro definition directly calculates the memory address of the sdshdr header # define SDS_HDR (TMagazs) ((struct sdshdr##T *) ((s)-(sizeof (struct sdshdr##T) # define SDS_TYPE_5_LEN (f) ((f) > > SDS_TYPE_BITS) / / get the length supported by sds static inline size_t sdslen (const sds s) {unsigned char flags = s [- 1] / /-1 equals to getting the flag field switch (flags&SDS_TYPE_MASK) {case SDS_TYPE_5: return SDS_TYPE_5_LEN (flags) in sdshdr; case SDS_TYPE_8: return SDS_HDR (8Jing s)-> len / / Macro replacement gets the len in sdshdr. / / the code that omits SDS_TYPE_16 SDS_TYPE_32. Case SDS_TYPE_64: return SDS_HDR (64 flags&SDS_TYPE_MASK)-> len;} return 0;} / / get the size of sds remaining free space 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 alloc s); return sh- > alloc-sh- > len;}. / / omit the code of SDS_TYPE_16 SDS_TYPE_32. Case SDS_TYPE_64: {SDS_HDR_VAR (64 sh-); return sh- > alloc-sh- > len;}} return 0;} / * return the actual starting position pointer of sds * / void* sdsAllocPtr (sds s) {return (void*) (s-sdsHdrSize (s [- 1]));} expansion of SDS

When doing string concatenation, the remaining free space of sds may be insufficient. You need to expand your capacity at this time. When and how should you expand it? This is a question that has to be considered. Many data structures in Java have a dynamic capacity expansion mechanism, such as StringBuffer,HashMap, which is very similar to sds, they will dynamically determine whether there is enough space in the process of use, and basically they all adopt the method of exponential expansion first, and then linear expansion begins after a certain size limit. Redis is no exception. Redis is doubled within 10241024. As long as it does not exceed 10241024, it is necessary to apply for an additional 200% space. However, once the total length exceeds 10241024 bytes, the capacity will only be expanded by 10241024 bytes at most. The sds expansion code in Redis is in sdsMakeRoomFor (), and you can see that this is called directly or indirectly at the beginning of the API of many string changes. Unlike the expansion of StringBuffer in Java, Redis also needs to consider the change of sdshdr type with different string length. The specific code is as follows:

/ / expand the actual free space of sds so that more strings can be concatenated later. / Note: the length of sds is not actually changed here, but more available space is added (buf) sds sdsMakeRoomFor (sds s, size_t addlen) {void * sh, * newsh; size_t avail = sdsavail (s); size_t len, newlen; char type, oldtype = s [- 1] & SDS_TYPE_MASK; / / SDS_TYPE_MASK = 7 int hdrlen / * if there is enough space left, directly return * / if (avail > = addlen) return s; len = sdslen (s); sh = (char*) s-sdsHdrSize (oldtype); newlen = (len+addlen) / / before the SDS_MAX_PREALLOC is exceeded, the capacity is expanded by two times, and only if (newlen < SDS_MAX_PREALLOC) / / SDS_MAX_PREALLOC = 1024024 newlen * = 2; else newlen + = SDS_MAX_PREALLOC; type = sdsReqType (newlen) / * type5 will not be used in real use. If you encounter type5, use type8*/ if (type== SDS_TYPE_5) type= SDS_TYPE_8; hdrlen = sdsHdrSize (type) directly; if (oldtype==type) {newsh = s_realloc (sh, hdrlen+newlen+1); if (newsh = = NULL) return NULL; s = (char*) newsh+hdrlen } else {/ / expansion is actually applying for new space, and then moving the old data over newsh = s_malloc (hdrlen+newlen+1); if (newsh = = NULL) return NULL; memcpy ((char*) newsh+hdrlen, s, len+1); s_free (sh); s = (char*) newsh+hdrlen; s [- 1] = type; sdssetlen (s, len) } sdssetalloc (s, newlen); return s;} commonly used API

Sds.c and a lot of source code I have not posted, other code is essentially written around sdshdr data structures and various string operations (basically all kinds of string creation, splicing, copy, expansion …) As long as you know the design principle of sds, I believe you can easily write it. Here I will list all the API related to sds. Those who are interested in the source code can move to src/sds.c. For a list of API in the Chinese annotated version, please see src/sds.c.

Sds sdsnewlen (const void * init, size_t initlen); / / create a new sdssds sdsnew with the capacity of initlen (const char * init); / / create a new sds with a string of null and the default length of 0 sds sdsempty (void); / / create a new sds based on the actual length of s to reduce the memory footprint void sdsfree (sdss) / / release sds sds sdsgrowzero (sds s, size_t len); / / increase sds to a specified length, and fill sds sdscatlen (sds s, const void * t, size_t len) with 0 in the new space created; / / concatenate the specified length part of the string t on sds sds sdscat (sds s, const char * t); / / concatenate the string t to sds sds sdscatsds (sds s, const sds t) / concatenate two sds together sds sdscpylen (sds s, const char * t, size_t len); / / copy the specified length of the string t to sds sds sdscpy (sds s, const char * t); / / copy the string t to sds sds sdscatvprintf (sds s, const char * fmt, va_list ap); / / concatenate the characters formatted in printf to sds sds sdscatfmt (sds s, char const * fmt,...) / / format multiple parameters into a string and then concatenate sds sdstrim (sds s, const char * cset) on sds; / / remove the characters void sdsrange (sds s, ssize_t start, ssize_t end) that begin or end in cset in sds; / / intercept void sdsupdatelen (sds s) of sds; / / update the length of sds string void sdsclear (sds s) / / clear the contents of sds without releasing space int sdscmp (const sds S1, const sds S2); / / sds string comparison size sds * sdssplitlen (const char * s, ssize_t len, const char * sep, int seplen, int * count); void sdsfreesplitres (sds * tokens, int count); void sdstolower (sdss); / / string conversion to lowercase void sdstoupper (sdss); / / string to uppercase sds sdsfromlonglong (longlong value) / convert a long long number into sds sds sdscatrepr (sdss, const char * p, size_t len); sds * sdssplitargs (const char * line, int * argc); sds sdsmapchars (sdss, const char * from, const char * to, size_t setlen); sds sdsjoin (char * * argv, int argc, char * sep); / / concatenate string arrays with specified delimiters sds sdsjoinsds (sds * argv, int argc, const char * sep, size_t seplen) / / concatenate the sds array with specified delimiters / * sds underlying api * / sds sdsMakeRoomFor (sds s, size_t addlen); / / sds expand void sdsIncrLen (sds s, ssize_t incr); / / expand specified length sds sdsRemoveFreeSpace (sds s); / / release excess space size_t sdsAllocSize (sds s) occupied by sds; / / return the total memory occupied by sds void * sdsAllocPtr (sds s) / / return sds actual starting position pointer void * sds_malloc (size_t size); / / allocate space for sds void * sds_realloc (void * ptr, size_t size); / / void sds_free (void * ptr); / / release sds space about "what is the Redis SDS-related source code". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.