lib/port-array.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 "port-array.h"
  36
  37 static struct port_array_l2 l2_sentinel;
  38 static struct port_array_l3 l3_sentinel;
  39 static bool inited;
  40
  41 /* Initializes 'pa' as an empty port_array. */
  42 void
  43 port_array_init(struct port_array *pa)
  44 {
  45     size_t i;
  46     if (!inited) {
  47         inited = true;
  48         for (i = 0; i < PORT_ARRAY_L2_SIZE; i++) {
  49             l2_sentinel.l2[i] = &l3_sentinel;
  50         }
  51     }
  52     for (i = 0; i < PORT_ARRAY_L1_SIZE; i++) {
  53         pa->l1[i] = &l2_sentinel;
  54     }
  55 }
  56
  57 /* Sets 'pa' element numbered 'idx' to 'p'. */
  58 void
  59 port_array_set(struct port_array *pa, uint16_t idx, void *p)
  60 {
  61     struct port_array_l2 **l2p, *l2;
  62     struct port_array_l3 **l3p, *l3;
  63
  64     /* Traverse level 1. */
  65     l2p = &pa->l1[PORT_ARRAY_L1(idx)];
  66     if (*l2p == &l2_sentinel) {
  67         *l2p = xmemdup(&l2_sentinel, sizeof l2_sentinel);
  68     }
  69     l2 = *l2p;
  70
  71     /* Traverse level 2. */
  72     l3p = &l2->l2[PORT_ARRAY_L2(idx)];
  73     if (*l3p == &l3_sentinel) {
  74         *l3p = xmemdup(&l3_sentinel, sizeof l3_sentinel);
  75     }
  76     l3 = *l3p;
  77
  78     /* Set level 3. */
  79     l3->l3[PORT_ARRAY_L3(idx)] = p;
  80 }
  81
  82 static void *
  83 next(const struct port_array *pa, unsigned int *idxp)
  84 {
  85     unsigned int idx = *idxp;
  86
  87     /* Using shift-right directly here, instead of PORT_ARRAY_L1(idx), ensures
  88      * that with an initially too-big value of '*idxp' we will skip the outer
  89      * loop and return NULL. */
  90     unsigned int l1_idx = idx >> PORT_ARRAY_L1_SHIFT;
  91     unsigned int l2_idx = PORT_ARRAY_L2(idx);
  92     unsigned int l3_idx = PORT_ARRAY_L3(idx);
  93     while (l1_idx < PORT_ARRAY_L1_SIZE) {
  94         struct port_array_l2 *l2 = pa->l1[l1_idx];
  95         if (l2 != &l2_sentinel) {
  96             while (l2_idx < PORT_ARRAY_L2_SIZE) {
  97                 struct port_array_l3 *l3 = l2->l2[l2_idx];
  98                 if (l3 != &l3_sentinel) {
  99                     while (l3_idx < PORT_ARRAY_L3_SIZE) {
 100                         void *p = l3->l3[l3_idx];
 101                         if (p) {
 102                             *idxp = ((l1_idx << PORT_ARRAY_L1_SHIFT)
 103                                      | (l2_idx << PORT_ARRAY_L2_SHIFT)
 104                                      | (l3_idx << PORT_ARRAY_L3_SHIFT));
 105                             return p;
 106                         }
 107                         l3_idx++;
 108                     }
 109                 }
 110                 l2_idx++;
 111                 l3_idx = 0;
 112             }
 113         }
 114         l1_idx++;
 115         l2_idx = 0;
 116         l3_idx = 0;
 117     }
 118     *idxp = PORT_ARRAY_SIZE;
 119     return NULL;
 120 }
 121
 122 /* Returns the value of the lowest-numbered non-empty element of 'pa', and sets
 123  * '*idxp' to that element's index.  If 'pa' is entirely empty, returns a null
 124  * pointer and sets '*idxp' to 65536.  */
 125 void *
 126 port_array_first(const struct port_array *pa, unsigned int *idxp)
 127 {
 128     *idxp = 0;
 129     return next(pa, idxp);
 130 }
 131
 132 /* Returns the value of the lowest-numbered non-empty element of 'pa' greater
 133  * than the initial value of '*idxp', and sets '*idxp' to that element's index.
 134  * If 'pa' contains no non-empty elements with indexes greater than the initial
 135  * value of '*idxp', returns a null pointer and sets '*idxp' to 65536.  */
 136 void *
 137 port_array_next(const struct port_array *pa, unsigned int *idxp)
 138 {
 139     ++*idxp;
 140     return next(pa, idxp);
 141 }