unrealircd

- supernets unrealircd source & configuration
git clone git://git.acid.vegas/unrealircd.git
Log | Files | Refs | Archive | README | LICENSE

list.h (19550B)

      1 /*
      2  * These are list macros/functions derived from the Linux kernel.
      3  * All original copyright (GPLv2) applies here.
      4  *        -- nenolod
      5  */
      6 
      7 #ifndef __LIST_H
      8 #define __LIST_H
      9 
     10 #include "common.h"
     11 
     12 #ifndef _WIN32
     13 #define SINLINE static inline
     14 #else
     15 #define SINLINE static
     16 #endif
     17 
     18 #ifdef _WIN32
     19 #define typeof(x)   Client 
     20 /* ^ FIXME if/when Microsoft supports this.
     21  * All functions use Client at the moment, with the exception of CAP, which has
     22  * to use list_for_each_entry2 because of it
     23  * Yeah this looks ugly and hacky.. thanks nenolod for making all code use this
     24  * non-portable gcc-specific stuff and violating all our code rules. Once again.
     25  */
     26 #endif
     27 
     28 /**
     29  * container_of - cast a member of a structure out to the containing structure
     30  * @ptr:        the pointer to the member.
     31  * @type:       the type of the container struct this is embedded in.
     32  * @member:     the name of the member within the struct.
     33  *
     34  */
     35 #define container_of(ptr, type, member) \
     36 	((type *)( (char *)ptr - offsetof(type, member) ))
     37 
     38 struct list_head {
     39 	struct list_head *next, *prev;
     40 };
     41 
     42 /*
     43  * Simple doubly linked list implementation.
     44  *
     45  * Some of the internal functions ("__xxx") are useful when
     46  * manipulating whole lists rather than single entries, as
     47  * sometimes we already know the next/prev entries and we can
     48  * generate better code by using them directly rather than
     49  * using the generic single-entry routines.
     50  */
     51 
     52 #define LIST_HEAD_INIT(name) { &(name), &(name) }
     53 
     54 #define LIST_HEAD(name) \
     55 	struct list_head name = LIST_HEAD_INIT(name)
     56 
     57 SINLINE void INIT_LIST_HEAD(struct list_head *list)
     58 {
     59 	list->next = list;
     60 	list->prev = list;
     61 }
     62 
     63 /*
     64  * Insert a new entry between two known consecutive entries.
     65  *
     66  * This is only for internal list manipulation where we know
     67  * the prev/next entries already!
     68  */
     69 SINLINE void __list_add(struct list_head *new,
     70 			      struct list_head *prev,
     71 			      struct list_head *next)
     72 {
     73 	next->prev = new;
     74 	new->next = next;
     75 	new->prev = prev;
     76 	prev->next = new;
     77 }
     78 
     79 /**
     80  * list_add - add a new entry
     81  * @new: new entry to be added
     82  * @head: list head to add it after
     83  *
     84  * Insert a new entry after the specified head.
     85  * This is good for implementing stacks.
     86  */
     87 SINLINE void list_add(struct list_head *new, struct list_head *head)
     88 {
     89 	__list_add(new, head, head->next);
     90 }
     91 
     92 
     93 /**
     94  * list_add_tail - add a new entry
     95  * @new: new entry to be added
     96  * @head: list head to add it before
     97  *
     98  * Insert a new entry before the specified head.
     99  * This is useful for implementing queues.
    100  */
    101 SINLINE void list_add_tail(struct list_head *new, struct list_head *head)
    102 {
    103 	__list_add(new, head->prev, head);
    104 }
    105 
    106 /*
    107  * Delete a list entry by making the prev/next entries
    108  * point to each other.
    109  *
    110  * This is only for internal list manipulation where we know
    111  * the prev/next entries already!
    112  */
    113 SINLINE void __list_del(struct list_head * prev, struct list_head * next)
    114 {
    115 	next->prev = prev;
    116 	prev->next = next;
    117 }
    118 
    119 /**
    120  * list_del - deletes entry from list.
    121  * @entry: the element to delete from the list.
    122  * Note: list_empty() on entry does not return true after this, the entry is
    123  * in an undefined state.
    124  */
    125 SINLINE void __list_del_entry(struct list_head *entry)
    126 {
    127 	__list_del(entry->prev, entry->next);
    128 }
    129 
    130 SINLINE void list_del(struct list_head *entry)
    131 {
    132 	__list_del_entry(entry);
    133 	INIT_LIST_HEAD(entry);
    134 }
    135 
    136 /**
    137  * list_replace - replace old entry by new one
    138  * @old : the element to be replaced
    139  * @new : the new element to insert
    140  *
    141  * If @old was empty, it will be overwritten.
    142  */
    143 SINLINE void list_replace(struct list_head *old,
    144 				struct list_head *new)
    145 {
    146 	new->next = old->next;
    147 	new->next->prev = new;
    148 	new->prev = old->prev;
    149 	new->prev->next = new;
    150 }
    151 
    152 SINLINE void list_replace_init(struct list_head *old,
    153 					struct list_head *new)
    154 {
    155 	list_replace(old, new);
    156 	INIT_LIST_HEAD(old);
    157 }
    158 
    159 /**
    160  * list_del_init - deletes entry from list and reinitialize it.
    161  * @entry: the element to delete from the list.
    162  */
    163 SINLINE void list_del_init(struct list_head *entry)
    164 {
    165 	__list_del_entry(entry);
    166 	INIT_LIST_HEAD(entry);
    167 }
    168 
    169 /**
    170  * list_move - delete from one list and add as another's head
    171  * @list: the entry to move
    172  * @head: the head that will precede our entry
    173  */
    174 SINLINE void list_move(struct list_head *list, struct list_head *head)
    175 {
    176 	__list_del_entry(list);
    177 	list_add(list, head);
    178 }
    179 
    180 /**
    181  * list_move_tail - delete from one list and add as another's tail
    182  * @list: the entry to move
    183  * @head: the head that will follow our entry
    184  */
    185 SINLINE void list_move_tail(struct list_head *list,
    186 				  struct list_head *head)
    187 {
    188 	__list_del_entry(list);
    189 	list_add_tail(list, head);
    190 }
    191 
    192 /**
    193  * list_is_last - tests whether @list is the last entry in list @head
    194  * @list: the entry to test
    195  * @head: the head of the list
    196  */
    197 SINLINE int list_is_last(const struct list_head *list,
    198 				const struct list_head *head)
    199 {
    200 	return list->next == head;
    201 }
    202 
    203 /**
    204  * list_empty - tests whether a list is empty
    205  * @head: the list to test.
    206  */
    207 SINLINE int list_empty(const struct list_head *head)
    208 {
    209 	return head->next == head;
    210 }
    211 
    212 /**
    213  * list_empty_careful - tests whether a list is empty and not being modified
    214  * @head: the list to test
    215  *
    216  * Description:
    217  * tests whether a list is empty _and_ checks that no other CPU might be
    218  * in the process of modifying either member (next or prev)
    219  *
    220  * NOTE: using list_empty_careful() without synchronization
    221  * can only be safe if the only activity that can happen
    222  * to the list entry is list_del_init(). Eg. it cannot be used
    223  * if another CPU could re-list_add() it.
    224  */
    225 SINLINE int list_empty_careful(const struct list_head *head)
    226 {
    227 	struct list_head *next = head->next;
    228 	return (next == head) && (next == head->prev);
    229 }
    230 
    231 /**
    232  * list_rotate_left - rotate the list to the left
    233  * @head: the head of the list
    234  */
    235 SINLINE void list_rotate_left(struct list_head *head)
    236 {
    237 	struct list_head *first;
    238 
    239 	if (!list_empty(head)) {
    240 		first = head->next;
    241 		list_move_tail(first, head);
    242 	}
    243 }
    244 
    245 /**
    246  * list_is_singular - tests whether a list has just one entry.
    247  * @head: the list to test.
    248  */
    249 SINLINE int list_is_singular(const struct list_head *head)
    250 {
    251 	return !list_empty(head) && (head->next == head->prev);
    252 }
    253 
    254 SINLINE void __list_cut_position(struct list_head *list,
    255 		struct list_head *head, struct list_head *entry)
    256 {
    257 	struct list_head *new_first = entry->next;
    258 	list->next = head->next;
    259 	list->next->prev = list;
    260 	list->prev = entry;
    261 	entry->next = list;
    262 	head->next = new_first;
    263 	new_first->prev = head;
    264 }
    265 
    266 /**
    267  * list_cut_position - cut a list into two
    268  * @list: a new list to add all removed entries
    269  * @head: a list with entries
    270  * @entry: an entry within head, could be the head itself
    271  *	and if so we won't cut the list
    272  *
    273  * This helper moves the initial part of @head, up to and
    274  * including @entry, from @head to @list. You should
    275  * pass on @entry an element you know is on @head. @list
    276  * should be an empty list or a list you do not care about
    277  * losing its data.
    278  *
    279  */
    280 SINLINE void list_cut_position(struct list_head *list,
    281 		struct list_head *head, struct list_head *entry)
    282 {
    283 	if (list_empty(head))
    284 		return;
    285 	if (list_is_singular(head) &&
    286 		(head->next != entry && head != entry))
    287 		return;
    288 	if (entry == head)
    289 		INIT_LIST_HEAD(list);
    290 	else
    291 		__list_cut_position(list, head, entry);
    292 }
    293 
    294 SINLINE void __list_splice(const struct list_head *list,
    295 				 struct list_head *prev,
    296 				 struct list_head *next)
    297 {
    298 	struct list_head *first = list->next;
    299 	struct list_head *last = list->prev;
    300 
    301 	first->prev = prev;
    302 	prev->next = first;
    303 
    304 	last->next = next;
    305 	next->prev = last;
    306 }
    307 
    308 /**
    309  * list_splice - join two lists, this is designed for stacks
    310  * @list: the new list to add.
    311  * @head: the place to add it in the first list.
    312  */
    313 SINLINE void list_splice(const struct list_head *list,
    314 				struct list_head *head)
    315 {
    316 	if (!list_empty(list))
    317 		__list_splice(list, head, head->next);
    318 }
    319 
    320 /**
    321  * list_splice_tail - join two lists, each list being a queue
    322  * @list: the new list to add.
    323  * @head: the place to add it in the first list.
    324  */
    325 SINLINE void list_splice_tail(struct list_head *list,
    326 				struct list_head *head)
    327 {
    328 	if (!list_empty(list))
    329 		__list_splice(list, head->prev, head);
    330 }
    331 
    332 /**
    333  * list_splice_init - join two lists and reinitialise the emptied list.
    334  * @list: the new list to add.
    335  * @head: the place to add it in the first list.
    336  *
    337  * The list at @list is reinitialised
    338  */
    339 SINLINE void list_splice_init(struct list_head *list,
    340 				    struct list_head *head)
    341 {
    342 	if (!list_empty(list)) {
    343 		__list_splice(list, head, head->next);
    344 		INIT_LIST_HEAD(list);
    345 	}
    346 }
    347 
    348 /**
    349  * list_splice_tail_init - join two lists and reinitialise the emptied list
    350  * @list: the new list to add.
    351  * @head: the place to add it in the first list.
    352  *
    353  * Each of the lists is a queue.
    354  * The list at @list is reinitialised
    355  */
    356 SINLINE void list_splice_tail_init(struct list_head *list,
    357 					 struct list_head *head)
    358 {
    359 	if (!list_empty(list)) {
    360 		__list_splice(list, head->prev, head);
    361 		INIT_LIST_HEAD(list);
    362 	}
    363 }
    364 
    365 /**
    366  * list_entry - get the struct for this entry
    367  * @ptr:	the &struct list_head pointer.
    368  * @type:	the type of the struct this is embedded in.
    369  * @member:	the name of the list_struct within the struct.
    370  */
    371 #define list_entry(ptr, type, member) \
    372 	container_of(ptr, type, member)
    373 
    374 /**
    375  * list_first_entry - get the first element from a list
    376  * @ptr:	the list head to take the element from.
    377  * @type:	the type of the struct this is embedded in.
    378  * @member:	the name of the list_struct within the struct.
    379  *
    380  * Note, that list is expected to be not empty.
    381  */
    382 #define list_first_entry(ptr, type, member) \
    383 	list_entry((ptr)->next, type, member)
    384 
    385 /**
    386  * list_for_each	-	iterate over a list
    387  * @pos:	the &struct list_head to use as a loop cursor.
    388  * @head:	the head for your list.
    389  */
    390 #define list_for_each(pos, head) \
    391 	for (pos = (head)->next; pos != (head); pos = pos->next)
    392 
    393 /**
    394  * __list_for_each	-	iterate over a list
    395  * @pos:	the &struct list_head to use as a loop cursor.
    396  * @head:	the head for your list.
    397  *
    398  * This variant doesn't differ from list_for_each() any more.
    399  * We don't do prefetching in either case.
    400  */
    401 #define __list_for_each(pos, head) \
    402 	for (pos = (head)->next; pos != (head); pos = pos->next)
    403 
    404 /**
    405  * list_for_each_prev	-	iterate over a list backwards
    406  * @pos:	the &struct list_head to use as a loop cursor.
    407  * @head:	the head for your list.
    408  */
    409 #define list_for_each_prev(pos, head) \
    410 	for (pos = (head)->prev; pos != (head); pos = pos->prev)
    411 
    412 /**
    413  * list_for_each_safe - iterate over a list safe against removal of list entry
    414  * @pos:	the &struct list_head to use as a loop cursor.
    415  * @n:		another &struct list_head to use as temporary storage
    416  * @head:	the head for your list.
    417  */
    418 #define list_for_each_safe(pos, n, head) \
    419 	for (pos = (head)->next, n = pos->next; pos != (head); \
    420 		pos = n, n = pos->next)
    421 
    422 /**
    423  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
    424  * @pos:	the &struct list_head to use as a loop cursor.
    425  * @n:		another &struct list_head to use as temporary storage
    426  * @head:	the head for your list.
    427  */
    428 #define list_for_each_prev_safe(pos, n, head) \
    429 	for (pos = (head)->prev, n = pos->prev; \
    430 	     pos != (head); \
    431 	     pos = n, n = pos->prev)
    432 
    433 /** Walk through client lists (with examples).
    434  * @param	pos	The variable to use as a loop cursor
    435  * @param	head	The head of your list
    436  * @param	member	The name of the list_struct within the struct.
    437  * @ingroup ListFunctions
    438  * @section Examples
    439  * @subsection client_list List all clients
    440  * @code
    441  * CMD_FUNC(cmd_listallclients)
    442  * {
    443  *     Client *acptr;
    444  *     sendnotice(client, "List of all clients:");
    445  *     list_for_each_entry(acptr, &client_list, client_node)
    446  *         sendnotice(client, "Client %s", acptr->name);
    447  * }
    448  * @endcode
    449  * @subsection lclient_list List all LOCAL clients
    450  * @code
    451  * CMD_FUNC(cmd_listalllocalclients)
    452  * {
    453  *     Client *acptr;
    454  *     sendnotice(client, "List of all local clients:");
    455  *     list_for_each_entry(acptr, &lclient_list, lclient_node)
    456  *         sendnotice(client, "Client %s", acptr->name);
    457  * }
    458  * @endcode
    459  * @subsection global_server_list List all servers
    460  * @code
    461  * CMD_FUNC(cmd_listallservers)
    462  * {
    463  *     Client *acptr;
    464  *     sendnotice(client, "List of all servers:");
    465  *     list_for_each_entry(acptr, &global_server_list, client_node)
    466  *         sendnotice(client, "Server %s", acptr->name);
    467  * }
    468  * @endcode
    469  * @subsection server_list List all LOCALLY connected servers
    470  * @code
    471  * CMD_FUNC(cmd_listallservers)
    472  * {
    473  *     Client *acptr;
    474  *     sendnotice(client, "List of all LOCAL servers:");
    475  *     list_for_each_entry(acptr, &server_list, special_node)
    476  *         sendnotice(client, "Server %s", acptr->name);
    477  * }
    478  * @endcode
    479  * @subsection oper_list List all LOCALLY connected IRCOps
    480  * @code
    481  * CMD_FUNC(cmd_listlocalircops)
    482  * {
    483  *     Client *acptr;
    484  *     sendnotice(client, "List of all LOCAL IRCOps:");
    485  *     list_for_each_entry(acptr, &oper_list, special_node)
    486  *         sendnotice(client, "User %s", acptr->name);
    487  * }
    488  * @endcode
    489  */
    490 #define list_for_each_entry(pos, head, member)				\
    491 	for (pos = list_entry((head)->next, typeof(*pos), member);	\
    492 	     &pos->member != (head); 	\
    493 	     pos = list_entry(pos->member.next, typeof(*pos), member))
    494 
    495 /**
    496  * list_for_each_entry	-	iterate over list of given type
    497  * @pos:	the type * to use as a loop cursor.
    498  * @head:	the head for your list.
    499  * @member:	the name of the list_struct within the struct.
    500  */
    501 #define list_for_each_entry2(pos, tpe, head, member)				\
    502 	for (pos = list_entry((head)->next, tpe, member);	\
    503 	     &pos->member != (head); 	\
    504 	     pos = list_entry(pos->member.next, tpe, member))
    505 
    506 /**
    507  * list_for_each_entry_reverse - iterate backwards over list of given type.
    508  * @pos:	the type * to use as a loop cursor.
    509  * @head:	the head for your list.
    510  * @member:	the name of the list_struct within the struct.
    511  */
    512 #define list_for_each_entry_reverse(pos, head, member)			\
    513 	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
    514 	     &pos->member != (head); 	\
    515 	     pos = list_entry(pos->member.prev, typeof(*pos), member))
    516 
    517 /**
    518  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
    519  * @pos:	the type * to use as a start point
    520  * @head:	the head of the list
    521  * @member:	the name of the list_struct within the struct.
    522  *
    523  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
    524  */
    525 #define list_prepare_entry(pos, head, member) \
    526 	((pos) ? : list_entry(head, typeof(*pos), member))
    527 
    528 /**
    529  * list_for_each_entry_continue - continue iteration over list of given type
    530  * @pos:	the type * to use as a loop cursor.
    531  * @head:	the head for your list.
    532  * @member:	the name of the list_struct within the struct.
    533  *
    534  * Continue to iterate over list of given type, continuing after
    535  * the current position.
    536  */
    537 #define list_for_each_entry_continue(pos, head, member) 		\
    538 	for (pos = list_entry(pos->member.next, typeof(*pos), member);	\
    539 	     &pos->member != (head);	\
    540 	     pos = list_entry(pos->member.next, typeof(*pos), member))
    541 
    542 /**
    543  * list_for_each_entry_continue_reverse - iterate backwards from the given point
    544  * @pos:	the type * to use as a loop cursor.
    545  * @head:	the head for your list.
    546  * @member:	the name of the list_struct within the struct.
    547  *
    548  * Start to iterate over list of given type backwards, continuing after
    549  * the current position.
    550  */
    551 #define list_for_each_entry_continue_reverse(pos, head, member)		\
    552 	for (pos = list_entry(pos->member.prev, typeof(*pos), member);	\
    553 	     &pos->member != (head);	\
    554 	     pos = list_entry(pos->member.prev, typeof(*pos), member))
    555 
    556 /**
    557  * list_for_each_entry_from - iterate over list of given type from the current point
    558  * @pos:	the type * to use as a loop cursor.
    559  * @head:	the head for your list.
    560  * @member:	the name of the list_struct within the struct.
    561  *
    562  * Iterate over list of given type, continuing from current position.
    563  */
    564 #define list_for_each_entry_from(pos, head, member) 			\
    565 	for (; &pos->member != (head);	\
    566 	     pos = list_entry(pos->member.next, typeof(*pos), member))
    567 
    568 /** Walk through client lists - special 'safe' version.
    569  * This is a special version, in case clients are removed from the list
    570  * while the list is iterated. It is unlikely that you need to use this
    571  * from modules, so use list_for_each_entry() instead.
    572  * Examples are also in list_for_each_entry().
    573  * @param	pos	The variable to use as a loop cursor
    574  * @param	n	Variable to be used for temporary storage
    575  * @param	head	The head of your list
    576  * @param	member	The name of the list_struct within the struct.
    577  * @ingroup ListFunctions
    578  */
    579 #define list_for_each_entry_safe(pos, n, head, member)			\
    580 	for (pos = list_entry((head)->next, typeof(*pos), member),	\
    581 		n = list_entry(pos->member.next, typeof(*pos), member);	\
    582 	     &pos->member != (head); 					\
    583 	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
    584 
    585 /**
    586  * list_for_each_entry_safe_continue - continue list iteration safe against removal
    587  * @pos:	the type * to use as a loop cursor.
    588  * @n:		another type * to use as temporary storage
    589  * @head:	the head for your list.
    590  * @member:	the name of the list_struct within the struct.
    591  *
    592  * Iterate over list of given type, continuing after current point,
    593  * safe against removal of list entry.
    594  */
    595 #define list_for_each_entry_safe_continue(pos, n, head, member) 		\
    596 	for (pos = list_entry(pos->member.next, typeof(*pos), member), 		\
    597 		n = list_entry(pos->member.next, typeof(*pos), member);		\
    598 	     &pos->member != (head);						\
    599 	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
    600 
    601 /**
    602  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
    603  * @pos:	the type * to use as a loop cursor.
    604  * @n:		another type * to use as temporary storage
    605  * @head:	the head for your list.
    606  * @member:	the name of the list_struct within the struct.
    607  *
    608  * Iterate over list of given type from current point, safe against
    609  * removal of list entry.
    610  */
    611 #define list_for_each_entry_safe_from(pos, n, head, member) 			\
    612 	for (n = list_entry(pos->member.next, typeof(*pos), member);		\
    613 	     &pos->member != (head);						\
    614 	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
    615 
    616 /**
    617  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
    618  * @pos:	the type * to use as a loop cursor.
    619  * @n:		another type * to use as temporary storage
    620  * @head:	the head for your list.
    621  * @member:	the name of the list_struct within the struct.
    622  *
    623  * Iterate backwards over list of given type, safe against removal
    624  * of list entry.
    625  */
    626 #define list_for_each_entry_safe_reverse(pos, n, head, member)		\
    627 	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
    628 		n = list_entry(pos->member.prev, typeof(*pos), member);	\
    629 	     &pos->member != (head); 					\
    630 	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))
    631 
    632 /**
    633  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
    634  * @pos:	the loop cursor used in the list_for_each_entry_safe loop
    635  * @n:		temporary storage used in list_for_each_entry_safe
    636  * @member:	the name of the list_struct within the struct.
    637  *
    638  * list_safe_reset_next is not safe to use in general if the list may be
    639  * modified concurrently (eg. the lock is dropped in the loop body). An
    640  * exception to this is if the cursor element (pos) is pinned in the list,
    641  * and list_safe_reset_next is called after re-taking the lock and before
    642  * completing the current iteration of the loop body.
    643  */
    644 #define list_safe_reset_next(pos, n, member)				\
    645 	n = list_entry(pos->member.next, typeof(*pos), member)
    646 
    647 #endif