IxEthDBPortUpdate.c 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716
  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. * SPDX-License-Identifier: BSD-3-Clause
  17. * @par
  18. * -- End of Copyright Notice --
  19. */
  20. #include "IxEthDB_p.h"
  21. /* forward prototype declarations */
  22. IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor);
  23. IX_ETH_DB_PRIVATE void ixEthDBCreateTrees(IxEthDBPortMap updatePorts);
  24. IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree);
  25. IX_ETH_DB_PRIVATE void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size);
  26. IX_ETH_DB_PRIVATE void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size);
  27. IX_ETH_DB_PRIVATE void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count);
  28. IX_ETH_DB_PRIVATE UINT32 ixEthDBRebalanceLog2Floor(UINT32 x);
  29. extern HashTable dbHashtable;
  30. /**
  31. * @brief register types requiring automatic updates
  32. *
  33. * @param typeArray array indexed on record types, each
  34. * element indicating whether the record type requires an
  35. * automatic update (true) or not (false)
  36. *
  37. * Automatic updates are done for registered record types
  38. * upon adding, updating (that is, updating the record portID)
  39. * and removing records. Whenever an automatic update is triggered
  40. * the appropriate ports will be provided with new database
  41. * information.
  42. *
  43. * It is assumed that the typeArray parameter is allocated large
  44. * enough to hold all the user defined types. Also, the type
  45. * array should be initialized to false as this function only
  46. * caters for types which do require automatic updates.
  47. *
  48. * Note that this function should be called by the component
  49. * initialization function.
  50. *
  51. * @return number of record types registered for automatic
  52. * updates
  53. *
  54. * @internal
  55. */
  56. IX_ETH_DB_PUBLIC
  57. UINT32 ixEthDBUpdateTypeRegister(BOOL *typeArray)
  58. {
  59. typeArray[IX_ETH_DB_FILTERING_RECORD] = true;
  60. typeArray[IX_ETH_DB_FILTERING_VLAN_RECORD] = true;
  61. return 2;
  62. }
  63. /**
  64. * @brief computes dependencies and triggers port learning tree updates
  65. *
  66. * @param triggerPorts port map consisting in the ports which triggered the update
  67. *
  68. * This function browses through all the ports and determines how to waterfall the update
  69. * event from the trigger ports to all other ports depending on them.
  70. *
  71. * Once the list of ports to be updated is determined this function
  72. * calls @ref ixEthDBCreateTrees.
  73. *
  74. * @internal
  75. */
  76. IX_ETH_DB_PUBLIC
  77. void ixEthDBUpdatePortLearningTrees(IxEthDBPortMap triggerPorts)
  78. {
  79. IxEthDBPortMap updatePorts;
  80. UINT32 portIndex;
  81. ixEthDBUpdateLock();
  82. SET_EMPTY_DEPENDENCY_MAP(updatePorts);
  83. for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
  84. {
  85. PortInfo *port = &ixEthDBPortInfo[portIndex];
  86. BOOL mapsCollide;
  87. MAPS_COLLIDE(mapsCollide, triggerPorts, port->dependencyPortMap);
  88. if (mapsCollide /* do triggers influence this port? */
  89. && !IS_PORT_INCLUDED(portIndex, updatePorts) /* and it's not already in the update list */
  90. && port->updateMethod.updateEnabled) /* and we're allowed to update it */
  91. {
  92. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding port %d to update set\n", portIndex);
  93. JOIN_PORT_TO_MAP(updatePorts, portIndex);
  94. }
  95. else
  96. {
  97. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Didn't add port %d to update set, reasons follow:\n", portIndex);
  98. if (!mapsCollide)
  99. {
  100. IX_ETH_DB_UPDATE_TRACE("\tMaps don't collide on port %d\n", portIndex);
  101. }
  102. if (IS_PORT_INCLUDED(portIndex, updatePorts))
  103. {
  104. IX_ETH_DB_UPDATE_TRACE("\tPort %d is already in the update set\n", portIndex);
  105. }
  106. if (!port->updateMethod.updateEnabled)
  107. {
  108. IX_ETH_DB_UPDATE_TRACE("\tPort %d doesn't have updateEnabled set\n", portIndex);
  109. }
  110. }
  111. }
  112. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Updating port set\n");
  113. ixEthDBCreateTrees(updatePorts);
  114. ixEthDBUpdateUnlock();
  115. }
  116. /**
  117. * @brief creates learning trees and calls the port update handlers
  118. *
  119. * @param updatePorts set of ports in need of learning trees
  120. *
  121. * This function determines the optimal method of creating learning
  122. * trees using a minimal number of database queries, keeping in mind
  123. * that different ports can either use the same learning trees or they
  124. * can partially share them. The actual tree building routine is
  125. * @ref ixEthDBQuery.
  126. *
  127. * @internal
  128. */
  129. IX_ETH_DB_PRIVATE
  130. void ixEthDBCreateTrees(IxEthDBPortMap updatePorts)
  131. {
  132. UINT32 portIndex;
  133. BOOL result;
  134. BOOL portsLeft = true;
  135. while (portsLeft)
  136. {
  137. /* get port with minimal dependency map and NULL search tree */
  138. UINT32 minPortIndex = MAX_PORT_SIZE;
  139. UINT32 minimalSize = MAX_PORT_SIZE;
  140. for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
  141. {
  142. UINT32 size;
  143. PortInfo *port = &ixEthDBPortInfo[portIndex];
  144. /* generate trees only for ports that need them */
  145. if (!port->updateMethod.searchTreePendingWrite && IS_PORT_INCLUDED(portIndex, updatePorts))
  146. {
  147. GET_MAP_SIZE(port->dependencyPortMap, size);
  148. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Dependency map for port %d: size %d\n",
  149. portIndex, size);
  150. if (size < minimalSize)
  151. {
  152. minPortIndex = portIndex;
  153. minimalSize = size;
  154. }
  155. }
  156. else
  157. {
  158. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Skipped port %d from tree diff (%s)\n", portIndex,
  159. port->updateMethod.searchTreePendingWrite ? "pending write access" : "ignored by query");
  160. }
  161. }
  162. /* if a port was found than minimalSize is not MAX_PORT_SIZE */
  163. if (minimalSize != MAX_PORT_SIZE)
  164. {
  165. /* minPortIndex is the port we seek */
  166. PortInfo *port = &ixEthDBPortInfo[minPortIndex];
  167. IxEthDBPortMap query;
  168. MacTreeNode *baseTree;
  169. /* now try to find a port with minimal map difference */
  170. PortInfo *minimalDiffPort = NULL;
  171. UINT32 minimalDiff = MAX_PORT_SIZE;
  172. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal size port is %d\n", minPortIndex);
  173. for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
  174. {
  175. PortInfo *diffPort = &ixEthDBPortInfo[portIndex];
  176. BOOL mapIsSubset;
  177. IS_MAP_SUBSET(mapIsSubset, diffPort->dependencyPortMap, port->dependencyPortMap);
  178. if (portIndex != minPortIndex
  179. && diffPort->updateMethod.searchTree != NULL
  180. && mapIsSubset)
  181. {
  182. /* compute size and pick only minimal size difference */
  183. UINT32 diffPortSize;
  184. UINT32 sizeDifference;
  185. GET_MAP_SIZE(diffPort->dependencyPortMap, diffPortSize);
  186. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Checking port %d for differences...\n", portIndex);
  187. sizeDifference = minimalSize - diffPortSize;
  188. if (sizeDifference < minimalDiff)
  189. {
  190. minimalDiffPort = diffPort;
  191. minimalDiff = sizeDifference;
  192. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal difference 0x%x was found on port %d\n",
  193. minimalDiff, portIndex);
  194. }
  195. }
  196. }
  197. /* check if filtering is enabled on this port */
  198. if ((port->featureStatus & IX_ETH_DB_FILTERING) != 0)
  199. {
  200. /* if minimalDiff is not MAX_PORT_SIZE minimalDiffPort points to the most similar port */
  201. if (minimalDiff != MAX_PORT_SIZE)
  202. {
  203. baseTree = ixEthDBCloneMacTreeNode(minimalDiffPort->updateMethod.searchTree);
  204. DIFF_MAPS(query, port->dependencyPortMap , minimalDiffPort->dependencyPortMap);
  205. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Found minimal diff, extending tree %d on query\n",
  206. minimalDiffPort->portID);
  207. }
  208. else /* .. otherwise no similar port was found, build tree from scratch */
  209. {
  210. baseTree = NULL;
  211. COPY_DEPENDENCY_MAP(query, port->dependencyPortMap);
  212. IX_ETH_DB_UPDATE_TRACE("DB: (Update) No similar diff, creating tree from query\n");
  213. }
  214. IS_EMPTY_DEPENDENCY_MAP(result, query);
  215. if (!result) /* otherwise we don't need anything more on top of the cloned tree */
  216. {
  217. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding query tree to port %d\n", minPortIndex);
  218. /* build learning tree */
  219. port->updateMethod.searchTree = ixEthDBQuery(baseTree, query, IX_ETH_DB_ALL_FILTERING_RECORDS, MAX_ELT_SIZE);
  220. }
  221. else
  222. {
  223. IX_ETH_DB_UPDATE_TRACE("DB: (Update) Query is empty, assuming identical nearest tree\n");
  224. port->updateMethod.searchTree = baseTree;
  225. }
  226. }
  227. else
  228. {
  229. /* filtering is not enabled, will download an empty tree */
  230. if (port->updateMethod.searchTree != NULL)
  231. {
  232. ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
  233. }
  234. port->updateMethod.searchTree = NULL;
  235. }
  236. /* mark tree as valid */
  237. port->updateMethod.searchTreePendingWrite = true;
  238. }
  239. else
  240. {
  241. portsLeft = false;
  242. IX_ETH_DB_UPDATE_TRACE("DB: (Update) No trees to create this round\n");
  243. }
  244. }
  245. for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
  246. {
  247. PortInfo *updatePort = &ixEthDBPortInfo[portIndex];
  248. if (updatePort->updateMethod.searchTreePendingWrite)
  249. {
  250. IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Starting procedure to upload new search tree (%snull) into NPE %d\n",
  251. updatePort->updateMethod.searchTree != NULL ? "not " : "",
  252. portIndex);
  253. updatePort->updateMethod.updateHandler(portIndex, IX_ETH_DB_FILTERING_RECORD);
  254. }
  255. }
  256. }
  257. /**
  258. * @brief standard NPE update handler
  259. *
  260. * @param portID id of the port to be updated
  261. * @param type record type to be pushed during this update
  262. *
  263. * The NPE update handler manages updating the NPE databases
  264. * given a certain record type.
  265. *
  266. * @internal
  267. */
  268. IX_ETH_DB_PUBLIC
  269. IxEthDBStatus ixEthDBNPEUpdateHandler(IxEthDBPortId portID, IxEthDBRecordType type)
  270. {
  271. UINT32 epDelta, blockCount;
  272. IxNpeMhMessage message;
  273. UINT32 treeSize = 0;
  274. PortInfo *port = &ixEthDBPortInfo[portID];
  275. /* size selection and type check */
  276. if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
  277. {
  278. treeSize = FULL_ELT_BYTE_SIZE;
  279. }
  280. else if (type == IX_ETH_DB_FIREWALL_RECORD)
  281. {
  282. treeSize = FULL_FW_BYTE_SIZE;
  283. }
  284. else
  285. {
  286. return IX_ETH_DB_INVALID_ARG;
  287. }
  288. /* serialize tree into memory */
  289. ixEthDBNPETreeWrite(type, treeSize, port->updateMethod.npeUpdateZone, port->updateMethod.searchTree, &epDelta, &blockCount);
  290. /* free internal copy */
  291. if (port->updateMethod.searchTree != NULL)
  292. {
  293. ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
  294. }
  295. /* forget last used search tree */
  296. port->updateMethod.searchTree = NULL;
  297. port->updateMethod.searchTreePendingWrite = false;
  298. /* dependending on the update type we do different things */
  299. if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
  300. {
  301. IX_STATUS result;
  302. FILL_SETMACADDRESSDATABASE_MSG(message, IX_ETH_DB_PORT_ID_TO_NPE_LOGICAL_ID(portID),
  303. epDelta, blockCount,
  304. IX_OSAL_MMU_VIRT_TO_PHYS(port->updateMethod.npeUpdateZone));
  305. IX_ETHDB_SEND_NPE_MSG(IX_ETH_DB_PORT_ID_TO_NPE(portID), message, result);
  306. if (result == IX_SUCCESS)
  307. {
  308. IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Finished downloading NPE tree on port %d\n", portID);
  309. }
  310. else
  311. {
  312. ixEthDBPortInfo[portID].agingEnabled = false;
  313. ixEthDBPortInfo[portID].updateMethod.updateEnabled = false;
  314. ixEthDBPortInfo[portID].updateMethod.userControlled = true;
  315. ERROR_LOG("EthDB: (PortUpdate) disabling aging and updates on port %d (assumed dead)\n", portID);
  316. ixEthDBDatabaseClear(portID, IX_ETH_DB_ALL_RECORD_TYPES);
  317. return IX_ETH_DB_FAIL;
  318. }
  319. return IX_ETH_DB_SUCCESS;
  320. }
  321. else if (type == IX_ETH_DB_FIREWALL_RECORD)
  322. {
  323. return ixEthDBFirewallUpdate(portID, port->updateMethod.npeUpdateZone, epDelta);
  324. }
  325. return IX_ETH_DB_INVALID_ARG;
  326. }
  327. /**
  328. * @brief queries the database for a set of records to be inserted into a given tree
  329. *
  330. * @param searchTree pointer to a tree where insertions will be performed; can be NULL
  331. * @param query set of ports that a database record must match to be inserted into the tree
  332. *
  333. * The query method browses through the database, extracts all the descriptors matching
  334. * the given query parameter and inserts them into the given learning tree.
  335. * Note that this is an append procedure, the given tree needs not to be empty.
  336. * A "descriptor matching the query" is a descriptor whose port id is in the query map.
  337. * If the given tree is empty (NULL) a new tree is created and returned.
  338. *
  339. * @return the tree root
  340. *
  341. * @internal
  342. */
  343. IX_ETH_DB_PUBLIC
  344. MacTreeNode* ixEthDBQuery(MacTreeNode *searchTree, IxEthDBPortMap query, IxEthDBRecordType recordFilter, UINT32 maxEntries)
  345. {
  346. HashIterator iterator;
  347. UINT32 entryCount = 0;
  348. /* browse database */
  349. BUSY_RETRY(ixEthDBInitHashIterator(&dbHashtable, &iterator));
  350. while (IS_ITERATOR_VALID(&iterator))
  351. {
  352. MacDescriptor *descriptor = (MacDescriptor *) iterator.node->data;
  353. IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) querying [%s]:%d on port map ... ",
  354. mac2string(descriptor->macAddress),
  355. descriptor->portID);
  356. if ((descriptor->type & recordFilter) != 0
  357. && IS_PORT_INCLUDED(descriptor->portID, query))
  358. {
  359. MacDescriptor *descriptorClone = ixEthDBCloneMacDescriptor(descriptor);
  360. IX_ETH_DB_UPDATE_TRACE("match\n");
  361. if (descriptorClone != NULL)
  362. {
  363. /* add descriptor to tree */
  364. searchTree = ixEthDBTreeInsert(searchTree, descriptorClone);
  365. entryCount++;
  366. }
  367. }
  368. else
  369. {
  370. IX_ETH_DB_UPDATE_TRACE("no match\n");
  371. }
  372. if (entryCount < maxEntries)
  373. {
  374. /* advance to the next record */
  375. BUSY_RETRY(ixEthDBIncrementHashIterator(&dbHashtable, &iterator));
  376. }
  377. else
  378. {
  379. /* the NPE won't accept more entries so we can stop now */
  380. ixEthDBReleaseHashIterator(&iterator);
  381. IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) number of elements reached maximum supported by port\n");
  382. break;
  383. }
  384. }
  385. IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) query inserted %d records in the search tree\n", entryCount);
  386. return ixEthDBTreeRebalance(searchTree);
  387. }
  388. /**
  389. * @brief inserts a mac descriptor into an tree
  390. *
  391. * @param searchTree tree where the insertion is to be performed (may be NULL)
  392. * @param descriptor descriptor to insert into tree
  393. *
  394. * @return the tree root
  395. *
  396. * @internal
  397. */
  398. IX_ETH_DB_PRIVATE
  399. MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor)
  400. {
  401. MacTreeNode *currentNode = searchTree;
  402. MacTreeNode *insertLocation = NULL;
  403. MacTreeNode *newNode;
  404. INT32 insertPosition = RIGHT;
  405. if (descriptor == NULL)
  406. {
  407. return searchTree;
  408. }
  409. /* create a new node */
  410. newNode = ixEthDBAllocMacTreeNode();
  411. if (newNode == NULL)
  412. {
  413. /* out of memory */
  414. ERROR_LOG("Warning: ixEthDBAllocMacTreeNode returned NULL in file %s:%d (out of memory?)\n", __FILE__, __LINE__);
  415. ixEthDBFreeMacDescriptor(descriptor);
  416. return NULL;
  417. }
  418. /* populate node */
  419. newNode->descriptor = descriptor;
  420. /* an empty initial tree is a special case */
  421. if (searchTree == NULL)
  422. {
  423. return newNode;
  424. }
  425. /* get insertion location */
  426. while (insertLocation == NULL)
  427. {
  428. MacTreeNode *nextNode;
  429. /* compare given key with current node key */
  430. insertPosition = ixEthDBAddressCompare(descriptor->macAddress, currentNode->descriptor->macAddress);
  431. /* navigate down */
  432. if (insertPosition == RIGHT)
  433. {
  434. nextNode = currentNode->right;
  435. }
  436. else if (insertPosition == LEFT)
  437. {
  438. nextNode = currentNode->left;
  439. }
  440. else
  441. {
  442. /* error, duplicate key */
  443. ERROR_LOG("Warning: trapped insertion of a duplicate MAC address in an NPE search tree\n");
  444. /* this will free the MAC descriptor as well */
  445. ixEthDBFreeMacTreeNode(newNode);
  446. return searchTree;
  447. }
  448. /* when we can no longer dive through the tree we found the insertion place */
  449. if (nextNode != NULL)
  450. {
  451. currentNode = nextNode;
  452. }
  453. else
  454. {
  455. insertLocation = currentNode;
  456. }
  457. }
  458. /* insert node */
  459. if (insertPosition == RIGHT)
  460. {
  461. insertLocation->right = newNode;
  462. }
  463. else
  464. {
  465. insertLocation->left = newNode;
  466. }
  467. return searchTree;
  468. }
  469. /**
  470. * @brief balance a tree
  471. *
  472. * @param searchTree tree to balance
  473. *
  474. * Converts a tree into a balanced tree and returns the root of
  475. * the balanced tree. The resulting tree is <i>route balanced</i>
  476. * not <i>perfectly balanced</i>. This makes no difference to the
  477. * average tree search time which is the same in both cases, O(log2(n)).
  478. *
  479. * @return root of the balanced tree or NULL if there's no memory left
  480. *
  481. * @internal
  482. */
  483. IX_ETH_DB_PRIVATE
  484. MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree)
  485. {
  486. MacTreeNode *pseudoRoot = ixEthDBAllocMacTreeNode();
  487. UINT32 size;
  488. if (pseudoRoot == NULL)
  489. {
  490. /* out of memory */
  491. return NULL;
  492. }
  493. pseudoRoot->right = searchTree;
  494. ixEthDBRebalanceTreeToVine(pseudoRoot, &size);
  495. ixEthDBRebalanceVineToTree(pseudoRoot, size);
  496. searchTree = pseudoRoot->right;
  497. /* remove pseudoRoot right branch, otherwise it will free the entire tree */
  498. pseudoRoot->right = NULL;
  499. ixEthDBFreeMacTreeNode(pseudoRoot);
  500. return searchTree;
  501. }
  502. /**
  503. * @brief converts a tree into a vine
  504. *
  505. * @param root root of tree to convert
  506. * @param size depth of vine (equal to the number of nodes in the tree)
  507. *
  508. * @internal
  509. */
  510. IX_ETH_DB_PRIVATE
  511. void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size)
  512. {
  513. MacTreeNode *vineTail = root;
  514. MacTreeNode *remainder = vineTail->right;
  515. MacTreeNode *tempPtr;
  516. *size = 0;
  517. while (remainder != NULL)
  518. {
  519. if (remainder->left == NULL)
  520. {
  521. /* move tail down one */
  522. vineTail = remainder;
  523. remainder = remainder->right;
  524. (*size)++;
  525. }
  526. else
  527. {
  528. /* rotate around remainder */
  529. tempPtr = remainder->left;
  530. remainder->left = tempPtr->right;
  531. tempPtr->right = remainder;
  532. remainder = tempPtr;
  533. vineTail->right = tempPtr;
  534. }
  535. }
  536. }
  537. /**
  538. * @brief converts a vine into a balanced tree
  539. *
  540. * @param root vine to convert
  541. * @param size depth of vine
  542. *
  543. * @internal
  544. */
  545. IX_ETH_DB_PRIVATE
  546. void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size)
  547. {
  548. UINT32 leafCount = size + 1 - (1 << ixEthDBRebalanceLog2Floor(size + 1));
  549. ixEthDBRebalanceCompression(root, leafCount);
  550. size = size - leafCount;
  551. while (size > 1)
  552. {
  553. ixEthDBRebalanceCompression(root, size / 2);
  554. size /= 2;
  555. }
  556. }
  557. /**
  558. * @brief compresses a vine/tree stage into a more balanced vine/tree
  559. *
  560. * @param root root of the tree to compress
  561. * @param count number of "spine" nodes
  562. *
  563. * @internal
  564. */
  565. IX_ETH_DB_PRIVATE
  566. void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count)
  567. {
  568. MacTreeNode *scanner = root;
  569. MacTreeNode *child;
  570. UINT32 local_index;
  571. for (local_index = 0 ; local_index < count ; local_index++)
  572. {
  573. child = scanner->right;
  574. scanner->right = child->right;
  575. scanner = scanner->right;
  576. child->right = scanner->left;
  577. scanner->left = child;
  578. }
  579. }
  580. /**
  581. * @brief computes |_log2(x)_| (a.k.a. floor(log2(x)))
  582. *
  583. * @param x number to compute |_log2(x)_| for
  584. *
  585. * @return |_log2(x)_|
  586. *
  587. * @internal
  588. */
  589. IX_ETH_DB_PRIVATE
  590. UINT32 ixEthDBRebalanceLog2Floor(UINT32 x)
  591. {
  592. UINT32 log = 0;
  593. UINT32 val = 1;
  594. while (val < x)
  595. {
  596. log++;
  597. val <<= 1;
  598. }
  599. return val == x ? log : log - 1;
  600. }