Index: trunk/src/compat_cc.h =================================================================== --- trunk/src/compat_cc.h (revision 29281) +++ trunk/src/compat_cc.h (nonexistent) @@ -1,73 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * (this file is based on PCB, interactive printed circuit board design) - * Copyright (C) 1994,1995,1996, 2004 Thomas Nau - * 15 Oct 2008 Ineiev: add different crosshair shapes - * - * 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 St, Fifth Floor, Boston, MA 02110-1301 USA - * - * Contact: - * Project page: http://repo.hu/projects/pcb-rnd - * lead developer: http://repo.hu/projects/pcb-rnd/contact.html - * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") - * - */ - -#ifndef PCB_COMPAT_CC_H -#define PCB_COMPAT_CC_H - -/* --------------------------------------------------------------------------- - * Macros to annotate branch-prediction information. - * Taken from GLib 2.16.3 (LGPL 2).G_ / g_ prefixes have - * been removed to avoid namespace clashes. - */ - -/* The LIKELY and UNLIKELY macros let the programmer give hints to - * the compiler about the expected result of an expression. Some compilers - * can use this information for optimizations. - * - * The PCB_BOOLEAN_EXPR macro is intended to trigger a gcc warning when - * putting assignments inside the test. - */ -#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) -# define PCB_BOOLEAN_EXPR(expr) \ - __extension__ ({ \ - int _boolean_var_; \ - if (expr) \ - _boolean_var_ = 1; \ - else \ - _boolean_var_ = 0; \ - _boolean_var_; \ -}) -# define PCB_LIKELY(expr) (__builtin_expect (PCB_BOOLEAN_EXPR(expr), 1)) -# define PCB_UNLIKELY(expr) (__builtin_expect (PCB_BOOLEAN_EXPR(expr), 0)) -#else -# define PCB_LIKELY(expr) (expr) -# define PCB_UNLIKELY(expr) (expr) -#endif - -#ifndef GCC_VERSION -# define GCC_VERSION (__GNUC__ * 1000 + __GNUC_MINOR__) -#endif /* GCC_VERSION */ - -#if GCC_VERSION > 2007 -# define PCB_ATTRIBUTE_UNUSED __attribute__((unused)) -#else -# define PCB_ATTRIBUTE_UNUSED -#endif - -#endif Index: trunk/src/heap.c =================================================================== --- trunk/src/heap.c (revision 29281) +++ trunk/src/heap.c (nonexistent) @@ -1,233 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * (this file is based on PCB, interactive printed circuit board design) - * Copyright (C) 1994,1995,1996 Thomas Nau - * Copyright (C) 1998,1999,2000,2001 harry eaton - * - * this file, heap.c, was written and is - * Copyright (c) 2001 C. Scott Ananian. - * - * 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: - * Project page: http://repo.hu/projects/pcb-rnd - * lead developer: http://repo.hu/projects/pcb-rnd/contact.html - * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") - * - * - * Old contact info: - * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA - * haceaton@aplcomm.jhuapl.edu - * - */ - - -/* operations on heaps. */ - -#include -#include -#include "config.h" -#include "heap.h" - -/* define this for more thorough self-checking of data structures */ -#undef SLOW_ASSERTIONS - -struct heap_element { - pcb_cost_t cost; - void *data; -}; -struct pcb_heap_s { - struct heap_element *element; - int size, max; -}; - -static pcb_cost_t MIN_COST = 0; - -/* --------------------------------------------------------------------------- - * functions. - */ -/* helper functions for assertions */ -#ifndef NDEBUG -#ifdef SLOW_ASSERTIONS -static int __heap_is_good_slow(pcb_heap_t * heap) -{ - int i; - /* heap condition: key in each node should be smaller than in its children */ - /* alternatively (and this is what we check): key in each node should be - * larger than (or equal to) key of its parent. */ - /* note that array element[0] is not used (except as a sentinel) */ - for (i = 2; i < heap->size; i++) - if (heap->element[i].cost < heap->element[i / 2].cost) - return 0; - return 1; -} -#endif /* SLOW_ASSERTIONS */ -static int __heap_is_good(pcb_heap_t * heap) -{ - return heap && (heap->max == 0 || heap->element) && - (heap->max >= 0) && (heap->size >= 0) && (heap->max == 0 || heap->size < heap->max) && -#ifdef SLOW_ASSERTIONS - __heap_is_good_slow(heap) && -#endif - 1; -} -#endif /* ! NDEBUG */ - -/* create an empty heap */ -pcb_heap_t *pcb_heap_create() -{ - pcb_heap_t *heap; - /* initialize MIN_COST if necessary */ - if (MIN_COST == 0) - MIN_COST = -1e23; - assert(MIN_COST < 0); - /* okay, create empty heap */ - heap = (pcb_heap_t *) calloc(1, sizeof(*heap)); - assert(heap); - assert(__heap_is_good(heap)); - return heap; -} - -/* destroy a heap */ -void pcb_heap_destroy(pcb_heap_t ** heap) -{ - assert(heap && *heap); - assert(__heap_is_good(*heap)); - if ((*heap)->element) - free((*heap)->element); - free(*heap); - *heap = NULL; -} - -/* free all elements in the heap */ -void pcb_heap_free(pcb_heap_t * heap, void (*freefunc) (void *)) -{ - assert(heap); - assert(__heap_is_good(heap)); - for (; heap->size; heap->size--) { - if (heap->element[heap->size].data) - freefunc(heap->element[heap->size].data); - } -} - -/* -- mutation -- */ -static void __upheap(pcb_heap_t * heap, int k) -{ - struct heap_element v; - - assert(heap && heap->size < heap->max); - assert(k <= heap->size); - - v = heap->element[k]; - heap->element[0].cost = MIN_COST; - for (v = heap->element[k]; heap->element[k / 2].cost > v.cost; k = k / 2) - heap->element[k] = heap->element[k / 2]; - heap->element[k] = v; -} - -void pcb_heap_insert(pcb_heap_t * heap, pcb_cost_t cost, void *data) -{ - assert(heap && __heap_is_good(heap)); - assert(cost >= MIN_COST); - - /* determine whether we need to grow the heap */ - if (heap->size + 1 >= heap->max) { - heap->max *= 2; - if (heap->max == 0) - heap->max = 256; /* default initial heap size */ - heap->element = (struct heap_element *) realloc(heap->element, heap->max * sizeof(*heap->element)); - } - heap->size++; - assert(heap->size < heap->max); - heap->element[heap->size].cost = cost; - heap->element[heap->size].data = data; - __upheap(heap, heap->size); /* fix heap condition violation */ - assert(__heap_is_good(heap)); - return; -} - -/* 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. - */ -static void __downheap(pcb_heap_t * heap, int k) -{ - struct heap_element v; - - assert(heap && heap->size < heap->max); - assert(k <= heap->size); - - v = heap->element[k]; - while (k <= heap->size / 2) { - int j = k + k; - if (j < heap->size && heap->element[j].cost > heap->element[j + 1].cost) - j++; - if (v.cost < heap->element[j].cost) - break; - heap->element[k] = heap->element[j]; - k = j; - } - heap->element[k] = v; -} - -void *pcb_heap_remove_smallest(pcb_heap_t * heap) -{ - struct heap_element v; - assert(heap && __heap_is_good(heap)); - assert(heap->size > 0); - assert(heap->max > 1); - - v = heap->element[1]; - heap->element[1] = heap->element[heap->size--]; - if (heap->size > 0) - __downheap(heap, 1); - - assert(__heap_is_good(heap)); - return v.data; -} - -void *pcb_heap_replace(pcb_heap_t * heap, pcb_cost_t cost, void *data) -{ - assert(heap && __heap_is_good(heap)); - - if (pcb_heap_is_empty(heap)) - return data; - - assert(heap->size > 0); - assert(heap->max > 1); - - heap->element[0].cost = cost; - heap->element[0].data = data; - __downheap(heap, 0); /* ooh, tricky! */ - - assert(__heap_is_good(heap)); - return heap->element[0].data; -} - -/* -- interrogation -- */ -int pcb_heap_is_empty(pcb_heap_t * heap) -{ - assert(__heap_is_good(heap)); - return heap->size == 0; -} - -/* -- size -- */ -int pcb_heap_size(pcb_heap_t * heap) -{ - assert(__heap_is_good(heap)); - return heap->size; -} Index: trunk/src/heap.h =================================================================== --- trunk/src/heap.h (revision 29281) +++ trunk/src/heap.h (nonexistent) @@ -1,68 +0,0 @@ -/* - * COPYRIGHT - * - * pcb-rnd, interactive printed circuit board design - * (this file is based on PCB, interactive printed circuit board design) - * Copyright (C) 1994,1995,1996 Thomas Nau - * Copyright (C) 1998,1999,2000,2001 harry eaton - * - * this file, heap.h, was written and is - * Copyright (c) 2001 C. Scott Ananian. - * - * 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: - * Project page: http://repo.hu/projects/pcb-rnd - * lead developer: http://repo.hu/projects/pcb-rnd/contact.html - * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") - * - * - * Old contact info: - * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA - * haceaton@aplcomm.jhuapl.edu - * - */ - -/* Heap used by the polygon code and autoroute */ - -#ifndef PCB_HEAP_H -#define PCB_HEAP_H - -#include "config.h" - -/* type of heap costs */ -typedef double pcb_cost_t; -/* what a heap looks like */ -typedef struct pcb_heap_s pcb_heap_t; - -/* create an empty heap */ -pcb_heap_t *pcb_heap_create(); -/* destroy a heap */ -void pcb_heap_destroy(pcb_heap_t ** heap); -/* free all elements in a heap */ -void pcb_heap_free(pcb_heap_t * heap, void (*funcfree) (void *)); - -/* -- mutation -- */ -void pcb_heap_insert(pcb_heap_t * heap, pcb_cost_t cost, void *data); -void *pcb_heap_remove_smallest(pcb_heap_t * heap); -/* replace the smallest item with a new item and return the smallest item. - * (if the new item is the smallest, than return it, instead.) */ -void *pcb_heap_replace(pcb_heap_t * heap, pcb_cost_t cost, void *data); - -/* -- interrogation -- */ -int pcb_heap_is_empty(pcb_heap_t * heap); -int pcb_heap_size(pcb_heap_t * heap); - -#endif /* PCB_HEAP_H */ Index: trunk/src/Makefile.dep =================================================================== --- trunk/src/Makefile.dep (revision 29281) +++ trunk/src/Makefile.dep (revision 29282) @@ -731,7 +731,7 @@ ../src_3rd/genht/ht.h ../src_3rd/genht/hash.h obj_pstk_list.h obj_pstk.h \ vtpadstack.h obj_pstk_shape.h polygon.h vtpadstack_t.h macro.h \ ../src_plugins/autoroute/autoroute.h board.h vtroutestyle.h rats_patch.h \ - board.h librnd/core/hidlib.h draw.h find.h heap.h rtree.h netlist.h \ + board.h librnd/core/hidlib.h draw.h find.h librnd/core/heap.h rtree.h netlist.h \ ../src_plugins/autoroute/mtspace.h ../src_plugins/autoroute/vector.h \ polygon.h remove.h obj_pinvia_therm.h undo.h ../src_3rd/libuundo/uundo.h \ undo_old.h layer.h obj_line_draw.h draw.h obj_pstk_draw.h \ @@ -740,7 +740,7 @@ ../src_plugins/autoroute/mtspace.o: ../src_plugins/autoroute/mtspace.c \ ../config.h librnd/core/box.h librnd/core/math_helper.h \ librnd/core/global_typedefs.h librnd/core/pcb_bool.h \ - librnd/core/misc_util.h librnd/core/unit.h heap.h rtree.h \ + librnd/core/misc_util.h librnd/core/unit.h librnd/core/heap.h rtree.h \ ../src_3rd/genrtree/genrtree_api.h ../src_plugins/autoroute/mtspace.h \ ../src_plugins/autoroute/vector.h rtree2_compat.h rtree.h ../src_plugins/autoroute/vector.o: ../src_plugins/autoroute/vector.c \ @@ -4401,7 +4401,7 @@ ../src_plugins/io_pcb/file.h board.h vtroutestyle.h rats_patch.h board.h \ librnd/core/hidlib.h plug_io.h ../src_plugins/io_pcb/parse_common.h \ ../src_plugins/io_pcb/parse_y.h plug_footprint.h vtlibrary.h data.h \ - ../src_plugins/io_pcb/attribs.h librnd/core/compat_misc.h compat_cc.h \ + ../src_plugins/io_pcb/attribs.h librnd/core/compat_misc.h librnd/core/compat_cc.h \ obj_common.h librnd/core/paths.h librnd/core/safe_fs.h macro.h ../src_plugins/io_pcb/parse_y.o: ../src_plugins/io_pcb/parse_y.c \ ../config.h flag.h librnd/core/globalconst.h board.h \ @@ -7743,7 +7743,7 @@ ../src_3rd/puplug/libs.h librnd/core/compat_misc.h librnd/core/event.h \ layer_ui.h layer_vis.h librnd/core/hid_attrib.h operation.h \ obj_subc_op.h route_style.h -heap.o: heap.c ../config.h heap.h +heap.o: heap.c ../config.h librnd/core/heap.h hid_cam.o: hid_cam.c ../config.h ../src_3rd/genht/htsp.h \ ../src_3rd/genht/ht.h ../src_3rd/genht/hash.h board.h \ librnd/core/global_typedefs.h librnd/core/pcb_bool.h vtroutestyle.h \ @@ -8742,7 +8742,7 @@ polygon_offs.c librnd/core/compat_misc.h polygon_offs.h polygon1.o: polygon1.c ../config.h rtree.h librnd/core/global_typedefs.h \ librnd/core/pcb_bool.h ../src_3rd/genrtree/genrtree_api.h \ - librnd/core/math_helper.h heap.h compat_cc.h librnd/core/pcb-printf.h \ + librnd/core/math_helper.h librnd/core/heap.h librnd/core/compat_cc.h librnd/core/pcb-printf.h \ ../src_3rd/genvector/gds_char.h ../src_3rd/genvector/genvector_impl.h \ ../src_3rd/genvector/genvector_undef.h librnd/core/unit.h polyarea.h \ obj_common.h flag.h librnd/core/globalconst.h librnd/core/attrib.h \ Index: trunk/src/Makefile.in =================================================================== --- trunk/src/Makefile.in (revision 29281) +++ trunk/src/Makefile.in (revision 29282) @@ -80,6 +80,7 @@ $(LIBRND)/core/file_loaded.o $(LIBRND)/core/funchash.o $(LIBRND)/core/grid.o + $(LIBRND)/core/heap.o $(LIBRND)/core/hid_attrib.o $(LIBRND)/core/hid_cfg.o $(LIBRND)/core/hid_cfg_action.o @@ -108,7 +109,6 @@ put /local/pcb/OBJS_POLYLIB [@ polygon1.o polygon1_gen.o - heap.o rtree.o @] Index: trunk/src/librnd/core/compat_cc.h =================================================================== --- trunk/src/librnd/core/compat_cc.h (nonexistent) +++ trunk/src/librnd/core/compat_cc.h (revision 29282) @@ -0,0 +1,73 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * (this file is based on PCB, interactive printed circuit board design) + * Copyright (C) 1994,1995,1996, 2004 Thomas Nau + * 15 Oct 2008 Ineiev: add different crosshair shapes + * + * 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 St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Contact: + * Project page: http://repo.hu/projects/pcb-rnd + * lead developer: http://repo.hu/projects/pcb-rnd/contact.html + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + * + */ + +#ifndef PCB_COMPAT_CC_H +#define PCB_COMPAT_CC_H + +/* --------------------------------------------------------------------------- + * Macros to annotate branch-prediction information. + * Taken from GLib 2.16.3 (LGPL 2).G_ / g_ prefixes have + * been removed to avoid namespace clashes. + */ + +/* The LIKELY and UNLIKELY macros let the programmer give hints to + * the compiler about the expected result of an expression. Some compilers + * can use this information for optimizations. + * + * The PCB_BOOLEAN_EXPR macro is intended to trigger a gcc warning when + * putting assignments inside the test. + */ +#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) +# define PCB_BOOLEAN_EXPR(expr) \ + __extension__ ({ \ + int _boolean_var_; \ + if (expr) \ + _boolean_var_ = 1; \ + else \ + _boolean_var_ = 0; \ + _boolean_var_; \ +}) +# define PCB_LIKELY(expr) (__builtin_expect (PCB_BOOLEAN_EXPR(expr), 1)) +# define PCB_UNLIKELY(expr) (__builtin_expect (PCB_BOOLEAN_EXPR(expr), 0)) +#else +# define PCB_LIKELY(expr) (expr) +# define PCB_UNLIKELY(expr) (expr) +#endif + +#ifndef GCC_VERSION +# define GCC_VERSION (__GNUC__ * 1000 + __GNUC_MINOR__) +#endif /* GCC_VERSION */ + +#if GCC_VERSION > 2007 +# define PCB_ATTRIBUTE_UNUSED __attribute__((unused)) +#else +# define PCB_ATTRIBUTE_UNUSED +#endif + +#endif Index: trunk/src/librnd/core/heap.c =================================================================== --- trunk/src/librnd/core/heap.c (nonexistent) +++ trunk/src/librnd/core/heap.c (revision 29282) @@ -0,0 +1,233 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * (this file is based on PCB, interactive printed circuit board design) + * Copyright (C) 1994,1995,1996 Thomas Nau + * Copyright (C) 1998,1999,2000,2001 harry eaton + * + * this file, heap.c, was written and is + * Copyright (c) 2001 C. Scott Ananian. + * + * 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: + * Project page: http://repo.hu/projects/pcb-rnd + * lead developer: http://repo.hu/projects/pcb-rnd/contact.html + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + * + * + * Old contact info: + * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA + * haceaton@aplcomm.jhuapl.edu + * + */ + + +/* operations on heaps. */ + +#include +#include +#include "config.h" +#include + +/* define this for more thorough self-checking of data structures */ +#undef SLOW_ASSERTIONS + +struct heap_element { + pcb_cost_t cost; + void *data; +}; +struct pcb_heap_s { + struct heap_element *element; + int size, max; +}; + +static pcb_cost_t MIN_COST = 0; + +/* --------------------------------------------------------------------------- + * functions. + */ +/* helper functions for assertions */ +#ifndef NDEBUG +#ifdef SLOW_ASSERTIONS +static int __heap_is_good_slow(pcb_heap_t * heap) +{ + int i; + /* heap condition: key in each node should be smaller than in its children */ + /* alternatively (and this is what we check): key in each node should be + * larger than (or equal to) key of its parent. */ + /* note that array element[0] is not used (except as a sentinel) */ + for (i = 2; i < heap->size; i++) + if (heap->element[i].cost < heap->element[i / 2].cost) + return 0; + return 1; +} +#endif /* SLOW_ASSERTIONS */ +static int __heap_is_good(pcb_heap_t * heap) +{ + return heap && (heap->max == 0 || heap->element) && + (heap->max >= 0) && (heap->size >= 0) && (heap->max == 0 || heap->size < heap->max) && +#ifdef SLOW_ASSERTIONS + __heap_is_good_slow(heap) && +#endif + 1; +} +#endif /* ! NDEBUG */ + +/* create an empty heap */ +pcb_heap_t *pcb_heap_create() +{ + pcb_heap_t *heap; + /* initialize MIN_COST if necessary */ + if (MIN_COST == 0) + MIN_COST = -1e23; + assert(MIN_COST < 0); + /* okay, create empty heap */ + heap = (pcb_heap_t *) calloc(1, sizeof(*heap)); + assert(heap); + assert(__heap_is_good(heap)); + return heap; +} + +/* destroy a heap */ +void pcb_heap_destroy(pcb_heap_t ** heap) +{ + assert(heap && *heap); + assert(__heap_is_good(*heap)); + if ((*heap)->element) + free((*heap)->element); + free(*heap); + *heap = NULL; +} + +/* free all elements in the heap */ +void pcb_heap_free(pcb_heap_t * heap, void (*freefunc) (void *)) +{ + assert(heap); + assert(__heap_is_good(heap)); + for (; heap->size; heap->size--) { + if (heap->element[heap->size].data) + freefunc(heap->element[heap->size].data); + } +} + +/* -- mutation -- */ +static void __upheap(pcb_heap_t * heap, int k) +{ + struct heap_element v; + + assert(heap && heap->size < heap->max); + assert(k <= heap->size); + + v = heap->element[k]; + heap->element[0].cost = MIN_COST; + for (v = heap->element[k]; heap->element[k / 2].cost > v.cost; k = k / 2) + heap->element[k] = heap->element[k / 2]; + heap->element[k] = v; +} + +void pcb_heap_insert(pcb_heap_t * heap, pcb_cost_t cost, void *data) +{ + assert(heap && __heap_is_good(heap)); + assert(cost >= MIN_COST); + + /* determine whether we need to grow the heap */ + if (heap->size + 1 >= heap->max) { + heap->max *= 2; + if (heap->max == 0) + heap->max = 256; /* default initial heap size */ + heap->element = (struct heap_element *) realloc(heap->element, heap->max * sizeof(*heap->element)); + } + heap->size++; + assert(heap->size < heap->max); + heap->element[heap->size].cost = cost; + heap->element[heap->size].data = data; + __upheap(heap, heap->size); /* fix heap condition violation */ + assert(__heap_is_good(heap)); + return; +} + +/* 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. + */ +static void __downheap(pcb_heap_t * heap, int k) +{ + struct heap_element v; + + assert(heap && heap->size < heap->max); + assert(k <= heap->size); + + v = heap->element[k]; + while (k <= heap->size / 2) { + int j = k + k; + if (j < heap->size && heap->element[j].cost > heap->element[j + 1].cost) + j++; + if (v.cost < heap->element[j].cost) + break; + heap->element[k] = heap->element[j]; + k = j; + } + heap->element[k] = v; +} + +void *pcb_heap_remove_smallest(pcb_heap_t * heap) +{ + struct heap_element v; + assert(heap && __heap_is_good(heap)); + assert(heap->size > 0); + assert(heap->max > 1); + + v = heap->element[1]; + heap->element[1] = heap->element[heap->size--]; + if (heap->size > 0) + __downheap(heap, 1); + + assert(__heap_is_good(heap)); + return v.data; +} + +void *pcb_heap_replace(pcb_heap_t * heap, pcb_cost_t cost, void *data) +{ + assert(heap && __heap_is_good(heap)); + + if (pcb_heap_is_empty(heap)) + return data; + + assert(heap->size > 0); + assert(heap->max > 1); + + heap->element[0].cost = cost; + heap->element[0].data = data; + __downheap(heap, 0); /* ooh, tricky! */ + + assert(__heap_is_good(heap)); + return heap->element[0].data; +} + +/* -- interrogation -- */ +int pcb_heap_is_empty(pcb_heap_t * heap) +{ + assert(__heap_is_good(heap)); + return heap->size == 0; +} + +/* -- size -- */ +int pcb_heap_size(pcb_heap_t * heap) +{ + assert(__heap_is_good(heap)); + return heap->size; +} Index: trunk/src/librnd/core/heap.h =================================================================== --- trunk/src/librnd/core/heap.h (nonexistent) +++ trunk/src/librnd/core/heap.h (revision 29282) @@ -0,0 +1,68 @@ +/* + * COPYRIGHT + * + * pcb-rnd, interactive printed circuit board design + * (this file is based on PCB, interactive printed circuit board design) + * Copyright (C) 1994,1995,1996 Thomas Nau + * Copyright (C) 1998,1999,2000,2001 harry eaton + * + * this file, heap.h, was written and is + * Copyright (c) 2001 C. Scott Ananian. + * + * 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: + * Project page: http://repo.hu/projects/pcb-rnd + * lead developer: http://repo.hu/projects/pcb-rnd/contact.html + * mailing list: pcb-rnd (at) list.repo.hu (send "subscribe") + * + * + * Old contact info: + * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA + * haceaton@aplcomm.jhuapl.edu + * + */ + +/* Heap used by the polygon code and autoroute */ + +#ifndef PCB_HEAP_H +#define PCB_HEAP_H + +#include "config.h" + +/* type of heap costs */ +typedef double pcb_cost_t; +/* what a heap looks like */ +typedef struct pcb_heap_s pcb_heap_t; + +/* create an empty heap */ +pcb_heap_t *pcb_heap_create(); +/* destroy a heap */ +void pcb_heap_destroy(pcb_heap_t ** heap); +/* free all elements in a heap */ +void pcb_heap_free(pcb_heap_t * heap, void (*funcfree) (void *)); + +/* -- mutation -- */ +void pcb_heap_insert(pcb_heap_t * heap, pcb_cost_t cost, void *data); +void *pcb_heap_remove_smallest(pcb_heap_t * heap); +/* replace the smallest item with a new item and return the smallest item. + * (if the new item is the smallest, than return it, instead.) */ +void *pcb_heap_replace(pcb_heap_t * heap, pcb_cost_t cost, void *data); + +/* -- interrogation -- */ +int pcb_heap_is_empty(pcb_heap_t * heap); +int pcb_heap_size(pcb_heap_t * heap); + +#endif /* PCB_HEAP_H */ Index: trunk/src/polygon1.c =================================================================== --- trunk/src/polygon1.c (revision 29281) +++ trunk/src/polygon1.c (revision 29282) @@ -48,8 +48,8 @@ #include "config.h" #include "rtree.h" #include -#include "heap.h" -#include "compat_cc.h" +#include +#include #include #include "polyarea.h" #include "obj_common.h" Index: trunk/src_plugins/autoroute/autoroute.c =================================================================== --- trunk/src_plugins/autoroute/autoroute.c (revision 29281) +++ trunk/src_plugins/autoroute/autoroute.c (revision 29282) @@ -72,7 +72,7 @@ #include "draw.h" #include #include "find.h" -#include "heap.h" +#include #include "rtree.h" #include "netlist.h" #include "mtspace.h" Index: trunk/src_plugins/autoroute/mtspace.c =================================================================== --- trunk/src_plugins/autoroute/mtspace.c (revision 29281) +++ trunk/src_plugins/autoroute/mtspace.c (revision 29282) @@ -48,7 +48,7 @@ #include #include -#include "heap.h" +#include #include "rtree.h" #include "mtspace.h" #include "vector.h" Index: trunk/src_plugins/io_pcb/parse_l.c =================================================================== --- trunk/src_plugins/io_pcb/parse_l.c (revision 29281) +++ trunk/src_plugins/io_pcb/parse_l.c (revision 29282) @@ -923,7 +923,7 @@ #include "plug_footprint.h" #include "attribs.h" #include -#include "compat_cc.h" +#include #include "obj_common.h" #include #include Index: trunk/src_plugins/io_pcb/parse_l.l =================================================================== --- trunk/src_plugins/io_pcb/parse_l.l (revision 29281) +++ trunk/src_plugins/io_pcb/parse_l.l (revision 29282) @@ -54,7 +54,7 @@ #include "plug_footprint.h" #include "attribs.h" #include -#include "compat_cc.h" +#include #include "obj_common.h" #include #include