| /* AUTORIGHTS |
| Copyright (C) 2007 Princeton University |
| |
| This file is part of Ferret Toolkit. |
| |
| Ferret Toolkit is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software Foundation, |
| Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
| */ |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| #include "heap.h" |
| |
| typedef unsigned int u32int; |
| #define nil NULL |
| #define print printf |
| |
| |
| struct Heap { |
| int size; |
| int nheap; |
| int mheap; |
| u32int *heap; |
| int (*compare)(void*, void*); |
| }; |
| |
| #define swap(a, b, n) { \ |
| int __k; \ |
| u32int __tmp; \ |
| for(__k=n; __k>0; __k--){ \ |
| __tmp = *a; \ |
| *a++ = *b; \ |
| *b++ = __tmp; \ |
| } \ |
| } |
| |
| Heap* |
| mkheap(int (*compare)(void*, void*), int k, int m) |
| { |
| Heap *heap; |
| |
| heap = malloc(sizeof *heap); |
| if(heap == nil) |
| return nil; |
| heap->size = k/4; |
| heap->nheap = 0; |
| heap->mheap = m; |
| heap->compare = compare; |
| heap->heap = malloc(heap->mheap*4*heap->size); |
| if(heap->heap == nil){ |
| free(heap); |
| return nil; |
| } |
| memset(heap->heap, 0, heap->mheap*4*heap->size); |
| return heap; |
| } |
| |
| void |
| freeheap(Heap *heap) |
| { |
| if(heap == nil) |
| return; |
| free(heap->heap); |
| free(heap); |
| return; |
| } |
| |
| void |
| heapreset(Heap *heap) |
| { |
| heap->nheap = 0; |
| return; |
| } |
| |
| int |
| heapsize(Heap *heap) |
| { |
| return heap->nheap; |
| } |
| |
| int |
| heapmaxsize(Heap *heap) |
| { |
| return heap->mheap; |
| } |
| |
| int |
| heapinsert(Heap *heap, void *v) |
| { |
| int i; |
| int k, p; |
| u32int *h; |
| u32int *a, *b; |
| int (*compare)(void*, void*); |
| |
| if(heap->nheap == heap->mheap) |
| return -1; |
| |
| k = heap->size; |
| h = heap->heap; |
| compare = heap->compare; |
| |
| i = heap->nheap++; |
| a = h+i*k; |
| memmove(a, v, k<<2); |
| |
| for(;;){ |
| if(i == 0) |
| break; |
| p = (i-1)/2; |
| a = h+i*k; |
| b = h+p*k; |
| if(compare(a, b) > 0) |
| break; |
| swap(a, b, k); |
| i = p; |
| } |
| |
| return 0; |
| } |
| |
| void* |
| heapmin(Heap *heap) |
| { |
| if(heap->nheap == 0) |
| return nil; |
| return heap->heap; |
| } |
| |
| int |
| heapextractmin(Heap *heap, void *v) |
| { |
| int n, i; |
| int j, k; |
| u32int *h; |
| u32int *a, *b; |
| int (*compare)(void*, void*); |
| |
| if(heap->nheap == 0) |
| return -1; |
| |
| h = heap->heap; |
| k = heap->size; |
| n = heap->nheap-1; |
| compare = heap->compare; |
| |
| heap->nheap--; |
| |
| memmove(v, h, k<<2); |
| memmove(h, h+n*k, k<<2); |
| |
| /* restore heap property */ |
| for(i=0, j=1; j<=n; i=j, j=2*i+1){ |
| if(j<n){ |
| a = h+j*k; |
| if(compare(a, a+k) >= 0) |
| j++; |
| } |
| a = h+i*k; |
| b = h+j*k; |
| if(compare(a, b) <= 0) |
| break; |
| swap(a, b, k); |
| } |
| return 0; |
| } |
| |
| #define HEAPTEST |
| #ifdef HEAPTEST |
| enum { |
| NHeap = 50, |
| }; |
| |
| static int |
| heapcmp(void *v1, void *v2) |
| { |
| u32int *p1, *p2; |
| |
| p1 = (u32int*)v1; |
| p2 = (u32int*)v2; |
| |
| if(*p1 < *p2) |
| return +1; |
| else if(*p1 > *p2) |
| return -1; |
| return 0; |
| } |
| |
| static void |
| dumpheap(Heap *heap) |
| { |
| int i; |
| |
| for(i=0; i<heap->nheap; i++) |
| print("\t%d\t%d\n", i, heap->heap[i]); |
| return; |
| } |
| |
| int |
| heaptest(void) |
| { |
| int i, x; |
| Heap *heap; |
| |
| heap = mkheap(heapcmp, sizeof(u32int), NHeap); |
| |
| for(i=0; i<NHeap; i++){ |
| x = i+1; |
| heapinsert(heap, &x); |
| } |
| for(i=0; i<NHeap; i++){ |
| heapextractmin(heap, &x); |
| print("%d\n", x); |
| } |
| |
| freeheap(heap); |
| return 0; |
| } |
| #endif |