lib/port-array.c

   1 /*
   2  * Copyright (c) 2008, 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 "port-array.h"
  19 #include <stdlib.h>
  20
  21 static struct port_array_l2 l2_sentinel;
  22 static struct port_array_l3 l3_sentinel;
  23 static bool inited;
  24
  25 /* Initializes 'pa' as an empty port_array. */
  26 void
  27 port_array_init(struct port_array *pa)
  28 {
  29     size_t i;
  30     if (!inited) {
  31         inited = true;
  32         for (i = 0; i < PORT_ARRAY_L2_SIZE; i++) {
  33             l2_sentinel.l2[i] = &l3_sentinel;
  34         }
  35     }
  36     for (i = 0; i < PORT_ARRAY_L1_SIZE; i++) {
  37         pa->l1[i] = &l2_sentinel;
  38     }
  39 }
  40
  41 /* Frees all the memory allocated for 'pa'.  It is the client's responsibility
  42  * to free memory that 'pa' elements point to. */
  43 void
  44 port_array_destroy(struct port_array *pa)
  45 {
  46     unsigned int l1_idx;
  47
  48     for (l1_idx = 0; l1_idx < PORT_ARRAY_L1_SIZE; l1_idx++) {
  49         struct port_array_l2 *l2 = pa->l1[l1_idx];
  50
  51         if (l2 != &l2_sentinel) {
  52             unsigned int l2_idx;
  53
  54             for (l2_idx = 0; l2_idx < PORT_ARRAY_L2_SIZE; l2_idx++) {
  55                 struct port_array_l3 *l3 = l2->l2[l2_idx];
  56                 if (l3 != &l3_sentinel) {
  57                     free(l3);
  58                 }
  59             }
  60             free(l2);
  61         }
  62     }
  63 }
  64
  65 /* Clears all elements of 'pa' to null pointers. */
  66 void
  67 port_array_clear(struct port_array *pa)
  68 {
  69     port_array_destroy(pa);
  70     port_array_init(pa);
  71 }
  72
  73 /* Sets 'pa' element numbered 'idx' to 'p'. */
  74 void
  75 port_array_set(struct port_array *pa, uint16_t idx, void *p)
  76 {
  77     struct port_array_l2 **l2p, *l2;
  78     struct port_array_l3 **l3p, *l3;
  79
  80     /* Traverse level 1. */
  81     l2p = &pa->l1[PORT_ARRAY_L1(idx)];
  82     if (*l2p == &l2_sentinel) {
  83         *l2p = xmemdup(&l2_sentinel, sizeof l2_sentinel);
  84     }
  85     l2 = *l2p;
  86
  87     /* Traverse level 2. */
  88     l3p = &l2->l2[PORT_ARRAY_L2(idx)];
  89     if (*l3p == &l3_sentinel) {
  90         *l3p = xmemdup(&l3_sentinel, sizeof l3_sentinel);
  91     }
  92     l3 = *l3p;
  93
  94     /* Set level 3. */
  95     l3->l3[PORT_ARRAY_L3(idx)] = p;
  96 }
  97
  98 /* Sets 'pa' element numbered 'idx' to NULL. */
  99 void
 100 port_array_delete(struct port_array *pa, uint16_t idx)
 101 {
 102     unsigned int l1_idx = PORT_ARRAY_L1(idx);
 103     unsigned int l2_idx = PORT_ARRAY_L2(idx);
 104     unsigned int l3_idx = PORT_ARRAY_L3(idx);
 105
 106     pa->l1[l1_idx]->l2[l2_idx]->l3[l3_idx] = NULL;
 107 }
 108
 109 static void *
 110 next(const struct port_array *pa, unsigned int *idxp)
 111 {
 112     unsigned int idx = *idxp;
 113
 114     /* Using shift-right directly here, instead of PORT_ARRAY_L1(idx), ensures
 115      * that with an initially too-big value of '*idxp' we will skip the outer
 116      * loop and return NULL. */
 117     unsigned int l1_idx = idx >> PORT_ARRAY_L1_SHIFT;
 118     unsigned int l2_idx = PORT_ARRAY_L2(idx);
 119     unsigned int l3_idx = PORT_ARRAY_L3(idx);
 120     while (l1_idx < PORT_ARRAY_L1_SIZE) {
 121         struct port_array_l2 *l2 = pa->l1[l1_idx];
 122         if (l2 != &l2_sentinel) {
 123             while (l2_idx < PORT_ARRAY_L2_SIZE) {
 124                 struct port_array_l3 *l3 = l2->l2[l2_idx];
 125                 if (l3 != &l3_sentinel) {
 126                     while (l3_idx < PORT_ARRAY_L3_SIZE) {
 127                         void *p = l3->l3[l3_idx];
 128                         if (p) {
 129                             *idxp = ((l1_idx << PORT_ARRAY_L1_SHIFT)
 130                                      | (l2_idx << PORT_ARRAY_L2_SHIFT)
 131                                      | (l3_idx << PORT_ARRAY_L3_SHIFT));
 132                             return p;
 133                         }
 134                         l3_idx++;
 135                     }
 136                 }
 137                 l2_idx++;
 138                 l3_idx = 0;
 139             }
 140         }
 141         l1_idx++;
 142         l2_idx = 0;
 143         l3_idx = 0;
 144     }
 145     *idxp = PORT_ARRAY_SIZE;
 146     return NULL;
 147 }
 148
 149 /* Returns the value of the lowest-numbered non-empty element of 'pa', and sets
 150  * '*idxp' to that element's index.  If 'pa' is entirely empty, returns a null
 151  * pointer and sets '*idxp' to 65536.  */
 152 void *
 153 port_array_first(const struct port_array *pa, unsigned int *idxp)
 154 {
 155     *idxp = 0;
 156     return next(pa, idxp);
 157 }
 158
 159 /* Returns the value of the lowest-numbered non-empty element of 'pa' greater
 160  * than the initial value of '*idxp', and sets '*idxp' to that element's index.
 161  * If 'pa' contains no non-empty elements with indexes greater than the initial
 162  * value of '*idxp', returns a null pointer and sets '*idxp' to 65536.  */
 163 void *
 164 port_array_next(const struct port_array *pa, unsigned int *idxp)
 165 {
 166     ++*idxp;
 167     return next(pa, idxp);
 168 }
 169
 170 /* Returns the number of non-null elements of 'pa'. */
 171 unsigned int
 172 port_array_count(const struct port_array *pa)
 173 {
 174     unsigned int l1_idx, l2_idx, l3_idx;
 175     unsigned int count;
 176
 177     count = 0;
 178     for (l1_idx = 0; l1_idx < PORT_ARRAY_L1_SIZE; l1_idx++) {
 179         struct port_array_l2 *l2 = pa->l1[l1_idx];
 180         if (l2 != &l2_sentinel) {
 181             for (l2_idx = 0; l2_idx < PORT_ARRAY_L2_SIZE; l2_idx++) {
 182                 struct port_array_l3 *l3 = l2->l2[l2_idx];
 183                 if (l3 != &l3_sentinel) {
 184                     for (l3_idx = 0; l3_idx < PORT_ARRAY_L3_SIZE; l3_idx++) {
 185                         if (l3->l3[l3_idx]) {
 186                             count++;
 187                         }
 188                     }
 189                 }
 190             }
 191         }
 192     }
 193     return count;
 194 }