IxEthDBPortUpdate.c 23 KB

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