pintos-os.org Git - openvswitch/blob - lib/queue.c

   1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
   2  * Junior University
   3  *
   4  * We are making the OpenFlow specification and associated documentation
   5  * (Software) available for public use and benefit with the expectation
   6  * that others will use, modify and enhance the Software and contribute
   7  * those enhancements back to the community. However, since we would
   8  * like to make the Software available for broadest use, with as few
   9  * restrictions as possible permission is hereby granted, free of
  10  * charge, to any person obtaining a copy of this Software to deal in
  11  * the Software under the copyrights without restriction, including
  12  * without limitation the rights to use, copy, modify, merge, publish,
  13  * distribute, sublicense, and/or sell copies of the Software, and to
  14  * permit persons to whom the Software is furnished to do so, subject to
  15  * the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27  * SOFTWARE.
  28  *
  29  * The name and trademarks of copyright holder(s) may NOT be used in
  30  * advertising or publicity pertaining to the Software or any
  31  * derivatives without specific, written prior permission.
  32  */
  33
  34 #include "queue.h"
  35 #include <assert.h>
  36 #include "buffer.h"
  37
  38 static void check_queue(struct queue *q);
  39
  40 /* Initializes 'q' as an empty packet queue. */
  41 void
  42 queue_init(struct queue *q)
  43 {
  44     q->n = 0;
  45     q->head = NULL;
  46     q->tail = NULL;
  47 }
  48
  49 /* Destroys 'q' and all of the packets that it contains. */
  50 void
  51 queue_destroy(struct queue *q)
  52 {
  53     struct buffer *cur, *next;
  54     for (cur = q->head; cur != NULL; cur = next) {
  55         next = cur->next;
  56         buffer_delete(cur);
  57     }
  58 }
  59
  60 /* Removes and destroys all of the packets in 'q', rendering it empty. */
  61 void
  62 queue_clear(struct queue *q)
  63 {
  64     queue_destroy(q);
  65     queue_init(q);
  66 }
  67
  68 /* Advances the first packet in 'q' from 'q->head' to 'next', which should be
  69  * the second packet in the queue.
  70  *
  71  * The odd, unsafe interface here allows the first packet in the queue to be
  72  * passed to a function for possible consumption (and destruction) and only
  73  * dropped from the queue if that function actually accepts it. */
  74 void
  75 queue_advance_head(struct queue *q, struct buffer *next)
  76 {
  77     assert(q->n);
  78     assert(q->head);
  79     q->head = next;
  80     if (q->head == NULL) {
  81         q->tail = NULL;
  82     }
  83     q->n--;
  84 }
  85
  86 /* Appends 'b' to the tail of 'q'. */
  87 void
  88 queue_push_tail(struct queue *q, struct buffer *b)
  89 {
  90     check_queue(q);
  91
  92     b->next = NULL;
  93     if (q->n++) {
  94         q->tail->next = b;
  95     } else {
  96         q->head = b;
  97     }
  98     q->tail = b;
  99
 100     check_queue(q);
 101 }
 102
 103 /* Checks the internal integrity of 'q'.  For use in debugging. */
 104 static void
 105 check_queue(struct queue *q)
 106 {
 107 #if 0
 108     struct buffer *iter;
 109     size_t n;
 110
 111     assert(q->n == 0
 112            ? q->head == NULL && q->tail == NULL
 113            : q->head != NULL && q->tail != NULL);
 114
 115     n = 0;
 116     for (iter = q->head; iter != NULL; iter = iter->next) {
 117         n++;
 118         assert((iter->next != NULL) == (iter != q->tail));
 119     }
 120     assert(n == q->n);
 121 #endif
 122 }