pintos-os.org Git - openvswitch/blob - lib/port-array.c

   1 /*
   2  * Copyright (c) 2008 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 static void *
  99 next(const struct port_array *pa, unsigned int *idxp)
 100 {
 101     unsigned int idx = *idxp;
 102
 103     /* Using shift-right directly here, instead of PORT_ARRAY_L1(idx), ensures
 104      * that with an initially too-big value of '*idxp' we will skip the outer
 105      * loop and return NULL. */
 106     unsigned int l1_idx = idx >> PORT_ARRAY_L1_SHIFT;
 107     unsigned int l2_idx = PORT_ARRAY_L2(idx);
 108     unsigned int l3_idx = PORT_ARRAY_L3(idx);
 109     while (l1_idx < PORT_ARRAY_L1_SIZE) {
 110         struct port_array_l2 *l2 = pa->l1[l1_idx];
 111         if (l2 != &l2_sentinel) {
 112             while (l2_idx < PORT_ARRAY_L2_SIZE) {
 113                 struct port_array_l3 *l3 = l2->l2[l2_idx];
 114                 if (l3 != &l3_sentinel) {
 115                     while (l3_idx < PORT_ARRAY_L3_SIZE) {
 116                         void *p = l3->l3[l3_idx];
 117                         if (p) {
 118                             *idxp = ((l1_idx << PORT_ARRAY_L1_SHIFT)
 119                                      | (l2_idx << PORT_ARRAY_L2_SHIFT)
 120                                      | (l3_idx << PORT_ARRAY_L3_SHIFT));
 121                             return p;
 122                         }
 123                         l3_idx++;
 124                     }
 125                 }
 126                 l2_idx++;
 127                 l3_idx = 0;
 128             }
 129         }
 130         l1_idx++;
 131         l2_idx = 0;
 132         l3_idx = 0;
 133     }
 134     *idxp = PORT_ARRAY_SIZE;
 135     return NULL;
 136 }
 137
 138 /* Returns the value of the lowest-numbered non-empty element of 'pa', and sets
 139  * '*idxp' to that element's index.  If 'pa' is entirely empty, returns a null
 140  * pointer and sets '*idxp' to 65536.  */
 141 void *
 142 port_array_first(const struct port_array *pa, unsigned int *idxp)
 143 {
 144     *idxp = 0;
 145     return next(pa, idxp);
 146 }
 147
 148 /* Returns the value of the lowest-numbered non-empty element of 'pa' greater
 149  * than the initial value of '*idxp', and sets '*idxp' to that element's index.
 150  * If 'pa' contains no non-empty elements with indexes greater than the initial
 151  * value of '*idxp', returns a null pointer and sets '*idxp' to 65536.  */
 152 void *
 153 port_array_next(const struct port_array *pa, unsigned int *idxp)
 154 {
 155     ++*idxp;
 156     return next(pa, idxp);
 157 }
 158
 159 /* Returns the number of non-null elements of 'pa'. */
 160 unsigned int
 161 port_array_count(const struct port_array *pa)
 162 {
 163     unsigned int l1_idx, l2_idx, l3_idx;
 164     unsigned int count;
 165
 166     count = 0;
 167     for (l1_idx = 0; l1_idx < PORT_ARRAY_L1_SIZE; l1_idx++) {
 168         struct port_array_l2 *l2 = pa->l1[l1_idx];
 169         if (l2 != &l2_sentinel) {
 170             for (l2_idx = 0; l2_idx < PORT_ARRAY_L2_SIZE; l2_idx++) {
 171                 struct port_array_l3 *l3 = l2->l2[l2_idx];
 172                 if (l3 != &l3_sentinel) {
 173                     for (l3_idx = 0; l3_idx < PORT_ARRAY_L3_SIZE; l3_idx++) {
 174                         if (l3->l3[l3_idx]) {
 175                             count++;
 176                         }
 177                     }
 178                 }
 179             }
 180         }
 181     }
 182     return count;
 183 }