+/* Important note: the ZIP_END value is used to depict the end of the
+ * ziplist structure. When a pointer contains an entry, the first couple
+ * of bytes contain the encoded length of the previous entry. This length
+ * is encoded as ZIP_ENC_RAW length, so the first two bits will contain 00
+ * and the byte will therefore never have a value of 255. */
+#define ZIP_END 255
+#define ZIP_BIGLEN 254
+
+/* Entry encoding */
+#define ZIP_ENC_RAW 0
+#define ZIP_ENC_INT16 1
+#define ZIP_ENC_INT32 2
+#define ZIP_ENC_INT64 3
+#define ZIP_ENCODING(p) ((p)[0] >> 6)
+
+/* Length encoding for raw entries */
+#define ZIP_LEN_INLINE 0
+#define ZIP_LEN_UINT16 1
+#define ZIP_LEN_UINT32 2
+
+/* Utility macros */
+#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
+#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
+#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
+#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
+#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
+#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+ZIPLIST_TAIL_OFFSET(zl))
+#define ZIPLIST_ENTRY_END(zl) ((zl)+ZIPLIST_BYTES(zl)-1)
+
+/* We know a positive increment can only be 1 because entries can only be
+ * pushed one at a time. */
+#define ZIPLIST_INCR_LENGTH(zl,incr) { \
+ if (ZIPLIST_LENGTH(zl) < UINT16_MAX) ZIPLIST_LENGTH(zl)+=incr; }
+
+typedef struct zlentry {
+ unsigned int prevrawlensize, prevrawlen;
+ unsigned int lensize, len;
+ unsigned int headersize;
+ unsigned char encoding;
+ unsigned char *p;
+} zlentry;
+
+/* Return bytes needed to store integer encoded by 'encoding' */
+static unsigned int zipEncodingSize(unsigned char encoding) {
+ if (encoding == ZIP_ENC_INT16) {
+ return sizeof(int16_t);
+ } else if (encoding == ZIP_ENC_INT32) {
+ return sizeof(int32_t);
+ } else if (encoding == ZIP_ENC_INT64) {
+ return sizeof(int64_t);
+ }
+ assert(NULL);
+}
+
+/* Decode the encoded length pointed by 'p'. If a pointer to 'lensize' is
+ * provided, it is set to the number of bytes required to encode the length. */
+static unsigned int zipDecodeLength(unsigned char *p, unsigned int *lensize) {
+ unsigned char encoding = ZIP_ENCODING(p), lenenc;
+ unsigned int len;
+
+ if (encoding == ZIP_ENC_RAW) {
+ lenenc = (p[0] >> 4) & 0x3;
+ if (lenenc == ZIP_LEN_INLINE) {
+ len = p[0] & 0xf;
+ if (lensize) *lensize = 1;
+ } else if (lenenc == ZIP_LEN_UINT16) {
+ len = p[1] | (p[2] << 8);
+ if (lensize) *lensize = 3;
+ } else {
+ len = p[1] | (p[2] << 8) | (p[3] << 16) | (p[4] << 24);
+ if (lensize) *lensize = 5;
+ }
+ } else {
+ len = zipEncodingSize(encoding);
+ if (lensize) *lensize = 1;
+ }
+ return len;
+}
+
+/* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
+ * the amount of bytes required to encode such a length. */
+static unsigned int zipEncodeLength(unsigned char *p, char encoding, unsigned int rawlen) {
+ unsigned char len = 1, lenenc, buf[5];
+ if (encoding == ZIP_ENC_RAW) {
+ if (rawlen <= 0xf) {
+ if (!p) return len;
+ lenenc = ZIP_LEN_INLINE;
+ buf[0] = rawlen;
+ } else if (rawlen <= 0xffff) {
+ len += 2;
+ if (!p) return len;
+ lenenc = ZIP_LEN_UINT16;
+ buf[1] = (rawlen ) & 0xff;
+ buf[2] = (rawlen >> 8) & 0xff;
+ } else {
+ len += 4;
+ if (!p) return len;
+ lenenc = ZIP_LEN_UINT32;
+ buf[1] = (rawlen ) & 0xff;
+ buf[2] = (rawlen >> 8) & 0xff;
+ buf[3] = (rawlen >> 16) & 0xff;
+ buf[4] = (rawlen >> 24) & 0xff;
+ }
+ buf[0] = (lenenc << 4) | (buf[0] & 0xf);
+ }
+ if (!p) return len;
+
+ /* Apparently we need to store the length in 'p' */
+ buf[0] = (encoding << 6) | (buf[0] & 0x3f);
+ memcpy(p,buf,len);
+ return len;
+}
+
+/* Decode the length of the previous element stored at "p". */
+static unsigned int zipPrevDecodeLength(unsigned char *p, unsigned int *lensize) {
+ unsigned int len = *p;
+ if (len < ZIP_BIGLEN) {
+ if (lensize) *lensize = 1;
+ } else {
+ if (lensize) *lensize = 1+sizeof(len);
+ memcpy(&len,p+1,sizeof(len));
+ }
+ return len;
+}
+
+/* Encode the length of the previous entry and write it to "p". Return the
+ * number of bytes needed to encode this length if "p" is NULL. */
+static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) {
+ if (p == NULL) {
+ return (len < ZIP_BIGLEN) ? 1 : sizeof(len)+1;
+ } else {
+ if (len < ZIP_BIGLEN) {
+ p[0] = len;
+ return 1;
+ } else {
+ p[0] = ZIP_BIGLEN;
+ memcpy(p+1,&len,sizeof(len));
+ return 1+sizeof(len);
+ }
+ }
+}
+
+/* Return the difference in number of bytes needed to store the new length
+ * "len" on the entry pointed to by "p". */
+static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
+ unsigned int prevlensize;
+ zipPrevDecodeLength(p,&prevlensize);
+ return zipPrevEncodeLength(NULL,len)-prevlensize;
+}
+
+/* Check if string pointed to by 'entry' can be encoded as an integer.
+ * Stores the integer value in 'v' and its encoding in 'encoding'.
+ * Warning: this function requires a NULL-terminated string! */
+static int zipTryEncoding(unsigned char *entry, long long *v, unsigned char *encoding) {
+ long long value;
+ char *eptr;
+
+ if (entry[0] == '-' || (entry[0] >= '0' && entry[0] <= '9')) {
+ value = strtoll((char*)entry,&eptr,10);
+ if (eptr[0] != '\0') return 0;
+ if (value >= INT16_MIN && value <= INT16_MAX) {
+ *encoding = ZIP_ENC_INT16;
+ } else if (value >= INT32_MIN && value <= INT32_MAX) {
+ *encoding = ZIP_ENC_INT32;
+ } else {
+ *encoding = ZIP_ENC_INT64;
+ }
+ *v = value;
+ return 1;
+ }
+ return 0;
+}
+
+/* Store integer 'value' at 'p', encoded as 'encoding' */
+static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) {
+ int16_t i16;
+ int32_t i32;
+ int64_t i64;
+ if (encoding == ZIP_ENC_INT16) {
+ i16 = value;
+ memcpy(p,&i16,sizeof(i16));
+ } else if (encoding == ZIP_ENC_INT32) {
+ i32 = value;
+ memcpy(p,&i32,sizeof(i32));
+ } else if (encoding == ZIP_ENC_INT64) {
+ i64 = value;
+ memcpy(p,&i64,sizeof(i64));
+ } else {
+ assert(NULL);
+ }
+}
+
+/* Read integer encoded as 'encoding' from 'p' */
+static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
+ int16_t i16;
+ int32_t i32;
+ int64_t i64, ret;
+ if (encoding == ZIP_ENC_INT16) {
+ memcpy(&i16,p,sizeof(i16));
+ ret = i16;
+ } else if (encoding == ZIP_ENC_INT32) {
+ memcpy(&i32,p,sizeof(i32));
+ ret = i32;
+ } else if (encoding == ZIP_ENC_INT64) {
+ memcpy(&i64,p,sizeof(i64));
+ ret = i64;
+ } else {
+ assert(NULL);
+ }
+ return ret;
+}
+
+/* Return a struct with all information about an entry. */
+static zlentry zipEntry(unsigned char *p) {
+ zlentry e;
+ e.prevrawlen = zipPrevDecodeLength(p,&e.prevrawlensize);
+ e.len = zipDecodeLength(p+e.prevrawlensize,&e.lensize);
+ e.headersize = e.prevrawlensize+e.lensize;
+ e.encoding = ZIP_ENCODING(p+e.prevrawlensize);
+ e.p = p;
+ return e;
+}
+
+/* Return the total number of bytes used by the entry at "p". */
+static unsigned int zipRawEntryLength(unsigned char *p) {
+ zlentry e = zipEntry(p);
+ return e.headersize + e.len;
+}
projects / redis.git / blobdiff