Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/ntirpc/misc/opr_queue.h


$ cat -n /usr/include/ntirpc/misc/opr_queue.h

     1	/*
     2	 * Copyright (c) 2010 Your File System Inc. All rights reserved.
     3	 *
     4	 * Redistribution and use in source and binary forms, with or without
     5	 * modification, are permitted provided that the following conditions
     6	 * are met:
     7	 * 1. Redistributions of source code must retain the above copyright
     8	 *    notice, this list of conditions and the following disclaimer.
     9	 * 2. Redistributions in binary form must reproduce the above copyright
    10	 *    notice, this list of conditions and the following disclaimer in the
    11	 *    documentation and/or other materials provided with the distribution.
    12	 *
    13	 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
    14	 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    15	 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    16	 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    17	 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    18	 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    19	 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    20	 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    21	 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    22	 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    23	 */
    24	
    25	/* A better queue implementation.
    26	 *
    27	 * This differs from the original queue implementation in that that would
    28	 * only allow a structure to be threaded onto a single queue. This permits
    29	 * a given object to be on multiple queues, providing that each queue has
    30	 * a place in the structure definition.
    31	 */
    32	
    33	#ifndef OPR_QUEUE_H
    34	#define OPR_QUEUE_H 1
    35	
    36	#include <stdlib.h>
    37	
    38	struct opr_queue {
    39		struct opr_queue *next;
    40		struct opr_queue *prev;
    41	};
    42	
    43	#define opr_queue_Scan(head, cursor) \
    44		cursor = (head)->next; cursor != (head); cursor = cursor->next
    45	
    46	#define opr_queue_ScanSafe(head, cursor, store) \
    47		cursor = (head)->next, store = cursor->next; \
    48		cursor != (head); \
    49		cursor = store, store = store->next
    50	
    51	#define opr_queue_ScanFrom(head, cursor) \
    52		/* nothing */; cursor != (head); cursor = cursor->next
    53	
    54	#define opr_queue_ScanSafeFrom(head, cursor, store) \
    55		/* nothing */, store = cursor->next; \
    56		cursor != (head); \
    57		cursor = store, store = store->next
    58	
    59	#define opr_queue_ScanBackwards(head, cursor) \
    60		cursor = (head)->prev; cursor != (head); cursor = cursor->prev
    61	
    62	#define opr_queue_ScanBackwards(head, cursor) \
    63		cursor = (head)->prev; cursor != (head); cursor = cursor->prev
    64	
    65	#define opr_queue_ScanBackwardsFrom(head, cursor) \
    66		/* nothing */; cursor != (head); cursor = cursor->prev
    67	
    68	#define opr_queue_ScanBackwardsSafe(head, cursor, store) \
    69		cursor = (head)->prev, store = cursor->prev; \
    70		cursor != (head); \
    71		cursor = store, store = store->prev
    72	
    73	#define opr_queue_ScanBackwardsSafeFrom(head, cursor, store) \
    74		/* nothing */, store = cursor->prev; \
    75		cursor != (head); \
    76		cursor = store, store = store->prev
    77	
    78	static inline void opr_queue_Zero(struct opr_queue *q)
    79	{
    80		q->prev = q->next = NULL;
    81	}
    82	
    83	static inline void opr_queue_Init(struct opr_queue *q)
    84	{
    85		q->prev = q->next = q;
    86	}
    87	
    88	static inline void opr_queue_add(struct opr_queue *element,
    89					 struct opr_queue *before,
    90					 struct opr_queue *after)
    91	{
    92		after->prev = element;
    93		element->next = after;
    94		element->prev = before;
    95		before->next = element;
    96	}
    97	
    98	static inline void opr_queue_Append(struct opr_queue *queue,
    99					    struct opr_queue *element)
   100	{
   101		opr_queue_add(element, queue->prev, queue);
   102	}
   103	
   104	static inline void opr_queue_Prepend(struct opr_queue *queue,
   105					     struct opr_queue *element)
   106	{
   107		opr_queue_add(element, queue, queue->next);
   108	}
   109	
   110	static inline void opr_queue_InsertBefore(struct opr_queue *exist,
   111						  struct opr_queue *adding)
   112	{
   113		/* This may seem back to front, but take a list A, B, C where we want
   114		 * to add 1 before B. So, we're adding 1 with A the element before,
   115		 * and B the element after, hence the following: */
   116		opr_queue_add(adding, exist->prev, exist);
   117	}
   118	
   119	static inline void opr_queue_InsertAfter(struct opr_queue *exist,
   120						 struct opr_queue *adding)
   121	{
   122		opr_queue_add(adding, exist, exist->next);
   123	}
   124	
   125	static inline void opr_queue_Remove(struct opr_queue *element)
   126	{
   127		element->next->prev = element->prev;
   128		element->prev->next = element->next;
   129		element->prev = NULL;
   130		element->next = NULL;
   131	}
   132	
   133	static inline int opr_queue_IsEmpty(struct opr_queue *q)
   134	{
   135		return (q->prev == q);
   136	}
   137	
   138	static inline int opr_queue_IsOnQueue(struct opr_queue *q)
   139	{
   140		return (q->prev != NULL);
   141	}
   142	
   143	static inline int opr_queue_IsEnd(struct opr_queue *q, struct opr_queue *cursor)
   144	{
   145		return (cursor->next == q);
   146	}
   147	
   148	static inline int opr_queue_Count(struct opr_queue *q)
   149	{
   150		struct opr_queue *cursor;
   151		int n = 0;
   152	
   153		for (opr_queue_Scan(q, cursor)) {
   154			n++;
   155		}
   156		return n;
   157	}
   158	
   159	static inline void opr_queue_Swap(struct opr_queue *a, struct opr_queue *b)
   160	{
   161		struct opr_queue tq = *b;
   162	
   163		if (a->prev == a) {
   164			b->prev = b->next = b;
   165		} else {
   166			*b = *a;
   167			b->prev->next = b;
   168			b->next->prev = b;
   169		}
   170	
   171		if (tq.prev == b) {
   172			a->prev = a->next = a;
   173		} else {
   174			*a = tq;
   175			a->prev->next = a;
   176			a->next->prev = a;
   177		}
   178	}
   179	
   180	/* Remove the members before pivot from Q1, and append them to Q2 */
   181	
   182	static inline void opr_queue_SplitBeforeAppend(struct opr_queue *q1,
   183						       struct opr_queue *q2,
   184						       struct opr_queue *pivot)
   185	{
   186		if (q1 == pivot->prev)
   187			return;
   188		/* Add ourselves to the end of list 2 */
   189		q2->prev->next = q1->next; /* end of q 2, is now the start of q 1 */
   190		q1->next->prev = q2->prev;
   191		pivot->prev->next = q2;	/* entry before the pivot is it at end of q2 */
   192		q2->prev = pivot->prev;
   193	
   194		/* Pull ourselves out of list q1. */
   195		q1->next = pivot;
   196		pivot->prev = q1;
   197	}
   198	
   199	/* Remove the members after the pivot from Q1, and prepend them onto Q2 */
   200	static inline void opr_queue_SplitAfterPrepend(struct opr_queue *q1,
   201						       struct opr_queue *q2,
   202						       struct opr_queue *pivot)
   203	{
   204		if (q1 == pivot->next)
   205			return;
   206	
   207		/* start of q2 has last element of q1 before it */
   208		q2->next->prev = q1->prev;
   209		q1->prev->next = q2->next;
   210		/* item that we're breaking at (pivot->next) is at start of q2 */
   211		q2->next = pivot->next;
   212		pivot->next->prev = q2;
   213	
   214		/* Q1 now ends after pivot */
   215		pivot->next = q1;
   216		q1->prev = pivot;
   217	}
   218	
   219	static inline void opr_queue_SpliceAppend(struct opr_queue *target,
   220						  struct opr_queue *source)
   221	{
   222		if (source->next == source)
   223			return;
   224	
   225		/* Stick the contents of source onto the end of target */
   226		target->prev->next = source->next;
   227		source->next->prev = target->prev;
   228		source->prev->next = target;
   229		target->prev = source->prev;
   230	
   231		/* Reinitialise source */
   232		source->next = source->prev = source;
   233	}
   234	
   235	static inline void opr_queue_SplicePrepend(struct opr_queue *target,
   236						   struct opr_queue *source)
   237	{
   238		if (source->next == source)
   239			return;
   240	
   241		/* Contents of source go onto the beginning of target */
   242		target->next->prev = source->prev;
   243		source->prev->next = target->next;
   244		source->next->prev = target;
   245		target->next = source->next;
   246	
   247		/* Reinitialise source */
   248		source->next = source->prev = source;
   249	}
   250	
   251	#define opr_queue_Entry(queue, structure, member) \
   252		((structure *)((char *)(queue)-(char *)(&((structure *)NULL)->member)))
   253	
   254	#define opr_queue_First(queue, structure, member) \
   255		opr_queue_Entry((queue)->next, structure, member)
   256	
   257	#define opr_queue_Last(queue, structure, member) \
   258		opr_queue_Entry((queue)->prev, structure, member)
   259	
   260	#define opr_queue_Next(entry, structure, member) \
   261		opr_queue_Entry((entry)->next, structure, member)
   262	
   263	#define opr_queue_Prev(entry, structure, member) \
   264		opr_queue_Entry((entry)->prev, structure, member)
   265	
   266	#endif