LCOV - code coverage report
Current view: | top level - Modules - rotatingtree.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 0 | 60 | 0.0 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 0 | 4 | 0.0 %
|  |  | Branches: | 0 | 34 | 0.0 %

               Branch data     Line data    Source code
           1                 :            : #include "rotatingtree.h"
           2                 :            :
           3                 :            : #define KEY_LOWER_THAN(key1, key2)  ((char*)(key1) < (char*)(key2))
           4                 :            :
           5                 :            : /* The randombits() function below is a fast-and-dirty generator that
           6                 :            :  * is probably irregular enough for our purposes.  Note that it's biased:
           7                 :            :  * I think that ones are slightly more probable than zeroes.  It's not
           8                 :            :  * important here, though.
           9                 :            :  */
          10                 :            :
          11                 :            : static unsigned int random_value = 1;
          12                 :            : static unsigned int random_stream = 0;
          13                 :            :
          14                 :            : static int
          15                 :          0 : randombits(int bits)
          16                 :            : {
          17                 :            :     int result;
          18         [ #  # ]:          0 :     if (random_stream < (1U << bits)) {
          19                 :          0 :         random_value *= 1082527;
          20                 :          0 :         random_stream = random_value;
          21                 :            :     }
          22                 :          0 :     result = random_stream & ((1<<bits)-1);
          23                 :          0 :     random_stream >>= bits;
          24                 :          0 :     return result;
          25                 :            : }
          26                 :            :
          27                 :            :
          28                 :            : /* Insert a new node into the tree.
          29                 :            :    (*root) is modified to point to the new root. */
          30                 :            : void
          31                 :          0 : RotatingTree_Add(rotating_node_t **root, rotating_node_t *node)
          32                 :            : {
          33         [ #  # ]:          0 :     while (*root != NULL) {
          34         [ #  # ]:          0 :         if (KEY_LOWER_THAN(node->key, (*root)->key))
          35                 :          0 :             root = &((*root)->left);
          36                 :            :         else
          37                 :          0 :             root = &((*root)->right);
          38                 :            :     }
          39                 :          0 :     node->left = NULL;
          40                 :          0 :     node->right = NULL;
          41                 :          0 :     *root = node;
          42                 :          0 : }
          43                 :            :
          44                 :            : /* Locate the node with the given key.  This is the most complicated
          45                 :            :    function because it occasionally rebalances the tree to move the
          46                 :            :    resulting node closer to the root. */
          47                 :            : rotating_node_t *
          48                 :          0 : RotatingTree_Get(rotating_node_t **root, void *key)
          49                 :            : {
          50         [ #  # ]:          0 :     if (randombits(3) != 4) {
          51                 :            :         /* Fast path, no rebalancing */
          52                 :          0 :         rotating_node_t *node = *root;
          53         [ #  # ]:          0 :         while (node != NULL) {
          54         [ #  # ]:          0 :             if (node->key == key)
          55                 :          0 :                 return node;
          56         [ #  # ]:          0 :             if (KEY_LOWER_THAN(key, node->key))
          57                 :          0 :                 node = node->left;
          58                 :            :             else
          59                 :          0 :                 node = node->right;
          60                 :            :         }
          61                 :          0 :         return NULL;
          62                 :            :     }
          63                 :            :     else {
          64                 :          0 :         rotating_node_t **pnode = root;
          65                 :          0 :         rotating_node_t *node = *pnode;
          66                 :            :         rotating_node_t *next;
          67                 :            :         int rotate;
          68         [ #  # ]:          0 :         if (node == NULL)
          69                 :          0 :             return NULL;
          70                 :            :         while (1) {
          71         [ #  # ]:          0 :             if (node->key == key)
          72                 :          0 :                 return node;
          73                 :          0 :             rotate = !randombits(1);
          74         [ #  # ]:          0 :             if (KEY_LOWER_THAN(key, node->key)) {
          75                 :          0 :                 next = node->left;
          76         [ #  # ]:          0 :                 if (next == NULL)
          77                 :          0 :                     return NULL;
          78         [ #  # ]:          0 :                 if (rotate) {
          79                 :          0 :                     node->left = next->right;
          80                 :          0 :                     next->right = node;
          81                 :          0 :                     *pnode = next;
          82                 :            :                 }
          83                 :            :                 else
          84                 :          0 :                     pnode = &(node->left);
          85                 :            :             }
          86                 :            :             else {
          87                 :          0 :                 next = node->right;
          88         [ #  # ]:          0 :                 if (next == NULL)
          89                 :          0 :                     return NULL;
          90         [ #  # ]:          0 :                 if (rotate) {
          91                 :          0 :                     node->right = next->left;
          92                 :          0 :                     next->left = node;
          93                 :          0 :                     *pnode = next;
          94                 :            :                 }
          95                 :            :                 else
          96                 :          0 :                     pnode = &(node->right);
          97                 :            :             }
          98                 :          0 :             node = next;
          99                 :            :         }
         100                 :            :     }
         101                 :            : }
         102                 :            :
         103                 :            : /* Enumerate all nodes in the tree.  The callback enumfn() should return
         104                 :            :    zero to continue the enumeration, or non-zero to interrupt it.
         105                 :            :    A non-zero value is directly returned by RotatingTree_Enum(). */
         106                 :            : int
         107                 :          0 : RotatingTree_Enum(rotating_node_t *root, rotating_tree_enum_fn enumfn,
         108                 :            :                   void *arg)
         109                 :            : {
         110                 :            :     int result;
         111                 :            :     rotating_node_t *node;
         112         [ #  # ]:          0 :     while (root != NULL) {
         113                 :          0 :         result = RotatingTree_Enum(root->left, enumfn, arg);
         114         [ #  # ]:          0 :         if (result != 0) return result;
         115                 :          0 :         node = root->right;
         116                 :          0 :         result = enumfn(root, arg);
         117         [ #  # ]:          0 :         if (result != 0) return result;
         118                 :          0 :         root = node;
         119                 :            :     }
         120                 :          0 :     return 0;
         121                 :            : }

Generated by: LCOV version 1.14