Redis source code learning (29), compressed list learning, ziplist C (II)

   I haven't seen you for a long time , front 2 Months were delayed by some things Redis Source code learning , After getting rid of these trivial things, I came back , We can't put it down all the time because we put it down halfway , We should do things from beginning to end 、 Stick to it , So we continue to learn Redis Source code , Until he finishes his study , It may take a long time , It is also possible to leave temporarily because of some things , But just keep going , One day we will climb over this mountain .

1 ziplistIndex

1.1 Method statement

   Returns a pointer to the specified index position of the compressed list .

1.2 Method source code

	unsigned char *ziplistIndex(unsigned char *zl, int index) {
    
	    unsigned char *p;
	    unsigned int prevlensize, prevlen = 0;
	    
	    //  If the index is less than  0
	    if (index < 0) {
    
	        index = (-index)-1;
	         
	        //  Get the pointer to the node at the end of the compressed list 
	        p = ZIPLIST_ENTRY_TAIL(zl);

			//  If the tail node is not the end flag 
	        if (p[0] != ZIP_END) {
    
	            //  Get the length of the last node 、 length 
	            ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
	            // Go straight ahead 
	            while (prevlen > 0 && index--) {
    
	                p -= prevlen;
	                ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
	            }
	        }
	    } else {
    
	        // Get the pointer to the header of the compressed list 
	        p = ZIPLIST_ENTRY_HEAD(zl);
	        
	        // Traverse back and forth , Each time the pointer moves the length of the current node 
	        while (p[0] != ZIP_END && index--) {
    
	            p += zipRawEntryLength(p);
	        }
	    }
		
		// Returns a pointer to the index position 
	    return (p[0] == ZIP_END || index > 0) ? NULL : p;
	}

1.3 Related codes

1.3.1 ZIP_DECODE_PREVLENSIZE

	/* Decode the number of bytes required to store the length of the previous * element, from the perspective of the entry pointed to by 'ptr'. */
	#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {
       \ if ((ptr)[0] < ZIP_BIGLEN) {
       \ (prevlensize) = 1; \ } else {
       \ (prevlensize) = 5; \ } \ } while(0);

1.3.2 ZIP_DECODE_PREVLEN

	/* Decode the length of the previous element, from the perspective of the entry * pointed to by 'ptr'. */
	#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {
       \ ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \ if ((prevlensize) == 1) {
       \ (prevlen) = (ptr)[0]; \ } else if ((prevlensize) == 5) {
       \ assert(sizeof((prevlensize)) == 4); \ memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \ memrev32ifbe(&prevlen); \ } \ } while(0);

1.3.3 zipRawEntryLength

	/* Return the total number of bytes used by the entry pointed to by 'p'. */
	static unsigned int zipRawEntryLength(unsigned char *p) {
    
	    unsigned int prevlensize, encoding, lensize, len;
	    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
	    ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
	    return prevlensize + lensize + len;
	}

1.4 Code understanding

1.4.1 Traversal methods

  ziplistIndex It mainly returns the pointer position according to the index , It is convenient for other methods to obtain the nodes of the index , The core idea is to move the pointer position , The moving distance is the length of the node .
   If it is moving forward , Each time the pointer is moved, the length of the previous node must be obtained ;
   If it is moving backwards , Then each time you move the pointer, you need to get the length of the current node ;

1.4.2 ZIP_DECODE_PREVLENSIZE

   stay ziplistIndex Method has two macro defined methods ZIP_DECODE_PREVLENSIZE and ZIP_DECODE_PREVLEN, First of all ZIP_DECODE_PREVLENSIZE This method , This method mainly uses a few bytes to calculate the length of the previous node .

   As you can see from the source code , Just made a simple judgment , Judge whether the data of the first byte of the node is less than ZIP_BIGLEN , If it is less than, it will prevlensize Set to 1, Otherwise it's set to 5 .

	#define ZIP_BIGLEN 254

 * The length of the previous entry is encoded in the following way:
 * If this length is smaller than 254 bytes, it will only consume a single
 * byte that takes the length as value. When the length is greater than or
 * equal to 254, it will consume 5 bytes. The first byte is set to 254 to
 * indicate a larger value is following. The remaining 4 bytes take the
 * length of the previous entry as value.
 * 

	/* Decode the number of bytes required to store the length of the previous * element, from the perspective of the entry pointed to by 'ptr'. */
	#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {
       \ if ((ptr)[0] < ZIP_BIGLEN) {
       \ (prevlensize) = 1; \ } else {
       \ (prevlensize) = 5; \ } \ } while(0);

   Simply looking at this code may not understand , So I re posted the description of the length of the last node stored in the compressed list , It can be seen from the description that , If the length of the last node is less than 254 Bytes , So you need 1 You can store this length in bytes .

   If it is greater than or equal to 254 Bytes , Then it will use 5 Bytes to store the length of the last node , And the first byte will be stored 254 To mark the use of 5 Bytes , be left over 4 Bytes record the value of the last node length .

   Through these instructions, it is not difficult to understand what this method does , This is to judge how many bytes the current node uses to store the length of the previous node .

   One last thing , Maybe many friends, like me, have some doubts when they first read the macro definition and method call the macro definition .

Be confused ：
1、 Why can a function directly change the value of a variable when calling this macro definition ？
   Because macro definition is equivalent to code replacement , So we can't see it as another method , Instead, replace the macro definition to the place where it is called , The scope of the equivalent variable is still in the called function , Instead of going to a new function .

2、 Why do macro definitions use do while() wrap up ？
   If not do while Wrapping may cause logical errors after replacement, especially when encountering some control statements , Using this writing method can well take the code snippet of macro definition as a whole .

1.4.3 ZIP_DECODE_PREVLEN

	/* Decode the length of the previous element, from the perspective of the entry * pointed to by 'ptr'. */
	#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {
       \ // Calculate the number of bytes occupied by the previous node 
	    ZIP_DECODE_PREVLENSIZE(ptr, prevlensize);                                  \
		
		// If it takes  1  Bytes , Then the length of the previous node is directly equal to the value stored in the first byte of the node 
	    if ((prevlensize) == 1) {
                                                      \
	        (prevlen) = (ptr)[0];                                                  \
	    } 
	    // If occupied is  5  Bytes , Then the length of the last node is equal to the following 4 A value stored in bytes 
		else if ((prevlensize) == 5) {
                                               \
	        assert(sizeof((prevlensize)) == 4);                                    \
	        memcpy(&(prevlen), ((char*)(ptr)) + 1, 4);                             \
	        memrev32ifbe(&prevlen);                                                \
	    }                                                                          \
	} while(0);

   This method is also a macro definition method , It is mainly used to calculate the length of the last node , First, calculate the number of bytes occupied according to the previous method , To read the values of different bytes .
   If you occupy 1 Bytes , Then read the page directly 1 The value of bytes .
   If you occupy 4 Bytes , Then read the back 4 The value of bytes .

1.4.4 zipRawEntryLength

	/* Return the total number of bytes used by the entry pointed to by 'p'. */
	static unsigned int zipRawEntryLength(unsigned char *p) {
    
	    unsigned int prevlensize, encoding, lensize, len;
	    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
	    ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
	    return prevlensize + lensize + len;
	}

   This method is used to return the length of the node , First, calculate the number of bytes occupied by the length of the previous node , Then calculate the number of bytes occupied by the current node code , Then calculate the length of the actual data , The length of the whole node is obtained by adding .

2 ziplistNext

2.1 Method statement

   Returns a pointer to the next node of a node in the compressed list .

2.2 Method source code

	unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
    
	    ((void) zl);
	
	    /* "p" could be equal to ZIP_END, caused by ziplistDelete, * and we should return NULL. Otherwise, we should return NULL * when the *next* element is ZIP_END (there is no next entry). */
	    if (p[0] == ZIP_END) {
    
	        return NULL;
	    }
	
	    p += zipRawEntryLength(p);
	    if (p[0] == ZIP_END) {
    
	        return NULL;
	    }
	
	    return p;
	}

2.3 Code understanding

   With the understanding of the above method , There must be a lot of understanding about the movement of compressed list pointers , The main purpose is to access the next node by moving the length of one node , So you can see that ziplistNext There is not much code in the method , First determine whether to compress the end of the list , If not, get the length of the current node , Then move these distances , Finally, return the latest pointer position , To access the next node .

3 ziplistPrev

3.1 Method statement

   Returns the pointer to the previous node of a node in the compressed list .

3.2 Method source code

	/* Return pointer to previous entry in ziplist. */
	unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
    
	    unsigned int prevlensize, prevlen = 0;
	
	    /* Iterating backwards from ZIP_END should return the tail. When "p" is * equal to the first element of the list, we're already at the head, * and should return NULL. */
	    if (p[0] == ZIP_END) {
    
	        p = ZIPLIST_ENTRY_TAIL(zl);
	        return (p[0] == ZIP_END) ? NULL : p;
	    } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
    
	        return NULL;
	    } else {
    
	        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
	        assert(prevlen > 0);
	        return p-prevlen;
	    }
	}

3.3 Code understanding

   You can see from the method code , Instead of moving to the next node , Moving to the previous node is a bit complicated .
If the pointer is the terminator , Then return to the tail node .
If the pointer is a header node , Then return to NULL.
If not , Get the length of the previous node , Subtract the length of the previous node from the current pointer , To move the previous node .

4 summary

1. This section mainly studies the traversal method of compressed nodes , Contains ziplistIndex、ziplistNext、ziplistPrev.
2. The main idea of traversing nodes is to calculate the length of nodes , Move to the previous or next node by moving the length of a node .
3. ZIP_DECODE_PREVLEN You can calculate the length of the previous node .
4. zipRawEntryLength You can calculate the length of the current node .
5. Each node header is used to store the length of the previous node .
6. If the length of the previous node is less than 254 Bytes , Then the node header will only use 1 Bytes to store the length of the last node .
7. If the length of the previous node is greater than 254 Bytes , Then the node header will use 5 Bytes to store the length of the last node , And the first byte will be stored 254 Indicates that 5 Bytes to store the length , be left over 4 Bytes store the length of the last node .