190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* 2f71323e297a928af368937089d3ed71239786f86Andreas Huber * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber * 4f71323e297a928af368937089d3ed71239786f86Andreas Huber * Use of this source code is governed by a BSD-style license 5f71323e297a928af368937089d3ed71239786f86Andreas Huber * that can be found in the LICENSE file in the root of the source 6f71323e297a928af368937089d3ed71239786f86Andreas Huber * tree. An additional intellectual property rights grant can be found 7f71323e297a928af368937089d3ed71239786f86Andreas Huber * in the file PATENTS. All contributing project authors may 8f71323e297a928af368937089d3ed71239786f86Andreas Huber * be found in the AUTHORS file in the root of the source tree. 990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber */ 1090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11b08e2e23eec181e9951df33cd704ac294c5407b6Vignesh Venkatasubramanian#ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_ 12b08e2e23eec181e9951df33cd704ac294c5407b6Vignesh Venkatasubramanian#define VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_ 1390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Abstract AVL Tree Generic C Package. 1590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** Implementation generation header file. 1690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** 1790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** This code is in the public domain. See cavl_tree.html for interface 1890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** documentation. 1990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** 2090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** Version: 1.5 Author: Walt Karas 2190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 2290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_ 2490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_EST_LONG_BIT 2590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SIZE 2690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef l_tree 2790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_MASK_HIGH_BIT 2890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_LONG_BIT 2990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_DEFN 3090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_VAL 3190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_0 3290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_1 3390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_ALL 3490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_LONGS 3590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_IMPL_MASK 3690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR 3790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR_INV_DEPTH 3890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SC 3990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BALANCE_PARAM_PREFIX 4090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_UNIQUE 4290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_ AVL_UNIQUE 4490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 4690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_(X) X 4890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 5090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Determine correct storage class for functions */ 5290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_PRIVATE 5390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SC static 5590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 5790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SC 5990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 6190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_SIZE 6390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SIZE AVL_SIZE 6590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 6790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SIZE unsigned long 6990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 7190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_MASK_HIGH_BIT ((int) ~ ((~ (unsigned) 0) >> 1)) 7390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* ANSI C/ISO C++ require that a long have at least 32 bits. Set 7590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** L_EST_LONG_BIT to be the greatest multiple of 8 in the range 7690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** 32 - 64 (inclusive) that is less than or equal to the number of 7790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** bits in a long. 7890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 7990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (((LONG_MAX >> 31) >> 7) == 0) 8190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 32 8390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif (((LONG_MAX >> 31) >> 15) == 0) 8590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 40 8790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif (((LONG_MAX >> 31) >> 23) == 0) 8990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 48 9190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif (((LONG_MAX >> 31) >> 31) == 0) 9390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 56 9590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 9790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 64 9990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 10190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_LONG_BIT (sizeof(long) * CHAR_BIT) 10390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT) 10590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* The maximum depth may be greater than the number of bits in a long, 10790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** so multiple longs are needed to hold a bit array indexed by node 10890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** depth. */ 10990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_LONGS (((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT) 11190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_DEFN(NAME) unsigned long NAME[L_BIT_ARR_LONGS]; 11390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) \ 115ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ((BIT_ARR)[(BIT_NUM) / L_LONG_BIT] & (1L << ((BIT_NUM) % L_LONG_BIT))) 11690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) \ 118ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] &= ~(1L << ((BIT_NUM) % L_LONG_BIT)); 11990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) \ 121ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] |= 1L << ((BIT_NUM) % L_LONG_BIT); 12290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) \ 124ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang { int i = L_BIT_ARR_LONGS; do (BIT_ARR)[--i] = 0L - (BIT_VAL); while(i); } 12590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else /* The bit array can definitely fit in one long */ 12790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_DEFN(NAME) unsigned long NAME; 12990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) ((BIT_ARR) & (1L << (BIT_NUM))) 13190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) (BIT_ARR) &= ~(1L << (BIT_NUM)); 13390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) (BIT_ARR) |= 1L << (BIT_NUM); 13590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) (BIT_ARR) = 0L - (BIT_VAL); 13790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 13990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_READ_ERRORS_HAPPEN 14190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR(ERROR_RETURN) \ 143ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang { if (AVL_READ_ERROR) return(ERROR_RETURN); } 14490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 14690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR(ERROR_RETURN) 14890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 15090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 15190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* The presumed reason that an instantiation places additional fields 15290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** inside the AVL tree structure is that the SET_ and GET_ macros 15390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** need these fields. The "balance" function does not explicitly use 15490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** any fields in the AVL tree structure, so only pass an AVL tree 15590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** structure pointer to "balance" if it has instantiation-specific 15690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** fields that are (presumably) needed by the SET_/GET_ calls within 15790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** "balance". 15890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 15990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_INSIDE_STRUCT 16090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_CALL_PREFIX l_tree, 16290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_DECL_PREFIX L_(avl) *l_tree, 16390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 16590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_CALL_PREFIX 16790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_DECL_PREFIX 16890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 17090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_IMPL_MASK 17290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_IMPL_MASK (AVL_IMPL_MASK) 17490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 17690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Define all functions. */ 17890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_IMPL_MASK AVL_IMPL_ALL 17990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 18190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_INIT) 18390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 184ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC void L_(init)(L_(avl) *l_tree) { 185ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = AVL_NULL; 18690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 18790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 18990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 19090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_IS_EMPTY) 19190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 192ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC int L_(is_empty)(L_(avl) *l_tree) { 193ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(l_tree->root == AVL_NULL); 19490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 19590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 19690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 19790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 19890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Put the private balance function in the same compilation module as 19990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** the insert function. */ 20090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_INSERT) 20190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 20290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Balances subtree, returns handle of root node of subtree after balancing. 20390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 204ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h) { 205ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE deep_h; 20690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 207ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Either the "greater than" or the "less than" subtree of 208ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** this node has to be 2 levels deeper (or else it wouldn't 209ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** need balancing). 210ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang */ 211ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (AVL_GET_BALANCE_FACTOR(bal_h) > 0) { 212ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* "Greater than" subtree is deeper. */ 21390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 214ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang deep_h = AVL_GET_GREATER(bal_h, 1); 21590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 216ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 21790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 218ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (AVL_GET_BALANCE_FACTOR(deep_h) < 0) { 219ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int bf; 220ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 221ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE old_h = bal_h; 222ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bal_h = AVL_GET_LESS(deep_h, 1); 223ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 224ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1)) 225ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1)) 226ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(bal_h, old_h) 227ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(bal_h, deep_h) 228ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 229ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bf = AVL_GET_BALANCE_FACTOR(bal_h); 230ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 231ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (bf != 0) { 232ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (bf > 0) { 233ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(old_h, -1) 234ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 0) 235ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 236ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 1) 237ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(old_h, 0) 23890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 239ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 240ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(bal_h, 0) 241ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 242ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(old_h, 0) 243ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 0) 244ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 245ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 246ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0)) 247ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(deep_h, bal_h) 248ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 249ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) { 250ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, -1) 251ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(bal_h, 1) 252ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 253ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 0) 254ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(bal_h, 0) 255ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 256ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 257ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bal_h = deep_h; 25890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 259ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 260ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* "Less than" subtree is deeper. */ 26190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 262ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang deep_h = AVL_GET_LESS(bal_h, 1); 263ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 26490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 265ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (AVL_GET_BALANCE_FACTOR(deep_h) > 0) { 266ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int bf; 267ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE old_h = bal_h; 268ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bal_h = AVL_GET_GREATER(deep_h, 1); 269ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 270ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0)) 271ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0)) 272ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(bal_h, old_h) 273ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(bal_h, deep_h) 274ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 275ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bf = AVL_GET_BALANCE_FACTOR(bal_h); 276ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 277ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (bf != 0) { 278ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (bf < 0) { 279ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(old_h, 1) 280ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 0) 281ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 282ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, -1) 283ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(old_h, 0) 28490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 285ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 286ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(bal_h, 0) 287ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 288ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(old_h, 0) 289ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 0) 290ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 291ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 292ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0)) 293ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(deep_h, bal_h) 294ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 295ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) { 296ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 1) 297ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(bal_h, -1) 298ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 299ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(deep_h, 0) 300ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(bal_h, 0) 301ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 302ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 303ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bal_h = deep_h; 30490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 305ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 30690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 307ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(bal_h); 30890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 30990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 310ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(insert)(L_(avl) *l_tree, AVL_HANDLE h) { 311ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(h, AVL_NULL) 312ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, AVL_NULL) 313ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(h, 0) 31490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 315ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (l_tree->root == AVL_NULL) 316ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = h; 317ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else { 318ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Last unbalanced node encountered in search for insertion point. */ 319ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE unbal = AVL_NULL; 320ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Parent of last unbalanced node. */ 321ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE parent_unbal = AVL_NULL; 322ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Balance factor of last unbalanced node. */ 323ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int unbal_bf; 32490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 325ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Zero-based depth in tree. */ 326ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned depth = 0, unbal_depth = 0; 32790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 328ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Records a path into the tree. If bit n is true, indicates 329ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** take greater branch from the nth node in the path, otherwise 330ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** take the less branch. bit 0 gives branch from root, and 331ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** so on. */ 332ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_DEFN(branch) 33390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 334ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE hh = l_tree->root; 335ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE parent = AVL_NULL; 336ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int cmp; 33790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 338ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang do { 339ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (AVL_GET_BALANCE_FACTOR(hh) != 0) { 340ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unbal = hh; 341ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent_unbal = parent; 342ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unbal_depth = depth; 343ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 34490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 345ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = AVL_COMPARE_NODE_NODE(h, hh); 34690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 347ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp == 0) 348ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Duplicate key. */ 349ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(hh); 35090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 351ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = hh; 35290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 353ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp > 0) { 354ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang hh = AVL_GET_GREATER(hh, 1); 355ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(branch, depth) 356ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 357ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang hh = AVL_GET_LESS(hh, 1); 358ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(branch, depth) 359ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 360ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 361ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 362ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 363ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } while (hh != AVL_NULL); 364ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 365ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Add node to insert as leaf of tree. */ 366ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp < 0) 367ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(parent, h) 368ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 369ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(parent, h) 370ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 371ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth = unbal_depth; 372ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 373ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (unbal == AVL_NULL) 374ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang hh = l_tree->root; 375ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else { 376ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 377ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 378ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unbal_bf = AVL_GET_BALANCE_FACTOR(unbal); 379ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 380ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp < 0) 381ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unbal_bf--; 382ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else /* cmp > 0 */ 383ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unbal_bf++; 384ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 385ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1); 386ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 387ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 388ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if ((unbal_bf != -2) && (unbal_bf != 2)) { 389ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* No rebalancing of tree is necessary. */ 390ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(unbal, unbal_bf) 391ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unbal = AVL_NULL; 392ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 393ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 39490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 395ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (hh != AVL_NULL) 396ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (h != hh) { 397ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 398ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 39990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 400ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp < 0) { 401ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(hh, -1) 402ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang hh = AVL_GET_LESS(hh, 1); 403ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { /* cmp > 0 */ 404ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(hh, 1) 405ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang hh = AVL_GET_GREATER(hh, 1); 406ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 40790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 408ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 409ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 41090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 411ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (unbal != AVL_NULL) { 412ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unbal = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX unbal); 413ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 41490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 415ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (parent_unbal == AVL_NULL) 416ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = unbal; 417ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else { 418ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth = unbal_depth - 1; 419ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 42090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 421ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp < 0) 422ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(parent_unbal, unbal) 423ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else /* cmp > 0 */ 424ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(parent_unbal, unbal) 425ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 42690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 42790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 428ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 429ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 430ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(h); 431ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang} 432ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 433ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#endif 434ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 435ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#if (L_IMPL_MASK & AVL_IMPL_SEARCH) 436ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 437ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(search)(L_(avl) *l_tree, AVL_KEY k, avl_search_type st) { 438ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int cmp, target_cmp; 439ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE match_h = AVL_NULL; 440ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 441ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 442ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (st & AVL_LESS) 443ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang target_cmp = 1; 444ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else if (st & AVL_GREATER) 445ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang target_cmp = -1; 446ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 447ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang target_cmp = 0; 448ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 449ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (h != AVL_NULL) { 450ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = AVL_COMPARE_KEY_NODE(k, h); 451ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 452ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp == 0) { 453ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (st & AVL_EQUAL) { 454ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang match_h = h; 455ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 456ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 457ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 458ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = -target_cmp; 459ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else if (target_cmp != 0) 460ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 461ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* cmp and target_cmp are both positive or both negative. */ 462ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang match_h = h; 463ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 464ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 465ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 466ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 467ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 468ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(match_h); 46990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 47090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 47190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 47290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 47390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_SEARCH_LEAST) 47490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 475ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(search_least)(L_(avl) *l_tree) { 476ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 477ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE parent = AVL_NULL; 47890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 479ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (h != AVL_NULL) { 480ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = h; 481ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_LESS(h, 1); 482ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 483ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 48490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 485ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(parent); 48690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 48790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 48890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 48990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 49090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_SEARCH_GREATEST) 49190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 492ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(search_greatest)(L_(avl) *l_tree) { 493ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 494ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE parent = AVL_NULL; 49590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 496ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (h != AVL_NULL) { 497ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = h; 498ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_GREATER(h, 1); 499ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 500ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 50190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 502ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(parent); 50390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 50490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 50590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 50690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 50790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_REMOVE) 50890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 50990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Prototype of balance function (called by remove) in case not in 51090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** same compilation unit. 51190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 51290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h); 51390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 514ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(remove)(L_(avl) *l_tree, AVL_KEY k) { 515ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Zero-based depth in tree. */ 516ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned depth = 0, rm_depth; 517ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 518ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Records a path into the tree. If bit n is true, indicates 519ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** take greater branch from the nth node in the path, otherwise 520ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** take the less branch. bit 0 gives branch from root, and 521ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** so on. */ 522ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_DEFN(branch) 523ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 524ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 525ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE parent = AVL_NULL; 526ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE child; 527ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE path; 528ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int cmp, cmp_shortened_sub_with_path; 529ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int reduced_depth; 530ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int bf; 531ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE rm; 532ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE parent_rm; 533ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 534ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for (;;) { 535ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h == AVL_NULL) 536ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* No node in tree with given key. */ 537ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(AVL_NULL); 53890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 539ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = AVL_COMPARE_KEY_NODE(k, h); 54090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 541ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp == 0) 542ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Found node to remove. */ 543ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 54490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 545ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = h; 54690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 547ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp > 0) { 548ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_GREATER(h, 1); 549ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(branch, depth) 550ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 551ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_LESS(h, 1); 552ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(branch, depth) 55390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 55490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 555ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 556ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 557ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp_shortened_sub_with_path = cmp; 558ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 559ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 560ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang rm = h; 561ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent_rm = parent; 562ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang rm_depth = depth; 563ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 564ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* If the node to remove is not a leaf node, we need to get a 565ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** leaf node, or a node with a single leaf as its child, to put 566ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** in the place of the node to remove. We will get the greatest 567ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** node in the less subtree (of the node to remove), or the least 568ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** node in the greater subtree. We take the leaf node from the 569ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** deeper subtree, if there is one. */ 570ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 571ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (AVL_GET_BALANCE_FACTOR(h) < 0) { 572ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = AVL_GET_LESS(h, 1); 573ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(branch, depth) 574ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = -1; 575ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 576ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = AVL_GET_GREATER(h, 1); 577ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(branch, depth) 578ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = 1; 579ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 580ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 581ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 582ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 583ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 584ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (child != AVL_NULL) { 585ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = -cmp; 586ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 587ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang do { 588ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = h; 589ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = child; 590ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 591ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp < 0) { 59290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_LESS(h, 1); 59390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(branch, depth) 594ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 59590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_GREATER(h, 1); 59690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(branch, depth) 597ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 59890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 599ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 600ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 601ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } while (child != AVL_NULL); 60290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 603ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (parent == rm) 604ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Only went through do loop once. Deleted node will be replaced 605ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** in the tree structure by one of its immediate children. */ 606ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp_shortened_sub_with_path = -cmp; 607ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 608ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp_shortened_sub_with_path = cmp; 609ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 610ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Get the handle of the opposite child, which may not be null. */ 611ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0); 612ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 61390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 614ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (parent == AVL_NULL) 615ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* There were only 1 or 2 nodes in this tree. */ 616ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = child; 617ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else if (cmp_shortened_sub_with_path < 0) 618ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(parent, child) 619ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 620ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(parent, child) 621ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 622ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* "path" is the parent of the subtree being eliminated or reduced 623ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** from a depth of 2 to 1. If "path" is the node to be removed, we 624ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** set path to the node we're about to poke into the position of the 625ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** node to be removed. */ 626ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang path = parent == rm ? h : parent; 627ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 628ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h != rm) { 629ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Poke in the replacement for the node to be removed. */ 630ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(h, AVL_GET_LESS(rm, 0)) 631ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0)) 632ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm)) 633ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 634ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (parent_rm == AVL_NULL) 635ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = h; 636ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else { 637ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth = rm_depth - 1; 638ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 639ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (L_BIT_ARR_VAL(branch, depth)) 640ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(parent_rm, h) 64190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 642ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(parent_rm, h) 643ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 644ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 64590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 646ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (path != AVL_NULL) { 647ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Create a temporary linked list from the parent of the path node 648ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** to the root node. */ 649ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = l_tree->root; 650ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = AVL_NULL; 651ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth = 0; 65290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 653ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (h != path) { 654ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (L_BIT_ARR_VAL(branch, depth)) { 655ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = AVL_GET_GREATER(h, 1); 656ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, parent) 657ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 658ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = AVL_GET_LESS(h, 1); 659ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(h, parent) 660ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 661ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 662ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 663ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 664ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = h; 665ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = child; 66690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 66790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 668ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Climb from the path node to the root node using the linked 669ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** list, restoring the tree structure and rebalancing as necessary. 670ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang */ 671ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang reduced_depth = 1; 672ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = cmp_shortened_sub_with_path; 67390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 674ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for (;;) { 675ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (reduced_depth) { 676ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bf = AVL_GET_BALANCE_FACTOR(h); 677ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 678ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp < 0) 679ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bf++; 680ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else /* cmp > 0 */ 681ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bf--; 682ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 683ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if ((bf == -2) || (bf == 2)) { 684ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX h); 685ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 686ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bf = AVL_GET_BALANCE_FACTOR(h); 687ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else 688ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(h, bf) 689ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang reduced_depth = (bf == 0); 690ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 691ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 692ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (parent == AVL_NULL) 693ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 694ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 695ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = h; 696ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = parent; 697ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth--; 698ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 699ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 700ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp < 0) { 701ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = AVL_GET_LESS(h, 1); 702ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(h, child) 703ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 704ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = AVL_GET_GREATER(h, 1); 705ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, child) 706ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 70790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 708ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 70990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 71090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 711ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = h; 712ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 713ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 714ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(rm); 71590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 71690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 71790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 71890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 71990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_SUBST) 72090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 721ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(subst)(L_(avl) *l_tree, AVL_HANDLE new_node) { 722ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 723ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE parent = AVL_NULL; 724ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int cmp, last_cmp; 72590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 726ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Search for node already in tree with same key. */ 727ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for (;;) { 728ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h == AVL_NULL) 729ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* No node in tree with same key as new node. */ 730ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(AVL_NULL); 73190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 732ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = AVL_COMPARE_NODE_NODE(new_node, h); 73390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 734ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp == 0) 735ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Found the node to substitute new one for. */ 736ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 73790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 738ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang last_cmp = cmp; 739ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang parent = h; 740ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 741ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(AVL_NULL) 742ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 743ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 744ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Copy tree housekeeping fields from node in tree to new node. */ 745ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0)) 746ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0)) 747ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h)) 748ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 749ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (parent == AVL_NULL) 750ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* New node is also new root. */ 751ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = new_node; 752ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else { 753ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Make parent point to new node. */ 754ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (last_cmp < 0) 755ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(parent, new_node) 756ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 757ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(parent, new_node) 758ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 759ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 760ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(h); 76190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 76290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 76390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 76490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 76590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_BUILD_ITER_TYPE 76690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 76790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_BUILD) 76890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 76990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC int L_(build)( 770ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_(avl) *l_tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes) { 771ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Gives path to subtree being built. If bit n is false, branch 772ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** less from the node at depth n, if true branch greater. */ 773ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_DEFN(branch) 774ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 775ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* If bit n is true, then for the current subtree at depth n, its 776ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** greater subtree has one more node than its less subtree. */ 777ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_DEFN(rem) 778ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 779ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Depth of root node of current subtree. */ 780ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned depth = 0; 781ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 782ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Number of nodes in current subtree. */ 783ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_SIZE num_sub = num_nodes; 784ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 785ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* The algorithm relies on a stack of nodes whose less subtree has 786ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** been built, but whose greater subtree has not yet been built. 787ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** The stack is implemented as linked list. The nodes are linked 788ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** together by having the "greater" handle of a node set to the 789ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** next node in the list. "less_parent" is the handle of the first 790ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** node in the list. */ 791ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE less_parent = AVL_NULL; 792ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 793ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* h is root of current subtree, child is one of its children. */ 794ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h; 795ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE child; 796ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 797ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (num_nodes == 0) { 798ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = AVL_NULL; 799ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(1); 800ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 80190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 802ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for (;;) { 803ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (num_sub > 2) { 804ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Subtract one for root of subtree. */ 805ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang num_sub--; 80690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 807ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (num_sub & 1) 808ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(rem, depth) 809ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 810ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(rem, depth) 811ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(branch, depth) 812ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 81390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 814ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang num_sub >>= 1; 815ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 81690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 817ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (num_sub == 2) { 818ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Build a subtree with two nodes, slanting to greater. 819ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** I arbitrarily chose to always have the extra node in the 820ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** greater subtree when there is an odd number of nodes to 821ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** split between the two subtrees. */ 822ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 823ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_BUILD_ITER_VAL(p); 824ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(0) 825ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_BUILD_ITER_INCR(p) 826ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = AVL_BUILD_ITER_VAL(p); 827ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(0) 828ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_BUILD_ITER_INCR(p) 829ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(child, AVL_NULL) 830ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(child, AVL_NULL) 831ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(child, 0) 832ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, child) 833ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(h, AVL_NULL) 834ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(h, 1) 835ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { /* num_sub == 1 */ 836ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Build a subtree with one node. */ 837ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 838ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_BUILD_ITER_VAL(p); 839ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(0) 840ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_BUILD_ITER_INCR(p) 841ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(h, AVL_NULL) 842ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, AVL_NULL) 843ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(h, 0) 84490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 84590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 846ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (depth) { 847ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth--; 848ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 849ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (!L_BIT_ARR_VAL(branch, depth)) 850ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* We've completed a less subtree. */ 851ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 852ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 853ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* We've completed a greater subtree, so attach it to 854ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** its parent (that is less than it). We pop the parent 855ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** off the stack of less parents. */ 856ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = h; 857ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = less_parent; 858ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang less_parent = AVL_GET_GREATER(h, 1); 859ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(0) 860ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, child) 861ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */ 862ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang num_sub <<= 1; 863ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang num_sub += L_BIT_ARR_VAL(rem, depth) ? 0 : 1; 864ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 865ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (num_sub & (num_sub - 1)) 866ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* num_sub is not a power of 2. */ 867ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(h, 0) 868ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 869ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* num_sub is a power of 2. */ 870ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_BALANCE_FACTOR(h, 1) 87190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 87290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 873ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (num_sub == num_nodes) 874ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* We've completed the full tree. */ 875ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 87690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 877ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* The subtree we've completed is the less subtree of the 878ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** next node in the sequence. */ 87990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 880ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang child = h; 881ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_BUILD_ITER_VAL(p); 882ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR(0) 883ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_BUILD_ITER_INCR(p) 884ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_LESS(h, child) 88590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 886ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Put h into stack of less parents. */ 887ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_SET_GREATER(h, less_parent) 888ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang less_parent = h; 88990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 890ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Proceed to creating greater than subtree of h. */ 891ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(branch, depth) 892ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang num_sub += L_BIT_ARR_VAL(rem, depth) ? 1 : 0; 893ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang depth++; 89490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 895ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } /* end for (;; ) */ 89690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 897ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang l_tree->root = h; 898ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 899ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(1); 90090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 90190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 90290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 90390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 90490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 90590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 90690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_INIT_ITER) 90790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 90890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Initialize depth to invalid value, to indicate iterator is 90990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** invalid. (Depth is zero-base.) It's not necessary to initialize 91090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** iterators prior to passing them to the "start" function. 91190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 912ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC void L_(init_iter)(L_(iter) *iter) { 913ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = ~0; 91490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 91590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 91690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 91790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 91890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_READ_ERRORS_HAPPEN 91990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 92090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR_INV_DEPTH \ 921ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang { if (AVL_READ_ERROR) { iter->depth = ~0; return; } } 92290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 92390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 92490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 92590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR_INV_DEPTH 92690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 92790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 92890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 92990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_START_ITER) 93090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 93190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(start_iter)( 932ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_(avl) *l_tree, L_(iter) *iter, AVL_KEY k, avl_search_type st) { 933ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 934ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned d = 0; 935ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int cmp, target_cmp; 936ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 937ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Save the tree that we're going to iterate through in a 938ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** member variable. */ 939ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->tree_ = l_tree; 940ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 941ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = ~0; 942ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 943ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h == AVL_NULL) 944ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Tree is empty. */ 945ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return; 946ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 947ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (st & AVL_LESS) 948ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Key can be greater than key of starting node. */ 949ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang target_cmp = 1; 950ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else if (st & AVL_GREATER) 951ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Key can be less than key of starting node. */ 952ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang target_cmp = -1; 953ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 954ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Key must be same as key of starting node. */ 955ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang target_cmp = 0; 956ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 957ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for (;;) { 958ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = AVL_COMPARE_KEY_NODE(k, h); 959ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 960ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp == 0) { 961ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (st & AVL_EQUAL) { 962ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Equal node was sought and found as starting node. */ 963ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = d; 964ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 965ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 966ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 967ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang cmp = -target_cmp; 968ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else if (target_cmp != 0) 969ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 970ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* cmp and target_cmp are both negative or both positive. */ 971ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = d; 972ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 973ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 974ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR_INV_DEPTH 97590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 97690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 977ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 978ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 979ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (cmp > 0) 980ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(iter->branch, d) 981ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 982ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(iter->branch, d) 983ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->path_h[d++] = h; 984ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 98590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 98690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 98790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 98890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 98990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_START_ITER_LEAST) 99090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 991ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC void L_(start_iter_least)(L_(avl) *l_tree, L_(iter) *iter) { 992ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 99390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 994ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->tree_ = l_tree; 99590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 996ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = ~0; 99790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 998ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_ALL(iter->branch, 0) 99990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1000ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (h != AVL_NULL) { 1001ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (iter->depth != ~0) 1002ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->path_h[iter->depth] = h; 100390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1004ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth++; 1005ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_LESS(h, 1); 1006ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR_INV_DEPTH 1007ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 100890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 100990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 101090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 101190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 101290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_START_ITER_GREATEST) 101390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1014ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC void L_(start_iter_greatest)(L_(avl) *l_tree, L_(iter) *iter) { 1015ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = l_tree->root; 101690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1017ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->tree_ = l_tree; 101890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1019ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = ~0; 102090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1021ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_ALL(iter->branch, 1) 102290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1023ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang while (h != AVL_NULL) { 1024ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (iter->depth != ~0) 1025ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->path_h[iter->depth] = h; 102690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1027ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth++; 1028ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_GREATER(h, 1); 1029ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR_INV_DEPTH 1030ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 103190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 103290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 103390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 103490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 103590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_GET_ITER) 103690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1037ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter) { 1038ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (iter->depth == ~0) 1039ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(AVL_NULL); 104090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1041ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return(iter->depth == 0 ? 1042ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->tree_->root : iter->path_h[iter->depth - 1]); 104390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 104490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 104590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 104690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 104790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_INCR_ITER) 104890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1049ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC void L_(incr_iter)(L_(iter) *iter) { 105090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define l_tree (iter->tree_) 105190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1052ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (iter->depth != ~0) { 1053ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = 1054ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_GET_GREATER((iter->depth == 0 ? 1055ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 1056ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR_INV_DEPTH 105790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1058ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h == AVL_NULL) 1059ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang do { 1060ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (iter->depth == 0) { 1061ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = ~0; 1062ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 1063ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 106490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1065ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth--; 1066ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } while (L_BIT_ARR_VAL(iter->branch, iter->depth)); 1067ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else { 1068ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(iter->branch, iter->depth) 1069ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->path_h[iter->depth++] = h; 107090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1071ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for (;;) { 1072ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_LESS(h, 1); 1073ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR_INV_DEPTH 107490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1075ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h == AVL_NULL) 1076ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 1077ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 1078ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(iter->branch, iter->depth) 1079ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->path_h[iter->depth++] = h; 1080ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 108190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 1082ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 108390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 108490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef l_tree 108590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 108690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 108790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 108890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 108990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_DECR_ITER) 109090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1091ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangL_SC void L_(decr_iter)(L_(iter) *iter) { 109290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define l_tree (iter->tree_) 109390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1094ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (iter->depth != ~0) { 1095ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_HANDLE h = 1096ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AVL_GET_LESS((iter->depth == 0 ? 1097ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 1098ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR_INV_DEPTH 109990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1100ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h == AVL_NULL) 1101ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang do { 1102ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (iter->depth == 0) { 1103ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth = ~0; 1104ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 1105ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 110690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1107ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->depth--; 1108ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } while (!L_BIT_ARR_VAL(iter->branch, iter->depth)); 1109ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else { 1110ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_0(iter->branch, iter->depth) 1111ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->path_h[iter->depth++] = h; 111290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1113ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for (;;) { 1114ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang h = AVL_GET_GREATER(h, 1); 1115ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_CHECK_READ_ERROR_INV_DEPTH 111690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1117ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (h == AVL_NULL) 1118ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang break; 1119ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 1120ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang L_BIT_ARR_1(iter->branch, iter->depth) 1121ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang iter->path_h[iter->depth++] = h; 1122ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 112390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 1124ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 112590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 112690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef l_tree 112790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 112890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 112990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 113090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 113190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Tidy up the preprocessor symbol name space. */ 113290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_ 113390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_EST_LONG_BIT 113490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SIZE 113590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_MASK_HIGH_BIT 113690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_LONG_BIT 113790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_DEFN 113890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_VAL 113990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_0 114090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_1 114190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_ALL 114290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR 114390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR_INV_DEPTH 114490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_LONGS 114590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_IMPL_MASK 114690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR 114790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR_INV_DEPTH 114890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SC 114990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BALANCE_PARAM_CALL_PREFIX 115090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BALANCE_PARAM_DECL_PREFIX 1151b08e2e23eec181e9951df33cd704ac294c5407b6Vignesh Venkatasubramanian 1152b08e2e23eec181e9951df33cd704ac294c5407b6Vignesh Venkatasubramanian#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_ 1153