本文主要是介绍漫话Redis源码之三十三，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一个函数是分配新的rax, 返回的是指针。这个函数对异常的考虑也还很全，如果获取不到内存，就返回NULL
/* Allocate a new rax and return its pointer. On out of memory the function* returns NULL. */
rax *raxNew(void) {rax *rax = rax_malloc(sizeof(*rax));if (rax == NULL) return NULL;rax->numele = 0;rax->numnodes = 1;rax->head = raxNewNode(0,0);if (rax->head == NULL) {rax_free(rax);return NULL;} else {return rax;}
}/* realloc the node to make room for auxiliary data in order* to store an item in that node. On out of memory NULL is returned. */
raxNode *raxReallocForData(raxNode *n, void *data) {if (data == NULL) return n; /* No reallocation needed, setting isnull=1 */size_t curlen = raxNodeCurrentLength(n);return rax_realloc(n,curlen+sizeof(void*));
}/* Set the node auxiliary data to the specified pointer. */
void raxSetData(raxNode *n, void *data) {n->iskey = 1;if (data != NULL) {n->isnull = 0;void **ndata = (void**)((char*)n+raxNodeCurrentLength(n)-sizeof(void*));memcpy(ndata,&data,sizeof(data));} else {n->isnull = 1;}
}/* Get the node auxiliary data. */
void *raxGetData(raxNode *n) {if (n->isnull) return NULL;void **ndata =(void**)((char*)n+raxNodeCurrentLength(n)-sizeof(void*));void *data;memcpy(&data,ndata,sizeof(data));return data;
}/* Add a new child to the node 'n' representing the character 'c' and return* its new pointer, as well as the child pointer by reference. Additionally* '***parentlink' is populated with the raxNode pointer-to-pointer of where* the new child was stored, which is useful for the caller to replace the* child pointer if it gets reallocated.** On success the new parent node pointer is returned (it may change because* of the realloc, so the caller should discard 'n' and use the new value).* On out of memory NULL is returned, and the old node is still valid. */
raxNode *raxAddChild(raxNode *n, unsigned char c, raxNode **childptr, raxNode ***parentlink) {assert(n->iscompr == 0);size_t curlen = raxNodeCurrentLength(n);n->size++;size_t newlen = raxNodeCurrentLength(n);n->size--; /* For now restore the orignal size. We'll update it only onsuccess at the end. *//* Alloc the new child we will link to 'n'. */raxNode *child = raxNewNode(0,0);if (child == NULL) return NULL;/* Make space in the original node. */raxNode *newn = rax_realloc(n,newlen);if (newn == NULL) {rax_free(child);return NULL;}n = newn;/* After the reallocation, we have up to 8/16 (depending on the system* pointer size, and the required node padding) bytes at the end, that is,* the additional char in the 'data' section, plus one pointer to the new* child, plus the padding needed in order to store addresses into aligned* locations.** So if we start with the following node, having "abde" edges.** Note:* - We assume 4 bytes pointer for simplicity.* - Each space below corresponds to one byte** [HDR*][abde][Aptr][Bptr][Dptr][Eptr]|AUXP|** After the reallocation we need: 1 byte for the new edge character* plus 4 bytes for a new child pointer (assuming 32 bit machine).* However after adding 1 byte to the edge char, the header + the edge* characters are no longer aligned, so we also need 3 bytes of padding.* In total the reallocation will add 1+4+3 bytes = 8 bytes:** (Blank bytes are represented by ".")** [HDR*][abde][Aptr][Bptr][Dptr][Eptr]|AUXP|[....][....]** Let's find where to insert the new child in order to make sure* it is inserted in-place lexicographically. Assuming we are adding* a child "c" in our case pos will be = 2 after the end of the following* loop. */int pos;for (pos = 0; pos < n->size; pos++) {if (n->data[pos] > c) break;}/* Now, if present, move auxiliary data pointer at the end* so that we can mess with the other data without overwriting it.* We will obtain something like that:** [HDR*][abde][Aptr][Bptr][Dptr][Eptr][....][....]|AUXP|*/unsigned char *src, *dst;if (n->iskey && !n->isnull) {src = ((unsigned char*)n+curlen-sizeof(void*));dst = ((unsigned char*)n+newlen-sizeof(void*));memmove(dst,src,sizeof(void*));}/* Compute the "shift", that is, how many bytes we need to move the* pointers section forward because of the addition of the new child* byte in the string section. Note that if we had no padding, that* would be always "1", since we are adding a single byte in the string* section of the node (where now there is "abde" basically).** However we have padding, so it could be zero, or up to 8.** Another way to think at the shift is, how many bytes we need to* move child pointers forward *other than* the obvious sizeof(void*)* needed for the additional pointer itself. */size_t shift = newlen - curlen - sizeof(void*);/* We said we are adding a node with edge 'c'. The insertion* point is between 'b' and 'd', so the 'pos' variable value is* the index of the first child pointer that we need to move forward* to make space for our new pointer.** To start, move all the child pointers after the insertion point* of shift+sizeof(pointer) bytes on the right, to obtain:** [HDR*][abde][Aptr][Bptr][....][....][Dptr][Eptr]|AUXP|*/src = n->data+n->size+raxPadding(n->size)+sizeof(raxNode*)*pos;memmove(src+shift+sizeof(raxNode*),src,sizeof(raxNode*)*(n->size-pos));/* Move the pointers to the left of the insertion position as well. Often* we don't need to do anything if there was already some padding to use. In* that case the final destination of the pointers will be the same, however* in our example there was no pre-existing padding, so we added one byte* plus thre bytes of padding. After the next memmove() things will look* like thata:** [HDR*][abde][....][Aptr][Bptr][....][Dptr][Eptr]|AUXP|*/if (shift) {src = (unsigned char*) raxNodeFirstChildPtr(n);memmove(src+shift,src,sizeof(raxNode*)*pos);}/* Now make the space for the additional char in the data section,* but also move the pointers before the insertion point to the right* by shift bytes, in order to obtain the following:** [HDR*][ab.d][e...][Aptr][Bptr][....][Dptr][Eptr]|AUXP|*/src = n->data+pos;memmove(src+1,src,n->size-pos);/* We can now set the character and its child node pointer to get:** [HDR*][abcd][e...][Aptr][Bptr][....][Dptr][Eptr]|AUXP|* [HDR*][abcd][e...][Aptr][Bptr][Cptr][Dptr][Eptr]|AUXP|*/n->data[pos] = c;n->size++;src = (unsigned char*) raxNodeFirstChildPtr(n);raxNode **childfield = (raxNode**)(src+sizeof(raxNode*)*pos);memcpy(childfield,&child,sizeof(child));*childptr = child;*parentlink = childfield;return n;
}
这篇关于漫话Redis源码之三十三的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
