| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
| |
| <html lang="en"> |
| |
| <head> |
| <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> |
| <title>LCOV - skiboot.info - ccan/heap/heap.c</title> |
| <link rel="stylesheet" type="text/css" href="../../gcov.css"> |
| </head> |
| |
| <body> |
| |
| <table width="100%" border=0 cellspacing=0 cellpadding=0> |
| <tr><td class="title">LCOV - code coverage report</td></tr> |
| <tr><td class="ruler"><img src="../../glass.png" width=3 height=3 alt=""></td></tr> |
| |
| <tr> |
| <td width="100%"> |
| <table cellpadding=1 border=0 width="100%"> |
| <tr> |
| <td width="10%" class="headerItem">Current view:</td> |
| <td width="10%" class="headerValue"><a href="../../index.html">top level</a> - <a href="index.html">ccan/heap</a> - heap.c<span style="font-size: 80%;"> (source / <a href="heap.c.func-c.html">functions</a>)</span></td> |
| <td width="5%"></td> |
| <td width="5%"></td> |
| <td width="5%" class="headerCovTableHead">Coverage</td> |
| <td width="5%" class="headerCovTableHead" title="Covered + Uncovered code">Total</td> |
| <td width="5%" class="headerCovTableHead" title="Exercised code only">Hit</td> |
| </tr> |
| <tr> |
| <td class="headerItem">Test:</td> |
| <td class="headerValue">skiboot.info</td> |
| <td></td> |
| <td class="headerItem">Lines:</td> |
| <td class="headerCovTableEntryHi">95.3 %</td> |
| <td class="headerCovTableEntry">64</td> |
| <td class="headerCovTableEntry">61</td> |
| </tr> |
| <tr> |
| <td class="headerItem">Test Date:</td> |
| <td class="headerValue">2025-06-27 16:54:26</td> |
| <td></td> |
| <td class="headerItem">Functions:</td> |
| <td class="headerCovTableEntryHi">100.0 %</td> |
| <td class="headerCovTableEntry">8</td> |
| <td class="headerCovTableEntry">8</td> |
| </tr> |
| <tr> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td class="headerItem">Branches:</td> |
| <td class="headerCovTableEntryHi">-</td> |
| <td class="headerCovTableEntry">0</td> |
| <td class="headerCovTableEntry">0</td> |
| </tr> |
| <tr><td><img src="../../glass.png" width=3 height=3 alt=""></td></tr> |
| </table> |
| </td> |
| </tr> |
| |
| <tr><td class="ruler"><img src="../../glass.png" width=3 height=3 alt=""></td></tr> |
| </table> |
| |
| <table cellpadding=0 cellspacing=0 border=0> |
| <tr> |
| <td><br></td> |
| </tr> |
| <tr> |
| <td> |
| <pre class="sourceHeading"> Branch data Line data Source code</pre> |
| <pre class="source"> |
| <span id="L1"><span class="lineNum"> 1</span> : : /* Licensed under BSD-MIT - see LICENSE file for details */</span> |
| <span id="L2"><span class="lineNum"> 2</span> : : #include <ccan/heap/heap.h></span> |
| <span id="L3"><span class="lineNum"> 3</span> : : </span> |
| <span id="L4"><span class="lineNum"> 4</span> : : /*</span> |
| <span id="L5"><span class="lineNum"> 5</span> : : * Allocating memory in chunks greater than needed does not yield measurable</span> |
| <span id="L6"><span class="lineNum"> 6</span> : : * speedups of the test program when linking against glibc 2.15.</span> |
| <span id="L7"><span class="lineNum"> 7</span> : : *</span> |
| <span id="L8"><span class="lineNum"> 8</span> : : * When the data array has to be shrunk though, limiting calls to realloc</span> |
| <span id="L9"><span class="lineNum"> 9</span> : : * does help a little bit (~7% speedup), hence the following parameter.</span> |
| <span id="L10"><span class="lineNum"> 10</span> : : */</span> |
| <span id="L11"><span class="lineNum"> 11</span> : : #define HEAP_MEM_HYSTERESIS 4096</span> |
| <span id="L12"><span class="lineNum"> 12</span> : : </span> |
| <span id="L13"><span class="lineNum"> 13</span> :<span class="tlaGNC tlaBgGNC"> 140194 : static inline void swap(struct heap *h, size_t i, size_t j)</span></span> |
| <span id="L14"><span class="lineNum"> 14</span> : : {</span> |
| <span id="L15"><span class="lineNum"> 15</span> :<span class="tlaGNC"> 140194 : void *foo = h->data[i];</span></span> |
| <span id="L16"><span class="lineNum"> 16</span> : : </span> |
| <span id="L17"><span class="lineNum"> 17</span> :<span class="tlaGNC"> 140194 : h->data[i] = h->data[j];</span></span> |
| <span id="L18"><span class="lineNum"> 18</span> :<span class="tlaGNC"> 140194 : h->data[j] = foo;</span></span> |
| <span id="L19"><span class="lineNum"> 19</span> :<span class="tlaGNC"> 140194 : }</span></span> |
| <span id="L20"><span class="lineNum"> 20</span> : : </span> |
| <span id="L21"><span class="lineNum"> 21</span> :<span class="tlaGNC"> 10068 : static void __up(struct heap *h, size_t j)</span></span> |
| <span id="L22"><span class="lineNum"> 22</span> : : {</span> |
| <span id="L23"><span class="lineNum"> 23</span> : : size_t i; /* parent */</span> |
| <span id="L24"><span class="lineNum"> 24</span> : : </span> |
| <span id="L25"><span class="lineNum"> 25</span> :<span class="tlaGNC"> 23256 : while (j) {</span></span> |
| <span id="L26"><span class="lineNum"> 26</span> :<span class="tlaGNC"> 23224 : i = (j - 1) / 2;</span></span> |
| <span id="L27"><span class="lineNum"> 27</span> : : </span> |
| <span id="L28"><span class="lineNum"> 28</span> :<span class="tlaGNC"> 23224 : if (h->less(h->data[j], h->data[i])) {</span></span> |
| <span id="L29"><span class="lineNum"> 29</span> :<span class="tlaGNC"> 13188 : swap(h, i, j);</span></span> |
| <span id="L30"><span class="lineNum"> 30</span> :<span class="tlaGNC"> 13188 : j = i;</span></span> |
| <span id="L31"><span class="lineNum"> 31</span> : : } else {</span> |
| <span id="L32"><span class="lineNum"> 32</span> :<span class="tlaGNC"> 10036 : break;</span></span> |
| <span id="L33"><span class="lineNum"> 33</span> : : }</span> |
| <span id="L34"><span class="lineNum"> 34</span> : : }</span> |
| <span id="L35"><span class="lineNum"> 35</span> :<span class="tlaGNC"> 10068 : }</span></span> |
| <span id="L36"><span class="lineNum"> 36</span> : : </span> |
| <span id="L37"><span class="lineNum"> 37</span> :<span class="tlaGNC"> 10068 : int heap_push(struct heap *h, void *data)</span></span> |
| <span id="L38"><span class="lineNum"> 38</span> : : {</span> |
| <span id="L39"><span class="lineNum"> 39</span> :<span class="tlaGNC"> 10068 : if (h->len == h->cap) {</span></span> |
| <span id="L40"><span class="lineNum"> 40</span> :<span class="tlaGNC"> 10068 : void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));</span></span> |
| <span id="L41"><span class="lineNum"> 41</span> :<span class="tlaGNC"> 10068 : if (m == NULL)</span></span> |
| <span id="L42"><span class="lineNum"> 42</span> :<span class="tlaUNC tlaBgUNC"> 0 : return -1;</span></span> |
| <span id="L43"><span class="lineNum"> 43</span> :<span class="tlaGNC tlaBgGNC"> 10068 : h->data = m;</span></span> |
| <span id="L44"><span class="lineNum"> 44</span> :<span class="tlaGNC"> 10068 : h->cap++;</span></span> |
| <span id="L45"><span class="lineNum"> 45</span> : : }</span> |
| <span id="L46"><span class="lineNum"> 46</span> :<span class="tlaGNC"> 10068 : h->data[h->len++] = data;</span></span> |
| <span id="L47"><span class="lineNum"> 47</span> :<span class="tlaGNC"> 10068 : __up(h, h->len - 1);</span></span> |
| <span id="L48"><span class="lineNum"> 48</span> :<span class="tlaGNC"> 10068 : return 0;</span></span> |
| <span id="L49"><span class="lineNum"> 49</span> : : }</span> |
| <span id="L50"><span class="lineNum"> 50</span> : : </span> |
| <span id="L51"><span class="lineNum"> 51</span> :<span class="tlaGNC"> 137032 : static void __down(struct heap *h, size_t i)</span></span> |
| <span id="L52"><span class="lineNum"> 52</span> : : {</span> |
| <span id="L53"><span class="lineNum"> 53</span> : : size_t l, r, j; /* left, right, min child */</span> |
| <span id="L54"><span class="lineNum"> 54</span> : : </span> |
| <span id="L55"><span class="lineNum"> 55</span> : : while (1) {</span> |
| <span id="L56"><span class="lineNum"> 56</span> :<span class="tlaGNC"> 137032 : l = 2 * i + 1;</span></span> |
| <span id="L57"><span class="lineNum"> 57</span> :<span class="tlaGNC"> 137032 : if (l >= h->len)</span></span> |
| <span id="L58"><span class="lineNum"> 58</span> :<span class="tlaGNC"> 18554 : break;</span></span> |
| <span id="L59"><span class="lineNum"> 59</span> :<span class="tlaGNC"> 118478 : r = l + 1;</span></span> |
| <span id="L60"><span class="lineNum"> 60</span> :<span class="tlaGNC"> 118478 : if (r >= h->len)</span></span> |
| <span id="L61"><span class="lineNum"> 61</span> :<span class="tlaGNC"> 50 : j = l;</span></span> |
| <span id="L62"><span class="lineNum"> 62</span> : : else</span> |
| <span id="L63"><span class="lineNum"> 63</span> :<span class="tlaGNC"> 118428 : j = h->less(h->data[l], h->data[r]) ? l : r;</span></span> |
| <span id="L64"><span class="lineNum"> 64</span> : : </span> |
| <span id="L65"><span class="lineNum"> 65</span> :<span class="tlaGNC"> 118478 : if (h->less(h->data[j], h->data[i])) {</span></span> |
| <span id="L66"><span class="lineNum"> 66</span> :<span class="tlaGNC"> 116938 : swap(h, i, j);</span></span> |
| <span id="L67"><span class="lineNum"> 67</span> :<span class="tlaGNC"> 116938 : i = j;</span></span> |
| <span id="L68"><span class="lineNum"> 68</span> : : } else {</span> |
| <span id="L69"><span class="lineNum"> 69</span> :<span class="tlaGNC"> 1540 : break;</span></span> |
| <span id="L70"><span class="lineNum"> 70</span> : : }</span> |
| <span id="L71"><span class="lineNum"> 71</span> : : }</span> |
| <span id="L72"><span class="lineNum"> 72</span> :<span class="tlaGNC"> 20094 : }</span></span> |
| <span id="L73"><span class="lineNum"> 73</span> : : </span> |
| <span id="L74"><span class="lineNum"> 74</span> :<span class="tlaGNC"> 10068 : void *heap_pop(struct heap *h)</span></span> |
| <span id="L75"><span class="lineNum"> 75</span> : : {</span> |
| <span id="L76"><span class="lineNum"> 76</span> :<span class="tlaGNC"> 10068 : void *ret = h->data[0];</span></span> |
| <span id="L77"><span class="lineNum"> 77</span> : : void *m;</span> |
| <span id="L78"><span class="lineNum"> 78</span> : : </span> |
| <span id="L79"><span class="lineNum"> 79</span> :<span class="tlaGNC"> 10068 : swap(h, 0, --h->len);</span></span> |
| <span id="L80"><span class="lineNum"> 80</span> :<span class="tlaGNC"> 10068 : if (h->len) {</span></span> |
| <span id="L81"><span class="lineNum"> 81</span> :<span class="tlaGNC"> 10062 : __down(h, 0);</span></span> |
| <span id="L82"><span class="lineNum"> 82</span> :<span class="tlaGNC"> 10062 : if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {</span></span> |
| <span id="L83"><span class="lineNum"> 83</span> :<span class="tlaGNC"> 2 : m = realloc(h->data, h->len * sizeof(void *));</span></span> |
| <span id="L84"><span class="lineNum"> 84</span> :<span class="tlaGNC"> 2 : if (m == NULL)</span></span> |
| <span id="L85"><span class="lineNum"> 85</span> :<span class="tlaUNC tlaBgUNC"> 0 : return NULL;</span></span> |
| <span id="L86"><span class="lineNum"> 86</span> :<span class="tlaGNC tlaBgGNC"> 2 : h->data = m;</span></span> |
| <span id="L87"><span class="lineNum"> 87</span> :<span class="tlaGNC"> 2 : h->cap = h->len;</span></span> |
| <span id="L88"><span class="lineNum"> 88</span> : : }</span> |
| <span id="L89"><span class="lineNum"> 89</span> : : }</span> |
| <span id="L90"><span class="lineNum"> 90</span> : : </span> |
| <span id="L91"><span class="lineNum"> 91</span> :<span class="tlaGNC"> 10068 : return ret;</span></span> |
| <span id="L92"><span class="lineNum"> 92</span> : : }</span> |
| <span id="L93"><span class="lineNum"> 93</span> : : </span> |
| <span id="L94"><span class="lineNum"> 94</span> :<span class="tlaGNC"> 6 : struct heap *heap_init(heap_less_func_t less)</span></span> |
| <span id="L95"><span class="lineNum"> 95</span> : : {</span> |
| <span id="L96"><span class="lineNum"> 96</span> :<span class="tlaGNC"> 6 : struct heap *heap = calloc(1, sizeof(*heap));</span></span> |
| <span id="L97"><span class="lineNum"> 97</span> : : </span> |
| <span id="L98"><span class="lineNum"> 98</span> :<span class="tlaGNC"> 6 : if (heap == NULL)</span></span> |
| <span id="L99"><span class="lineNum"> 99</span> :<span class="tlaUNC tlaBgUNC"> 0 : return NULL;</span></span> |
| <span id="L100"><span class="lineNum"> 100</span> :<span class="tlaGNC tlaBgGNC"> 6 : heap->less = less;</span></span> |
| <span id="L101"><span class="lineNum"> 101</span> :<span class="tlaGNC"> 6 : return heap;</span></span> |
| <span id="L102"><span class="lineNum"> 102</span> : : }</span> |
| <span id="L103"><span class="lineNum"> 103</span> : : </span> |
| <span id="L104"><span class="lineNum"> 104</span> :<span class="tlaGNC"> 10 : void heap_ify(struct heap *h, heap_less_func_t less)</span></span> |
| <span id="L105"><span class="lineNum"> 105</span> : : {</span> |
| <span id="L106"><span class="lineNum"> 106</span> : : int i;</span> |
| <span id="L107"><span class="lineNum"> 107</span> : : </span> |
| <span id="L108"><span class="lineNum"> 108</span> :<span class="tlaGNC"> 10 : if (less)</span></span> |
| <span id="L109"><span class="lineNum"> 109</span> :<span class="tlaGNC"> 8 : h->less = less;</span></span> |
| <span id="L110"><span class="lineNum"> 110</span> : : </span> |
| <span id="L111"><span class="lineNum"> 111</span> :<span class="tlaGNC"> 10042 : for (i = h->len / 2 - 1; i >= 0; i--)</span></span> |
| <span id="L112"><span class="lineNum"> 112</span> :<span class="tlaGNC"> 10032 : __down(h, i);</span></span> |
| <span id="L113"><span class="lineNum"> 113</span> :<span class="tlaGNC"> 10 : }</span></span> |
| <span id="L114"><span class="lineNum"> 114</span> : : </span> |
| <span id="L115"><span class="lineNum"> 115</span> :<span class="tlaGNC"> 6 : void heap_free(struct heap *heap)</span></span> |
| <span id="L116"><span class="lineNum"> 116</span> : : {</span> |
| <span id="L117"><span class="lineNum"> 117</span> :<span class="tlaGNC"> 6 : free(heap->data);</span></span> |
| <span id="L118"><span class="lineNum"> 118</span> :<span class="tlaGNC"> 6 : free(heap);</span></span> |
| <span id="L119"><span class="lineNum"> 119</span> :<span class="tlaGNC"> 6 : }</span></span> |
| </pre> |
| </td> |
| </tr> |
| </table> |
| <br> |
| |
| <table width="100%" border=0 cellspacing=0 cellpadding=0> |
| <tr><td class="ruler"><img src="../../glass.png" width=3 height=3 alt=""></td></tr> |
| <tr><td class="versionInfo">Generated by: <a href="https://github.com//linux-test-project/lcov" target="_parent">LCOV version 2.0-1</a></td></tr> |
| </table> |
| <br> |
| |
| </body> |
| </html> |
