File: heap.c

package info (click to toggle)
mcl 1%3A14-137-1
  • links: PTS, VCS
  • area: main
  • in suites: jessie, jessie-kfreebsd, stretch
  • size: 10,704 kB
  • ctags: 5,125
  • sloc: ansic: 53,217; sh: 4,448; perl: 3,967; makefile: 422
file content (145 lines) | stat: -rw-r--r-- 3,151 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/*   (C) Copyright 2001, 2002, 2003, 2004, 2005 Stijn van Dongen
 *   (C) Copyright 2006, 2007, 2008, 2009  Stijn van Dongen
 *
 * This file is part of tingea.  You can redistribute and/or modify tingea
 * under the terms of the GNU General Public License; either version 3 of the
 * License or (at your option) any later version.  You should have received a
 * copy of the GPL along with tingea, in the file COPYING.
*/


#include <stdio.h>
#include <string.h>

#include "alloc.h"
#include "heap.h"
#include "types.h"
#include "err.h"


mcxHeap* mcxHeapInit
(  void* h
)
   {  mcxHeap* heap  =     h

   ;  if (!heap && !(heap = mcxAlloc(sizeof(mcxHeap), RETURN_ON_FAIL)))
      return NULL

   ;  heap->base     =     NULL
   ;  heap->heapSize =     0
   ;  heap->elemSize =     0
   ;  heap->cmp      =     NULL
   ;  heap->n_inserted =   0
   ;  return heap
;  }


mcxHeap* mcxHeapNew
(  mcxHeap*    h
,  dim         heapSize
,  dim         elemSize
,  int (*cmp)  (const void* lft, const void* rgt)
)
   {  mcxHeap* heap     =  mcxHeapInit(h)
   ;  mcxstatus status  =  STATUS_FAIL
   ;  char*    base

   ;  do
      {  if (!heap)
         break
      ;  if (!(heap->base = mcxAlloc (heapSize*elemSize, RETURN_ON_FAIL)))
         break
      ;  status = STATUS_OK
   ;  }
      while (0)

   ;  if (status)
      {  mcxHeapFree(&heap)
      ;  return NULL
   ;  }
      heap->heapSize    =  heapSize
   ;  heap->elemSize    =  elemSize
   ;  heap->cmp         =  cmp
   ;  heap->n_inserted  =  0
   ;  base              =  (char*) heap->base
   ;  return heap
;  }


void mcxHeapClean
(  mcxHeap*   heap
)  
   {  heap->n_inserted = 0
;  }


void mcxHeapRelease
(  void* heapv
)  
   {  mcxHeap* heap = (mcxHeap*) heapv

   ;  if (heap->base)
      mcxFree(heap->base)
   ;  heap->base     = NULL
   ;  heap->heapSize = 0
;  }


void mcxHeapFree
(  mcxHeap**   heap
)  
   {  if (*heap)
      {  if ((*heap)->base)
         mcxFree((*heap)->base)
         
      ;  mcxFree(*heap)
      ;  *heap       =  NULL
   ;  }
   }



void mcxHeapInsert
(  mcxHeap* heap
,  void*    elem
)  
   {  char* heapRoot =  heap->base
   ;  char* elemch   =  elem
   ;  dim   elsz     =  heap->elemSize
   ;  dim   hpsz     =  heap->heapSize

   ;  int (*cmp)(const void *, const void*) =  heap->cmp

   ;  if (heap->n_inserted  < hpsz)
      {  dim i =  heap->n_inserted

      ;  while (i != 0 && (cmp)(heapRoot+elsz*((i-1)/2), elemch) < 0)
         {  memcpy(heapRoot + i*elsz, heapRoot + elsz*((i-1)/2), elsz)
         ;  i = (i-1)/2
      ;  }
         memcpy(heapRoot + i*elsz, elemch, elsz)
      ;  heap->n_inserted++
   ;  }
      else if ((cmp)(elemch, heapRoot) < 0)
      {  dim root = 0
      ;  dim d

      ;  while ((d = 2*root+1) < hpsz)
         {  if
            (  (d+1<hpsz)
            && (cmp)(heapRoot + d*elsz, heapRoot + (d+1)*elsz) < 0
            )
            d++

         ;  if ((cmp)(elemch, heapRoot + d*elsz) < 0)
            {  memcpy(heapRoot+root*elsz, heapRoot+d*elsz, elsz)
            ;  root = d
         ;  }
            else
            break
      ;  }
         memcpy(heapRoot+root*elsz, elemch, elsz)
   ;  }
   }