| 1886 | } |
| 1887 | |
| 1888 | static void malloc_rebalance_insert(struct malloc_pool_s *pool, uint32_t n) |
| 1889 | { |
| 1890 | uint32_t parent, gparent, tmp; |
| 1891 | for (uint32_t m = n; m != MA_NIL; m = MA_PARENT(pool, m)) |
| 1892 | malloc_fix_invariant(pool, m); |
| 1893 | while ((parent = MA_PARENT(pool, n)) != MA_NIL && |
| 1894 | MA_COLOR(pool, parent) == MA_RED) |
| 1895 | { |
| 1896 | gparent = MA_PARENT(pool, parent); |
| 1897 | if (parent == MA_LEFT(pool, gparent)) |
| 1898 | { |
| 1899 | tmp = MA_RIGHT(pool, gparent); |
| 1900 | if (tmp != MA_NIL && MA_COLOR(pool, tmp) == MA_RED) |
| 1901 | { |
| 1902 | MA_COLOR(pool, tmp) = MA_BLACK; |
| 1903 | MA_COLOR(pool, parent) = MA_BLACK; |
| 1904 | MA_COLOR(pool, gparent) = MA_RED; |
| 1905 | n = gparent; |
| 1906 | continue; |
| 1907 | } |
| 1908 | if (MA_RIGHT(pool, parent) == n) |
| 1909 | { |
| 1910 | malloc_rotate_left(pool, parent); |
| 1911 | tmp = parent; |
| 1912 | parent = n; |
| 1913 | n = tmp; |
| 1914 | } |
| 1915 | MA_COLOR(pool, parent) = MA_BLACK; |
| 1916 | MA_COLOR(pool, gparent) = MA_RED; |
| 1917 | malloc_rotate_right(pool, gparent); |
| 1918 | } |
| 1919 | else |
| 1920 | { |
| 1921 | tmp = MA_LEFT(pool, gparent); |
| 1922 | if (tmp != MA_NIL && MA_COLOR(pool, tmp) == MA_RED) |
| 1923 | { |
| 1924 | MA_COLOR(pool, tmp) = MA_BLACK; |
| 1925 | MA_COLOR(pool, parent) = MA_BLACK; |
| 1926 | MA_COLOR(pool, gparent) = MA_RED; |
| 1927 | n = gparent; |
| 1928 | continue; |
| 1929 | } |
| 1930 | if (MA_LEFT(pool, parent) == n) |
| 1931 | { |
| 1932 | malloc_rotate_right(pool, parent); |
| 1933 | tmp = parent; |
| 1934 | parent = n; |
| 1935 | n = tmp; |
| 1936 | } |
| 1937 | MA_COLOR(pool, parent) = MA_BLACK; |
| 1938 | MA_COLOR(pool, gparent) = MA_RED; |
| 1939 | malloc_rotate_left(pool, gparent); |
| 1940 | } |
| 1941 | } |
| 1942 | MA_COLOR(pool, pool->root) = MA_BLACK; |
| 1943 | } |
| 1944 | |
| 1945 | static void malloc_rebalance_remove(struct malloc_pool_s *pool, |
no test coverage detected