xenserver: Add explicit license to refresh-xs-network-uuids.
[sliver-openvswitch.git] / 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 }