1474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* 2474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * 4474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * Use of this source code is governed by a BSD-style license 5474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * that can be found in the LICENSE file in the root of the source 6474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * tree. An additional intellectual property rights grant can be found 7474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * in the file PATENTS. All contributing project authors may 8474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * be found in the AUTHORS file in the root of the source tree. 9474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org */ 10474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 118b26fe55f3e4daa2311dbd2d95e8ac2b4e080685johannkoenig@chromium.org#ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_ 128b26fe55f3e4daa2311dbd2d95e8ac2b4e080685johannkoenig@chromium.org#define VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_ 13474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 14474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Abstract AVL Tree Generic C Package. 15474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** Implementation generation header file. 16474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** 17474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** This code is in the public domain. See cavl_tree.html for interface 18474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** documentation. 19474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** 20474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** Version: 1.5 Author: Walt Karas 21474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 22474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 23474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_ 24474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_EST_LONG_BIT 25474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_SIZE 26474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef l_tree 27474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_MASK_HIGH_BIT 28474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_LONG_BIT 29474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_DEFN 30474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_VAL 31474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_0 32474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_1 33474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_ALL 34474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_LONGS 35474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_IMPL_MASK 36474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_CHECK_READ_ERROR 37474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_CHECK_READ_ERROR_INV_DEPTH 38474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_SC 39474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BALANCE_PARAM_PREFIX 40474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 41474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_UNIQUE 42474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 43474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_ AVL_UNIQUE 44474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 45474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 46474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 47474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_(X) X 48474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 49474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 50474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 51474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Determine correct storage class for functions */ 52474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_PRIVATE 53474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 54474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_SC static 55474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 56474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 57474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 58474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_SC 59474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 60474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 61474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 62474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_SIZE 63474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 64474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_SIZE AVL_SIZE 65474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 66474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 67474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 68474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_SIZE unsigned long 69474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 70474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 71474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 72474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_MASK_HIGH_BIT ((int) ~ ((~ (unsigned) 0) >> 1)) 73474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 74474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* ANSI C/ISO C++ require that a long have at least 32 bits. Set 75474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** L_EST_LONG_BIT to be the greatest multiple of 8 in the range 76474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** 32 - 64 (inclusive) that is less than or equal to the number of 77474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** bits in a long. 78474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 79474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 80474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (((LONG_MAX >> 31) >> 7) == 0) 81474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 82474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_EST_LONG_BIT 32 83474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 84474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#elif (((LONG_MAX >> 31) >> 15) == 0) 85474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 86474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_EST_LONG_BIT 40 87474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 88474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#elif (((LONG_MAX >> 31) >> 23) == 0) 89474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 90474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_EST_LONG_BIT 48 91474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 92474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#elif (((LONG_MAX >> 31) >> 31) == 0) 93474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 94474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_EST_LONG_BIT 56 95474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 96474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 97474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 98474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_EST_LONG_BIT 64 99474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 100474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 101474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 102474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_LONG_BIT (sizeof(long) * CHAR_BIT) 103474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 104474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT) 105474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 106474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* The maximum depth may be greater than the number of bits in a long, 107474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** so multiple longs are needed to hold a bit array indexed by node 108474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** depth. */ 109474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 110474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_LONGS (((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT) 111474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 112474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_DEFN(NAME) unsigned long NAME[L_BIT_ARR_LONGS]; 113474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 114474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) \ 1156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ((BIT_ARR)[(BIT_NUM) / L_LONG_BIT] & (1L << ((BIT_NUM) % L_LONG_BIT))) 116474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 117474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) \ 1186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] &= ~(1L << ((BIT_NUM) % L_LONG_BIT)); 119474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 120474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) \ 1216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] |= 1L << ((BIT_NUM) % L_LONG_BIT); 122474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 123474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) \ 1246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org { int i = L_BIT_ARR_LONGS; do (BIT_ARR)[--i] = 0L - (BIT_VAL); while(i); } 125474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 126474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else /* The bit array can definitely fit in one long */ 127474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 128474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_DEFN(NAME) unsigned long NAME; 129474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 130474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) ((BIT_ARR) & (1L << (BIT_NUM))) 131474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 132474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) (BIT_ARR) &= ~(1L << (BIT_NUM)); 133474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 134474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) (BIT_ARR) |= 1L << (BIT_NUM); 135474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 136474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) (BIT_ARR) = 0L - (BIT_VAL); 137474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 138474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 139474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 140474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_READ_ERRORS_HAPPEN 141474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 142474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_CHECK_READ_ERROR(ERROR_RETURN) \ 1436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org { if (AVL_READ_ERROR) return(ERROR_RETURN); } 144474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 145474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 146474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 147474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_CHECK_READ_ERROR(ERROR_RETURN) 148474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 149474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 150474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 151474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* The presumed reason that an instantiation places additional fields 152474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** inside the AVL tree structure is that the SET_ and GET_ macros 153474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** need these fields. The "balance" function does not explicitly use 154474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** any fields in the AVL tree structure, so only pass an AVL tree 155474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** structure pointer to "balance" if it has instantiation-specific 156474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** fields that are (presumably) needed by the SET_/GET_ calls within 157474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** "balance". 158474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 159474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_INSIDE_STRUCT 160474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 161474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BALANCE_PARAM_CALL_PREFIX l_tree, 162474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BALANCE_PARAM_DECL_PREFIX L_(avl) *l_tree, 163474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 164474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 165474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 166474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BALANCE_PARAM_CALL_PREFIX 167474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_BALANCE_PARAM_DECL_PREFIX 168474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 169474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 170474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 171474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_IMPL_MASK 172474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 173474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_IMPL_MASK (AVL_IMPL_MASK) 174474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 175474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 176474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 177474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Define all functions. */ 178474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_IMPL_MASK AVL_IMPL_ALL 179474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 180474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 181474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 182474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_INIT) 183474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC void L_(init)(L_(avl) *l_tree) { 1856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = AVL_NULL; 186474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 187474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 188474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 189474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 190474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_IS_EMPTY) 191474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC int L_(is_empty)(L_(avl) *l_tree) { 1936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(l_tree->root == AVL_NULL); 194474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 195474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 196474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 197474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 198474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Put the private balance function in the same compilation module as 199474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** the insert function. */ 200474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_INSERT) 201474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 202474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Balances subtree, returns handle of root node of subtree after balancing. 203474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 2046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h) { 2056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE deep_h; 206474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 2076fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Either the "greater than" or the "less than" subtree of 2086fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** this node has to be 2 levels deeper (or else it wouldn't 2096fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** need balancing). 2106fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org */ 2116fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (AVL_GET_BALANCE_FACTOR(bal_h) > 0) { 2126fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* "Greater than" subtree is deeper. */ 213474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 2146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org deep_h = AVL_GET_GREATER(bal_h, 1); 215474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 2166fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 217474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 2186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (AVL_GET_BALANCE_FACTOR(deep_h) < 0) { 2196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int bf; 2206fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE old_h = bal_h; 2226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bal_h = AVL_GET_LESS(deep_h, 1); 2236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 2246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1)) 2256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1)) 2266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(bal_h, old_h) 2276fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(bal_h, deep_h) 2286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bf = AVL_GET_BALANCE_FACTOR(bal_h); 2306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2316fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (bf != 0) { 2326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (bf > 0) { 2336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(old_h, -1) 2346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 0) 2356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 1) 2376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(old_h, 0) 238474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 2396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(bal_h, 0) 2416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(old_h, 0) 2436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 0) 2446fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 2456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2466fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0)) 2476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(deep_h, bal_h) 2486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) { 2506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, -1) 2516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(bal_h, 1) 2526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 0) 2546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(bal_h, 0) 2556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 2566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bal_h = deep_h; 258474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 2596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* "Less than" subtree is deeper. */ 261474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 2626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org deep_h = AVL_GET_LESS(bal_h, 1); 2636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 264474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 2656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (AVL_GET_BALANCE_FACTOR(deep_h) > 0) { 2666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int bf; 2676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE old_h = bal_h; 2686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bal_h = AVL_GET_GREATER(deep_h, 1); 2696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 2706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0)) 2716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0)) 2726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(bal_h, old_h) 2736fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(bal_h, deep_h) 2746fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bf = AVL_GET_BALANCE_FACTOR(bal_h); 2766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (bf != 0) { 2786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (bf < 0) { 2796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(old_h, 1) 2806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 0) 2816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, -1) 2836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(old_h, 0) 284474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 2856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2866fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(bal_h, 0) 2876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(old_h, 0) 2896fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 0) 2906fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 2916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0)) 2936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(deep_h, bal_h) 2946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 2956fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) { 2966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 1) 2976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(bal_h, -1) 2986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 2996fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(deep_h, 0) 3006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(bal_h, 0) 3016fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 3026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3036fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bal_h = deep_h; 304474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 3056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 306474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3076fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(bal_h); 308474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 309474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3106fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(insert)(L_(avl) *l_tree, AVL_HANDLE h) { 3116fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(h, AVL_NULL) 3126fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, AVL_NULL) 3136fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(h, 0) 314474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (l_tree->root == AVL_NULL) 3166fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = h; 3176fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else { 3186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Last unbalanced node encountered in search for insertion point. */ 3196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE unbal = AVL_NULL; 3206fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Parent of last unbalanced node. */ 3216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE parent_unbal = AVL_NULL; 3226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Balance factor of last unbalanced node. */ 3236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int unbal_bf; 324474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Zero-based depth in tree. */ 3266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unsigned depth = 0, unbal_depth = 0; 327474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Records a path into the tree. If bit n is true, indicates 3296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** take greater branch from the nth node in the path, otherwise 3306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** take the less branch. bit 0 gives branch from root, and 3316fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** so on. */ 3326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_DEFN(branch) 333474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE hh = l_tree->root; 3356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE parent = AVL_NULL; 3366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int cmp; 337474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org do { 3396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (AVL_GET_BALANCE_FACTOR(hh) != 0) { 3406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unbal = hh; 3416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent_unbal = parent; 3426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unbal_depth = depth; 3436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 344474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = AVL_COMPARE_NODE_NODE(h, hh); 346474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp == 0) 3486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Duplicate key. */ 3496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(hh); 350474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = hh; 352474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp > 0) { 3546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org hh = AVL_GET_GREATER(hh, 1); 3556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(branch, depth) 3566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 3576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org hh = AVL_GET_LESS(hh, 1); 3586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(branch, depth) 3596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 3606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 3626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 3636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } while (hh != AVL_NULL); 3646fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Add node to insert as leaf of tree. */ 3666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp < 0) 3676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(parent, h) 3686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 3696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(parent, h) 3706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth = unbal_depth; 3726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3736fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (unbal == AVL_NULL) 3746fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org hh = l_tree->root; 3756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else { 3766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 3776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 3786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unbal_bf = AVL_GET_BALANCE_FACTOR(unbal); 3796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp < 0) 3816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unbal_bf--; 3826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else /* cmp > 0 */ 3836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unbal_bf++; 3846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1); 3866fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 3876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 3886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if ((unbal_bf != -2) && (unbal_bf != 2)) { 3896fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* No rebalancing of tree is necessary. */ 3906fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(unbal, unbal_bf) 3916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unbal = AVL_NULL; 3926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 3936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 394474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3956fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (hh != AVL_NULL) 3966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (h != hh) { 3976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 3986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 399474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp < 0) { 4016fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(hh, -1) 4026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org hh = AVL_GET_LESS(hh, 1); 4036fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { /* cmp > 0 */ 4046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(hh, 1) 4056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org hh = AVL_GET_GREATER(hh, 1); 4066fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 407474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4086fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 4096fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 410474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4116fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (unbal != AVL_NULL) { 4126fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unbal = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX unbal); 4136fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 414474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (parent_unbal == AVL_NULL) 4166fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = unbal; 4176fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else { 4186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth = unbal_depth - 1; 4196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 420474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp < 0) 4226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(parent_unbal, unbal) 4236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else /* cmp > 0 */ 4246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(parent_unbal, unbal) 4256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 426474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 427474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 4296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(h); 4316fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org} 4326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org#endif 4346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org#if (L_IMPL_MASK & AVL_IMPL_SEARCH) 4366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(search)(L_(avl) *l_tree, AVL_KEY k, avl_search_type st) { 4386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int cmp, target_cmp; 4396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE match_h = AVL_NULL; 4406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 4416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (st & AVL_LESS) 4436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org target_cmp = 1; 4446fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else if (st & AVL_GREATER) 4456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org target_cmp = -1; 4466fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 4476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org target_cmp = 0; 4486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (h != AVL_NULL) { 4506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = AVL_COMPARE_KEY_NODE(k, h); 4516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp == 0) { 4536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (st & AVL_EQUAL) { 4546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org match_h = h; 4556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 4566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 4576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = -target_cmp; 4596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else if (target_cmp != 0) 4606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 4616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* cmp and target_cmp are both positive or both negative. */ 4626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org match_h = h; 4636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4646fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 4656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 4666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 4676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 4686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(match_h); 469474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 470474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 471474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 472474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 473474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_SEARCH_LEAST) 474474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(search_least)(L_(avl) *l_tree) { 4766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 4776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE parent = AVL_NULL; 478474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (h != AVL_NULL) { 4806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = h; 4816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_LESS(h, 1); 4826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 4836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 484474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(parent); 486474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 487474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 488474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 489474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 490474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_SEARCH_GREATEST) 491474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(search_greatest)(L_(avl) *l_tree) { 4936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 4946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE parent = AVL_NULL; 495474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 4966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (h != AVL_NULL) { 4976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = h; 4986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_GREATER(h, 1); 4996fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 5006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 501474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(parent); 503474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 504474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 505474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 506474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 507474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_REMOVE) 508474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 509474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Prototype of balance function (called by remove) in case not in 510474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** same compilation unit. 511474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 512474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgL_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h); 513474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(remove)(L_(avl) *l_tree, AVL_KEY k) { 5156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Zero-based depth in tree. */ 5166fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unsigned depth = 0, rm_depth; 5176fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Records a path into the tree. If bit n is true, indicates 5196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** take greater branch from the nth node in the path, otherwise 5206fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** take the less branch. bit 0 gives branch from root, and 5216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** so on. */ 5226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_DEFN(branch) 5236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 5256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE parent = AVL_NULL; 5266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE child; 5276fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE path; 5286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int cmp, cmp_shortened_sub_with_path; 5296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int reduced_depth; 5306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int bf; 5316fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE rm; 5326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE parent_rm; 5336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org for (;;) { 5356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h == AVL_NULL) 5366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* No node in tree with given key. */ 5376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(AVL_NULL); 538474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = AVL_COMPARE_KEY_NODE(k, h); 540474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp == 0) 5426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Found node to remove. */ 5436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 544474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = h; 546474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp > 0) { 5486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_GREATER(h, 1); 5496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(branch, depth) 5506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 5516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_LESS(h, 1); 5526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(branch, depth) 553474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 554474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 5566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 5576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp_shortened_sub_with_path = cmp; 5586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 5596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org rm = h; 5616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent_rm = parent; 5626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org rm_depth = depth; 5636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5646fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* If the node to remove is not a leaf node, we need to get a 5656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** leaf node, or a node with a single leaf as its child, to put 5666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** in the place of the node to remove. We will get the greatest 5676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** node in the less subtree (of the node to remove), or the least 5686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** node in the greater subtree. We take the leaf node from the 5696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** deeper subtree, if there is one. */ 5706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (AVL_GET_BALANCE_FACTOR(h) < 0) { 5726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = AVL_GET_LESS(h, 1); 5736fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(branch, depth) 5746fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = -1; 5756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 5766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = AVL_GET_GREATER(h, 1); 5776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(branch, depth) 5786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = 1; 5796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 5806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 5826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 5836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (child != AVL_NULL) { 5856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = -cmp; 5866fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org do { 5886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = h; 5896fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = child; 5906fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 5916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp < 0) { 592474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org child = AVL_GET_LESS(h, 1); 593474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org L_BIT_ARR_0(branch, depth) 5946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 595474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org child = AVL_GET_GREATER(h, 1); 596474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org L_BIT_ARR_1(branch, depth) 5976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 598474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 5996fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 6006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 6016fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } while (child != AVL_NULL); 602474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 6036fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (parent == rm) 6046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Only went through do loop once. Deleted node will be replaced 6056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** in the tree structure by one of its immediate children. */ 6066fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp_shortened_sub_with_path = -cmp; 6076fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 6086fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp_shortened_sub_with_path = cmp; 6096fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6106fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Get the handle of the opposite child, which may not be null. */ 6116fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0); 6126fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 613474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 6146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (parent == AVL_NULL) 6156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* There were only 1 or 2 nodes in this tree. */ 6166fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = child; 6176fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else if (cmp_shortened_sub_with_path < 0) 6186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(parent, child) 6196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 6206fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(parent, child) 6216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* "path" is the parent of the subtree being eliminated or reduced 6236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** from a depth of 2 to 1. If "path" is the node to be removed, we 6246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** set path to the node we're about to poke into the position of the 6256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** node to be removed. */ 6266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org path = parent == rm ? h : parent; 6276fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h != rm) { 6296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Poke in the replacement for the node to be removed. */ 6306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(h, AVL_GET_LESS(rm, 0)) 6316fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0)) 6326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm)) 6336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (parent_rm == AVL_NULL) 6356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = h; 6366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else { 6376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth = rm_depth - 1; 6386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (L_BIT_ARR_VAL(branch, depth)) 6406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(parent_rm, h) 641474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org else 6426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(parent_rm, h) 6436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 6446fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 645474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 6466fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (path != AVL_NULL) { 6476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Create a temporary linked list from the parent of the path node 6486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** to the root node. */ 6496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = l_tree->root; 6506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = AVL_NULL; 6516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth = 0; 652474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 6536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (h != path) { 6546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (L_BIT_ARR_VAL(branch, depth)) { 6556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = AVL_GET_GREATER(h, 1); 6566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, parent) 6576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 6586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = AVL_GET_LESS(h, 1); 6596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(h, parent) 6606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 6616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 6636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 6646fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = h; 6656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = child; 666474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 667474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 6686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Climb from the path node to the root node using the linked 6696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** list, restoring the tree structure and rebalancing as necessary. 6706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org */ 6716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org reduced_depth = 1; 6726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = cmp_shortened_sub_with_path; 673474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 6746fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org for (;;) { 6756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (reduced_depth) { 6766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bf = AVL_GET_BALANCE_FACTOR(h); 6776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp < 0) 6796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bf++; 6806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else /* cmp > 0 */ 6816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bf--; 6826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if ((bf == -2) || (bf == 2)) { 6846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX h); 6856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 6866fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bf = AVL_GET_BALANCE_FACTOR(h); 6876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else 6886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(h, bf) 6896fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org reduced_depth = (bf == 0); 6906fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 6916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (parent == AVL_NULL) 6936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 6946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 6956fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = h; 6966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = parent; 6976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth--; 6986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 6996fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp < 0) { 7016fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = AVL_GET_LESS(h, 1); 7026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(h, child) 7036fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 7046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = AVL_GET_GREATER(h, 1); 7056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, child) 7066fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 707474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 7086fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 709474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 710474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 7116fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = h; 7126fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 7136fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(rm); 715474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 716474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 717474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 718474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 719474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_SUBST) 720474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 7216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(subst)(L_(avl) *l_tree, AVL_HANDLE new_node) { 7226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 7236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE parent = AVL_NULL; 7246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int cmp, last_cmp; 725474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 7266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Search for node already in tree with same key. */ 7276fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org for (;;) { 7286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h == AVL_NULL) 7296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* No node in tree with same key as new node. */ 7306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(AVL_NULL); 731474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 7326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = AVL_COMPARE_NODE_NODE(new_node, h); 733474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 7346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp == 0) 7356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Found the node to substitute new one for. */ 7366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 737474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 7386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org last_cmp = cmp; 7396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org parent = h; 7406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 7416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(AVL_NULL) 7426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 7436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7446fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Copy tree housekeeping fields from node in tree to new node. */ 7456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0)) 7466fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0)) 7476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h)) 7486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (parent == AVL_NULL) 7506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* New node is also new root. */ 7516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = new_node; 7526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else { 7536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Make parent point to new node. */ 7546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (last_cmp < 0) 7556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(parent, new_node) 7566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 7576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(parent, new_node) 7586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 7596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(h); 761474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 762474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 763474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 764474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 765474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_BUILD_ITER_TYPE 766474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 767474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_BUILD) 768474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 769474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgL_SC int L_(build)( 7706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_(avl) *l_tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes) { 7716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Gives path to subtree being built. If bit n is false, branch 7726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** less from the node at depth n, if true branch greater. */ 7736fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_DEFN(branch) 7746fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* If bit n is true, then for the current subtree at depth n, its 7766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** greater subtree has one more node than its less subtree. */ 7776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_DEFN(rem) 7786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Depth of root node of current subtree. */ 7806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unsigned depth = 0; 7816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Number of nodes in current subtree. */ 7836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_SIZE num_sub = num_nodes; 7846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* The algorithm relies on a stack of nodes whose less subtree has 7866fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** been built, but whose greater subtree has not yet been built. 7876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** The stack is implemented as linked list. The nodes are linked 7886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** together by having the "greater" handle of a node set to the 7896fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** next node in the list. "less_parent" is the handle of the first 7906fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** node in the list. */ 7916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE less_parent = AVL_NULL; 7926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* h is root of current subtree, child is one of its children. */ 7946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h; 7956fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE child; 7966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 7976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (num_nodes == 0) { 7986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = AVL_NULL; 7996fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(1); 8006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 801474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org for (;;) { 8036fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (num_sub > 2) { 8046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Subtract one for root of subtree. */ 8056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org num_sub--; 806474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8076fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (num_sub & 1) 8086fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(rem, depth) 8096fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 8106fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(rem, depth) 8116fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(branch, depth) 8126fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 813474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org num_sub >>= 1; 8156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 816474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8176fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (num_sub == 2) { 8186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Build a subtree with two nodes, slanting to greater. 8196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** I arbitrarily chose to always have the extra node in the 8206fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** greater subtree when there is an odd number of nodes to 8216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** split between the two subtrees. */ 8226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 8236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_BUILD_ITER_VAL(p); 8246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(0) 8256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_BUILD_ITER_INCR(p) 8266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = AVL_BUILD_ITER_VAL(p); 8276fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(0) 8286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_BUILD_ITER_INCR(p) 8296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(child, AVL_NULL) 8306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(child, AVL_NULL) 8316fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(child, 0) 8326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, child) 8336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(h, AVL_NULL) 8346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(h, 1) 8356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { /* num_sub == 1 */ 8366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Build a subtree with one node. */ 8376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 8386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_BUILD_ITER_VAL(p); 8396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(0) 8406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_BUILD_ITER_INCR(p) 8416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(h, AVL_NULL) 8426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, AVL_NULL) 8436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(h, 0) 844474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 845474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8466fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (depth) { 8476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth--; 8486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 8496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (!L_BIT_ARR_VAL(branch, depth)) 8506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* We've completed a less subtree. */ 8516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 8526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 8536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* We've completed a greater subtree, so attach it to 8546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** its parent (that is less than it). We pop the parent 8556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** off the stack of less parents. */ 8566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = h; 8576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = less_parent; 8586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org less_parent = AVL_GET_GREATER(h, 1); 8596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(0) 8606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, child) 8616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */ 8626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org num_sub <<= 1; 8636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org num_sub += L_BIT_ARR_VAL(rem, depth) ? 0 : 1; 8646fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 8656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (num_sub & (num_sub - 1)) 8666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* num_sub is not a power of 2. */ 8676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(h, 0) 8686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 8696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* num_sub is a power of 2. */ 8706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_BALANCE_FACTOR(h, 1) 871474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 872474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8736fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (num_sub == num_nodes) 8746fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* We've completed the full tree. */ 8756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 876474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* The subtree we've completed is the less subtree of the 8786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** next node in the sequence. */ 879474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org child = h; 8816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_BUILD_ITER_VAL(p); 8826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR(0) 8836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_BUILD_ITER_INCR(p) 8846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_LESS(h, child) 885474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8866fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Put h into stack of less parents. */ 8876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_SET_GREATER(h, less_parent) 8886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org less_parent = h; 889474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8906fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Proceed to creating greater than subtree of h. */ 8916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(branch, depth) 8926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org num_sub += L_BIT_ARR_VAL(rem, depth) ? 1 : 0; 8936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org depth++; 894474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8956fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } /* end for (;; ) */ 896474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 8976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org l_tree->root = h; 8986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 8996fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(1); 900474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 901474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 902474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 903474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 904474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 905474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 906474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_INIT_ITER) 907474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 908474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Initialize depth to invalid value, to indicate iterator is 909474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** invalid. (Depth is zero-base.) It's not necessary to initialize 910474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** iterators prior to passing them to the "start" function. 911474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 9126fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC void L_(init_iter)(L_(iter) *iter) { 9136fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = ~0; 914474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 915474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 916474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 917474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 918474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef AVL_READ_ERRORS_HAPPEN 919474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 920474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_CHECK_READ_ERROR_INV_DEPTH \ 9216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org { if (AVL_READ_ERROR) { iter->depth = ~0; return; } } 922474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 923474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#else 924474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 925474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define L_CHECK_READ_ERROR_INV_DEPTH 926474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 927474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 928474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 929474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_START_ITER) 930474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 931474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgL_SC void L_(start_iter)( 9326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_(avl) *l_tree, L_(iter) *iter, AVL_KEY k, avl_search_type st) { 9336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 9346fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org unsigned d = 0; 9356fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int cmp, target_cmp; 9366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Save the tree that we're going to iterate through in a 9386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** member variable. */ 9396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->tree_ = l_tree; 9406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = ~0; 9426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h == AVL_NULL) 9446fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Tree is empty. */ 9456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return; 9466fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (st & AVL_LESS) 9486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Key can be greater than key of starting node. */ 9496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org target_cmp = 1; 9506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else if (st & AVL_GREATER) 9516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Key can be less than key of starting node. */ 9526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org target_cmp = -1; 9536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 9546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Key must be same as key of starting node. */ 9556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org target_cmp = 0; 9566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org for (;;) { 9586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = AVL_COMPARE_KEY_NODE(k, h); 9596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp == 0) { 9616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (st & AVL_EQUAL) { 9626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Equal node was sought and found as starting node. */ 9636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = d; 9646fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 9656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 9666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org cmp = -target_cmp; 9686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else if (target_cmp != 0) 9696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 9706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* cmp and target_cmp are both negative or both positive. */ 9716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = d; 9726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9736fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 9746fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR_INV_DEPTH 975474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 976474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (h == AVL_NULL) 9776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 9786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 9796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (cmp > 0) 9806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(iter->branch, d) 9816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 9826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(iter->branch, d) 9836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->path_h[d++] = h; 9846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 985474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 986474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 987474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 988474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 989474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_START_ITER_LEAST) 990474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 9916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC void L_(start_iter_least)(L_(avl) *l_tree, L_(iter) *iter) { 9926fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 993474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 9946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->tree_ = l_tree; 995474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 9966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = ~0; 997474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 9986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_ALL(iter->branch, 0) 999474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (h != AVL_NULL) { 10016fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (iter->depth != ~0) 10026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->path_h[iter->depth] = h; 1003474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth++; 10056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_LESS(h, 1); 10066fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR_INV_DEPTH 10076fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1008474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 1009474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1010474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 1011474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1012474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_START_ITER_GREATEST) 1013474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC void L_(start_iter_greatest)(L_(avl) *l_tree, L_(iter) *iter) { 10156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = l_tree->root; 1016474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10176fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->tree_ = l_tree; 1018474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = ~0; 1020474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_ALL(iter->branch, 1) 1022474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10236fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org while (h != AVL_NULL) { 10246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (iter->depth != ~0) 10256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->path_h[iter->depth] = h; 1026474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10276fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth++; 10286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_GREATER(h, 1); 10296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR_INV_DEPTH 10306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1031474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 1032474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1033474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 1034474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1035474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_GET_ITER) 1036474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter) { 10386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (iter->depth == ~0) 10396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(AVL_NULL); 1040474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org return(iter->depth == 0 ? 10426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->tree_->root : iter->path_h[iter->depth - 1]); 1043474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 1044474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1045474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 1046474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1047474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_INCR_ITER) 1048474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC void L_(incr_iter)(L_(iter) *iter) { 1050474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define l_tree (iter->tree_) 1051474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (iter->depth != ~0) { 10536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = 10546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_GET_GREATER((iter->depth == 0 ? 10556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 10566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR_INV_DEPTH 1057474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h == AVL_NULL) 10596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org do { 10606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (iter->depth == 0) { 10616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = ~0; 10626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 10636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1064474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth--; 10666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } while (L_BIT_ARR_VAL(iter->branch, iter->depth)); 10676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else { 10686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(iter->branch, iter->depth) 10696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->path_h[iter->depth++] = h; 1070474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org for (;;) { 10726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_LESS(h, 1); 10736fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR_INV_DEPTH 1074474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10756fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h == AVL_NULL) 10766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 10776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 10786fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(iter->branch, iter->depth) 10796fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->path_h[iter->depth++] = h; 10806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1081474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 10826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1083474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1084474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef l_tree 1085474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 1086474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1087474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 1088474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1089474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#if (L_IMPL_MASK & AVL_IMPL_DECR_ITER) 1090474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10916fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgL_SC void L_(decr_iter)(L_(iter) *iter) { 1092474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define l_tree (iter->tree_) 1093474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 10946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (iter->depth != ~0) { 10956fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_HANDLE h = 10966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AVL_GET_LESS((iter->depth == 0 ? 10976fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 10986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR_INV_DEPTH 1099474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 11006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h == AVL_NULL) 11016fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org do { 11026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (iter->depth == 0) { 11036fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth = ~0; 11046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 11056fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1106474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 11076fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->depth--; 11086fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } while (!L_BIT_ARR_VAL(iter->branch, iter->depth)); 11096fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else { 11106fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_0(iter->branch, iter->depth) 11116fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->path_h[iter->depth++] = h; 1112474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 11136fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org for (;;) { 11146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h = AVL_GET_GREATER(h, 1); 11156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_CHECK_READ_ERROR_INV_DEPTH 1116474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 11176fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (h == AVL_NULL) 11186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org break; 11196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 11206fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org L_BIT_ARR_1(iter->branch, iter->depth) 11216fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org iter->path_h[iter->depth++] = h; 11226fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1123474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 11246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 1125474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1126474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef l_tree 1127474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 1128474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1129474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 1130474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1131474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Tidy up the preprocessor symbol name space. */ 1132474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_ 1133474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_EST_LONG_BIT 1134474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_SIZE 1135474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_MASK_HIGH_BIT 1136474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_LONG_BIT 1137474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_DEFN 1138474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_VAL 1139474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_0 1140474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_1 1141474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_ALL 1142474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_CHECK_READ_ERROR 1143474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_CHECK_READ_ERROR_INV_DEPTH 1144474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BIT_ARR_LONGS 1145474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_IMPL_MASK 1146474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_CHECK_READ_ERROR 1147474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_CHECK_READ_ERROR_INV_DEPTH 1148474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_SC 1149474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BALANCE_PARAM_CALL_PREFIX 1150474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#undef L_BALANCE_PARAM_DECL_PREFIX 11518b26fe55f3e4daa2311dbd2d95e8ac2b4e080685johannkoenig@chromium.org 11528b26fe55f3e4daa2311dbd2d95e8ac2b4e080685johannkoenig@chromium.org#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_ 1153