ia64/xen-unstable

changeset 13051:34520c9451ac

[XEN] Clean up list.h for Xen formatting rules and add hlist macros
from Linux kernel.
Based on a patch from Alex Williamson <alex.williamson@hp.com>
Signed-off-by: Keir Fraser <keir@xensource.com>
author kfraser@localhost.localdomain
date Fri Dec 15 09:29:15 2006 +0000 (2006-12-15)
parents 67c5d83cdcd2
children 00199ed97fab
files xen/include/xen/list.h
line diff
     1.1 --- a/xen/include/xen/list.h	Fri Dec 15 09:17:41 2006 +0000
     1.2 +++ b/xen/include/xen/list.h	Fri Dec 15 09:29:15 2006 +0000
     1.3 @@ -1,5 +1,11 @@
     1.4 -#ifndef _LINUX_LIST_H
     1.5 -#define _LINUX_LIST_H
     1.6 +/******************************************************************************
     1.7 + * list.h
     1.8 + * 
     1.9 + * Useful linked-list definitions taken from the Linux kernel.
    1.10 + */
    1.11 +
    1.12 +#ifndef __XEN_LIST_H__
    1.13 +#define __XEN_LIST_H__
    1.14  
    1.15  #include <xen/lib.h>
    1.16  
    1.17 @@ -14,16 +20,16 @@
    1.18   */
    1.19  
    1.20  struct list_head {
    1.21 -	struct list_head *next, *prev;
    1.22 +    struct list_head *next, *prev;
    1.23  };
    1.24  
    1.25  #define LIST_HEAD_INIT(name) { &(name), &(name) }
    1.26  
    1.27  #define LIST_HEAD(name) \
    1.28 -	struct list_head name = LIST_HEAD_INIT(name)
    1.29 +    struct list_head name = LIST_HEAD_INIT(name)
    1.30  
    1.31  #define INIT_LIST_HEAD(ptr) do { \
    1.32 -	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
    1.33 +    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
    1.34  } while (0)
    1.35  
    1.36  /*
    1.37 @@ -32,14 +38,14 @@ struct list_head {
    1.38   * This is only for internal list manipulation where we know
    1.39   * the prev/next entries already!
    1.40   */
    1.41 -static __inline__ void __list_add(struct list_head * new,
    1.42 -	struct list_head * prev,
    1.43 -	struct list_head * next)
    1.44 +static inline void __list_add(struct list_head * new,
    1.45 +    struct list_head * prev,
    1.46 +    struct list_head * next)
    1.47  {
    1.48 -	next->prev = new;
    1.49 -	new->next = next;
    1.50 -	new->prev = prev;
    1.51 -	prev->next = new;
    1.52 +    next->prev = new;
    1.53 +    new->next = next;
    1.54 +    new->prev = prev;
    1.55 +    prev->next = new;
    1.56  }
    1.57  
    1.58  /**
    1.59 @@ -50,9 +56,9 @@ static __inline__ void __list_add(struct
    1.60   * Insert a new entry after the specified head.
    1.61   * This is good for implementing stacks.
    1.62   */
    1.63 -static __inline__ void list_add(struct list_head *new, struct list_head *head)
    1.64 +static inline void list_add(struct list_head *new, struct list_head *head)
    1.65  {
    1.66 -	__list_add(new, head, head->next);
    1.67 +    __list_add(new, head, head->next);
    1.68  }
    1.69  
    1.70  /**
    1.71 @@ -63,9 +69,9 @@ static __inline__ void list_add(struct l
    1.72   * Insert a new entry before the specified head.
    1.73   * This is useful for implementing queues.
    1.74   */
    1.75 -static __inline__ void list_add_tail(struct list_head *new, struct list_head *head)
    1.76 +static inline void list_add_tail(struct list_head *new, struct list_head *head)
    1.77  {
    1.78 -	__list_add(new, head->prev, head);
    1.79 +    __list_add(new, head->prev, head);
    1.80  }
    1.81  
    1.82  /*
    1.83 @@ -75,42 +81,43 @@ static __inline__ void list_add_tail(str
    1.84   * This is only for internal list manipulation where we know
    1.85   * the prev/next entries already!
    1.86   */
    1.87 -static __inline__ void __list_del(struct list_head * prev,
    1.88 -				  struct list_head * next)
    1.89 +static inline void __list_del(struct list_head * prev,
    1.90 +                              struct list_head * next)
    1.91  {
    1.92 -	next->prev = prev;
    1.93 -	prev->next = next;
    1.94 +    next->prev = prev;
    1.95 +    prev->next = next;
    1.96  }
    1.97  
    1.98  /**
    1.99   * list_del - deletes entry from list.
   1.100   * @entry: the element to delete from the list.
   1.101 - * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
   1.102 + * Note: list_empty on entry does not return true after this, the entry is
   1.103 + * in an undefined state.
   1.104   */
   1.105 -static __inline__ void list_del(struct list_head *entry)
   1.106 +static inline void list_del(struct list_head *entry)
   1.107  {
   1.108 -	ASSERT(entry->next->prev == entry);
   1.109 -	ASSERT(entry->prev->next == entry);
   1.110 -	__list_del(entry->prev, entry->next);
   1.111 +    ASSERT(entry->next->prev == entry);
   1.112 +    ASSERT(entry->prev->next == entry);
   1.113 +    __list_del(entry->prev, entry->next);
   1.114  }
   1.115  
   1.116  /**
   1.117   * list_del_init - deletes entry from list and reinitialize it.
   1.118   * @entry: the element to delete from the list.
   1.119   */
   1.120 -static __inline__ void list_del_init(struct list_head *entry)
   1.121 +static inline void list_del_init(struct list_head *entry)
   1.122  {
   1.123 -	__list_del(entry->prev, entry->next);
   1.124 -	INIT_LIST_HEAD(entry);
   1.125 +    __list_del(entry->prev, entry->next);
   1.126 +    INIT_LIST_HEAD(entry);
   1.127  }
   1.128  
   1.129  /**
   1.130   * list_empty - tests whether a list is empty
   1.131   * @head: the list to test.
   1.132   */
   1.133 -static __inline__ int list_empty(struct list_head *head)
   1.134 +static inline int list_empty(struct list_head *head)
   1.135  {
   1.136 -	return head->next == head;
   1.137 +    return head->next == head;
   1.138  }
   1.139  
   1.140  /**
   1.141 @@ -118,83 +125,239 @@ static __inline__ int list_empty(struct 
   1.142   * @list: the new list to add.
   1.143   * @head: the place to add it in the first list.
   1.144   */
   1.145 -static __inline__ void list_splice(struct list_head *list, struct list_head *head)
   1.146 +static inline void list_splice(struct list_head *list, struct list_head *head)
   1.147  {
   1.148 -	struct list_head *first = list->next;
   1.149 +    struct list_head *first = list->next;
   1.150  
   1.151 -	if (first != list) {
   1.152 -		struct list_head *last = list->prev;
   1.153 -		struct list_head *at = head->next;
   1.154 +    if ( first != list )
   1.155 +    {
   1.156 +        struct list_head *last = list->prev;
   1.157 +        struct list_head *at = head->next;
   1.158  
   1.159 -		first->prev = head;
   1.160 -		head->next = first;
   1.161 +        first->prev = head;
   1.162 +        head->next = first;
   1.163  
   1.164 -		last->next = at;
   1.165 -		at->prev = last;
   1.166 -	}
   1.167 +        last->next = at;
   1.168 +        at->prev = last;
   1.169 +    }
   1.170  }
   1.171  
   1.172  /**
   1.173   * list_entry - get the struct for this entry
   1.174 - * @ptr:	the &struct list_head pointer.
   1.175 - * @type:	the type of the struct this is embedded in.
   1.176 - * @member:	the name of the list_struct within the struct.
   1.177 + * @ptr:    the &struct list_head pointer.
   1.178 + * @type:    the type of the struct this is embedded in.
   1.179 + * @member:    the name of the list_struct within the struct.
   1.180   */
   1.181  #define list_entry(ptr, type, member) \
   1.182 -	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
   1.183 +    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
   1.184 +
   1.185 +/**
   1.186 + * list_for_each    -    iterate over a list
   1.187 + * @pos:    the &struct list_head to use as a loop counter.
   1.188 + * @head:    the head for your list.
   1.189 + */
   1.190 +#define list_for_each(pos, head)                                \
   1.191 +    for ( pos = (head)->next; pos != (head); pos = pos->next )
   1.192  
   1.193  /**
   1.194 - * list_for_each	-	iterate over a list
   1.195 - * @pos:	the &struct list_head to use as a loop counter.
   1.196 - * @head:	the head for your list.
   1.197 + * list_for_each_safe    -    iterate over a list safe against removal
   1.198 + *                            of list entry
   1.199 + * @pos:    the &struct list_head to use as a loop counter.
   1.200 + * @n:        another &struct list_head to use as temporary storage
   1.201 + * @head:    the head for your list.
   1.202   */
   1.203 -#define list_for_each(pos, head) \
   1.204 -	for (pos = (head)->next; pos != (head); pos = pos->next)
   1.205 -        	
   1.206 +#define list_for_each_safe(pos, n, head)                        \
   1.207 +    for ( pos = (head)->next, n = pos->next; pos != (head);     \
   1.208 +          pos = n, n = pos->next )
   1.209 +
   1.210  /**
   1.211 - * list_for_each_safe	-	iterate over a list safe against removal of list entry
   1.212 - * @pos:	the &struct list_head to use as a loop counter.
   1.213 - * @n:		another &struct list_head to use as temporary storage
   1.214 - * @head:	the head for your list.
   1.215 + * list_for_each_backwards_safe    -    iterate backwards over a list safe
   1.216 + *                                      against removal of list entry
   1.217 + * @pos:    the &struct list_head to use as a loop counter.
   1.218 + * @n:        another &struct list_head to use as temporary storage
   1.219 + * @head:    the head for your list.
   1.220   */
   1.221 -#define list_for_each_safe(pos, n, head) \
   1.222 -	for (pos = (head)->next, n = pos->next; pos != (head); \
   1.223 -		pos = n, n = pos->next)
   1.224 +#define list_for_each_backwards_safe(pos, n, head)              \
   1.225 +    for ( pos = (head)->prev, n = pos->prev; pos != (head);     \
   1.226 +          pos = n, n = pos->prev )
   1.227 +
   1.228 +/**
   1.229 + * list_for_each_entry    -    iterate over list of given type
   1.230 + * @pos:    the type * to use as a loop counter.
   1.231 + * @head:    the head for your list.
   1.232 + * @member:    the name of the list_struct within the struct.
   1.233 + */
   1.234 +#define list_for_each_entry(pos, head, member)                          \
   1.235 +    for ( pos = list_entry((head)->next, typeof(*pos), member),         \
   1.236 +          prefetch(pos->member.next);                                   \
   1.237 +          &pos->member != (head);                                       \
   1.238 +          pos = list_entry(pos->member.next, typeof(*pos), member),     \
   1.239 +          prefetch(pos->member.next) )
   1.240  
   1.241  /**
   1.242 - * list_for_each_backwards_safe	-	iterate backwards over a list safe against removal of list entry
   1.243 - * @pos:	the &struct list_head to use as a loop counter.
   1.244 - * @n:		another &struct list_head to use as temporary storage
   1.245 - * @head:	the head for your list.
   1.246 + * list_for_each_entry_safe - iterate over list of given type safe
   1.247 + *                            against removal of list entry
   1.248 + * @pos:    the type * to use as a loop counter.
   1.249 + * @n:        another type * to use as temporary storage
   1.250 + * @head:    the head for your list.
   1.251 + * @member:    the name of the list_struct within the struct.
   1.252 + */
   1.253 +#define list_for_each_entry_safe(pos, n, head, member)                  \
   1.254 +    for ( pos = list_entry((head)->next, typeof(*pos), member),         \
   1.255 +          n = list_entry(pos->member.next, typeof(*pos), member);       \
   1.256 +          &pos->member != (head);                                       \
   1.257 +          pos = n, n = list_entry(n->member.next, typeof(*n), member) )
   1.258 +
   1.259 +/*
   1.260 + * Double linked lists with a single pointer list head.
   1.261 + * Mostly useful for hash tables where the two pointer list head is
   1.262 + * too wasteful.
   1.263 + * You lose the ability to access the tail in O(1).
   1.264   */
   1.265 -#define list_for_each_backwards_safe(pos, n, head) \
   1.266 -	for (pos = (head)->prev, n = pos->prev; pos != (head); \
   1.267 -		pos = n, n = pos->prev)
   1.268 +
   1.269 +struct hlist_head {
   1.270 +    struct hlist_node *first;
   1.271 +};
   1.272 +
   1.273 +struct hlist_node {
   1.274 +    struct hlist_node *next, **pprev;
   1.275 +};
   1.276 +
   1.277 +#define HLIST_HEAD_INIT { .first = NULL }
   1.278 +#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
   1.279 +#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
   1.280 +static inline void INIT_HLIST_NODE(struct hlist_node *h)
   1.281 +{
   1.282 +    h->next = NULL;
   1.283 +    h->pprev = NULL;
   1.284 +}
   1.285 +
   1.286 +static inline int hlist_unhashed(const struct hlist_node *h)
   1.287 +{
   1.288 +    return !h->pprev;
   1.289 +}
   1.290 +
   1.291 +static inline int hlist_empty(const struct hlist_head *h)
   1.292 +{
   1.293 +    return !h->first;
   1.294 +}
   1.295 +
   1.296 +static inline void __hlist_del(struct hlist_node *n)
   1.297 +{
   1.298 +    struct hlist_node *next = n->next;
   1.299 +    struct hlist_node **pprev = n->pprev;
   1.300 +    *pprev = next;
   1.301 +    if ( next )
   1.302 +        next->pprev = pprev;
   1.303 +}
   1.304 +
   1.305 +static inline void hlist_del(struct hlist_node *n)
   1.306 +{
   1.307 +    __hlist_del(n);
   1.308 +}
   1.309 +
   1.310 +static inline void hlist_del_init(struct hlist_node *n)
   1.311 +{
   1.312 +    if ( !hlist_unhashed(n) )
   1.313 +    {
   1.314 +        __hlist_del(n);
   1.315 +        INIT_HLIST_NODE(n);
   1.316 +    }
   1.317 +}
   1.318 +
   1.319 +static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
   1.320 +{
   1.321 +    struct hlist_node *first = h->first;
   1.322 +    n->next = first;
   1.323 +    if ( first )
   1.324 +        first->pprev = &n->next;
   1.325 +    h->first = n;
   1.326 +    n->pprev = &h->first;
   1.327 +}
   1.328 +
   1.329 +/* next must be != NULL */
   1.330 +static inline void hlist_add_before(struct hlist_node *n,
   1.331 +                    struct hlist_node *next)
   1.332 +{
   1.333 +    n->pprev = next->pprev;
   1.334 +    n->next = next;
   1.335 +    next->pprev = &n->next;
   1.336 +    *(n->pprev) = n;
   1.337 +}
   1.338 +
   1.339 +static inline void hlist_add_after(struct hlist_node *n,
   1.340 +                    struct hlist_node *next)
   1.341 +{
   1.342 +    next->next = n->next;
   1.343 +    n->next = next;
   1.344 +    next->pprev = &n->next;
   1.345 +
   1.346 +    if ( next->next )
   1.347 +        next->next->pprev  = &next->next;
   1.348 +}
   1.349 +
   1.350 +#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
   1.351 +
   1.352 +#define hlist_for_each(pos, head)                                       \
   1.353 +    for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; });     \
   1.354 +         pos = pos->next)
   1.355 +
   1.356 +#define hlist_for_each_safe(pos, n, head)                       \
   1.357 +    for ( pos = (head)->first; pos && ({ n = pos->next; 1; });  \
   1.358 +          pos = n )
   1.359  
   1.360  /**
   1.361 - * list_for_each_entry	-	iterate over list of given type
   1.362 - * @pos:	the type * to use as a loop counter.
   1.363 - * @head:	the head for your list.
   1.364 - * @member:	the name of the list_struct within the struct.
   1.365 + * hlist_for_each_entry    - iterate over list of given type
   1.366 + * @tpos:    the type * to use as a loop cursor.
   1.367 + * @pos:    the &struct hlist_node to use as a loop cursor.
   1.368 + * @head:    the head for your list.
   1.369 + * @member:    the name of the hlist_node within the struct.
   1.370   */
   1.371 -#define list_for_each_entry(pos, head, member)				\
   1.372 -	for (pos = list_entry((head)->next, typeof(*pos), member),	\
   1.373 -		     prefetch(pos->member.next);			\
   1.374 -	     &pos->member != (head); 					\
   1.375 -	     pos = list_entry(pos->member.next, typeof(*pos), member),	\
   1.376 -		     prefetch(pos->member.next))
   1.377 +#define hlist_for_each_entry(tpos, pos, head, member)                   \
   1.378 +    for ( pos = (head)->first;                                          \
   1.379 +          pos && ({ prefetch(pos->next); 1;}) &&                        \
   1.380 +          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.381 +          pos = pos->next )
   1.382 +
   1.383 +/**
   1.384 + * hlist_for_each_entry_continue - iterate over a hlist continuing
   1.385 + *                                 after current point
   1.386 + * @tpos:    the type * to use as a loop cursor.
   1.387 + * @pos:    the &struct hlist_node to use as a loop cursor.
   1.388 + * @member:    the name of the hlist_node within the struct.
   1.389 + */
   1.390 +#define hlist_for_each_entry_continue(tpos, pos, member)                \
   1.391 +    for ( pos = (pos)->next;                                            \
   1.392 +          pos && ({ prefetch(pos->next); 1;}) &&                        \
   1.393 +          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.394 +          pos = pos->next )
   1.395  
   1.396  /**
   1.397 - * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
   1.398 - * @pos:	the type * to use as a loop counter.
   1.399 - * @n:		another type * to use as temporary storage
   1.400 - * @head:	the head for your list.
   1.401 - * @member:	the name of the list_struct within the struct.
   1.402 + * hlist_for_each_entry_from - iterate over a hlist continuing from
   1.403 + *                             current point
   1.404 + * @tpos:    the type * to use as a loop cursor.
   1.405 + * @pos:    the &struct hlist_node to use as a loop cursor.
   1.406 + * @member:    the name of the hlist_node within the struct.
   1.407   */
   1.408 -#define list_for_each_entry_safe(pos, n, head, member)			\
   1.409 -	for (pos = list_entry((head)->next, typeof(*pos), member),	\
   1.410 -		n = list_entry(pos->member.next, typeof(*pos), member);	\
   1.411 -	     &pos->member != (head); 					\
   1.412 -	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
   1.413 -#endif /* _LINUX_LIST_H */
   1.414 +#define hlist_for_each_entry_from(tpos, pos, member)                    \
   1.415 +    for ( ; pos && ({ prefetch(pos->next); 1;}) &&                      \
   1.416 +          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.417 +          pos = pos->next )
   1.418  
   1.419 +/**
   1.420 + * hlist_for_each_entry_safe - iterate over list of given type safe
   1.421 + *                             against removal of list entry
   1.422 + * @tpos:    the type * to use as a loop cursor.
   1.423 + * @pos:    the &struct hlist_node to use as a loop cursor.
   1.424 + * @n:        another &struct hlist_node to use as temporary storage
   1.425 + * @head:    the head for your list.
   1.426 + * @member:    the name of the hlist_node within the struct.
   1.427 + */
   1.428 +#define hlist_for_each_entry_safe(tpos, pos, n, head, member)           \
   1.429 +    for ( pos = (head)->first;                                          \
   1.430 +          pos && ({ n = pos->next; 1; }) &&                             \
   1.431 +          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});      \
   1.432 +          pos = n )
   1.433 +
   1.434 +#endif /* __XEN_LIST_H__ */
   1.435 +