+/* =================================== Lists ================================ */
+
+
+/* Check the argument length to see if it requires us to convert the ziplist
+ * to a real list. Only check raw-encoded objects because integer encoded
+ * objects are never too long. */
+static void listTypeTryConversion(robj *subject, robj *value) {
+ if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;
+ if (value->encoding == REDIS_ENCODING_RAW &&
+ sdslen(value->ptr) > server.list_max_ziplist_value)
+ listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
+}
+
+static void listTypePush(robj *subject, robj *value, int where) {
+ /* Check if we need to convert the ziplist */
+ listTypeTryConversion(subject,value);
+ if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
+ ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
+ listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
+
+ if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
+ int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
+ value = getDecodedObject(value);
+ subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
+ decrRefCount(value);
+ } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
+ if (where == REDIS_HEAD) {
+ listAddNodeHead(subject->ptr,value);
+ } else {
+ listAddNodeTail(subject->ptr,value);
+ }
+ incrRefCount(value);
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+}
+
+static robj *listTypePop(robj *subject, int where) {
+ robj *value = NULL;
+ if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *p;
+ unsigned char *vstr;
+ unsigned int vlen;
+ long long vlong;
+ int pos = (where == REDIS_HEAD) ? 0 : -1;
+ p = ziplistIndex(subject->ptr,pos);
+ if (ziplistGet(p,&vstr,&vlen,&vlong)) {
+ if (vstr) {
+ value = createStringObject((char*)vstr,vlen);
+ } else {
+ value = createStringObjectFromLongLong(vlong);
+ }
+ /* We only need to delete an element when it exists */
+ subject->ptr = ziplistDelete(subject->ptr,&p);
+ }
+ } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
+ list *list = subject->ptr;
+ listNode *ln;
+ if (where == REDIS_HEAD) {
+ ln = listFirst(list);
+ } else {
+ ln = listLast(list);
+ }
+ if (ln != NULL) {
+ value = listNodeValue(ln);
+ incrRefCount(value);
+ listDelNode(list,ln);
+ }
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+ return value;
+}
+
+static unsigned long listTypeLength(robj *subject) {
+ if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
+ return ziplistLen(subject->ptr);
+ } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
+ return listLength((list*)subject->ptr);
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+}
+
+/* Structure to hold set iteration abstraction. */
+typedef struct {
+ robj *subject;
+ unsigned char encoding;
+ unsigned char direction; /* Iteration direction */
+ unsigned char *zi;
+ listNode *ln;
+} listTypeIterator;
+
+/* Structure for an entry while iterating over a list. */
+typedef struct {
+ listTypeIterator *li;
+ unsigned char *zi; /* Entry in ziplist */
+ listNode *ln; /* Entry in linked list */
+} listTypeEntry;
+
+/* Initialize an iterator at the specified index. */
+static listTypeIterator *listTypeInitIterator(robj *subject, int index, unsigned char direction) {
+ listTypeIterator *li = zmalloc(sizeof(listTypeIterator));
+ li->subject = subject;
+ li->encoding = subject->encoding;
+ li->direction = direction;
+ if (li->encoding == REDIS_ENCODING_ZIPLIST) {
+ li->zi = ziplistIndex(subject->ptr,index);
+ } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
+ li->ln = listIndex(subject->ptr,index);
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+ return li;
+}
+
+/* Clean up the iterator. */
+static void listTypeReleaseIterator(listTypeIterator *li) {
+ zfree(li);
+}
+
+/* Stores pointer to current the entry in the provided entry structure
+ * and advances the position of the iterator. Returns 1 when the current
+ * entry is in fact an entry, 0 otherwise. */
+static int listTypeNext(listTypeIterator *li, listTypeEntry *entry) {
+ /* Protect from converting when iterating */
+ redisAssert(li->subject->encoding == li->encoding);
+
+ entry->li = li;
+ if (li->encoding == REDIS_ENCODING_ZIPLIST) {
+ entry->zi = li->zi;
+ if (entry->zi != NULL) {
+ if (li->direction == REDIS_TAIL)
+ li->zi = ziplistNext(li->subject->ptr,li->zi);
+ else
+ li->zi = ziplistPrev(li->subject->ptr,li->zi);
+ return 1;
+ }
+ } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
+ entry->ln = li->ln;
+ if (entry->ln != NULL) {
+ if (li->direction == REDIS_TAIL)
+ li->ln = li->ln->next;
+ else
+ li->ln = li->ln->prev;
+ return 1;
+ }
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+ return 0;
+}
+
+/* Return entry or NULL at the current position of the iterator. */
+static robj *listTypeGet(listTypeEntry *entry) {
+ listTypeIterator *li = entry->li;
+ robj *value = NULL;
+ if (li->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *vstr;
+ unsigned int vlen;
+ long long vlong;
+ redisAssert(entry->zi != NULL);
+ if (ziplistGet(entry->zi,&vstr,&vlen,&vlong)) {
+ if (vstr) {
+ value = createStringObject((char*)vstr,vlen);
+ } else {
+ value = createStringObjectFromLongLong(vlong);
+ }
+ }
+ } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
+ redisAssert(entry->ln != NULL);
+ value = listNodeValue(entry->ln);
+ incrRefCount(value);
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+ return value;
+}
+
+static void listTypeInsert(listTypeEntry *entry, robj *value, int where) {
+ robj *subject = entry->li->subject;
+ if (entry->li->encoding == REDIS_ENCODING_ZIPLIST) {
+ value = getDecodedObject(value);
+ if (where == REDIS_TAIL) {
+ unsigned char *next = ziplistNext(subject->ptr,entry->zi);
+
+ /* When we insert after the current element, but the current element
+ * is the tail of the list, we need to do a push. */
+ if (next == NULL) {
+ subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),REDIS_TAIL);
+ } else {
+ subject->ptr = ziplistInsert(subject->ptr,next,value->ptr,sdslen(value->ptr));
+ }
+ } else {
+ subject->ptr = ziplistInsert(subject->ptr,entry->zi,value->ptr,sdslen(value->ptr));
+ }
+ decrRefCount(value);
+ } else if (entry->li->encoding == REDIS_ENCODING_LINKEDLIST) {
+ if (where == REDIS_TAIL) {
+ listInsertNode(subject->ptr,entry->ln,value,AL_START_TAIL);
+ } else {
+ listInsertNode(subject->ptr,entry->ln,value,AL_START_HEAD);
+ }
+ incrRefCount(value);
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+}
+
+/* Compare the given object with the entry at the current position. */
+static int listTypeEqual(listTypeEntry *entry, robj *o) {
+ listTypeIterator *li = entry->li;
+ if (li->encoding == REDIS_ENCODING_ZIPLIST) {
+ redisAssert(o->encoding == REDIS_ENCODING_RAW);
+ return ziplistCompare(entry->zi,o->ptr,sdslen(o->ptr));
+ } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
+ return equalStringObjects(o,listNodeValue(entry->ln));
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+}
+
+/* Delete the element pointed to. */
+static void listTypeDelete(listTypeEntry *entry) {
+ listTypeIterator *li = entry->li;
+ if (li->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *p = entry->zi;
+ li->subject->ptr = ziplistDelete(li->subject->ptr,&p);
+
+ /* Update position of the iterator depending on the direction */
+ if (li->direction == REDIS_TAIL)
+ li->zi = p;
+ else
+ li->zi = ziplistPrev(li->subject->ptr,p);
+ } else if (entry->li->encoding == REDIS_ENCODING_LINKEDLIST) {
+ listNode *next;
+ if (li->direction == REDIS_TAIL)
+ next = entry->ln->next;
+ else
+ next = entry->ln->prev;
+ listDelNode(li->subject->ptr,entry->ln);
+ li->ln = next;
+ } else {
+ redisPanic("Unknown list encoding");
+ }
+}
+
+static void listTypeConvert(robj *subject, int enc) {
+ listTypeIterator *li;
+ listTypeEntry entry;
+ redisAssert(subject->type == REDIS_LIST);
+
+ if (enc == REDIS_ENCODING_LINKEDLIST) {
+ list *l = listCreate();
+ listSetFreeMethod(l,decrRefCount);
+
+ /* listTypeGet returns a robj with incremented refcount */
+ li = listTypeInitIterator(subject,0,REDIS_TAIL);
+ while (listTypeNext(li,&entry)) listAddNodeTail(l,listTypeGet(&entry));
+ listTypeReleaseIterator(li);
+
+ subject->encoding = REDIS_ENCODING_LINKEDLIST;
+ zfree(subject->ptr);
+ subject->ptr = l;
+ } else {
+ redisPanic("Unsupported list conversion");
+ }
+}
+
projects / redis.git / blobdiff