From 6435c76772bfc846c4f336d07f56668aef33a38b Mon Sep 17 00:00:00 2001 From: Pieter Noordhuis Date: Sat, 29 May 2010 18:52:49 +0200 Subject: [PATCH] function to insert an element at an arbitrary position in the list --- ziplist.c | 79 ++++++++++++++++++++++++++++++++----------------------- 1 file changed, 46 insertions(+), 33 deletions(-) diff --git a/ziplist.c b/ziplist.c index 57639c3a..e54f3211 100644 --- a/ziplist.c +++ b/ziplist.c @@ -286,66 +286,79 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, int n return zl; } -unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int elen, int where) { - unsigned int curlen = ZIPLIST_BYTES(zl), reqlen, prevlen; - unsigned char *p, *curtail; +/* Insert item at "p". */ +static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { + unsigned int curlen = ZIPLIST_BYTES(zl), reqlen, prevlen = 0; + unsigned int offset, nextdiff = 0; + unsigned char *tail; char encoding = ZIP_ENC_RAW; long long value; + zlentry entry; - /* We need to store the length of the current tail when the list - * is non-empty and we push at the tail. */ - curtail = zl+ZIPLIST_TAIL_OFFSET(zl); - if (where == ZIPLIST_TAIL && curtail[0] != ZIP_END) { - prevlen = zipRawEntryLength(curtail); + /* Find out prevlen for the entry that is inserted. */ + if (p[0] != ZIP_END) { + entry = zipEntry(p); + prevlen = entry.prevrawlen; } else { - prevlen = 0; + tail = ziplistTail(zl); + if (tail[0] != ZIP_END) { + prevlen = zipRawEntryLength(tail); + } } /* See if the entry can be encoded */ - if (zipTryEncoding(entry,&value,&encoding)) { + if (zipTryEncoding(s,&value,&encoding)) { reqlen = zipEncodingSize(encoding); } else { - reqlen = elen; + reqlen = slen; } /* We need space for both the length of the previous entry and * the length of the payload. */ reqlen += zipEncodeLength(NULL,ZIP_ENC_RAW,prevlen); - reqlen += zipEncodeLength(NULL,encoding,elen); - - /* Resize the ziplist and move if needed */ - zl = ziplistResize(zl,curlen+reqlen); - if (where == ZIPLIST_HEAD) { - p = zl+ZIPLIST_HEADER_SIZE; - if (*p != ZIP_END) { - /* Subtract one because of the ZIP_END bytes */ - memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1); - } + reqlen += zipEncodeLength(NULL,encoding,slen); + + /* When the insert position is not equal to the tail, we need to + * make sure that the next entry can hold this entry's length in + * its prevlen field. */ + nextdiff = p[0] != ZIP_END ? zipPrevLenByteDiff(p,reqlen) : 0; + + /* Store offset because a realloc may change the address of zl. */ + offset = p-zl; + zl = ziplistResize(zl,curlen+reqlen+nextdiff); + p = zl+offset; + + /* Apply memory move when necessary and update tail offset. */ + if (p[0] != ZIP_END) { + /* Subtract one because of the ZIP_END bytes */ + memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); + /* Encode this entry's raw length in the next entry. */ + zipEncodeLength(p+reqlen,ZIP_ENC_RAW,reqlen); + /* Update offset for tail */ + ZIPLIST_TAIL_OFFSET(zl) += reqlen+nextdiff; } else { - p = zl+curlen-1; - } - - /* Update tail offset if this is not the first element */ - if (curtail[0] != ZIP_END) { - if (where == ZIPLIST_HEAD) { - ZIPLIST_TAIL_OFFSET(zl) += reqlen; - } else { - ZIPLIST_TAIL_OFFSET(zl) += prevlen; - } + /* This element will be the new tail. */ + ZIPLIST_TAIL_OFFSET(zl) = p-zl; } /* Write the entry */ p += zipEncodeLength(p,ZIP_ENC_RAW,prevlen); - p += zipEncodeLength(p,encoding,elen); + p += zipEncodeLength(p,encoding,slen); if (encoding != ZIP_ENC_RAW) { zipSaveInteger(p,value,encoding); } else { - memcpy(p,entry,elen); + memcpy(p,s,slen); } ZIPLIST_INCR_LENGTH(zl,1); return zl; } +unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) { + unsigned char *p; + p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : (zl+ZIPLIST_BYTES(zl)-1); + return __ziplistInsert(zl,p,s,slen); +} + unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) { zlentry entry; unsigned char *p; -- 2.45.2