2 * Copyright (c) 2008, 2010 Nicira Networks.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #include "port-array.h"
21 static struct port_array_l2 l2_sentinel;
22 static struct port_array_l3 l3_sentinel;
25 /* Initializes 'pa' as an empty port_array. */
27 port_array_init(struct port_array *pa)
32 for (i = 0; i < PORT_ARRAY_L2_SIZE; i++) {
33 l2_sentinel.l2[i] = &l3_sentinel;
36 for (i = 0; i < PORT_ARRAY_L1_SIZE; i++) {
37 pa->l1[i] = &l2_sentinel;
41 /* Frees all the memory allocated for 'pa'. It is the client's responsibility
42 * to free memory that 'pa' elements point to. */
44 port_array_destroy(struct port_array *pa)
48 for (l1_idx = 0; l1_idx < PORT_ARRAY_L1_SIZE; l1_idx++) {
49 struct port_array_l2 *l2 = pa->l1[l1_idx];
51 if (l2 != &l2_sentinel) {
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) {
65 /* Clears all elements of 'pa' to null pointers. */
67 port_array_clear(struct port_array *pa)
69 port_array_destroy(pa);
73 /* Sets 'pa' element numbered 'idx' to 'p'. */
75 port_array_set(struct port_array *pa, uint16_t idx, void *p)
77 struct port_array_l2 **l2p, *l2;
78 struct port_array_l3 **l3p, *l3;
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);
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);
95 l3->l3[PORT_ARRAY_L3(idx)] = p;
98 /* Sets 'pa' element numbered 'idx' to NULL. */
100 port_array_delete(struct port_array *pa, uint16_t idx)
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);
106 pa->l1[l1_idx]->l2[l2_idx]->l3[l3_idx] = NULL;
110 next(const struct port_array *pa, unsigned int *idxp)
112 unsigned int idx = *idxp;
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];
129 *idxp = ((l1_idx << PORT_ARRAY_L1_SHIFT)
130 | (l2_idx << PORT_ARRAY_L2_SHIFT)
131 | (l3_idx << PORT_ARRAY_L3_SHIFT));
145 *idxp = PORT_ARRAY_SIZE;
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. */
153 port_array_first(const struct port_array *pa, unsigned int *idxp)
156 return next(pa, idxp);
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. */
164 port_array_next(const struct port_array *pa, unsigned int *idxp)
167 return next(pa, idxp);
170 /* Returns the number of non-null elements of 'pa'. */
172 port_array_count(const struct port_array *pa)
174 unsigned int l1_idx, l2_idx, l3_idx;
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]) {