2009-03-22 10:30:00 +01:00
|
|
|
/* adlist.h - A generic doubly linked list implementation
|
|
|
|
*
|
2024-03-20 23:38:24 +01:00
|
|
|
* Copyright (c) 2006-Present, Redis Ltd.
|
2009-03-22 10:30:00 +01:00
|
|
|
* All rights reserved.
|
|
|
|
*
|
2024-03-20 23:38:24 +01:00
|
|
|
* Licensed under your choice of the Redis Source Available License 2.0
|
|
|
|
* (RSALv2) or the Server Side Public License v1 (SSPLv1).
|
2009-03-22 10:30:00 +01:00
|
|
|
*/
|
|
|
|
|
|
|
|
#ifndef __ADLIST_H__
|
|
|
|
#define __ADLIST_H__
|
|
|
|
|
|
|
|
/* Node, List, and Iterator are the only data structures used currently. */
|
|
|
|
|
|
|
|
typedef struct listNode {
|
|
|
|
struct listNode *prev;
|
|
|
|
struct listNode *next;
|
|
|
|
void *value;
|
|
|
|
} listNode;
|
|
|
|
|
2009-04-20 23:51:51 +02:00
|
|
|
typedef struct listIter {
|
|
|
|
listNode *next;
|
|
|
|
int direction;
|
|
|
|
} listIter;
|
|
|
|
|
2009-03-22 10:30:00 +01:00
|
|
|
typedef struct list {
|
|
|
|
listNode *head;
|
|
|
|
listNode *tail;
|
|
|
|
void *(*dup)(void *ptr);
|
|
|
|
void (*free)(void *ptr);
|
|
|
|
int (*match)(void *ptr, void *key);
|
2012-01-31 10:35:52 +01:00
|
|
|
unsigned long len;
|
2009-03-22 10:30:00 +01:00
|
|
|
} list;
|
|
|
|
|
|
|
|
/* Functions implemented as macros */
|
|
|
|
#define listLength(l) ((l)->len)
|
|
|
|
#define listFirst(l) ((l)->head)
|
|
|
|
#define listLast(l) ((l)->tail)
|
|
|
|
#define listPrevNode(n) ((n)->prev)
|
|
|
|
#define listNextNode(n) ((n)->next)
|
|
|
|
#define listNodeValue(n) ((n)->value)
|
|
|
|
|
|
|
|
#define listSetDupMethod(l,m) ((l)->dup = (m))
|
|
|
|
#define listSetFreeMethod(l,m) ((l)->free = (m))
|
|
|
|
#define listSetMatchMethod(l,m) ((l)->match = (m))
|
|
|
|
|
|
|
|
#define listGetDupMethod(l) ((l)->dup)
|
2019-11-13 03:14:45 +01:00
|
|
|
#define listGetFreeMethod(l) ((l)->free)
|
2009-03-22 10:30:00 +01:00
|
|
|
#define listGetMatchMethod(l) ((l)->match)
|
|
|
|
|
|
|
|
/* Prototypes */
|
|
|
|
list *listCreate(void);
|
|
|
|
void listRelease(list *list);
|
2017-04-27 17:04:07 +02:00
|
|
|
void listEmpty(list *list);
|
2009-03-22 10:30:00 +01:00
|
|
|
list *listAddNodeHead(list *list, void *value);
|
|
|
|
list *listAddNodeTail(list *list, void *value);
|
2010-06-11 10:08:59 +02:00
|
|
|
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
|
2009-03-22 10:30:00 +01:00
|
|
|
void listDelNode(list *list, listNode *node);
|
|
|
|
listIter *listGetIterator(list *list, int direction);
|
2009-04-20 23:51:51 +02:00
|
|
|
listNode *listNext(listIter *iter);
|
2009-03-22 10:30:00 +01:00
|
|
|
void listReleaseIterator(listIter *iter);
|
|
|
|
list *listDup(list *orig);
|
|
|
|
listNode *listSearchKey(list *list, void *key);
|
2012-01-31 10:35:52 +01:00
|
|
|
listNode *listIndex(list *list, long index);
|
2010-01-13 19:18:07 +01:00
|
|
|
void listRewind(list *list, listIter *li);
|
|
|
|
void listRewindTail(list *list, listIter *li);
|
2020-04-08 12:55:57 +02:00
|
|
|
void listRotateTailToHead(list *list);
|
|
|
|
void listRotateHeadToTail(list *list);
|
2017-05-02 15:05:39 +02:00
|
|
|
void listJoin(list *l, list *o);
|
2022-09-15 05:39:47 +02:00
|
|
|
void listInitNode(listNode *node, void *value);
|
|
|
|
void listLinkNodeHead(list *list, listNode *node);
|
optimize unwatchAllKeys() (#11511)
In unwatchAllKeys() function, we traverse all the keys watched by the client,
and for each key we need to remove the client from the list of clients watching that key.
This is implemented by listSearchKey which traverses the list of clients.
If we can reach the node of the list of clients from watchedKey in O(1) time,
then we do not need to call listSearchKey anymore.
Changes in this PR: put the node of the list of clients of each watched key in the
db inside the watchedKey structure. In this way, for every key watched by the client,
we can get the watchedKey structure and then reach the node in the list of clients in
db->watched_keys to remove it from that list.
From the perspective of the list of clients watching the key, the list node is inside a
watchedKey structure, so we can get to the watchedKey struct from the listnode by
struct member offset math. And because of this, node->value is not used, we can point
node->value to the list itself, so that we don't need to fetch the list of clients from the dict.
2022-11-23 16:39:08 +01:00
|
|
|
void listLinkNodeTail(list *list, listNode *node);
|
2022-09-15 05:39:47 +02:00
|
|
|
void listUnlinkNode(list *list, listNode *node);
|
2009-03-22 10:30:00 +01:00
|
|
|
|
|
|
|
/* Directions for iterators */
|
|
|
|
#define AL_START_HEAD 0
|
|
|
|
#define AL_START_TAIL 1
|
|
|
|
|
|
|
|
#endif /* __ADLIST_H__ */
|