Library import 16 (#2433)

Co-authored-by: robot-piglet <[email protected]>
Co-authored-by: deshevoy <[email protected]>
Co-authored-by: robot-contrib <[email protected]>
Co-authored-by: thegeorg <[email protected]>
Co-authored-by: robot-ya-builder <[email protected]>
Co-authored-by: svidyuk <[email protected]>
Co-authored-by: shadchin <[email protected]>
Co-authored-by: robot-ratatosk <[email protected]>
Co-authored-by: innokentii <[email protected]>
Co-authored-by: arkady-e1ppa <[email protected]>
Co-authored-by: snermolaev <[email protected]>
Co-authored-by: dimdim11 <[email protected]>
Co-authored-by: kickbutt <[email protected]>
Co-authored-by: abdullinsaid <[email protected]>
Co-authored-by: korsunandrei <[email protected]>
Co-authored-by: petrk <[email protected]>
Co-authored-by: miroslav2 <[email protected]>
Co-authored-by: serjflint <[email protected]>
Co-authored-by: akhropov <[email protected]>
Co-authored-by: prettyboy <[email protected]>
Co-authored-by: ilikepugs <[email protected]>
Co-authored-by: hiddenpath <[email protected]>
Co-authored-by: mikhnenko <[email protected]>
Co-authored-by: spreis <[email protected]>
Co-authored-by: andreyshspb <[email protected]>
Co-authored-by: dimaandreev <[email protected]>
Co-authored-by: rashid <[email protected]>
Co-authored-by: robot-ydb-importer <[email protected]>
Co-authored-by: r-vetrov <[email protected]>
Co-authored-by: ypodlesov <[email protected]>
Co-authored-by: zaverden <[email protected]>
Co-authored-by: vpozdyayev <[email protected]>
Co-authored-by: robot-cozmo <[email protected]>
Co-authored-by: v-korovin <[email protected]>
Co-authored-by: arikon <[email protected]>
Co-authored-by: khoden <[email protected]>
Co-authored-by: psydmm <[email protected]>
Co-authored-by: robot-javacom <[email protected]>
Co-authored-by: dtorilov <[email protected]>
Co-authored-by: sennikovmv <[email protected]>
Co-authored-by: hcpp <[email protected]>

1 files changed, 0 insertions, 121 deletions

diff --git a/contrib/tools/python3/src/Modules/rotatingtree.c b/contrib/tools/python3/src/Modules/rotatingtree.c
deleted file mode 100644
index 07e08bc3167..00000000000
--- a/contrib/tools/python3/src/Modules/rotatingtree.c
+++ /dev/null
@@ -1,121 +0,0 @@
-#include "rotatingtree.h"
-
-#define KEY_LOWER_THAN(key1, key2)  ((char*)(key1) < (char*)(key2))
-
-/* The randombits() function below is a fast-and-dirty generator that
- * is probably irregular enough for our purposes.  Note that it's biased:
- * I think that ones are slightly more probable than zeroes.  It's not
- * important here, though.
- */
-
-static unsigned int random_value = 1;
-static unsigned int random_stream = 0;
-
-static int
-randombits(int bits)
-{
-    int result;
-    if (random_stream < (1U << bits)) {
-        random_value *= 1082527;
-        random_stream = random_value;
-    }
-    result = random_stream & ((1<<bits)-1);
-    random_stream >>= bits;
-    return result;
-}
-
-
-/* Insert a new node into the tree.
-   (*root) is modified to point to the new root. */
-void
-RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
-{
-    while (*root != NULL) {
-        if (KEY_LOWER_THAN(node->key, (*root)->key))
-            root = &((*root)->left);
-        else
-            root = &((*root)->right);
-    }
-    node->left = NULL;
-    node->right = NULL;
-    *root = node;
-}
-
-/* Locate the node with the given key.  This is the most complicated
-   function because it occasionally rebalances the tree to move the
-   resulting node closer to the root. */
-rotating_node_t *
-RotatingTree_Get(rotating_node_t **root, void *key)
-{
-    if (randombits(3) != 4) {
-        /* Fast path, no rebalancing */
-        rotating_node_t *node = *root;
-        while (node != NULL) {
-            if (node->key == key)
-                return node;
-            if (KEY_LOWER_THAN(key, node->key))
-                node = node->left;
-            else
-                node = node->right;
-        }
-        return NULL;
-    }
-    else {
-        rotating_node_t **pnode = root;
-        rotating_node_t *node = *pnode;
-        rotating_node_t *next;
-        int rotate;
-        if (node == NULL)
-            return NULL;
-        while (1) {
-            if (node->key == key)
-                return node;
-            rotate = !randombits(1);
-            if (KEY_LOWER_THAN(key, node->key)) {
-                next = node->left;
-                if (next == NULL)
-                    return NULL;
-                if (rotate) {
-                    node->left = next->right;
-                    next->right = node;
-                    *pnode = next;
-                }
-                else
-                    pnode = &(node->left);
-            }
-            else {
-                next = node->right;
-                if (next == NULL)
-                    return NULL;
-                if (rotate) {
-                    node->right = next->left;
-                    next->left = node;
-                    *pnode = next;
-                }
-                else
-                    pnode = &(node->right);
-            }
-            node = next;
-        }
-    }
-}
-
-/* Enumerate all nodes in the tree.  The callback enumfn() should return
-   zero to continue the enumeration, or non-zero to interrupt it.
-   A non-zero value is directly returned by RotatingTree_Enum(). */
-int
-RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
-                  void *arg)
-{
-    int result;
-    rotating_node_t *node;
-    while (root != NULL) {
-        result = RotatingTree_Enum(root->left, enumfn, arg);
-        if (result != 0) return result;
-        node = root->right;
-        result = enumfn(root, arg);
-        if (result != 0) return result;
-        root = node;
-    }
-    return 0;
-}