]>
Commit | Line | Data |
---|---|---|
064af421 BP |
1 | /* |
2 | * Copyright (c) 2008 Nicira Networks. | |
3 | * | |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
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 | } |