LCOV - code coverage report
Current view: top level - common - heap.h (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 2463e5ebed6d Lines: 69 73 94.5 %
Date: 2019-03-18 07:48:51 Functions: 76 82 92.7 %
Branches: 144 193 74.6 %

           Branch data     Line data    Source code
       1                 :            : /** @file heap.h
       2                 :            :  * @brief C++ STL heap implementation with extensions
       3                 :            :  *
       4                 :            :  * Adapted from libc++'s <algorithm>, with the following additions:
       5                 :            :  *
       6                 :            :  * * replace() - pop() followed by push(), but as efficient as just pop()
       7                 :            :  *   (i.e. at most 2 * log(N) compares rather than at most 3 * log(N))
       8                 :            :  * * siftdown() - sink adjusted entry to restore heap invariant
       9                 :            :  *
      10                 :            :  * Complexity:
      11                 :            :  *
      12                 :            :  * make() : At most 3*N comparisons
      13                 :            :  * pop()/replace()/siftdown() : At most 2*log(N) comparisons
      14                 :            :  * push() : At most log(N) comparisons (O(1) average)
      15                 :            :  * sort() : At most 2*N*log(N) comparisons
      16                 :            :  */
      17                 :            : 
      18                 :            : // This file is dual licensed under the MIT and the University of Illinois Open
      19                 :            : // Source Licenses:
      20                 :            : //
      21                 :            : // ==============================================================================
      22                 :            : // libc++ License
      23                 :            : // ==============================================================================
      24                 :            : //
      25                 :            : // The libc++ library is dual licensed under both the University of Illinois
      26                 :            : // "BSD-Like" license and the MIT license.  As a user of this code you may choose
      27                 :            : // to use it under either license.  As a contributor, you agree to allow your code
      28                 :            : // to be used under both.
      29                 :            : //
      30                 :            : // Full text of the relevant licenses is included below.
      31                 :            : //
      32                 :            : // ==============================================================================
      33                 :            : //
      34                 :            : // University of Illinois/NCSA
      35                 :            : // Open Source License
      36                 :            : //
      37                 :            : // Copyright (c) 2009-2016 by the contributors listed in CREDITS.TXT
      38                 :            : //
      39                 :            : // All rights reserved.
      40                 :            : //
      41                 :            : // Developed by:
      42                 :            : //
      43                 :            : //     LLVM Team
      44                 :            : //
      45                 :            : //     University of Illinois at Urbana-Champaign
      46                 :            : //
      47                 :            : //     http://llvm.org
      48                 :            : //
      49                 :            : // Permission is hereby granted, free of charge, to any person obtaining a copy of
      50                 :            : // this software and associated documentation files (the "Software"), to deal with
      51                 :            : // the Software without restriction, including without limitation the rights to
      52                 :            : // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
      53                 :            : // of the Software, and to permit persons to whom the Software is furnished to do
      54                 :            : // so, subject to the following conditions:
      55                 :            : //
      56                 :            : //     * Redistributions of source code must retain the above copyright notice,
      57                 :            : //       this list of conditions and the following disclaimers.
      58                 :            : //
      59                 :            : //     * Redistributions in binary form must reproduce the above copyright notice,
      60                 :            : //       this list of conditions and the following disclaimers in the
      61                 :            : //       documentation and/or other materials provided with the distribution.
      62                 :            : //
      63                 :            : //     * Neither the names of the LLVM Team, University of Illinois at
      64                 :            : //       Urbana-Champaign, nor the names of its contributors may be used to
      65                 :            : //       endorse or promote products derived from this Software without specific
      66                 :            : //       prior written permission.
      67                 :            : //
      68                 :            : // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      69                 :            : // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
      70                 :            : // FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
      71                 :            : // CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      72                 :            : // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      73                 :            : // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
      74                 :            : // SOFTWARE.
      75                 :            : //
      76                 :            : // ==============================================================================
      77                 :            : //
      78                 :            : // Copyright (c) 2009-2014 by the contributors listed in CREDITS.TXT
      79                 :            : //
      80                 :            : // Permission is hereby granted, free of charge, to any person obtaining a copy
      81                 :            : // of this software and associated documentation files (the "Software"), to deal
      82                 :            : // in the Software without restriction, including without limitation the rights
      83                 :            : // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      84                 :            : // copies of the Software, and to permit persons to whom the Software is
      85                 :            : // furnished to do so, subject to the following conditions:
      86                 :            : //
      87                 :            : // The above copyright notice and this permission notice shall be included in
      88                 :            : // all copies or substantial portions of the Software.
      89                 :            : //
      90                 :            : // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      91                 :            : // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      92                 :            : // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      93                 :            : // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      94                 :            : // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      95                 :            : // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
      96                 :            : // THE SOFTWARE.
      97                 :            : 
      98                 :            : #ifndef XAPIAN_INCLUDED_HEAP_H
      99                 :            : #define XAPIAN_INCLUDED_HEAP_H
     100                 :            : 
     101                 :            : namespace Heap {
     102                 :            : 
     103                 :            : // push_heap
     104                 :            : 
     105                 :            : template <class _Compare, class _RandomAccessIterator>
     106                 :            : void
     107                 :       1253 : sift_up_(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp,
     108                 :            :           typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
     109                 :            : {
     110                 :            :     typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
     111         [ +  - ]:       1253 :     if (len > 1)
     112                 :            :     {
     113                 :       1253 :         len = (len - 2) / 2;
     114                 :       1253 :         _RandomAccessIterator ptr = first + len;
     115         [ +  + ]:       1253 :         if (comp(*ptr, *--last))
     116                 :            :         {
     117                 :        678 :             value_type t(std::move(*last));
     118 [ #  # ][ #  # ]:          0 :             do
     119                 :            :             {
     120                 :        678 :                 *last = std::move(*ptr);
     121                 :        678 :                 last = ptr;
     122         [ +  - ]:        678 :                 if (len == 0)
     123                 :        678 :                     break;
     124                 :          0 :                 len = (len - 1) / 2;
     125                 :          0 :                 ptr = first + len;
     126                 :          0 :             } while (comp(*ptr, t));
     127                 :       1253 :             *last = std::move(t);
     128                 :            :         }
     129                 :            :     }
     130                 :       1253 : }
     131                 :            : 
     132                 :            : template <class _RandomAccessIterator, class _Compare>
     133                 :            : inline
     134                 :            : void
     135                 :       1253 : push(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
     136                 :            : {
     137                 :       1253 :     sift_up_(first, last, comp, last - first);
     138                 :       1253 : }
     139                 :            : 
     140                 :            : // pop_heap
     141                 :            : 
     142                 :            : template <class _Compare, class _RandomAccessIterator>
     143                 :            : void
     144                 :   25931298 : sift_down_(_RandomAccessIterator first, _Compare comp,
     145                 :            :             typename std::iterator_traits<_RandomAccessIterator>::difference_type len,
     146                 :            :             _RandomAccessIterator start)
     147                 :            : {
     148                 :            :     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     149                 :            :     typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
     150                 :            :     // left-child of start is at 2 * start + 1
     151                 :            :     // right-child of start is at 2 * start + 2
     152                 :   25931298 :     difference_type child = start - first;
     153                 :            : 
     154         [ +  + ]:   25931298 :     if (len < 2 || (len - 2) / 2 < child)
           [ -  +  +  + ]
         [ +  + ][ +  + ]
           [ -  +  +  - ]
                 [ -  + ]
     155                 :   25777917 :         return;
     156                 :            : 
     157                 :   25776992 :     child = 2 * child + 1;
     158                 :   25776992 :     _RandomAccessIterator child_i = first + child;
     159                 :            : 
     160 [ +  + ][ +  + ]:   25776992 :     if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
         [ +  + ][ +  + ]
           [ +  +  #  #  
           +  + ][ +  - ]
         [ +  + ][ +  + ]
           [ +  +  #  # ]
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ +  - ][ +  + ]
                 [ +  + ]
           [ +  +  #  # ]
     161                 :            :         // right-child exists and is greater than left-child
     162                 :   11385381 :         ++child_i;
     163                 :   11385381 :         ++child;
     164                 :            :     }
     165                 :            : 
     166                 :            :     // check if we are in heap-order
     167 [ +  + ][ +  + ]:   25776992 :     if (comp(*child_i, *start))
         [ +  - ][ +  + ]
         [ +  + ][ +  + ]
         [ +  - ][ +  + ]
     168                 :            :         // we are, start is larger than it's largest child
     169                 :    2008741 :         return;
     170                 :            : 
     171         [ +  - ]:   23768251 :     value_type top(std::move(*start));
     172 [ +  + ][ +  + ]:   88643579 :     do
         [ +  + ][ -  + ]
     173                 :            :     {
     174                 :            :         // we are not in heap-order, swap the parent with it's largest child
     175 [ +  - ][ +  - ]:  102630429 :         *start = std::move(*child_i);
     176                 :  102630429 :         start = child_i;
     177                 :            : 
     178         [ +  + ]:  102630429 :         if ((len - 2) / 2 < child)
           [ +  +  +  + ]
           [ #  #  +  + ]
     179                 :   13986850 :             break;
     180                 :            : 
     181                 :            :         // recompute the child based off of the updated parent
     182                 :   88643579 :         child = 2 * child + 1;
     183                 :   88643579 :         child_i = first + child;
     184                 :            : 
     185 [ +  + ][ +  + ]:   88643579 :         if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
         [ +  + ][ +  + ]
           [ +  +  #  #  
           +  + ][ +  - ]
         [ +  + ][ +  + ]
           [ +  +  #  # ]
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ #  # ][ -  + ]
         [ +  + ][ -  + ]
         [ #  # ][ #  # ]
                 [ -  + ]
           [ -  +  #  # ]
     186                 :            :             // right-child exists and is greater than left-child
     187                 :   42209492 :             ++child_i;
     188                 :   42209492 :             ++child;
     189                 :            :         }
     190                 :            : 
     191                 :            :         // check if we are in heap-order
     192 [ +  - ][ +  - ]:   88643579 :     } while (!comp(*child_i, top));
            [ + ][ +  - ]
     193 [ +  - ][ +  - ]:   23768251 :     *start = std::move(top);
     194                 :            : }
     195                 :            : 
     196                 :            : template <class _Compare, class _RandomAccessIterator>
     197                 :            : inline
     198                 :            : void
     199                 :     157637 : pop_heap_(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp,
     200                 :            :            typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
     201                 :            : {
     202 [ +  + ][ +  - ]:     157637 :     if (len > 1)
     203                 :            :     {
     204                 :            :         using std::swap;
     205                 :     156692 :         swap(*first, *--last);
     206                 :     156692 :         sift_down_(first, comp, len - 1, first);
     207                 :            :     }
     208                 :     157637 : }
     209                 :            : 
     210                 :            : template <class _RandomAccessIterator, class _Compare>
     211                 :            : inline
     212                 :            : void
     213                 :     156288 : pop(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
     214                 :            : {
     215                 :     156288 :     pop_heap_(first, last, comp, last - first);
     216                 :     156288 : }
     217                 :            : 
     218                 :            : template <class _Compare, class _RandomAccessIterator>
     219                 :            : inline
     220                 :            : void
     221                 :   17447930 : replace_heap_(_RandomAccessIterator first, _Compare comp,
     222                 :            :               typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
     223                 :            : {
     224                 :   17447930 :     sift_down_(first, comp, len, first);
     225                 :   17447930 : }
     226                 :            : 
     227                 :            : // Replace the tip of the heap then call replace() to restore the invariant.
     228                 :            : template <class _RandomAccessIterator, class _Compare>
     229                 :            : inline void
     230                 :   17447930 : replace(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
     231                 :            : {
     232                 :   17447930 :     replace_heap_(first, comp, last - first);
     233                 :   17447930 : }
     234                 :            : 
     235                 :            : template <class _Compare, class _RandomAccessIterator>
     236                 :            : inline void
     237                 :         44 : siftdown_heap_(_RandomAccessIterator first,
     238                 :            :                _RandomAccessIterator elt, _Compare comp,
     239                 :            :                typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
     240                 :            : {
     241                 :         44 :     sift_down_(first, comp, len, elt);
     242                 :         44 : }
     243                 :            : 
     244                 :            : // Replace an element with a "worse" one (in _Compare terms) and call siftdown_heap()
     245                 :            : // to restore the invariant.
     246                 :            : template <class _RandomAccessIterator, class _Compare>
     247                 :            : inline
     248                 :            : void
     249                 :         44 : siftdown(_RandomAccessIterator first, _RandomAccessIterator last,
     250                 :            :          _RandomAccessIterator elt, _Compare comp)
     251                 :            : {
     252                 :         44 :     siftdown_heap_(first, elt, comp, last - first);
     253                 :         44 : }
     254                 :            : 
     255                 :            : // make_heap
     256                 :            : 
     257                 :            : template <class _RandomAccessIterator, class _Compare>
     258                 :            : void
     259                 :     295584 : make(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
     260                 :            : {
     261                 :            :     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     262                 :     295584 :     difference_type n = last - first;
     263   [ +  +  +  + ]:     295584 :     if (n > 1)
                 [ +  + ]
     264                 :            :     {
     265                 :            :         // start from the first parent, there is no need to consider children
     266 [ +  + ][ +  + ]:    8621569 :         for (difference_type start = (n - 2) / 2; start >= 0; --start)
     267                 :            :         {
     268                 :    8326632 :             sift_down_(first, comp, n, first + start);
     269                 :            :         }
     270                 :            :     }
     271                 :     295584 : }
     272                 :            : 
     273                 :            : // sort_heap
     274                 :            : 
     275                 :            : template <class _Compare, class _RandomAccessIterator>
     276                 :            : void
     277                 :        229 : sort(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
     278                 :            : {
     279                 :            :     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     280         [ +  + ]:       1578 :     for (difference_type n = last - first; n > 1; --last, --n)
     281                 :       1349 :         pop_heap_<_Compare>(first, last, comp, n);
     282                 :        229 : }
     283                 :            : 
     284                 :            : }
     285                 :            : 
     286                 :            : #endif

Generated by: LCOV version 1.11