Branch data     Line data    Source code

       1                 :            : /*
       2                 :            :  * This file is part of the MicroPython project, http://micropython.org/
       3                 :            :  *
       4                 :            :  * The MIT License (MIT)
       5                 :            :  *
       6                 :            :  * Copyright (c) 2020 Damien P. George
       7                 :            :  *
       8                 :            :  * Permission is hereby granted, free of charge, to any person obtaining a copy
       9                 :            :  * of this software and associated documentation files (the "Software"), to deal
      10                 :            :  * in the Software without restriction, including without limitation the rights
      11                 :            :  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      12                 :            :  * copies of the Software, and to permit persons to whom the Software is
      13                 :            :  * furnished to do so, subject to the following conditions:
      14                 :            :  *
      15                 :            :  * The above copyright notice and this permission notice shall be included in
      16                 :            :  * all copies or substantial portions of the Software.
      17                 :            :  *
      18                 :            :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      19                 :            :  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      20                 :            :  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      21                 :            :  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      22                 :            :  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      23                 :            :  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
      24                 :            :  * THE SOFTWARE.
      25                 :            :  */
      26                 :            : 
      27                 :            : #include "py/pairheap.h"
      28                 :            : 
      29                 :            : // The mp_pairheap_t.next pointer can take one of the following values:
      30                 :            : //   - NULL: the node is the top of the heap
      31                 :            : //   - LSB set: the node is the last of the children and points to its parent node
      32                 :            : //   - other: the node is a child and not the last child
      33                 :            : // The macros below help manage this pointer.
      34                 :            : #define NEXT_MAKE_RIGHTMOST_PARENT(parent) ((void *)((uintptr_t)(parent) | 1))
      35                 :            : #define NEXT_IS_RIGHTMOST_PARENT(next) ((uintptr_t)(next) & 1)
      36                 :            : #define NEXT_GET_RIGHTMOST_PARENT(next) ((void *)((uintptr_t)(next) & ~1))
      37                 :            : 
      38                 :            : // O(1), stable
      39                 :    1280445 : mp_pairheap_t *mp_pairheap_meld(mp_pairheap_lt_t lt, mp_pairheap_t *heap1, mp_pairheap_t *heap2) {
      40         [ +  + ]:    1280445 :     if (heap1 == NULL) {
      41                 :            :         return heap2;
      42                 :            :     }
      43         [ +  + ]:     960219 :     if (heap2 == NULL) {
      44                 :            :         return heap1;
      45                 :            :     }
      46         [ +  + ]:     959512 :     if (lt(heap1, heap2)) {
      47         [ +  + ]:     638892 :         if (heap1->child == NULL) {
      48                 :     319499 :             heap1->child = heap2;
      49                 :            :         } else {
      50                 :     319393 :             heap1->child_last->next = heap2;
      51                 :            :         }
      52                 :     638892 :         heap1->child_last = heap2;
      53                 :     638892 :         heap2->next = NEXT_MAKE_RIGHTMOST_PARENT(heap1);
      54                 :     638892 :         return heap1;
      55                 :            :     } else {
      56                 :     320620 :         heap1->next = heap2->child;
      57                 :     320620 :         heap2->child = heap1;
      58         [ +  + ]:     320620 :         if (heap1->next == NULL) {
      59                 :        753 :             heap2->child_last = heap1;
      60                 :        753 :             heap1->next = NEXT_MAKE_RIGHTMOST_PARENT(heap2);
      61                 :            :         }
      62                 :     320620 :         return heap2;
      63                 :            :     }
      64                 :            : }
      65                 :            : 
      66                 :            : // amortised O(log N), stable
      67                 :     320925 : mp_pairheap_t *mp_pairheap_pairing(mp_pairheap_lt_t lt, mp_pairheap_t *child) {
      68         [ +  + ]:     320925 :     if (child == NULL) {
      69                 :            :         return NULL;
      70                 :            :     }
      71                 :            :     mp_pairheap_t *heap = NULL;
      72         [ +  + ]:     959923 :     while (!NEXT_IS_RIGHTMOST_PARENT(child)) {
      73                 :     639697 :         mp_pairheap_t *n1 = child;
      74                 :     639697 :         child = child->next;
      75                 :     639697 :         n1->next = NULL;
      76         [ +  + ]:     639697 :         if (!NEXT_IS_RIGHTMOST_PARENT(child)) {
      77                 :     319773 :             mp_pairheap_t *n2 = child;
      78                 :     319773 :             child = child->next;
      79                 :     319773 :             n2->next = NULL;
      80                 :     319773 :             n1 = mp_pairheap_meld(lt, n1, n2);
      81                 :            :         }
      82                 :     639697 :         heap = mp_pairheap_meld(lt, heap, n1);
      83                 :            :     }
      84                 :     320226 :     heap->next = NULL;
      85                 :     320226 :     return heap;
      86                 :            : }
      87                 :            : 
      88                 :            : // amortised O(log N), stable
      89                 :         96 : mp_pairheap_t *mp_pairheap_delete(mp_pairheap_lt_t lt, mp_pairheap_t *heap, mp_pairheap_t *node) {
      90                 :            :     // Simple case of the top being the node to delete
      91         [ +  + ]:         96 :     if (node == heap) {
      92                 :         54 :         mp_pairheap_t *child = heap->child;
      93                 :         54 :         node->child = NULL;
      94                 :         54 :         return mp_pairheap_pairing(lt, child);
      95                 :            :     }
      96                 :            : 
      97                 :            :     // Case where node is not in the heap
      98         [ +  + ]:         42 :     if (node->next == NULL) {
      99                 :            :         return heap;
     100                 :            :     }
     101                 :            : 
     102                 :            :     // Find parent of node
     103                 :            :     mp_pairheap_t *parent = node;
     104         [ +  + ]:         44 :     while (!NEXT_IS_RIGHTMOST_PARENT(parent->next)) {
     105                 :            :         parent = parent->next;
     106                 :            :     }
     107                 :         40 :     parent = NEXT_GET_RIGHTMOST_PARENT(parent->next);
     108                 :            : 
     109                 :            :     // Replace node with pairing of its children
     110                 :         40 :     mp_pairheap_t *next;
     111   [ +  +  +  + ]:         40 :     if (node == parent->child && node->child == NULL) {
     112         [ +  + ]:         24 :         if (NEXT_IS_RIGHTMOST_PARENT(node->next)) {
     113                 :         22 :             parent->child = NULL;
     114                 :            :         } else {
     115                 :          2 :             parent->child = node->next;
     116                 :            :         }
     117                 :         24 :         node->next = NULL;
     118                 :         24 :         return heap;
     119         [ +  + ]:         16 :     } else if (node == parent->child) {
     120                 :          4 :         mp_pairheap_t *child = node->child;
     121                 :          4 :         next = node->next;
     122                 :          4 :         node->child = NULL;
     123                 :          4 :         node->next = NULL;
     124                 :          4 :         node = mp_pairheap_pairing(lt, child);
     125                 :          4 :         parent->child = node;
     126                 :            :     } else {
     127                 :            :         mp_pairheap_t *n = parent->child;
     128         [ +  + ]:         18 :         while (node != n->next) {
     129                 :            :             n = n->next;
     130                 :            :         }
     131                 :         12 :         mp_pairheap_t *child = node->child;
     132                 :         12 :         next = node->next;
     133                 :         12 :         node->child = NULL;
     134                 :         12 :         node->next = NULL;
     135                 :         12 :         node = mp_pairheap_pairing(lt, child);
     136         [ +  + ]:         12 :         if (node == NULL) {
     137                 :            :             node = n;
     138                 :            :         } else {
     139                 :          2 :             n->next = node;
     140                 :            :         }
     141                 :            :     }
     142                 :         16 :     node->next = next;
     143         [ +  + ]:         16 :     if (NEXT_IS_RIGHTMOST_PARENT(next)) {
     144                 :         14 :         parent->child_last = node;
     145                 :            :     }
     146                 :            :     return heap;
     147                 :            : }