]>
Commit | Line | Data |
---|---|---|
ba94a1bb WD |
1 | /** |
2 | * @file IxEthDBDBPortUpdate.c | |
3 | * | |
4 | * @brief Implementation of dependency and port update handling | |
5 | * | |
6 | * @par | |
7 | * IXP400 SW Release version 2.0 | |
8 | * | |
9 | * -- Copyright Notice -- | |
10 | * | |
11 | * @par | |
12 | * Copyright 2001-2005, Intel Corporation. | |
13 | * All rights reserved. | |
14 | * | |
15 | * @par | |
16 | * Redistribution and use in source and binary forms, with or without | |
17 | * modification, are permitted provided that the following conditions | |
18 | * are met: | |
19 | * 1. Redistributions of source code must retain the above copyright | |
20 | * notice, this list of conditions and the following disclaimer. | |
21 | * 2. Redistributions in binary form must reproduce the above copyright | |
22 | * notice, this list of conditions and the following disclaimer in the | |
23 | * documentation and/or other materials provided with the distribution. | |
24 | * 3. Neither the name of the Intel Corporation nor the names of its contributors | |
25 | * may be used to endorse or promote products derived from this software | |
26 | * without specific prior written permission. | |
27 | * | |
28 | * @par | |
29 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' | |
30 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
31 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
32 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE | |
33 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
34 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
35 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
36 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
37 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
38 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
39 | * SUCH DAMAGE. | |
40 | * | |
41 | * @par | |
42 | * -- End of Copyright Notice -- | |
43 | */ | |
44 | ||
45 | #include "IxEthDB_p.h" | |
46 | ||
47 | /* forward prototype declarations */ | |
48 | IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor); | |
49 | IX_ETH_DB_PRIVATE void ixEthDBCreateTrees(IxEthDBPortMap updatePorts); | |
50 | IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree); | |
51 | IX_ETH_DB_PRIVATE void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size); | |
52 | IX_ETH_DB_PRIVATE void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size); | |
53 | IX_ETH_DB_PRIVATE void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count); | |
54 | IX_ETH_DB_PRIVATE UINT32 ixEthDBRebalanceLog2Floor(UINT32 x); | |
55 | ||
56 | extern HashTable dbHashtable; | |
57 | ||
58 | /** | |
59 | * @brief register types requiring automatic updates | |
60 | * | |
61 | * @param typeArray array indexed on record types, each | |
62 | * element indicating whether the record type requires an | |
472d5460 | 63 | * automatic update (true) or not (false) |
ba94a1bb WD |
64 | * |
65 | * Automatic updates are done for registered record types | |
66 | * upon adding, updating (that is, updating the record portID) | |
67 | * and removing records. Whenever an automatic update is triggered | |
68 | * the appropriate ports will be provided with new database | |
69 | * information. | |
70 | * | |
71 | * It is assumed that the typeArray parameter is allocated large | |
72 | * enough to hold all the user defined types. Also, the type | |
472d5460 | 73 | * array should be initialized to false as this function only |
ba94a1bb WD |
74 | * caters for types which do require automatic updates. |
75 | * | |
76 | * Note that this function should be called by the component | |
77 | * initialization function. | |
78 | * | |
79 | * @return number of record types registered for automatic | |
80 | * updates | |
81 | * | |
82 | * @internal | |
83 | */ | |
84 | IX_ETH_DB_PUBLIC | |
85 | UINT32 ixEthDBUpdateTypeRegister(BOOL *typeArray) | |
86 | { | |
472d5460 YS |
87 | typeArray[IX_ETH_DB_FILTERING_RECORD] = true; |
88 | typeArray[IX_ETH_DB_FILTERING_VLAN_RECORD] = true; | |
ba94a1bb WD |
89 | |
90 | return 2; | |
91 | } | |
92 | ||
93 | /** | |
94 | * @brief computes dependencies and triggers port learning tree updates | |
95 | * | |
96 | * @param triggerPorts port map consisting in the ports which triggered the update | |
97 | * | |
98 | * This function browses through all the ports and determines how to waterfall the update | |
99 | * event from the trigger ports to all other ports depending on them. | |
100 | * | |
101 | * Once the list of ports to be updated is determined this function | |
102 | * calls @ref ixEthDBCreateTrees. | |
103 | * | |
104 | * @internal | |
105 | */ | |
106 | IX_ETH_DB_PUBLIC | |
107 | void ixEthDBUpdatePortLearningTrees(IxEthDBPortMap triggerPorts) | |
108 | { | |
109 | IxEthDBPortMap updatePorts; | |
110 | UINT32 portIndex; | |
111 | ||
112 | ixEthDBUpdateLock(); | |
113 | ||
114 | SET_EMPTY_DEPENDENCY_MAP(updatePorts); | |
115 | ||
116 | for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++) | |
117 | { | |
118 | PortInfo *port = &ixEthDBPortInfo[portIndex]; | |
119 | BOOL mapsCollide; | |
120 | ||
121 | MAPS_COLLIDE(mapsCollide, triggerPorts, port->dependencyPortMap); | |
122 | ||
123 | if (mapsCollide /* do triggers influence this port? */ | |
124 | && !IS_PORT_INCLUDED(portIndex, updatePorts) /* and it's not already in the update list */ | |
125 | && port->updateMethod.updateEnabled) /* and we're allowed to update it */ | |
126 | { | |
127 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding port %d to update set\n", portIndex); | |
128 | ||
129 | JOIN_PORT_TO_MAP(updatePorts, portIndex); | |
130 | } | |
131 | else | |
132 | { | |
133 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Didn't add port %d to update set, reasons follow:\n", portIndex); | |
134 | ||
135 | if (!mapsCollide) | |
136 | { | |
137 | IX_ETH_DB_UPDATE_TRACE("\tMaps don't collide on port %d\n", portIndex); | |
138 | } | |
139 | ||
140 | if (IS_PORT_INCLUDED(portIndex, updatePorts)) | |
141 | { | |
142 | IX_ETH_DB_UPDATE_TRACE("\tPort %d is already in the update set\n", portIndex); | |
143 | } | |
144 | ||
145 | if (!port->updateMethod.updateEnabled) | |
146 | { | |
147 | IX_ETH_DB_UPDATE_TRACE("\tPort %d doesn't have updateEnabled set\n", portIndex); | |
148 | } | |
149 | } | |
150 | } | |
151 | ||
152 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Updating port set\n"); | |
153 | ||
154 | ixEthDBCreateTrees(updatePorts); | |
155 | ||
156 | ixEthDBUpdateUnlock(); | |
157 | } | |
158 | ||
159 | /** | |
160 | * @brief creates learning trees and calls the port update handlers | |
161 | * | |
162 | * @param updatePorts set of ports in need of learning trees | |
163 | * | |
164 | * This function determines the optimal method of creating learning | |
165 | * trees using a minimal number of database queries, keeping in mind | |
166 | * that different ports can either use the same learning trees or they | |
167 | * can partially share them. The actual tree building routine is | |
168 | * @ref ixEthDBQuery. | |
169 | * | |
170 | * @internal | |
171 | */ | |
172 | IX_ETH_DB_PRIVATE | |
173 | void ixEthDBCreateTrees(IxEthDBPortMap updatePorts) | |
174 | { | |
175 | UINT32 portIndex; | |
176 | BOOL result; | |
472d5460 | 177 | BOOL portsLeft = true; |
ba94a1bb WD |
178 | |
179 | while (portsLeft) | |
180 | { | |
181 | /* get port with minimal dependency map and NULL search tree */ | |
182 | UINT32 minPortIndex = MAX_PORT_SIZE; | |
183 | UINT32 minimalSize = MAX_PORT_SIZE; | |
184 | ||
185 | for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++) | |
186 | { | |
187 | UINT32 size; | |
188 | PortInfo *port = &ixEthDBPortInfo[portIndex]; | |
189 | ||
190 | /* generate trees only for ports that need them */ | |
191 | if (!port->updateMethod.searchTreePendingWrite && IS_PORT_INCLUDED(portIndex, updatePorts)) | |
192 | { | |
193 | GET_MAP_SIZE(port->dependencyPortMap, size); | |
194 | ||
195 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Dependency map for port %d: size %d\n", | |
196 | portIndex, size); | |
197 | ||
198 | if (size < minimalSize) | |
199 | { | |
200 | minPortIndex = portIndex; | |
201 | minimalSize = size; | |
202 | } | |
203 | } | |
204 | else | |
205 | { | |
206 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Skipped port %d from tree diff (%s)\n", portIndex, | |
207 | port->updateMethod.searchTreePendingWrite ? "pending write access" : "ignored by query"); | |
208 | } | |
209 | } | |
210 | ||
211 | /* if a port was found than minimalSize is not MAX_PORT_SIZE */ | |
212 | if (minimalSize != MAX_PORT_SIZE) | |
213 | { | |
214 | /* minPortIndex is the port we seek */ | |
215 | PortInfo *port = &ixEthDBPortInfo[minPortIndex]; | |
216 | ||
217 | IxEthDBPortMap query; | |
218 | MacTreeNode *baseTree; | |
219 | ||
220 | /* now try to find a port with minimal map difference */ | |
221 | PortInfo *minimalDiffPort = NULL; | |
222 | UINT32 minimalDiff = MAX_PORT_SIZE; | |
223 | ||
224 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal size port is %d\n", minPortIndex); | |
225 | ||
226 | for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++) | |
227 | { | |
228 | PortInfo *diffPort = &ixEthDBPortInfo[portIndex]; | |
229 | BOOL mapIsSubset; | |
230 | ||
231 | IS_MAP_SUBSET(mapIsSubset, diffPort->dependencyPortMap, port->dependencyPortMap); | |
232 | ||
233 | ||
234 | if (portIndex != minPortIndex | |
235 | && diffPort->updateMethod.searchTree != NULL | |
236 | && mapIsSubset) | |
237 | { | |
238 | /* compute size and pick only minimal size difference */ | |
239 | UINT32 diffPortSize; | |
240 | UINT32 sizeDifference; | |
241 | ||
242 | GET_MAP_SIZE(diffPort->dependencyPortMap, diffPortSize); | |
243 | ||
244 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Checking port %d for differences...\n", portIndex); | |
245 | ||
246 | sizeDifference = minimalSize - diffPortSize; | |
247 | ||
248 | if (sizeDifference < minimalDiff) | |
249 | { | |
250 | minimalDiffPort = diffPort; | |
251 | minimalDiff = sizeDifference; | |
252 | ||
253 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal difference 0x%x was found on port %d\n", | |
254 | minimalDiff, portIndex); | |
255 | } | |
256 | } | |
257 | } | |
258 | ||
259 | /* check if filtering is enabled on this port */ | |
260 | if ((port->featureStatus & IX_ETH_DB_FILTERING) != 0) | |
261 | { | |
262 | /* if minimalDiff is not MAX_PORT_SIZE minimalDiffPort points to the most similar port */ | |
263 | if (minimalDiff != MAX_PORT_SIZE) | |
264 | { | |
265 | baseTree = ixEthDBCloneMacTreeNode(minimalDiffPort->updateMethod.searchTree); | |
266 | DIFF_MAPS(query, port->dependencyPortMap , minimalDiffPort->dependencyPortMap); | |
267 | ||
268 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Found minimal diff, extending tree %d on query\n", | |
269 | minimalDiffPort->portID); | |
270 | } | |
271 | else /* .. otherwise no similar port was found, build tree from scratch */ | |
272 | { | |
273 | baseTree = NULL; | |
274 | ||
275 | COPY_DEPENDENCY_MAP(query, port->dependencyPortMap); | |
276 | ||
277 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) No similar diff, creating tree from query\n"); | |
278 | } | |
279 | ||
280 | IS_EMPTY_DEPENDENCY_MAP(result, query); | |
281 | ||
282 | if (!result) /* otherwise we don't need anything more on top of the cloned tree */ | |
283 | { | |
284 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding query tree to port %d\n", minPortIndex); | |
285 | ||
286 | /* build learning tree */ | |
287 | port->updateMethod.searchTree = ixEthDBQuery(baseTree, query, IX_ETH_DB_ALL_FILTERING_RECORDS, MAX_ELT_SIZE); | |
288 | } | |
289 | else | |
290 | { | |
291 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) Query is empty, assuming identical nearest tree\n"); | |
292 | ||
293 | port->updateMethod.searchTree = baseTree; | |
294 | } | |
295 | } | |
296 | else | |
297 | { | |
298 | /* filtering is not enabled, will download an empty tree */ | |
299 | if (port->updateMethod.searchTree != NULL) | |
300 | { | |
301 | ixEthDBFreeMacTreeNode(port->updateMethod.searchTree); | |
302 | } | |
303 | ||
304 | port->updateMethod.searchTree = NULL; | |
305 | } | |
306 | ||
307 | /* mark tree as valid */ | |
472d5460 | 308 | port->updateMethod.searchTreePendingWrite = true; |
ba94a1bb WD |
309 | } |
310 | else | |
311 | { | |
472d5460 | 312 | portsLeft = false; |
ba94a1bb WD |
313 | |
314 | IX_ETH_DB_UPDATE_TRACE("DB: (Update) No trees to create this round\n"); | |
315 | } | |
316 | } | |
317 | ||
318 | for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++) | |
319 | { | |
320 | PortInfo *updatePort = &ixEthDBPortInfo[portIndex]; | |
321 | ||
322 | if (updatePort->updateMethod.searchTreePendingWrite) | |
323 | { | |
324 | IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Starting procedure to upload new search tree (%snull) into NPE %d\n", | |
325 | updatePort->updateMethod.searchTree != NULL ? "not " : "", | |
326 | portIndex); | |
327 | ||
328 | updatePort->updateMethod.updateHandler(portIndex, IX_ETH_DB_FILTERING_RECORD); | |
329 | } | |
330 | } | |
331 | } | |
332 | ||
333 | /** | |
334 | * @brief standard NPE update handler | |
335 | * | |
336 | * @param portID id of the port to be updated | |
337 | * @param type record type to be pushed during this update | |
338 | * | |
339 | * The NPE update handler manages updating the NPE databases | |
340 | * given a certain record type. | |
341 | * | |
342 | * @internal | |
343 | */ | |
344 | IX_ETH_DB_PUBLIC | |
345 | IxEthDBStatus ixEthDBNPEUpdateHandler(IxEthDBPortId portID, IxEthDBRecordType type) | |
346 | { | |
347 | UINT32 epDelta, blockCount; | |
348 | IxNpeMhMessage message; | |
349 | UINT32 treeSize = 0; | |
350 | PortInfo *port = &ixEthDBPortInfo[portID]; | |
351 | ||
352 | /* size selection and type check */ | |
353 | if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD) | |
354 | { | |
355 | treeSize = FULL_ELT_BYTE_SIZE; | |
356 | } | |
357 | else if (type == IX_ETH_DB_FIREWALL_RECORD) | |
358 | { | |
359 | treeSize = FULL_FW_BYTE_SIZE; | |
360 | } | |
361 | else | |
362 | { | |
363 | return IX_ETH_DB_INVALID_ARG; | |
364 | } | |
365 | ||
366 | /* serialize tree into memory */ | |
367 | ixEthDBNPETreeWrite(type, treeSize, port->updateMethod.npeUpdateZone, port->updateMethod.searchTree, &epDelta, &blockCount); | |
368 | ||
369 | /* free internal copy */ | |
370 | if (port->updateMethod.searchTree != NULL) | |
371 | { | |
372 | ixEthDBFreeMacTreeNode(port->updateMethod.searchTree); | |
373 | } | |
374 | ||
375 | /* forget last used search tree */ | |
376 | port->updateMethod.searchTree = NULL; | |
472d5460 | 377 | port->updateMethod.searchTreePendingWrite = false; |
ba94a1bb WD |
378 | |
379 | /* dependending on the update type we do different things */ | |
380 | if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD) | |
381 | { | |
382 | IX_STATUS result; | |
383 | ||
384 | FILL_SETMACADDRESSDATABASE_MSG(message, IX_ETH_DB_PORT_ID_TO_NPE_LOGICAL_ID(portID), | |
385 | epDelta, blockCount, | |
386 | IX_OSAL_MMU_VIRT_TO_PHYS(port->updateMethod.npeUpdateZone)); | |
387 | ||
388 | IX_ETHDB_SEND_NPE_MSG(IX_ETH_DB_PORT_ID_TO_NPE(portID), message, result); | |
389 | ||
390 | if (result == IX_SUCCESS) | |
391 | { | |
392 | IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Finished downloading NPE tree on port %d\n", portID); | |
393 | } | |
394 | else | |
395 | { | |
472d5460 YS |
396 | ixEthDBPortInfo[portID].agingEnabled = false; |
397 | ixEthDBPortInfo[portID].updateMethod.updateEnabled = false; | |
398 | ixEthDBPortInfo[portID].updateMethod.userControlled = true; | |
ba94a1bb WD |
399 | |
400 | ERROR_LOG("EthDB: (PortUpdate) disabling aging and updates on port %d (assumed dead)\n", portID); | |
401 | ||
402 | ixEthDBDatabaseClear(portID, IX_ETH_DB_ALL_RECORD_TYPES); | |
403 | ||
404 | return IX_ETH_DB_FAIL; | |
405 | } | |
406 | ||
407 | return IX_ETH_DB_SUCCESS; | |
408 | } | |
409 | else if (type == IX_ETH_DB_FIREWALL_RECORD) | |
410 | { | |
411 | return ixEthDBFirewallUpdate(portID, port->updateMethod.npeUpdateZone, epDelta); | |
412 | } | |
413 | ||
414 | return IX_ETH_DB_INVALID_ARG; | |
415 | } | |
416 | ||
417 | /** | |
418 | * @brief queries the database for a set of records to be inserted into a given tree | |
419 | * | |
420 | * @param searchTree pointer to a tree where insertions will be performed; can be NULL | |
421 | * @param query set of ports that a database record must match to be inserted into the tree | |
422 | * | |
423 | * The query method browses through the database, extracts all the descriptors matching | |
424 | * the given query parameter and inserts them into the given learning tree. | |
425 | * Note that this is an append procedure, the given tree needs not to be empty. | |
426 | * A "descriptor matching the query" is a descriptor whose port id is in the query map. | |
427 | * If the given tree is empty (NULL) a new tree is created and returned. | |
428 | * | |
429 | * @return the tree root | |
430 | * | |
431 | * @internal | |
432 | */ | |
433 | IX_ETH_DB_PUBLIC | |
434 | MacTreeNode* ixEthDBQuery(MacTreeNode *searchTree, IxEthDBPortMap query, IxEthDBRecordType recordFilter, UINT32 maxEntries) | |
435 | { | |
436 | HashIterator iterator; | |
437 | UINT32 entryCount = 0; | |
438 | ||
439 | /* browse database */ | |
440 | BUSY_RETRY(ixEthDBInitHashIterator(&dbHashtable, &iterator)); | |
441 | ||
442 | while (IS_ITERATOR_VALID(&iterator)) | |
443 | { | |
444 | MacDescriptor *descriptor = (MacDescriptor *) iterator.node->data; | |
445 | ||
446 | IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) querying [%s]:%d on port map ... ", | |
447 | mac2string(descriptor->macAddress), | |
448 | descriptor->portID); | |
449 | ||
450 | if ((descriptor->type & recordFilter) != 0 | |
451 | && IS_PORT_INCLUDED(descriptor->portID, query)) | |
452 | { | |
453 | MacDescriptor *descriptorClone = ixEthDBCloneMacDescriptor(descriptor); | |
454 | ||
455 | IX_ETH_DB_UPDATE_TRACE("match\n"); | |
456 | ||
457 | if (descriptorClone != NULL) | |
458 | { | |
459 | /* add descriptor to tree */ | |
460 | searchTree = ixEthDBTreeInsert(searchTree, descriptorClone); | |
461 | ||
462 | entryCount++; | |
463 | } | |
464 | } | |
465 | else | |
466 | { | |
467 | IX_ETH_DB_UPDATE_TRACE("no match\n"); | |
468 | } | |
469 | ||
470 | if (entryCount < maxEntries) | |
471 | { | |
472 | /* advance to the next record */ | |
473 | BUSY_RETRY(ixEthDBIncrementHashIterator(&dbHashtable, &iterator)); | |
474 | } | |
475 | else | |
476 | { | |
477 | /* the NPE won't accept more entries so we can stop now */ | |
478 | ixEthDBReleaseHashIterator(&iterator); | |
479 | ||
480 | IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) number of elements reached maximum supported by port\n"); | |
481 | ||
482 | break; | |
483 | } | |
484 | } | |
485 | ||
486 | IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) query inserted %d records in the search tree\n", entryCount); | |
487 | ||
488 | return ixEthDBTreeRebalance(searchTree); | |
489 | } | |
490 | ||
491 | /** | |
492 | * @brief inserts a mac descriptor into an tree | |
493 | * | |
494 | * @param searchTree tree where the insertion is to be performed (may be NULL) | |
495 | * @param descriptor descriptor to insert into tree | |
496 | * | |
497 | * @return the tree root | |
498 | * | |
499 | * @internal | |
500 | */ | |
501 | IX_ETH_DB_PRIVATE | |
502 | MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor) | |
503 | { | |
504 | MacTreeNode *currentNode = searchTree; | |
505 | MacTreeNode *insertLocation = NULL; | |
506 | MacTreeNode *newNode; | |
507 | INT32 insertPosition = RIGHT; | |
508 | ||
509 | if (descriptor == NULL) | |
510 | { | |
511 | return searchTree; | |
512 | } | |
513 | ||
514 | /* create a new node */ | |
515 | newNode = ixEthDBAllocMacTreeNode(); | |
516 | ||
517 | if (newNode == NULL) | |
518 | { | |
519 | /* out of memory */ | |
520 | ERROR_LOG("Warning: ixEthDBAllocMacTreeNode returned NULL in file %s:%d (out of memory?)\n", __FILE__, __LINE__); | |
521 | ||
522 | ixEthDBFreeMacDescriptor(descriptor); | |
523 | ||
524 | return NULL; | |
525 | } | |
526 | ||
527 | /* populate node */ | |
528 | newNode->descriptor = descriptor; | |
529 | ||
530 | /* an empty initial tree is a special case */ | |
531 | if (searchTree == NULL) | |
532 | { | |
533 | return newNode; | |
534 | } | |
535 | ||
536 | /* get insertion location */ | |
537 | while (insertLocation == NULL) | |
538 | { | |
539 | MacTreeNode *nextNode; | |
540 | ||
541 | /* compare given key with current node key */ | |
542 | insertPosition = ixEthDBAddressCompare(descriptor->macAddress, currentNode->descriptor->macAddress); | |
543 | ||
544 | /* navigate down */ | |
545 | if (insertPosition == RIGHT) | |
546 | { | |
547 | nextNode = currentNode->right; | |
548 | } | |
549 | else if (insertPosition == LEFT) | |
550 | { | |
551 | nextNode = currentNode->left; | |
552 | } | |
553 | else | |
554 | { | |
555 | /* error, duplicate key */ | |
556 | ERROR_LOG("Warning: trapped insertion of a duplicate MAC address in an NPE search tree\n"); | |
557 | ||
558 | /* this will free the MAC descriptor as well */ | |
559 | ixEthDBFreeMacTreeNode(newNode); | |
560 | ||
561 | return searchTree; | |
562 | } | |
563 | ||
564 | /* when we can no longer dive through the tree we found the insertion place */ | |
565 | if (nextNode != NULL) | |
566 | { | |
567 | currentNode = nextNode; | |
568 | } | |
569 | else | |
570 | { | |
571 | insertLocation = currentNode; | |
572 | } | |
573 | } | |
574 | ||
575 | /* insert node */ | |
576 | if (insertPosition == RIGHT) | |
577 | { | |
578 | insertLocation->right = newNode; | |
579 | } | |
580 | else | |
581 | { | |
582 | insertLocation->left = newNode; | |
583 | } | |
584 | ||
585 | return searchTree; | |
586 | } | |
587 | ||
588 | /** | |
589 | * @brief balance a tree | |
590 | * | |
591 | * @param searchTree tree to balance | |
592 | * | |
593 | * Converts a tree into a balanced tree and returns the root of | |
594 | * the balanced tree. The resulting tree is <i>route balanced</i> | |
595 | * not <i>perfectly balanced</i>. This makes no difference to the | |
596 | * average tree search time which is the same in both cases, O(log2(n)). | |
597 | * | |
598 | * @return root of the balanced tree or NULL if there's no memory left | |
599 | * | |
600 | * @internal | |
601 | */ | |
602 | IX_ETH_DB_PRIVATE | |
603 | MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree) | |
604 | { | |
605 | MacTreeNode *pseudoRoot = ixEthDBAllocMacTreeNode(); | |
606 | UINT32 size; | |
607 | ||
608 | if (pseudoRoot == NULL) | |
609 | { | |
610 | /* out of memory */ | |
611 | return NULL; | |
612 | } | |
613 | ||
614 | pseudoRoot->right = searchTree; | |
615 | ||
616 | ixEthDBRebalanceTreeToVine(pseudoRoot, &size); | |
617 | ixEthDBRebalanceVineToTree(pseudoRoot, size); | |
618 | ||
619 | searchTree = pseudoRoot->right; | |
620 | ||
621 | /* remove pseudoRoot right branch, otherwise it will free the entire tree */ | |
622 | pseudoRoot->right = NULL; | |
623 | ||
624 | ixEthDBFreeMacTreeNode(pseudoRoot); | |
625 | ||
626 | return searchTree; | |
627 | } | |
628 | ||
629 | /** | |
630 | * @brief converts a tree into a vine | |
631 | * | |
632 | * @param root root of tree to convert | |
633 | * @param size depth of vine (equal to the number of nodes in the tree) | |
634 | * | |
635 | * @internal | |
636 | */ | |
637 | IX_ETH_DB_PRIVATE | |
638 | void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size) | |
639 | { | |
640 | MacTreeNode *vineTail = root; | |
641 | MacTreeNode *remainder = vineTail->right; | |
642 | MacTreeNode *tempPtr; | |
643 | ||
644 | *size = 0; | |
645 | ||
646 | while (remainder != NULL) | |
647 | { | |
648 | if (remainder->left == NULL) | |
649 | { | |
650 | /* move tail down one */ | |
651 | vineTail = remainder; | |
652 | remainder = remainder->right; | |
653 | (*size)++; | |
654 | } | |
655 | else | |
656 | { | |
657 | /* rotate around remainder */ | |
658 | tempPtr = remainder->left; | |
659 | remainder->left = tempPtr->right; | |
660 | tempPtr->right = remainder; | |
661 | remainder = tempPtr; | |
662 | vineTail->right = tempPtr; | |
663 | } | |
664 | } | |
665 | } | |
666 | ||
667 | /** | |
668 | * @brief converts a vine into a balanced tree | |
669 | * | |
670 | * @param root vine to convert | |
671 | * @param size depth of vine | |
672 | * | |
673 | * @internal | |
674 | */ | |
675 | IX_ETH_DB_PRIVATE | |
676 | void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size) | |
677 | { | |
678 | UINT32 leafCount = size + 1 - (1 << ixEthDBRebalanceLog2Floor(size + 1)); | |
679 | ||
680 | ixEthDBRebalanceCompression(root, leafCount); | |
681 | ||
682 | size = size - leafCount; | |
683 | ||
684 | while (size > 1) | |
685 | { | |
686 | ixEthDBRebalanceCompression(root, size / 2); | |
687 | ||
688 | size /= 2; | |
689 | } | |
690 | } | |
691 | ||
692 | /** | |
693 | * @brief compresses a vine/tree stage into a more balanced vine/tree | |
694 | * | |
695 | * @param root root of the tree to compress | |
696 | * @param count number of "spine" nodes | |
697 | * | |
698 | * @internal | |
699 | */ | |
700 | IX_ETH_DB_PRIVATE | |
701 | void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count) | |
702 | { | |
703 | MacTreeNode *scanner = root; | |
704 | MacTreeNode *child; | |
705 | UINT32 local_index; | |
706 | ||
707 | for (local_index = 0 ; local_index < count ; local_index++) | |
708 | { | |
709 | child = scanner->right; | |
710 | scanner->right = child->right; | |
711 | scanner = scanner->right; | |
712 | child->right = scanner->left; | |
713 | scanner->left = child; | |
714 | } | |
715 | } | |
716 | ||
717 | /** | |
718 | * @brief computes |_log2(x)_| (a.k.a. floor(log2(x))) | |
719 | * | |
720 | * @param x number to compute |_log2(x)_| for | |
721 | * | |
722 | * @return |_log2(x)_| | |
723 | * | |
724 | * @internal | |
725 | */ | |
726 | IX_ETH_DB_PRIVATE | |
727 | UINT32 ixEthDBRebalanceLog2Floor(UINT32 x) | |
728 | { | |
729 | UINT32 log = 0; | |
730 | UINT32 val = 1; | |
731 | ||
732 | while (val < x) | |
733 | { | |
734 | log++; | |
735 | val <<= 1; | |
736 | } | |
737 | ||
738 | return val == x ? log : log - 1; | |
739 | } | |
740 |