lib/queue.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "queue.h"
  19 #include <assert.h>
  20 #include "compiler.h"
  21 #include "leak-checker.h"
  22 #include "ofpbuf.h"
  23
  24 static void check_queue(struct ovs_queue *q);
  25
  26 /* Initializes 'q' as an empty packet queue. */
  27 void
  28 queue_init(struct ovs_queue *q)
  29 {
  30     q->n = 0;
  31     q->head = NULL;
  32     q->tail = NULL;
  33 }
  34
  35 /* Destroys 'q' and all of the packets that it contains. */
  36 void
  37 queue_destroy(struct ovs_queue *q)
  38 {
  39     struct ofpbuf *cur, *next;
  40     for (cur = q->head; cur != NULL; cur = next) {
  41         next = cur->next;
  42         ofpbuf_delete(cur);
  43     }
  44 }
  45
  46 /* Removes and destroys all of the packets in 'q', rendering it empty. */
  47 void
  48 queue_clear(struct ovs_queue *q)
  49 {
  50     queue_destroy(q);
  51     queue_init(q);
  52 }
  53
  54 /* Advances the first packet in 'q' from 'q->head' to 'next', which should be
  55  * the second packet in the queue.
  56  *
  57  * The odd, unsafe interface here allows the first packet in the queue to be
  58  * passed to a function for possible consumption (and destruction) and only
  59  * dropped from the queue if that function actually accepts it. */
  60 void
  61 queue_advance_head(struct ovs_queue *q, struct ofpbuf *next)
  62 {
  63     assert(q->n);
  64     assert(q->head);
  65     q->head = next;
  66     if (q->head == NULL) {
  67         q->tail = NULL;
  68     }
  69     q->n--;
  70 }
  71
  72 /* Appends 'b' to the tail of 'q'. */
  73 void
  74 queue_push_tail(struct ovs_queue *q, struct ofpbuf *b)
  75 {
  76     check_queue(q);
  77     leak_checker_claim(b);
  78
  79     b->next = NULL;
  80     if (q->n++) {
  81         q->tail->next = b;
  82     } else {
  83         q->head = b;
  84     }
  85     q->tail = b;
  86
  87     check_queue(q);
  88 }
  89
  90 /* Removes the first buffer from 'q', which must not be empty, and returns
  91  * it.  The caller must free the buffer (with ofpbuf_delete()) when it is no
  92  * longer needed. */
  93 struct ofpbuf *
  94 queue_pop_head(struct ovs_queue *q)
  95 {
  96     struct ofpbuf *head = q->head;
  97     queue_advance_head(q, head->next);
  98     return head;
  99 }
 100
 101 /* Checks the internal integrity of 'q'.  For use in debugging. */
 102 static void
 103 check_queue(struct ovs_queue *q OVS_UNUSED)
 104 {
 105 #if 0
 106     struct ofpbuf *iter;
 107     size_t n;
 108
 109     assert(q->n == 0
 110            ? q->head == NULL && q->tail == NULL
 111            : q->head != NULL && q->tail != NULL);
 112
 113     n = 0;
 114     for (iter = q->head; iter != NULL; iter = iter->next) {
 115         n++;
 116         assert((iter->next != NULL) == (iter != q->tail));
 117     }
 118     assert(n == q->n);
 119 #endif
 120 }