/***************************************************************************
 * gh_heap.c -- heap based priority queue.                                 *
 *                                                                         *
 ***********************IMPORTANT NSOCK LICENSE TERMS***********************
 *                                                                         *
 * The nsock parallel socket event library is (C) 1999-2013 Insecure.Com   *
 * LLC This library is free software; you may redistribute and/or          *
 * modify it under the terms of the GNU General Public License as          *
 * published by the Free Software Foundation; Version 2.  This guarantees  *
 * your right to use, modify, and redistribute this software under certain *
 * conditions.  If this license is unacceptable to you, Insecure.Com LLC   *
 * may be willing to sell alternative licenses (contact                    *
 * sales@insecure.com ).                                                   *
 *                                                                         *
 * As a special exception to the GPL terms, Insecure.Com LLC grants        *
 * permission to link the code of this program with any version of the     *
 * OpenSSL library which is distributed under a license identical to that  *
 * listed in the included docs/licenses/OpenSSL.txt file, and distribute   *
 * linked combinations including the two. You must obey the GNU GPL in all *
 * respects for all of the code used other than OpenSSL.  If you modify    *
 * this file, you may extend this exception to your version of the file,   *
 * but you are not obligated to do so.                                     *
 *                                                                         *
 * If you received these files with a written license agreement stating    *
 * terms other than the (GPL) terms above, then that alternative license   *
 * agreement takes precedence over this comment.                           *
 *                                                                         *
 * Source is provided to this software because we believe users have a     *
 * right to know exactly what a program is going to do before they run it. *
 * This also allows you to audit the software for security holes.          *
 *                                                                         *
 * Source code also allows you to port Nmap to new platforms, fix bugs,    *
 * and add new features.  You are highly encouraged to send your changes   *
 * to the dev@nmap.org mailing list for possible incorporation into the    *
 * main distribution.  By sending these changes to Fyodor or one of the    *
 * Insecure.Org development mailing lists, or checking them into the Nmap  *
 * source code repository, it is understood (unless you specify otherwise) *
 * that you are offering the Nmap Project (Insecure.Com LLC) the           *
 * unlimited, non-exclusive right to reuse, modify, and relicense the      *
 * code.  Nmap will always be available Open Source, but this is important *
 * because the inability to relicense code has caused devastating problems *
 * for other Free Software projects (such as KDE and NASM).  We also       *
 * occasionally relicense the code to third parties as discussed above.    *
 * If you wish to specify special license conditions of your               *
 * contributions, just say so when you send them.                          *
 *                                                                         *
 * 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 v2.0 for more details                            *
 * (http://www.gnu.org/licenses/gpl-2.0.html).                             *
 *                                                                         *
 ***************************************************************************/

/* $Id$ */

#ifdef HAVE_CONFIG_H
#include "nsock_config.h"
#include "nbase_config.h"
#endif

#ifdef WIN32
#include "nbase_winconfig.h"
#endif

#include <nbase.h>
#include "gh_heap.h"

#define GH_SLOTS   128


static gh_hnode_t **hnode_ptr(gh_heap_t *heap, unsigned int index) {
  assert(index >= 0);
  assert(index <= heap->count);
  return &(heap->slots[index]);
}

gh_hnode_t *gh_heap_find(gh_heap_t *heap, unsigned int index) {
  if (index >= heap->count)
    return NULL;

  return *hnode_ptr(heap, index);
}

static int hnode_up(gh_heap_t *heap, gh_hnode_t *hnode)
{
  unsigned int cur_idx = hnode->index;
  gh_hnode_t **cur_ptr = hnode_ptr(heap, cur_idx);
  unsigned int parent_idx;
  gh_hnode_t **parent_ptr;
  int action = 0;

  assert(*cur_ptr == hnode);

  while (cur_idx > 0) {
    parent_idx = (cur_idx - 1) >> 1;

    parent_ptr = hnode_ptr(heap, parent_idx);
    assert((*parent_ptr)->index == parent_idx);

    if (heap->cmp_op(*parent_ptr, hnode))
      break;

    (*parent_ptr)->index = cur_idx;
    *cur_ptr = *parent_ptr;
    cur_ptr = parent_ptr;
    cur_idx = parent_idx;
    action = 1;
  }

  hnode->index = cur_idx;
  *cur_ptr = hnode;

  return action;
}

static int hnode_down(gh_heap_t *heap, gh_hnode_t *hnode)
{
  unsigned int count = heap->count;
  unsigned int ch1_idx, ch2_idx, cur_idx;
  gh_hnode_t **ch1_ptr, **ch2_ptr, **cur_ptr;
  gh_hnode_t  *ch1, *ch2;
  int action = 0;

  cur_idx = hnode->index;
  cur_ptr = hnode_ptr(heap, cur_idx);
  assert(*cur_ptr == hnode);

  while (cur_idx < count) {
    ch1_idx = (cur_idx << 1) + 1;
    if (ch1_idx >= count)
      break;

    ch1_ptr = hnode_ptr(heap, ch1_idx);
    ch1 = *ch1_ptr;

    ch2_idx = ch1_idx + 1;
    if (ch2_idx < count) {
      ch2_ptr = hnode_ptr(heap, ch2_idx);
      ch2 = *ch2_ptr;

      if (heap->cmp_op(ch2, ch1)) {
        ch1_idx = ch2_idx;
        ch1_ptr = ch2_ptr;
        ch1 = ch2;
      }
    }

    assert(ch1->index == ch1_idx);

    if (heap->cmp_op(hnode, ch1))
      break;

    ch1->index = cur_idx;
    *cur_ptr = ch1;
    cur_ptr = ch1_ptr;
    cur_idx = ch1_idx;
    action = 1;
  }

  hnode->index = cur_idx;
  *cur_ptr = hnode;

  return action;
}

static int heap_grow(gh_heap_t *heap) {
  int newsize;

  /* Do we really need to grow? */
  assert(heap->count == heap->highwm);

  newsize = heap->count + GH_SLOTS;
  heap->slots = (gh_hnode_t **)safe_realloc(heap->slots,
                                            newsize * sizeof(gh_hnode_t *));
  heap->highwm += GH_SLOTS;
  return 0;
}

int gh_heap_init(gh_heap_t *heap, gh_heap_cmp_t cmp_op) {
  int rc;

  if (!cmp_op)
      return -1;

  heap->cmp_op = cmp_op;
  heap->count  = 0;
  heap->highwm = 0;
  heap->slots  = NULL;

  rc = heap_grow(heap);
  if (rc)
    gh_heap_free(heap);

  return rc;
}

void gh_heap_free(gh_heap_t *heap) {
  if (heap->highwm) {
    assert(heap->slots);
    free(heap->slots);
  }
  memset(heap, 0, sizeof(gh_heap_t));
}

int gh_heap_push(gh_heap_t *heap, gh_hnode_t *hnode) {
  gh_hnode_t **new_ptr;
  unsigned int new_index = heap->count;

  assert(!gh_hnode_is_valid(hnode));

  if (new_index == heap->highwm)
    heap_grow(heap);

  hnode->index = new_index;
  new_ptr = hnode_ptr(heap, new_index);
  heap->count++;
  *new_ptr = hnode;

  hnode_up(heap, hnode);
  return 0;
}

int gh_heap_remove(gh_heap_t *heap, gh_hnode_t *hnode)
{
  unsigned int count = heap->count;
  unsigned int cur_idx = hnode->index;
  gh_hnode_t **cur_ptr;
  gh_hnode_t *last;

  assert(gh_hnode_is_valid(hnode));
  assert(cur_idx < count);

  cur_ptr = hnode_ptr(heap, cur_idx);
  assert(*cur_ptr == hnode);

  count--;
  last = *hnode_ptr(heap, count);
  heap->count = count;
  if (last == hnode)
    return 0;

  last->index = cur_idx;
  *cur_ptr = last;
  if (!hnode_up(heap, *cur_ptr))
    hnode_down(heap, *cur_ptr);

  gh_hnode_invalidate(hnode);
  return 0;
}