Seek the specified element and returns the pointer to the seeked element. * Positive indexes specify the zero-based element to seek from the head to * the tail, negative indexes specify elements starting from the tail, where * -1 means the last element, -2 the penultimate and so forth. If the index * is out of range, NULL is returned. */
| 821 | * -1 means the last element, -2 the penultimate and so forth. If the index |
| 822 | * is out of range, NULL is returned. */ |
| 823 | unsigned char *lpSeek(unsigned char *lp, long index) { |
| 824 | int forward = 1; /* Seek forward by default. */ |
| 825 | |
| 826 | /* We want to seek from left to right or the other way around |
| 827 | * depending on the listpack length and the element position. |
| 828 | * However if the listpack length cannot be obtained in constant time, |
| 829 | * we always seek from left to right. */ |
| 830 | uint32_t numele = lpGetNumElements(lp); |
| 831 | if (numele != LP_HDR_NUMELE_UNKNOWN) { |
| 832 | if (index < 0) index = (long)numele+index; |
| 833 | if (index < 0) return NULL; /* Index still < 0 means out of range. */ |
| 834 | if (index >= (long)numele) return NULL; /* Out of range the other side. */ |
| 835 | /* We want to scan right-to-left if the element we are looking for |
| 836 | * is past the half of the listpack. */ |
| 837 | if (index > (long)numele/2) { |
| 838 | forward = 0; |
| 839 | /* Right to left scanning always expects a negative index. Convert |
| 840 | * our index to negative form. */ |
| 841 | index -= numele; |
| 842 | } |
| 843 | } else { |
| 844 | /* If the listpack length is unspecified, for negative indexes we |
| 845 | * want to always scan right-to-left. */ |
| 846 | if (index < 0) forward = 0; |
| 847 | } |
| 848 | |
| 849 | /* Forward and backward scanning is trivially based on lpNext()/lpPrev(). */ |
| 850 | if (forward) { |
| 851 | unsigned char *ele = lpFirst(lp); |
| 852 | while (index > 0 && ele) { |
| 853 | ele = lpNext(lp,ele); |
| 854 | index--; |
| 855 | } |
| 856 | return ele; |
| 857 | } else { |
| 858 | unsigned char *ele = lpLast(lp); |
| 859 | while (index < -1 && ele) { |
| 860 | ele = lpPrev(lp,ele); |
| 861 | index++; |
| 862 | } |
| 863 | return ele; |
| 864 | } |
| 865 | } |
| 866 | |
| 867 | /* Same as lpFirst but without validation assert, to be used right before lpValidateNext. */ |
| 868 | unsigned char *lpValidateFirst(unsigned char *lp) { |