heap.c revision 0c27b3fe77ac1d5094ba3521e8142d9e7973133f
/*
* Copyright (C) 1997-2001, 2004-2007, 2010-2016 Internet Systems Consortium, Inc. ("ISC")
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*/
/* $Id$ */
/*! \file
* Heap implementation of priority queues adapted from the following:
*
* \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest,
* MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.
*
* \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988,
* ISBN 0-201-06673-4, chapter 11.
*/
#include <config.h>
/*@{*/
/*%
* Note: to make heap_parent and heap_left easy to compute, the first
* element of the heap array is not used; i.e. heap subscripts are 1-based,
* not 0-based. The parent is index/2, and the left-child is index*2.
* The right child is index*2+1.
*/
#define heap_parent(i) ((i) >> 1)
#define heap_left(i) ((i) << 1)
/*@}*/
#define SIZE_INCREMENT 1024
/*%
* When the heap is in a consistent state, the following invariant
* holds true: for every element i > 1, heap_parent(i) has a priority
* higher than or equal to that of i.
*/
#define HEAPCONDITION(i) ((i) == 1 || \
/*% ISC heap structure. */
struct isc_heap {
unsigned int magic;
unsigned int size;
unsigned int size_increment;
unsigned int last;
void **array;
};
isc_heap_t **heapp)
{
return (ISC_R_NOMEMORY);
if (size_increment == 0)
else
return (ISC_R_SUCCESS);
}
void
}
static isc_boolean_t
void **new_array;
unsigned int new_size;
return (ISC_FALSE);
}
return (ISC_TRUE);
}
static void
unsigned int p;
for (p = heap_parent(i) ;
i = p, p = heap_parent(i)) {
}
INSIST(HEAPCONDITION(i));
}
static void
while (i <= half_size) {
/* Find the smallest of the (at most) two children. */
j = heap_left(i);
j++;
break;
i = j;
}
INSIST(HEAPCONDITION(i));
}
unsigned int new_last;
return (ISC_R_NOMEMORY);
return (ISC_R_SUCCESS);
}
void
void *elt;
} else {
if (less)
else
}
}
void
}
void
}
void *
return (NULL);
}
void
unsigned int i;
}