blob: cdf114bfc4311002578ce34d8d18fc00cafe77c7 [file] [log] [blame]
Wolfgang Denkba94a1b2006-05-30 15:56:48 +02001/**
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 */
48IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor);
49IX_ETH_DB_PRIVATE void ixEthDBCreateTrees(IxEthDBPortMap updatePorts);
50IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree);
51IX_ETH_DB_PRIVATE void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size);
52IX_ETH_DB_PRIVATE void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size);
53IX_ETH_DB_PRIVATE void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count);
54IX_ETH_DB_PRIVATE UINT32 ixEthDBRebalanceLog2Floor(UINT32 x);
55
56extern 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
63 * automatic update (TRUE) or not (FALSE)
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
73 * array should be initialized to FALSE as this function only
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 */
84IX_ETH_DB_PUBLIC
85UINT32 ixEthDBUpdateTypeRegister(BOOL *typeArray)
86{
87 typeArray[IX_ETH_DB_FILTERING_RECORD] = TRUE;
88 typeArray[IX_ETH_DB_FILTERING_VLAN_RECORD] = TRUE;
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 */
106IX_ETH_DB_PUBLIC
107void 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 */
172IX_ETH_DB_PRIVATE
173void ixEthDBCreateTrees(IxEthDBPortMap updatePorts)
174{
175 UINT32 portIndex;
176 BOOL result;
177 BOOL portsLeft = TRUE;
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 */
308 port->updateMethod.searchTreePendingWrite = TRUE;
309 }
310 else
311 {
312 portsLeft = FALSE;
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 */
344IX_ETH_DB_PUBLIC
345IxEthDBStatus 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;
377 port->updateMethod.searchTreePendingWrite = FALSE;
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 {
396 ixEthDBPortInfo[portID].agingEnabled = FALSE;
397 ixEthDBPortInfo[portID].updateMethod.updateEnabled = FALSE;
398 ixEthDBPortInfo[portID].updateMethod.userControlled = TRUE;
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 */
433IX_ETH_DB_PUBLIC
434MacTreeNode* 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 */
501IX_ETH_DB_PRIVATE
502MacTreeNode* 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 */
602IX_ETH_DB_PRIVATE
603MacTreeNode* 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 */
637IX_ETH_DB_PRIVATE
638void 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 */
675IX_ETH_DB_PRIVATE
676void 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 */
700IX_ETH_DB_PRIVATE
701void 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 */
726IX_ETH_DB_PRIVATE
727UINT32 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