Changeset 6539bea in rtems for testsuites


Ignore:
Timestamp:
06/29/18 18:00:28 (6 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
5, master
Children:
877aeab
Parents:
cf811a4
git-author:
Sebastian Huber <sebastian.huber@…> (06/29/18 18:00:28)
git-committer:
Sebastian Huber <sebastian.huber@…> (07/16/18 05:22:06)
Message:

score: Add postorder tree iteration support

Update #3465.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • testsuites/sptests/sprbtree01/init.c

    rcf811a4 r6539bea  
    17571757}
    17581758
     1759typedef struct {
     1760  rtems_rbtree_node *parent;
     1761  rtems_rbtree_node *left;
     1762  rtems_rbtree_node *right;
     1763} postorder_node_description;
     1764
     1765static const postorder_node_description postorder_tree_1[] = {
     1766  { NULL, NULL, NULL }
     1767};
     1768
     1769/*
     1770 *   TN_1
     1771 *   /
     1772 * TN_0
     1773 */
     1774static const postorder_node_description postorder_tree_2[] = {
     1775  { TN( 1 ), NULL, NULL },
     1776  { NULL, TN( 0 ), NULL }
     1777};
     1778
     1779/*
     1780 * TN_1
     1781 *     \
     1782 *    TN_0
     1783 */
     1784static const postorder_node_description postorder_tree_3[] = {
     1785  { TN( 1 ), NULL, NULL },
     1786  { NULL, NULL, TN( 0 ) }
     1787};
     1788
     1789/*
     1790 *    TN_2
     1791 *   /    \
     1792 * TN_0  TN_1
     1793 */
     1794static const postorder_node_description postorder_tree_4[] = {
     1795  { TN( 2 ), NULL, NULL },
     1796  { TN( 2 ), NULL, NULL },
     1797  { NULL, TN( 0 ), TN( 1 ) }
     1798};
     1799
     1800/*
     1801 *       TN_3
     1802 *      /
     1803 *    TN_2
     1804 *   /    \
     1805 * TN_0  TN_1
     1806 */
     1807static const postorder_node_description postorder_tree_5[] = {
     1808  { TN( 2 ), NULL, NULL },
     1809  { TN( 2 ), NULL, NULL },
     1810  { TN( 3 ), TN( 0 ), TN( 1 ) },
     1811  { NULL, TN( 2 ), NULL }
     1812};
     1813
     1814/*
     1815 *      TN_10
     1816 *     /      \
     1817 *    TN_6     TN_9
     1818 *   /    \        \
     1819 * TN_0  TN_5       TN_8
     1820 *      /    \      /
     1821 *    TN_2   TN_4  TN_7
     1822 *   /      /
     1823 * TN_1   TN_3
     1824 */
     1825static const postorder_node_description postorder_tree_6[] = {
     1826  { TN( 6 ), NULL, NULL },
     1827  { TN( 2 ), NULL, NULL },
     1828  { TN( 5 ), TN( 1 ), NULL },
     1829  { TN( 4 ), NULL, NULL },
     1830  { TN( 5 ), TN( 3 ), NULL },
     1831  { TN( 6 ), TN( 2 ), TN( 4 ) },
     1832  { TN( 10 ), TN( 0 ), TN( 5 ) },
     1833  { TN( 8 ), NULL, NULL },
     1834  { TN( 9 ), TN( 7 ), NULL },
     1835  { TN( 10 ), NULL, TN( 8 ) },
     1836  { NULL, TN( 6 ), TN( 9 ) }
     1837};
     1838
     1839/*
     1840 *      TN_5
     1841 *     /
     1842 *    TN_4
     1843 *   /
     1844 * TN_3
     1845 *     \
     1846 *    TN_2
     1847 *        \
     1848 *       TN_1
     1849 *      /
     1850 *    TN_0
     1851 */
     1852static const postorder_node_description postorder_tree_7[] = {
     1853  { TN( 1 ), NULL, NULL },
     1854  { TN( 2 ), TN( 0 ), NULL },
     1855  { TN( 3 ), NULL, TN( 1 ) },
     1856  { TN( 4 ), NULL, TN( 2 ) },
     1857  { TN( 5 ), TN( 3 ), NULL },
     1858  { NULL, TN( 0 ), NULL }
     1859};
     1860
     1861typedef struct {
     1862  const postorder_node_description *tree;
     1863  size_t                            node_count;
     1864} postorder_tree;
     1865
     1866#define POSTORDER_TREE( idx ) \
     1867  { postorder_tree_##idx, RTEMS_ARRAY_SIZE( postorder_tree_##idx ) }
     1868
     1869static const postorder_tree postorder_trees[] = {
     1870  { NULL, 0 },
     1871  POSTORDER_TREE( 1 ),
     1872  POSTORDER_TREE( 2 ),
     1873  POSTORDER_TREE( 3 ),
     1874  POSTORDER_TREE( 4 ),
     1875  POSTORDER_TREE( 5 ),
     1876  POSTORDER_TREE( 6 ),
     1877  POSTORDER_TREE( 7 )
     1878};
     1879
     1880static void postorder_tree_init(
     1881  RBTree_Control       *tree,
     1882  const postorder_tree *pt
     1883)
     1884{
     1885  size_t i;
     1886
     1887  memset( node_array, 0, pt->node_count * sizeof( node_array[ 0 ] ) );
     1888
     1889  if ( pt->node_count > 0 ) {
     1890    _RBTree_Initialize_node( TN( 0 ) );
     1891    _RBTree_Initialize_one( tree, TN( 0 ) );
     1892  } else {
     1893    _RBTree_Initialize_empty( tree );
     1894  }
     1895
     1896  for ( i = 0; i < pt->node_count; ++i ) {
     1897    const postorder_node_description *pnd;
     1898
     1899    pnd = &pt->tree[ i ];
     1900    RB_PARENT( TN( i ), Node) = pnd->parent;
     1901    RB_LEFT( TN( i ), Node) = pnd->left;
     1902    RB_RIGHT( TN( i ), Node) = pnd->right;
     1903  }
     1904}
     1905
     1906static void postorder_tree_check(
     1907  RBTree_Control       *tree,
     1908  const postorder_tree *pt
     1909)
     1910{
     1911  test_node *node;
     1912  size_t i;
     1913
     1914  node = _RBTree_Postorder_first( tree, offsetof( test_node, Node ) );
     1915
     1916  for ( i = 0; i < pt->node_count; ++i ) {
     1917    rtems_test_assert( node == &node_array[ i ] );
     1918    node = _RBTree_Postorder_next( &node->Node, offsetof( test_node, Node ) );
     1919  }
     1920
     1921  rtems_test_assert( node == NULL );
     1922}
     1923
     1924static void test_rbtree_postorder( void )
     1925{
     1926  RBTree_Control tree;
     1927  size_t         i;
     1928
     1929  puts( "INIT - Postorder operations" );
     1930
     1931  for ( i = 0; i < RTEMS_ARRAY_SIZE( postorder_trees ); ++i ) {
     1932    const postorder_tree *pt;
     1933
     1934    pt = &postorder_trees[ i ];
     1935    postorder_tree_init( &tree, pt );
     1936    postorder_tree_check( &tree, pt );
     1937  }
     1938}
     1939
    17591940rtems_task Init( rtems_task_argument ignored )
    17601941{
     
    22962477  }
    22972478
     2479  test_rbtree_postorder();
    22982480  test_rbtree_init_one();
    22992481  test_rbtree_min_max();
Note: See TracChangeset for help on using the changeset viewer.