heap.h File Reference

Prototypes for heap routines. More...

#include "global.h"

Include dependency graph for heap.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef double	cost_t
	Type of heap costs.
typedef struct heap_struct	heap_t
	What a heap looks like.
Functions
heap_t *	heap_create ()
	Create an empty heap.
void	heap_destroy (heap_t **heap)
	Destroy a heap.
void	heap_free (heap_t *heap, void(*funcfree)(void *))
	Free all elements in the heap.
void	heap_insert (heap_t *heap, cost_t cost, void *data)
void *	heap_remove_smallest (heap_t *heap)
	Remove the smallest item from the heap.
void *	heap_replace (heap_t *heap, cost_t cost, void *data)
	Replace the smallest item with a new item and return the smallest item.
int	heap_is_empty (heap_t *heap)
	Return whether the heap is empty.
int	heap_size (heap_t *heap)
	Return the size of the heap.

---

Detailed Description

Prototypes for heap routines.

This file, heap.h, was written and is

Copyright (c) 2001 C. Scott Ananian

---

Copyright.

PCB, interactive printed circuit board design

Copyright (C) 1994,1995,1996 Thomas Nau

Copyright (C) 1998,1999,2000,2001 harry eaton

This program 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 of the License, 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.

Contact addresses for paper mail and Email: harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA haceaton@aplcomm.jhuapl.edu

Definition in file heap.h.

---

Typedef Documentation

typedef double cost_t

Type of heap costs.

Definition at line 47 of file heap.h.

typedef struct heap_struct heap_t

What a heap looks like.

Definition at line 51 of file heap.h.

---

Function Documentation

heap_t* heap_create

(

)

Create an empty heap.

Definition at line 116 of file src/heap.c.

References __heap_is_good(), and MIN_COST.

Referenced by BreakManyEdges(), cntr_in_M_POLYAREA(), InsertHoles(), mtspace_query_rect(), RouteAll(), and RouteOne().

Here is the call graph for this function:

void heap_destroy

(

heap_t **

heap

)

Destroy a heap.

Definition at line 134 of file src/heap.c.

References __heap_is_good().

Referenced by BreakManyEdges(), cntr_in_M_POLYAREA(), gts_surface_strip(), InsertHoles(), mtsFreeWork(), RouteAll(), and RouteOne().

Here is the call graph for this function:

void heap_free	(	heap_t *	heap,
		void(*)(void *)	funcfree
	)

Free all elements in the heap.

Definition at line 147 of file src/heap.c.

References __heap_is_good().

Referenced by mtsFreeWork(), and RouteOne().

Here is the call graph for this function:

void heap_insert	(	heap_t *	heap,
		cost_t	cost,
		void *	data
	)

Definition at line 175 of file src/heap.c.

References __heap_is_good(), __upheap(), heap_element::cost, heap_element::data, MIN_COST, and realloc().

Referenced by add_or_destroy_edge(), blocker_to_heap(), cntr_in_M_POLYAREA(), CreateSearchEdge(), heap_append(), heap_it(), mtspace_query_rect(), RouteAll(), and RouteOne().

Here is the call graph for this function:

int heap_is_empty

(

heap_t *

heap

)

Return whether the heap is empty.

Definition at line 278 of file src/heap.c.

References __heap_is_good().

Referenced by BreakManyEdges(), cntr_in_M_POLYAREA(), gts_surface_strip(), heap_replace(), InsertHoles(), mtspace_query_rect(), qloop(), RouteAll(), and RouteOne().

Here is the call graph for this function:

void* heap_remove_smallest

(

heap_t *

heap

)

Remove the smallest item from the heap.

Definition at line 231 of file src/heap.c.

References __downheap(), __heap_is_good(), and heap_element::data.

Referenced by BreakManyEdges(), cntr_in_M_POLYAREA(), InsertHoles(), qloop(), RouteAll(), and RouteOne().

Here is the call graph for this function:

void* heap_replace	(	heap_t *	heap,
		cost_t	cost,
		void *	data
	)

Replace the smallest item with a new item and return the smallest item.

If the new item is the smallest, than return it, instead.

Definition at line 254 of file src/heap.c.

References __downheap(), __heap_is_good(), heap_element::cost, heap_element::data, and heap_is_empty().

Here is the call graph for this function:

int heap_size

(

heap_t *

heap

)

Return the size of the heap.

Definition at line 290 of file src/heap.c.

References __heap_is_good().

Referenced by RouteAll().

Here is the call graph for this function: