pcb 4.1.1
An interactive printed circuit board layout editor.

src/heap.c File Reference

Operations on heaps. More...

#include "global.h"
#include <assert.h>
#include "heap.h"
Include dependency graph for src/heap.c:

Go to the source code of this file.

Data Structures

struct  heap_element
struct  heap_struct

Functions

static int __heap_is_good (heap_t *heap)
heap_theap_create ()
 Create an empty heap.
void heap_destroy (heap_t **heap)
 Destroy a heap.
void heap_free (heap_t *heap, void(*freefunc)(void *))
 Free all elements in the heap.
static void __upheap (heap_t *heap, int k)
void heap_insert (heap_t *heap, cost_t cost, void *data)
static void __downheap (heap_t *heap, int k)
 This procedure moves down the heap.
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.

Variables

static cost_t MIN_COST = 0

Detailed Description

Operations on heaps.

This file, heap.c, 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 src/heap.c.


Function Documentation

static void __downheap ( heap_t heap,
int  k 
) [static]

This procedure moves down the heap.

Exchanging the node at position k with the smaller of its two children as necessary and stopping when the node at k is smaller than both children or the bottom is reached.

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

References heap_element::cost.

Referenced by heap_remove_smallest(), and heap_replace().

static int __heap_is_good ( heap_t heap) [static]
static void __upheap ( heap_t heap,
int  k 
) [static]

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

References heap_element::cost, and MIN_COST.

Referenced by heap_insert().

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 *)  freefunc 
)

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 
)
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:


Variable Documentation

cost_t MIN_COST = 0 [static]

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

Referenced by __upheap(), heap_create(), and heap_insert().