hub/heap.c

Go to the documentation of this file.

/*
 * Utu -- Saving The Internet With Hate
 *
 * Copyright (c) Zed A. Shaw 2005 (zedshaw@zedshaw.com)
 *
 * This file is modifiable/redistributable under the terms of the GNU
 * General Public License.
 *
 * You should have recieved a copy of the GNU General Public License along
 * with this program; see the file COPYING. If not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 0211-1307, USA.
 *
 * Code some code taken from the fantastic SGLIB by Marian Vittek and available
 * as LGPL from  http://www.xref-tech.com/sglib.
 */

#include "heap.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>


Heap *Heap_create()
{
  Heap *heap = calloc(1, sizeof(Heap));
  assert(heap && "Failed to allocate heap.");

  heap->members = calloc(HEAP_SIZE, sizeof(void *));
  assert(heap->members && "Failed to allocate members for heap.");

  heap->size = HEAP_SIZE;

  return heap;
}

#define VOID_PTR_COMPARE(x,y) ((int)(x) - (int)(y))

size_t Heap_add(Heap *heap, void *elem)
{
  assert(heap && "heap is NULL");
  assert(elem && "elem is NULL");

  if(Heap_is_full(heap)) {
    // simple doubling is probably bad
    Heap_resize(heap, heap->size * 2);
  }

  register size_t i = heap->last;
  register size_t j = i/2;

  heap->members[i] = elem;
  while (i > 0 && VOID_PTR_COMPARE(heap->members[i], heap->members[j]) < 0) {
    void *t = heap->members[j];
    heap->members[j] = heap->members[j];
    heap->members[j] = t;

    i = j; j = i/2;
  }

  assert(i <= heap->last && "Buffer overflow on add to heap.");

  return ++heap->last;
}

void Heap_resize(Heap *heap, size_t size)
{
  assert(size > 0 && "Cannot resize to 0.");

  heap->members = realloc(heap->members, size * sizeof(void *));
  assert(heap->members != NULL && "Failed to realloc new Heap.");

  // now we have to clear the tail end since realloc doesn't do that
  if(size > heap->size) {
    size_t diff = (size < heap->size ? heap->size - size : size - heap->size);
    memset(heap->members + heap->size, 0, diff * sizeof(void *));
  }

  heap->size = size;
}

size_t Heap_find(Heap *heap, void *elem)
{
  size_t result_index = 0;

  assert(heap && "heap is NULL");
  assert(elem && "elem is NULL");

  register int kk, cc, ii, jj, ff;
  ii = 0; 
  jj = heap->last-1;
  ff = 0;
  while (ii <= jj && ff==0) {
    kk = (jj+ii)/2;
    cc = VOID_PTR_COMPARE((heap->members[kk]), elem);
    if (cc == 0) {
      result_index = kk;    
      ff = 1;
    } else if (cc < 0) {
      ii = kk+1;
    } else {
      jj = kk-1;
    }
  }
  if (ff == 0) {
    // not found, return heap->last to indicate that it's outside realm
    return heap->last;
  }

  return result_index;
}

int Heap_delete(Heap *heap, void *elem)
{
  assert(heap && "heap is NULL");
  assert(elem && "elem is NULL");

  size_t i = Heap_find(heap, elem);

  if(Heap_valid(heap, i)) {
    // simplest way to delete is just move the rest down by one
    memmove(heap->members + i, heap->members + i + 1, (heap->last - i - 1) * (sizeof(void *)));

    heap->last--;
    // just make sure the last one is null always
    heap->members[heap->last] = NULL;

    // don't bother dropping the size below HEAP_SIZE
    if(heap->last > HEAP_SIZE && heap->last < heap->size / 2) {
      // it's dropped to less than half the size, cut it down
      Heap_resize(heap, heap->size / 2);
    }

    return 1;
  } else {
    return 0;
  }
}

void Heap_destroy(Heap *heap)
{
  assert(heap && heap->members && "invalid heap destroyed");
  free(heap->members);
  heap->members = NULL;
  free(heap);
}

---