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 1190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Abstract AVL Tree Generic C Package. 1390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** Implementation generation header file. 1490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** 1590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** This code is in the public domain. See cavl_tree.html for interface 1690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** documentation. 1790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** 1890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** Version: 1.5 Author: Walt Karas 1990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 2090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_ 2290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_EST_LONG_BIT 2390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SIZE 2490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef l_tree 2590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_MASK_HIGH_BIT 2690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_LONG_BIT 2790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_DEFN 2890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_VAL 2990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_0 3090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_1 3190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_ALL 3290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_LONGS 3390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_IMPL_MASK 3490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR 3590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR_INV_DEPTH 3690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SC 3790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BALANCE_PARAM_PREFIX 3890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 3990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_UNIQUE 4090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_ AVL_UNIQUE 4290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 4490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_(X) X 4690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 4890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Determine correct storage class for functions */ 5090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_PRIVATE 5190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SC static 5390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 5590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SC 5790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 5990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_SIZE 6190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SIZE AVL_SIZE 6390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 6590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_SIZE unsigned long 6790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 6990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_MASK_HIGH_BIT ((int) ~ ((~ (unsigned) 0) >> 1)) 7190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* ANSI C/ISO C++ require that a long have at least 32 bits. Set 7390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** L_EST_LONG_BIT to be the greatest multiple of 8 in the range 7490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** 32 - 64 (inclusive) that is less than or equal to the number of 7590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** bits in a long. 7690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 7790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (((LONG_MAX >> 31) >> 7) == 0) 7990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 32 8190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif (((LONG_MAX >> 31) >> 15) == 0) 8390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 40 8590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif (((LONG_MAX >> 31) >> 23) == 0) 8790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 48 8990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif (((LONG_MAX >> 31) >> 31) == 0) 9190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 56 9390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 9590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_EST_LONG_BIT 64 9790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 9990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_LONG_BIT (sizeof(long) * CHAR_BIT) 10190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT) 10390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* The maximum depth may be greater than the number of bits in a long, 10590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** so multiple longs are needed to hold a bit array indexed by node 10690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** depth. */ 10790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_LONGS (((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT) 10990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_DEFN(NAME) unsigned long NAME[L_BIT_ARR_LONGS]; 11190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) \ 11390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ((BIT_ARR)[(BIT_NUM) / L_LONG_BIT] & (1L << ((BIT_NUM) % L_LONG_BIT))) 11490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) \ 11690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] &= ~(1L << ((BIT_NUM) % L_LONG_BIT)); 11790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) \ 11990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] |= 1L << ((BIT_NUM) % L_LONG_BIT); 12090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) \ 12290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { int i = L_BIT_ARR_LONGS; do (BIT_ARR)[--i] = 0L - (BIT_VAL); while(i); } 12390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else /* The bit array can definitely fit in one long */ 12590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_DEFN(NAME) unsigned long NAME; 12790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) ((BIT_ARR) & (1L << (BIT_NUM))) 12990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_0(BIT_ARR, BIT_NUM) (BIT_ARR) &= ~(1L << (BIT_NUM)); 13190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_1(BIT_ARR, BIT_NUM) (BIT_ARR) |= 1L << (BIT_NUM); 13390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) (BIT_ARR) = 0L - (BIT_VAL); 13590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 13790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_READ_ERRORS_HAPPEN 13990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR(ERROR_RETURN) \ 14190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { if (AVL_READ_ERROR) return(ERROR_RETURN); } 14290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 14490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR(ERROR_RETURN) 14690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 14890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* The presumed reason that an instantiation places additional fields 15090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** inside the AVL tree structure is that the SET_ and GET_ macros 15190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** need these fields. The "balance" function does not explicitly use 15290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** any fields in the AVL tree structure, so only pass an AVL tree 15390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** structure pointer to "balance" if it has instantiation-specific 15490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** fields that are (presumably) needed by the SET_/GET_ calls within 15590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** "balance". 15690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 15790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_INSIDE_STRUCT 15890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 15990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_CALL_PREFIX l_tree, 16090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_DECL_PREFIX L_(avl) *l_tree, 16190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 16390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_CALL_PREFIX 16590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_BALANCE_PARAM_DECL_PREFIX 16690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 16890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 16990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_IMPL_MASK 17090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_IMPL_MASK (AVL_IMPL_MASK) 17290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 17490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Define all functions. */ 17690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_IMPL_MASK AVL_IMPL_ALL 17790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 17890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 17990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_INIT) 18190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(init)(L_(avl) *l_tree) 18390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 18490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = AVL_NULL; 18590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 18690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 18890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_IS_EMPTY) 19090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 19190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC int L_(is_empty)(L_(avl) *l_tree) 19290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 19390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 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*/ 20490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h) 20590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 20690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE deep_h; 20790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 20890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Either the "greater than" or the "less than" subtree of 20990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** this node has to be 2 levels deeper (or else it wouldn't 21090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** need balancing). 21190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber */ 21290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (AVL_GET_BALANCE_FACTOR(bal_h) > 0) 21390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 21490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* "Greater than" subtree is deeper. */ 21590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 21690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber deep_h = AVL_GET_GREATER(bal_h, 1); 21790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 21890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 21990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 22090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (AVL_GET_BALANCE_FACTOR(deep_h) < 0) 22190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 22290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int bf; 22390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 22490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE old_h = bal_h; 22590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bal_h = AVL_GET_LESS(deep_h, 1); 22690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 22790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1)) 22890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1)) 22990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(bal_h, old_h) 23090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(bal_h, deep_h) 23190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 23290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bf = AVL_GET_BALANCE_FACTOR(bal_h); 23390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 23490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (bf != 0) 23590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 23690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (bf > 0) 23790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 23890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(old_h, -1) 23990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 0) 24090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 24190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 24290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 24390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 1) 24490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(old_h, 0) 24590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 24690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 24790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(bal_h, 0) 24890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 24990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 25090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 25190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(old_h, 0) 25290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 0) 25390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 25490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 25590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 25690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 25790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0)) 25890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(deep_h, bal_h) 25990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 26090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) 26190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 26290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, -1) 26390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(bal_h, 1) 26490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 26590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 26690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 26790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 0) 26890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(bal_h, 0) 26990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 27090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 27190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bal_h = deep_h; 27290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 27390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 27490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 27590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 27690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* "Less than" subtree is deeper. */ 27790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 27890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber deep_h = AVL_GET_LESS(bal_h, 1); 27990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 28090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 28190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (AVL_GET_BALANCE_FACTOR(deep_h) > 0) 28290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 28390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int bf; 28490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE old_h = bal_h; 28590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bal_h = AVL_GET_GREATER(deep_h, 1); 28690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 28790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0)) 28890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0)) 28990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(bal_h, old_h) 29090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(bal_h, deep_h) 29190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 29290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bf = AVL_GET_BALANCE_FACTOR(bal_h); 29390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 29490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (bf != 0) 29590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 29690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (bf < 0) 29790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 29890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(old_h, 1) 29990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 0) 30090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 30190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 30290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 30390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, -1) 30490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(old_h, 0) 30590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 30690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 30790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(bal_h, 0) 30890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 30990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 31090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 31190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(old_h, 0) 31290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 0) 31390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 31490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 31590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 31690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 31790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0)) 31890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(deep_h, bal_h) 31990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 32090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) 32190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 32290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 1) 32390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(bal_h, -1) 32490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 32590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 32690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 32790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(deep_h, 0) 32890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(bal_h, 0) 32990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 33090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 33190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bal_h = deep_h; 33290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 33390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 33490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 33590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(bal_h); 33690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 33790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 33890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(insert)(L_(avl) *l_tree, AVL_HANDLE h) 33990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 34090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(h, AVL_NULL) 34190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, AVL_NULL) 34290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(h, 0) 34390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 34490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (l_tree->root == AVL_NULL) 34590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = h; 34690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 34790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 34890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Last unbalanced node encountered in search for insertion point. */ 34990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE unbal = AVL_NULL; 35090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Parent of last unbalanced node. */ 35190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE parent_unbal = AVL_NULL; 35290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Balance factor of last unbalanced node. */ 35390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int unbal_bf; 35490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 35590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Zero-based depth in tree. */ 35690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unsigned depth = 0, unbal_depth = 0; 35790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 35890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Records a path into the tree. If bit n is true, indicates 35990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** take greater branch from the nth node in the path, otherwise 36090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** take the less branch. bit 0 gives branch from root, and 36190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** so on. */ 36290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_DEFN(branch) 36390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 36490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE hh = l_tree->root; 36590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE parent = AVL_NULL; 36690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int cmp; 36790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 36890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber do 36990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 37090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (AVL_GET_BALANCE_FACTOR(hh) != 0) 37190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 37290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unbal = hh; 37390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent_unbal = parent; 37490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unbal_depth = depth; 37590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 37690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 37790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = AVL_COMPARE_NODE_NODE(h, hh); 37890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 37990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp == 0) 38090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Duplicate key. */ 38190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(hh); 38290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 38390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = hh; 38490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 38590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp > 0) 38690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 38790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber hh = AVL_GET_GREATER(hh, 1); 38890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(branch, depth) 38990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 39090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 39190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 39290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber hh = AVL_GET_LESS(hh, 1); 39390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(branch, depth) 39490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 39590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 39690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 39790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 39890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 39990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (hh != AVL_NULL); 40090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 40190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Add node to insert as leaf of tree. */ 40290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp < 0) 40390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(parent, h) 40490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 40590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(parent, h) 40690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 40790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth = unbal_depth; 40890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 40990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (unbal == AVL_NULL) 41090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber hh = l_tree->root; 41190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 41290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 41390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 41490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 41590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unbal_bf = AVL_GET_BALANCE_FACTOR(unbal); 41690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 41790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp < 0) 41890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unbal_bf--; 41990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else /* cmp > 0 */ 42090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unbal_bf++; 42190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 42290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1); 42390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 42490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 42590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if ((unbal_bf != -2) && (unbal_bf != 2)) 42690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 42790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* No rebalancing of tree is necessary. */ 42890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(unbal, unbal_bf) 42990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unbal = AVL_NULL; 43090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 43190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 43290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 43390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (hh != AVL_NULL) 43490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (h != hh) 43590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 43690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 43790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 43890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 43990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp < 0) 44090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 44190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(hh, -1) 44290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber hh = AVL_GET_LESS(hh, 1); 44390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 44490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else /* cmp > 0 */ 44590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 44690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(hh, 1) 44790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber hh = AVL_GET_GREATER(hh, 1); 44890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 44990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 45090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 45190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 45290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 45390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (unbal != AVL_NULL) 45490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 45590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unbal = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX unbal); 45690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 45790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 45890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (parent_unbal == AVL_NULL) 45990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = unbal; 46090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 46190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 46290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth = unbal_depth - 1; 46390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 46490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 46590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp < 0) 46690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(parent_unbal, unbal) 46790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else /* cmp > 0 */ 46890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(parent_unbal, unbal) 46990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 47090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 47190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 47290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 47390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 47490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(h); 47590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 47690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 47790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 47890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 47990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_SEARCH) 48090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 48190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(search)(L_(avl) *l_tree, AVL_KEY k, avl_search_type st) 48290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 48390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int cmp, target_cmp; 48490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE match_h = AVL_NULL; 48590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 48690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 48790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (st & AVL_LESS) 48890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber target_cmp = 1; 48990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else if (st & AVL_GREATER) 49090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber target_cmp = -1; 49190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 49290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber target_cmp = 0; 49390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 49490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (h != AVL_NULL) 49590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 49690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = AVL_COMPARE_KEY_NODE(k, h); 49790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 49890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp == 0) 49990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 50090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (st & AVL_EQUAL) 50190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 50290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber match_h = h; 50390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 50490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 50590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 50690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = -target_cmp; 50790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 50890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else if (target_cmp != 0) 50990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 51090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* cmp and target_cmp are both positive or both negative. */ 51190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber match_h = h; 51290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 51390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 51490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 51590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 51690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 51790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(match_h); 51890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 51990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 52090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 52190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 52290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_SEARCH_LEAST) 52390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 52490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(search_least)(L_(avl) *l_tree) 52590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 52690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 52790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE parent = AVL_NULL; 52890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 52990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (h != AVL_NULL) 53090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 53190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = h; 53290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_LESS(h, 1); 53390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 53490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 53590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 53690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(parent); 53790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 53890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 53990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 54090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 54190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_SEARCH_GREATEST) 54290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 54390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(search_greatest)(L_(avl) *l_tree) 54490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 54590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 54690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE parent = AVL_NULL; 54790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 54890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (h != AVL_NULL) 54990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 55090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = h; 55190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_GREATER(h, 1); 55290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 55390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 55490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 55590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(parent); 55690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 55790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 55890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 55990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 56090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_REMOVE) 56190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 56290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Prototype of balance function (called by remove) in case not in 56390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** same compilation unit. 56490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 56590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h); 56690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 56790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(remove)(L_(avl) *l_tree, AVL_KEY k) 56890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 56990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Zero-based depth in tree. */ 57090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unsigned depth = 0, rm_depth; 57190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 57290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Records a path into the tree. If bit n is true, indicates 57390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** take greater branch from the nth node in the path, otherwise 57490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** take the less branch. bit 0 gives branch from root, and 57590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** so on. */ 57690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_DEFN(branch) 57790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 57890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 57990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE parent = AVL_NULL; 58090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE child; 58190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE path; 58290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int cmp, cmp_shortened_sub_with_path; 58390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int reduced_depth; 58490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int bf; 58590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE rm; 58690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE parent_rm; 58790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 58890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (; ;) 58990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 59090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 59190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* No node in tree with given key. */ 59290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(AVL_NULL); 59390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 59490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = AVL_COMPARE_KEY_NODE(k, h); 59590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 59690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp == 0) 59790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Found node to remove. */ 59890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 59990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 60090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = h; 60190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 60290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp > 0) 60390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 60490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_GREATER(h, 1); 60590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(branch, depth) 60690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 60790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 60890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 60990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_LESS(h, 1); 61090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(branch, depth) 61190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 61290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 61390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 61490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 61590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp_shortened_sub_with_path = cmp; 61690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 61790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 61890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber rm = h; 61990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent_rm = parent; 62090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber rm_depth = depth; 62190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 62290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* If the node to remove is not a leaf node, we need to get a 62390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** leaf node, or a node with a single leaf as its child, to put 62490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** in the place of the node to remove. We will get the greatest 62590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** node in the less subtree (of the node to remove), or the least 62690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** node in the greater subtree. We take the leaf node from the 62790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** deeper subtree, if there is one. */ 62890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 62990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (AVL_GET_BALANCE_FACTOR(h) < 0) 63090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 63190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_LESS(h, 1); 63290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(branch, depth) 63390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = -1; 63490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 63590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 63690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 63790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_GREATER(h, 1); 63890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(branch, depth) 63990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = 1; 64090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 64190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 64290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 64390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 64490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 64590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (child != AVL_NULL) 64690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 64790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = -cmp; 64890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 64990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber do 65090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 65190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = h; 65290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = child; 65390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 65490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp < 0) 65590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 65690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_LESS(h, 1); 65790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(branch, depth) 65890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 65990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 66090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 66190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_GREATER(h, 1); 66290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(branch, depth) 66390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 66490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 66590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 66690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 66790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 66890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (child != AVL_NULL); 66990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 67090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (parent == rm) 67190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Only went through do loop once. Deleted node will be replaced 67290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** in the tree structure by one of its immediate children. */ 67390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp_shortened_sub_with_path = -cmp; 67490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 67590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp_shortened_sub_with_path = cmp; 67690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 67790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Get the handle of the opposite child, which may not be null. */ 67890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0); 67990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 68090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 68190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (parent == AVL_NULL) 68290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* There were only 1 or 2 nodes in this tree. */ 68390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = child; 68490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else if (cmp_shortened_sub_with_path < 0) 68590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(parent, child) 68690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 68790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(parent, child) 68890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 68990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* "path" is the parent of the subtree being eliminated or reduced 69090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** from a depth of 2 to 1. If "path" is the node to be removed, we 69190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** set path to the node we're about to poke into the position of the 69290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** node to be removed. */ 69390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber path = parent == rm ? h : parent; 69490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 69590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h != rm) 69690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 69790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Poke in the replacement for the node to be removed. */ 69890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(h, AVL_GET_LESS(rm, 0)) 69990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0)) 70090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm)) 70190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 70290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (parent_rm == AVL_NULL) 70390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = h; 70490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 70590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 70690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth = rm_depth - 1; 70790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 70890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (L_BIT_ARR_VAL(branch, depth)) 70990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(parent_rm, h) 71090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 71190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(parent_rm, h) 71290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 71390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 71490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 71590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (path != AVL_NULL) 71690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 71790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Create a temporary linked list from the parent of the path node 71890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** to the root node. */ 71990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = l_tree->root; 72090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = AVL_NULL; 72190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth = 0; 72290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 72390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (h != path) 72490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 72590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (L_BIT_ARR_VAL(branch, depth)) 72690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 72790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_GREATER(h, 1); 72890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, parent) 72990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 73090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 73190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 73290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_GET_LESS(h, 1); 73390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(h, parent) 73490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 73590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 73690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 73790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 73890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = h; 73990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = child; 74090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 74190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 74290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Climb from the path node to the root node using the linked 74390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** list, restoring the tree structure and rebalancing as necessary. 74490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber */ 74590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber reduced_depth = 1; 74690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = cmp_shortened_sub_with_path; 74790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 74890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (; ;) 74990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 75090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (reduced_depth) 75190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 75290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bf = AVL_GET_BALANCE_FACTOR(h); 75390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 75490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp < 0) 75590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bf++; 75690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else /* cmp > 0 */ 75790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bf--; 75890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 75990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if ((bf == -2) || (bf == 2)) 76090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 76190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX h); 76290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 76390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber bf = AVL_GET_BALANCE_FACTOR(h); 76490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 76590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 76690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(h, bf) 76790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber reduced_depth = (bf == 0); 76890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 76990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 77090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (parent == AVL_NULL) 77190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 77290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 77390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = h; 77490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = parent; 77590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth--; 77690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1; 77790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 77890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp < 0) 77990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 78090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = AVL_GET_LESS(h, 1); 78190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(h, child) 78290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 78390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 78490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 78590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = AVL_GET_GREATER(h, 1); 78690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, child) 78790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 78890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 78990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 79090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 79190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 79290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = h; 79390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 79490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 79590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(rm); 79690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 79790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 79890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 79990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 80090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_SUBST) 80190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 80290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(subst)(L_(avl) *l_tree, AVL_HANDLE new_node) 80390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 80490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 80590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE parent = AVL_NULL; 80690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int cmp, last_cmp; 80790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 80890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Search for node already in tree with same key. */ 80990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (; ;) 81090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 81190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 81290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* No node in tree with same key as new node. */ 81390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(AVL_NULL); 81490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 81590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = AVL_COMPARE_NODE_NODE(new_node, h); 81690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 81790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp == 0) 81890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Found the node to substitute new one for. */ 81990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 82090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 82190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber last_cmp = cmp; 82290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber parent = h; 82390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 82490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(AVL_NULL) 82590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 82690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 82790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Copy tree housekeeping fields from node in tree to new node. */ 82890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0)) 82990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0)) 83090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h)) 83190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 83290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (parent == AVL_NULL) 83390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* New node is also new root. */ 83490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = new_node; 83590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 83690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 83790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Make parent point to new node. */ 83890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (last_cmp < 0) 83990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(parent, new_node) 84090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 84190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(parent, new_node) 84290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 84390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 84490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(h); 84590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 84690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 84790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 84890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 84990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_BUILD_ITER_TYPE 85090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 85190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_BUILD) 85290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 85390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC int L_(build)( 85490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_(avl) *l_tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes) 85590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 85690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Gives path to subtree being built. If bit n is false, branch 85790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** less from the node at depth n, if true branch greater. */ 85890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_DEFN(branch) 85990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 86090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* If bit n is true, then for the current subtree at depth n, its 86190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** greater subtree has one more node than its less subtree. */ 86290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_DEFN(rem) 86390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 86490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Depth of root node of current subtree. */ 86590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unsigned depth = 0; 86690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 86790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Number of nodes in current subtree. */ 86890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_SIZE num_sub = num_nodes; 86990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 87090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* The algorithm relies on a stack of nodes whose less subtree has 87190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** been built, but whose greater subtree has not yet been built. 87290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** The stack is implemented as linked list. The nodes are linked 87390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** together by having the "greater" handle of a node set to the 87490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** next node in the list. "less_parent" is the handle of the first 87590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** node in the list. */ 87690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE less_parent = AVL_NULL; 87790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 87890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* h is root of current subtree, child is one of its children. */ 87990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h; 88090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE child; 88190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 88290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (num_nodes == 0) 88390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 88490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = AVL_NULL; 88590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(1); 88690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 88790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 88890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (; ;) 88990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 89090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (num_sub > 2) 89190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 89290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Subtract one for root of subtree. */ 89390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber num_sub--; 89490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 89590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (num_sub & 1) 89690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(rem, depth) 89790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 89890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(rem, depth) 89990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(branch, depth) 90090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 90190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 90290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber num_sub >>= 1; 90390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 90490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 90590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (num_sub == 2) 90690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 90790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Build a subtree with two nodes, slanting to greater. 90890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** I arbitrarily chose to always have the extra node in the 90990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** greater subtree when there is an odd number of nodes to 91090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** split between the two subtrees. */ 91190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 91290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_BUILD_ITER_VAL(p); 91390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(0) 91490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_BUILD_ITER_INCR(p) 91590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = AVL_BUILD_ITER_VAL(p); 91690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(0) 91790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_BUILD_ITER_INCR(p) 91890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(child, AVL_NULL) 91990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(child, AVL_NULL) 92090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(child, 0) 92190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, child) 92290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(h, AVL_NULL) 92390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(h, 1) 92490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 92590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else /* num_sub == 1 */ 92690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 92790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Build a subtree with one node. */ 92890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 92990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_BUILD_ITER_VAL(p); 93090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(0) 93190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_BUILD_ITER_INCR(p) 93290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(h, AVL_NULL) 93390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, AVL_NULL) 93490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(h, 0) 93590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 93690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 93790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (depth) 93890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 93990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth--; 94090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 94190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (!L_BIT_ARR_VAL(branch, depth)) 94290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* We've completed a less subtree. */ 94390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 94490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 94590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* We've completed a greater subtree, so attach it to 94690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** its parent (that is less than it). We pop the parent 94790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** off the stack of less parents. */ 94890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = h; 94990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = less_parent; 95090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber less_parent = AVL_GET_GREATER(h, 1); 95190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(0) 95290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, child) 95390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */ 95490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber num_sub <<= 1; 95590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber num_sub += L_BIT_ARR_VAL(rem, depth) ? 0 : 1; 95690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 95790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (num_sub & (num_sub - 1)) 95890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* num_sub is not a power of 2. */ 95990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(h, 0) 96090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 96190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* num_sub is a power of 2. */ 96290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_BALANCE_FACTOR(h, 1) 96390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 96490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 96590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (num_sub == num_nodes) 96690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* We've completed the full tree. */ 96790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 96890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 96990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* The subtree we've completed is the less subtree of the 97090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** next node in the sequence. */ 97190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 97290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber child = h; 97390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_BUILD_ITER_VAL(p); 97490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR(0) 97590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_BUILD_ITER_INCR(p) 97690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_LESS(h, child) 97790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 97890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Put h into stack of less parents. */ 97990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_SET_GREATER(h, less_parent) 98090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber less_parent = h; 98190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 98290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Proceed to creating greater than subtree of h. */ 98390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(branch, depth) 98490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber num_sub += L_BIT_ARR_VAL(rem, depth) ? 1 : 0; 98590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber depth++; 98690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 98790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } /* end for ( ; ; ) */ 98890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 98990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber l_tree->root = h; 99090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 99190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(1); 99290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 99390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 99490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 99590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 99690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 99790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 99890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_INIT_ITER) 99990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 100090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Initialize depth to invalid value, to indicate iterator is 100190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** invalid. (Depth is zero-base.) It's not necessary to initialize 100290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** iterators prior to passing them to the "start" function. 100390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 100490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(init_iter)(L_(iter) *iter) 100590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 100690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = ~0; 100790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 100890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 100990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 101090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 101190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef AVL_READ_ERRORS_HAPPEN 101290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 101390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR_INV_DEPTH \ 101490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { if (AVL_READ_ERROR) { iter->depth = ~0; return; } } 101590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 101690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#else 101790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 101890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define L_CHECK_READ_ERROR_INV_DEPTH 101990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 102090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 102190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 102290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_START_ITER) 102390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 102490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(start_iter)( 102590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_(avl) *l_tree, L_(iter) *iter, AVL_KEY k, avl_search_type st) 102690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 102790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 102890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber unsigned d = 0; 102990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber int cmp, target_cmp; 103090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 103190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Save the tree that we're going to iterate through in a 103290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** member variable. */ 103390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->tree_ = l_tree; 103490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 103590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = ~0; 103690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 103790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 103890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Tree is empty. */ 103990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return; 104090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 104190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (st & AVL_LESS) 104290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Key can be greater than key of starting node. */ 104390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber target_cmp = 1; 104490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else if (st & AVL_GREATER) 104590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Key can be less than key of starting node. */ 104690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber target_cmp = -1; 104790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 104890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Key must be same as key of starting node. */ 104990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber target_cmp = 0; 105090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 105190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (; ;) 105290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 105390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = AVL_COMPARE_KEY_NODE(k, h); 105490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 105590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp == 0) 105690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 105790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (st & AVL_EQUAL) 105890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 105990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Equal node was sought and found as starting node. */ 106090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = d; 106190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 106290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 106390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 106490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber cmp = -target_cmp; 106590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 106690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else if (target_cmp != 0) 106790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT)) 106890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* cmp and target_cmp are both negative or both positive. */ 106990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = d; 107090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 107190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1); 107290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR_INV_DEPTH 107390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 107490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 107590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 107690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 107790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (cmp > 0) 107890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(iter->branch, d) 107990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 108090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(iter->branch, d) 108190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->path_h[d++] = h; 108290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 108390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 108490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 108590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 108690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 108790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_START_ITER_LEAST) 108890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 108990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(start_iter_least)(L_(avl) *l_tree, L_(iter) *iter) 109090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 109190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 109290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 109390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->tree_ = l_tree; 109490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 109590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = ~0; 109690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 109790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_ALL(iter->branch, 0) 109890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 109990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (h != AVL_NULL) 110090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 110190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (iter->depth != ~0) 110290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->path_h[iter->depth] = h; 110390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 110490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth++; 110590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_LESS(h, 1); 110690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR_INV_DEPTH 110790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 110890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 110990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 111090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 111190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 111290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_START_ITER_GREATEST) 111390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 111490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(start_iter_greatest)(L_(avl) *l_tree, L_(iter) *iter) 111590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 111690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = l_tree->root; 111790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 111890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->tree_ = l_tree; 111990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 112090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = ~0; 112190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 112290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_ALL(iter->branch, 1) 112390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 112490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (h != AVL_NULL) 112590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 112690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (iter->depth != ~0) 112790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->path_h[iter->depth] = h; 112890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 112990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth++; 113090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_GREATER(h, 1); 113190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR_INV_DEPTH 113290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 113390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 113490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 113590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 113690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 113790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_GET_ITER) 113890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 113990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter) 114090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 114190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (iter->depth == ~0) 114290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(AVL_NULL); 114390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 114490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber return(iter->depth == 0 ? 114590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->tree_->root : iter->path_h[iter->depth - 1]); 114690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 114790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 114890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 114990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 115090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_INCR_ITER) 115190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 115290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(incr_iter)(L_(iter) *iter) 115390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 115490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define l_tree (iter->tree_) 115590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 115690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (iter->depth != ~0) 115790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 115890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = 115990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_GET_GREATER((iter->depth == 0 ? 116090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 116190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR_INV_DEPTH 116290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 116390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 116490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber do 116590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 116690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (iter->depth == 0) 116790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 116890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = ~0; 116990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 117090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 117190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 117290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth--; 117390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 117490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (L_BIT_ARR_VAL(iter->branch, iter->depth)); 117590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 117690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 117790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(iter->branch, iter->depth) 117890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->path_h[iter->depth++] = h; 117990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 118090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (; ;) 118190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 118290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_LESS(h, 1); 118390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR_INV_DEPTH 118490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 118590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 118690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 118790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 118890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(iter->branch, iter->depth) 118990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->path_h[iter->depth++] = h; 119090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 119190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 119290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 119390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 119490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef l_tree 119590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 119690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 119790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 119890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 119990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#if (L_IMPL_MASK & AVL_IMPL_DECR_ITER) 120090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 120190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberL_SC void L_(decr_iter)(L_(iter) *iter) 120290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 120390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define l_tree (iter->tree_) 120490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 120590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (iter->depth != ~0) 120690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 120790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_HANDLE h = 120890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber AVL_GET_LESS((iter->depth == 0 ? 120990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->tree_->root : iter->path_h[iter->depth - 1]), 1); 121090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR_INV_DEPTH 121190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 121290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 121390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber do 121490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 121590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (iter->depth == 0) 121690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 121790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth = ~0; 121890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 121990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 122090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 122190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->depth--; 122290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 122390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber while (!L_BIT_ARR_VAL(iter->branch, iter->depth)); 122490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber else 122590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 122690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_0(iter->branch, iter->depth) 122790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->path_h[iter->depth++] = h; 122890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 122990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber for (; ;) 123090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber { 123190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber h = AVL_GET_GREATER(h, 1); 123290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_CHECK_READ_ERROR_INV_DEPTH 123390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 123490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber if (h == AVL_NULL) 123590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber break; 123690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 123790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber L_BIT_ARR_1(iter->branch, iter->depth) 123890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber iter->path_h[iter->depth++] = h; 123990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 124090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 124190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber } 124290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 124390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef l_tree 124490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 124590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 124690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 124790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 124890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Tidy up the preprocessor symbol name space. */ 124990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_ 125090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_EST_LONG_BIT 125190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SIZE 125290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_MASK_HIGH_BIT 125390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_LONG_BIT 125490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_DEFN 125590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_VAL 125690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_0 125790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_1 125890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_ALL 125990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR 126090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR_INV_DEPTH 126190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BIT_ARR_LONGS 126290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_IMPL_MASK 126390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR 126490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_CHECK_READ_ERROR_INV_DEPTH 126590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_SC 126690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BALANCE_PARAM_CALL_PREFIX 126790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef L_BALANCE_PARAM_DECL_PREFIX 1268