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 <config.h>
  35 #include "queue.h"
  36 #include <assert.h>
  37 #include "ofpbuf.h"
  38
  39 static void check_queue(struct ofp_queue *q);
  40
  41 /* Initializes 'q' as an empty packet queue. */
  42 void
  43 queue_init(struct ofp_queue *q)
  44 {
  45     q->n = 0;
  46     q->head = NULL;
  47     q->tail = NULL;
  48 }
  49
  50 /* Destroys 'q' and all of the packets that it contains. */
  51 void
  52 queue_destroy(struct ofp_queue *q)
  53 {
  54     struct ofpbuf *cur, *next;
  55     for (cur = q->head; cur != NULL; cur = next) {
  56         next = cur->next;
  57         ofpbuf_delete(cur);
  58     }
  59 }
  60
  61 /* Removes and destroys all of the packets in 'q', rendering it empty. */
  62 void
  63 queue_clear(struct ofp_queue *q)
  64 {
  65     queue_destroy(q);
  66     queue_init(q);
  67 }
  68
  69 /* Advances the first packet in 'q' from 'q->head' to 'next', which should be
  70  * the second packet in the queue.
  71  *
  72  * The odd, unsafe interface here allows the first packet in the queue to be
  73  * passed to a function for possible consumption (and destruction) and only
  74  * dropped from the queue if that function actually accepts it. */
  75 void
  76 queue_advance_head(struct ofp_queue *q, struct ofpbuf *next)
  77 {
  78     assert(q->n);
  79     assert(q->head);
  80     q->head = next;
  81     if (q->head == NULL) {
  82         q->tail = NULL;
  83     }
  84     q->n--;
  85 }
  86
  87 /* Appends 'b' to the tail of 'q'. */
  88 void
  89 queue_push_tail(struct ofp_queue *q, struct ofpbuf *b)
  90 {
  91     check_queue(q);
  92
  93     b->next = NULL;
  94     if (q->n++) {
  95         q->tail->next = b;
  96     } else {
  97         q->head = b;
  98     }
  99     q->tail = b;
 100
 101     check_queue(q);
 102 }
 103
 104 /* Removes the first buffer from 'q', which must not be empty, and returns
 105  * it.  The caller must free the buffer (with ofpbuf_delete()) when it is no
 106  * longer needed. */
 107 struct ofpbuf *
 108 queue_pop_head(struct ofp_queue *q)
 109 {
 110     struct ofpbuf *head = q->head;
 111     queue_advance_head(q, head->next);
 112     return head;
 113 }
 114
 115 /* Checks the internal integrity of 'q'.  For use in debugging. */
 116 static void
 117 check_queue(struct ofp_queue *q)
 118 {
 119 #if 0
 120     struct ofpbuf *iter;
 121     size_t n;
 122
 123     assert(q->n == 0
 124            ? q->head == NULL && q->tail == NULL
 125            : q->head != NULL && q->tail != NULL);
 126
 127     n = 0;
 128     for (iter = q->head; iter != NULL; iter = iter->next) {
 129         n++;
 130         assert((iter->next != NULL) == (iter != q->tail));
 131     }
 132     assert(n == q->n);
 133 #endif
 134 }