From f01b59ed06353e2b0254f6fb6493d7407f8d166f Mon Sep 17 00:00:00 2001 From: DJ Delorie Date: Wed, 22 Aug 2001 02:12:15 +0000 Subject: merge from gcc --- libiberty/ChangeLog | 12 +++ libiberty/Makefile.in | 2 +- libiberty/configure | 124 ++++++++++++------------ libiberty/configure.in | 13 +-- libiberty/fibheap.c | 254 +++++++++++++++++++++++++------------------------ 5 files changed, 214 insertions(+), 191 deletions(-) (limited to 'libiberty') diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index d910b7f..45b2681 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,15 @@ +2001-08-21 Richard Henderson + + * Makefile.in (fibheap.o): Depend on config.h. + * fibheap.c: Tidy formatting. Use config.h.` Rearrange some + functions for inlining. + +Tue Aug 21 12:35:04 2001 Christopher Faylor + + * configure.in: Need to set HAVE_SYS_ERRLIST and HAVE_SYS_NERR whenever + hosting on cygwin. + * configure: Regenerate. + 2001-08-20 Daniel Berlin * fibheap.c: New file. Fibonacci heap. diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in index 41ea945..5786f99 100644 --- a/libiberty/Makefile.in +++ b/libiberty/Makefile.in @@ -265,7 +265,7 @@ cplus-dem.o: config.h $(INCDIR)/demangle.h cp-demangle.o: config.h $(INCDIR)/dyn-string.h $(INCDIR)/demangle.h dyn-string.o: config.h $(INCDIR)/dyn-string.h fdmatch.o: $(INCDIR)/libiberty.h -fibheap.o: $(INCDIR)/libiberty.h $(INCDIR)/fibheap.h +fibheap.o: config.h $(INCDIR)/libiberty.h $(INCDIR)/fibheap.h fnmatch.o: config.h $(INCDIR)/fnmatch.h getcwd.o: config.h getopt.o: config.h $(INCDIR)/getopt.h diff --git a/libiberty/configure b/libiberty/configure index 5c56812..0004ec9 100755 --- a/libiberty/configure +++ b/libiberty/configure @@ -1812,15 +1812,6 @@ EOF EOF - case "${host}" in - *-*-cygwin*) - cat >> confdefs.h <<\EOF -#define HAVE_SYS_ERRLIST 1 -EOF - - ;; - esac - setobjs=yes fi @@ -1834,6 +1825,19 @@ fi +case "${host}" in + *-*-cygwin*) + cat >> confdefs.h <<\EOF +#define HAVE_SYS_ERRLIST 1 +EOF + + cat >> confdefs.h <<\EOF +#define HAVE_SYS_NERR 1 +EOF + + ;; +esac + if test -z "${setobjs}"; then case "${host}" in @@ -1925,7 +1929,7 @@ if test -z "${setobjs}"; then # We haven't set the list of objects yet. Use the standard autoconf # tests. This will only work if the compiler works. echo $ac_n "checking whether the C compiler ($CC $CFLAGS $LDFLAGS) works""... $ac_c" 1>&6 -echo "configure:1929: checking whether the C compiler ($CC $CFLAGS $LDFLAGS) works" >&5 +echo "configure:1933: checking whether the C compiler ($CC $CFLAGS $LDFLAGS) works" >&5 ac_ext=c # CFLAGS is not in ac_cpp because -g, -O, etc. are not valid cpp options. @@ -1936,12 +1940,12 @@ cross_compiling=$ac_cv_prog_cc_cross cat > conftest.$ac_ext << EOF -#line 1940 "configure" +#line 1944 "configure" #include "confdefs.h" main(){return(0);} EOF -if { (eval echo configure:1945: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then +if { (eval echo configure:1949: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then ac_cv_prog_cc_works=yes # If we can't run a trivial program, we are probably using a cross compiler. if (./conftest; exit) 2>/dev/null; then @@ -1967,19 +1971,19 @@ if test $ac_cv_prog_cc_works = no; then { echo "configure: error: installation or configuration problem: C compiler cannot create executables." 1>&2; exit 1; } fi echo $ac_n "checking whether the C compiler ($CC $CFLAGS $LDFLAGS) is a cross-compiler""... $ac_c" 1>&6 -echo "configure:1971: checking whether the C compiler ($CC $CFLAGS $LDFLAGS) is a cross-compiler" >&5 +echo "configure:1975: checking whether the C compiler ($CC $CFLAGS $LDFLAGS) is a cross-compiler" >&5 echo "$ac_t""$ac_cv_prog_cc_cross" 1>&6 cross_compiling=$ac_cv_prog_cc_cross for ac_func in $funcs do echo $ac_n "checking for $ac_func""... $ac_c" 1>&6 -echo "configure:1978: checking for $ac_func" >&5 +echo "configure:1982: checking for $ac_func" >&5 if eval "test \"`echo '$''{'ac_cv_func_$ac_func'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then +if { (eval echo configure:2010: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then rm -rf conftest* eval "ac_cv_func_$ac_func=yes" else @@ -2029,12 +2033,12 @@ done echo $ac_n "checking whether alloca needs Cray hooks""... $ac_c" 1>&6 -echo "configure:2033: checking whether alloca needs Cray hooks" >&5 +echo "configure:2037: checking whether alloca needs Cray hooks" >&5 if eval "test \"`echo '$''{'ac_cv_os_cray'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext <&6 if test $ac_cv_os_cray = yes; then for ac_func in _getb67 GETB67 getb67; do echo $ac_n "checking for $ac_func""... $ac_c" 1>&6 -echo "configure:2063: checking for $ac_func" >&5 +echo "configure:2067: checking for $ac_func" >&5 if eval "test \"`echo '$''{'ac_cv_func_$ac_func'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then +if { (eval echo configure:2095: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then rm -rf conftest* eval "ac_cv_func_$ac_func=yes" else @@ -2113,7 +2117,7 @@ fi fi echo $ac_n "checking stack direction for C alloca""... $ac_c" 1>&6 -echo "configure:2117: checking stack direction for C alloca" >&5 +echo "configure:2121: checking stack direction for C alloca" >&5 if eval "test \"`echo '$''{'ac_cv_c_stack_direction'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else @@ -2121,7 +2125,7 @@ else ac_cv_c_stack_direction=0 else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null +if { (eval echo configure:2148: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null then ac_cv_c_stack_direction=1 else @@ -2161,12 +2165,12 @@ EOF echo $ac_n "checking for ANSI C header files""... $ac_c" 1>&6 -echo "configure:2165: checking for ANSI C header files" >&5 +echo "configure:2169: checking for ANSI C header files" >&5 if eval "test \"`echo '$''{'ac_cv_header_stdc'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext < #include @@ -2174,7 +2178,7 @@ else #include EOF ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out" -{ (eval echo configure:2178: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; } +{ (eval echo configure:2182: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; } ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"` if test -z "$ac_err"; then rm -rf conftest* @@ -2191,7 +2195,7 @@ rm -f conftest* if test $ac_cv_header_stdc = yes; then # SunOS 4.x string.h does not declare mem*, contrary to ANSI. cat > conftest.$ac_ext < EOF @@ -2209,7 +2213,7 @@ fi if test $ac_cv_header_stdc = yes; then # ISC 2.0.2 stdlib.h does not declare free, contrary to ANSI. cat > conftest.$ac_ext < EOF @@ -2230,7 +2234,7 @@ if test "$cross_compiling" = yes; then : else cat > conftest.$ac_ext < #define ISLOWER(c) ('a' <= (c) && (c) <= 'z') @@ -2241,7 +2245,7 @@ if (XOR (islower (i), ISLOWER (i)) || toupper (i) != TOUPPER (i)) exit(2); exit (0); } EOF -if { (eval echo configure:2245: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null +if { (eval echo configure:2249: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null then : else @@ -2265,12 +2269,12 @@ EOF fi echo $ac_n "checking for pid_t""... $ac_c" 1>&6 -echo "configure:2269: checking for pid_t" >&5 +echo "configure:2273: checking for pid_t" >&5 if eval "test \"`echo '$''{'ac_cv_type_pid_t'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext < #if STDC_HEADERS @@ -2299,17 +2303,17 @@ fi ac_safe=`echo "vfork.h" | sed 'y%./+-%__p_%'` echo $ac_n "checking for vfork.h""... $ac_c" 1>&6 -echo "configure:2303: checking for vfork.h" >&5 +echo "configure:2307: checking for vfork.h" >&5 if eval "test \"`echo '$''{'ac_cv_header_$ac_safe'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext < EOF ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out" -{ (eval echo configure:2313: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; } +{ (eval echo configure:2317: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; } ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"` if test -z "$ac_err"; then rm -rf conftest* @@ -2334,18 +2338,18 @@ else fi echo $ac_n "checking for working vfork""... $ac_c" 1>&6 -echo "configure:2338: checking for working vfork" >&5 +echo "configure:2342: checking for working vfork" >&5 if eval "test \"`echo '$''{'ac_cv_func_vfork_works'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else if test "$cross_compiling" = yes; then echo $ac_n "checking for vfork""... $ac_c" 1>&6 -echo "configure:2344: checking for vfork" >&5 +echo "configure:2348: checking for vfork" >&5 if eval "test \"`echo '$''{'ac_cv_func_vfork'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then +if { (eval echo configure:2376: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then rm -rf conftest* eval "ac_cv_func_vfork=yes" else @@ -2390,7 +2394,7 @@ fi ac_cv_func_vfork_works=$ac_cv_func_vfork else cat > conftest.$ac_ext < @@ -2485,7 +2489,7 @@ main() { } } EOF -if { (eval echo configure:2489: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null +if { (eval echo configure:2493: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null then ac_cv_func_vfork_works=yes else @@ -2512,19 +2516,19 @@ fi fi for v in $vars; do echo $ac_n "checking for $v""... $ac_c" 1>&6 -echo "configure:2516: checking for $v" >&5 +echo "configure:2520: checking for $v" >&5 if eval "test \"`echo '$''{'libiberty_cv_var_$v'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then +if { (eval echo configure:2532: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then rm -rf conftest* eval "libiberty_cv_var_$v=yes" else @@ -2550,12 +2554,12 @@ EOF for ac_func in $checkfuncs do echo $ac_n "checking for $ac_func""... $ac_c" 1>&6 -echo "configure:2554: checking for $ac_func" >&5 +echo "configure:2558: checking for $ac_func" >&5 if eval "test \"`echo '$''{'ac_cv_func_$ac_func'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then +if { (eval echo configure:2586: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then rm -rf conftest* eval "ac_cv_func_$ac_func=yes" else @@ -2608,17 +2612,17 @@ for ac_hdr in unistd.h do ac_safe=`echo "$ac_hdr" | sed 'y%./+-%__p_%'` echo $ac_n "checking for $ac_hdr""... $ac_c" 1>&6 -echo "configure:2612: checking for $ac_hdr" >&5 +echo "configure:2616: checking for $ac_hdr" >&5 if eval "test \"`echo '$''{'ac_cv_header_$ac_safe'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext < EOF ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out" -{ (eval echo configure:2622: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; } +{ (eval echo configure:2626: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; } ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"` if test -z "$ac_err"; then rm -rf conftest* @@ -2647,12 +2651,12 @@ done for ac_func in getpagesize do echo $ac_n "checking for $ac_func""... $ac_c" 1>&6 -echo "configure:2651: checking for $ac_func" >&5 +echo "configure:2655: checking for $ac_func" >&5 if eval "test \"`echo '$''{'ac_cv_func_$ac_func'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then +if { (eval echo configure:2683: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then rm -rf conftest* eval "ac_cv_func_$ac_func=yes" else @@ -2700,7 +2704,7 @@ fi done echo $ac_n "checking for working mmap""... $ac_c" 1>&6 -echo "configure:2704: checking for working mmap" >&5 +echo "configure:2708: checking for working mmap" >&5 if eval "test \"`echo '$''{'ac_cv_func_mmap_fixed_mapped'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else @@ -2708,7 +2712,7 @@ else ac_cv_func_mmap_fixed_mapped=no else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null +if { (eval echo configure:2856: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null then ac_cv_func_mmap_fixed_mapped=yes else @@ -2872,7 +2876,7 @@ fi echo $ac_n "checking for working strncmp""... $ac_c" 1>&6 -echo "configure:2876: checking for working strncmp" >&5 +echo "configure:2880: checking for working strncmp" >&5 if eval "test \"`echo '$''{'ac_cv_func_strncmp_works'+set}'`\" = set"; then echo $ac_n "(cached) $ac_c" 1>&6 else @@ -2880,7 +2884,7 @@ else ac_cv_func_strncmp_works=no else cat > conftest.$ac_ext <&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null +if { (eval echo configure:2949: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null then ac_cv_func_strncmp_works=yes else diff --git a/libiberty/configure.in b/libiberty/configure.in index 499e467..c3c25a5 100644 --- a/libiberty/configure.in +++ b/libiberty/configure.in @@ -177,12 +177,6 @@ if test -n "${with_target_subdir}"; then # Of the functions in $checkfuncs, newlib only has strerror. AC_DEFINE_NOAUTOHEADER(HAVE_STRERROR) - case "${host}" in - *-*-cygwin*) - AC_DEFINE(HAVE_SYS_ERRLIST) - ;; - esac - setobjs=yes fi @@ -196,6 +190,13 @@ fi AC_SUBST(CHECK) +case "${host}" in + *-*-cygwin*) + AC_DEFINE(HAVE_SYS_ERRLIST) + AC_DEFINE(HAVE_SYS_NERR) + ;; +esac + if test -z "${setobjs}"; then case "${host}" in diff --git a/libiberty/fibheap.c b/libiberty/fibheap.c index 3c8b347..7431e11 100644 --- a/libiberty/fibheap.c +++ b/libiberty/fibheap.c @@ -1,4 +1,3 @@ - /* A Fibonacci heap datatype. Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. Contributed by Daniel Berlin (dan@cgsoftware.com). @@ -20,13 +19,24 @@ along with GNU CC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ -/* Fibonacci heaps */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif +#ifdef HAVE_LIMITS_H #include +#endif +#ifdef HAVE_STDLIB_H #include +#endif +#ifdef HAVE_STRING_H +#include +#endif #include "libiberty.h" #include "fibheap.h" +#define FIBHEAPKEY_MIN LONG_MIN + static void fibheap_init PARAMS ((fibheap_t)); static void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t)); static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t)); @@ -36,13 +46,25 @@ static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t)); static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t)); static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t)); static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t)); -static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, fibnode_t)); +static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, + fibnode_t)); static fibnode_t fibnode_new PARAMS ((void)); static void fibnode_init PARAMS ((fibnode_t)); static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t)); #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) static fibnode_t fibnode_remove PARAMS ((fibnode_t)); + +/* Initialize the passed in fibonacci heap. */ +static inline void +fibheap_init (heap) + fibheap_t heap; +{ + heap->nodes = 0; + heap->min = NULL; + heap->root = NULL; +} + /* Create a new fibonacci heap. */ fibheap_t fibheap_new () @@ -57,14 +79,60 @@ fibheap_new () return result; } -/* Initialize the passed in fibonacci heap. */ -static void -fibheap_init (heap) +/* Initialize the passed in fibonacci heap node. */ +static inline void +fibnode_init (node) + fibnode_t node; +{ + node->degree = 0; + node->mark = 0; + node->parent = NULL; + node->child = NULL; + node->left = node; + node->right = node; + node->data = NULL; +} + +/* Create a new fibonacci heap node. */ +static inline fibnode_t +fibnode_new () +{ + fibnode_t e; + + if ((e = xmalloc (sizeof *e)) == NULL) + return NULL; + + fibnode_init (e); + + return e; +} + +static inline int +fibheap_compare (heap, a, b) + fibheap_t heap ATTRIBUTE_UNUSED; + fibnode_t a; + fibnode_t b; +{ + if (a->key < b->key) + return -1; + if (a->key > b->key) + return 1; + return 0; +} + +static inline int +fibheap_comp_data (heap, key, data, b) fibheap_t heap; + fibheapkey_t key; + void *data; + fibnode_t b; { - heap->nodes = 0; - heap->min = NULL; - heap->root = NULL; + struct fibnode a; + + a.key = key; + a.data = data; + + return fibheap_compare (heap, &a, b); } /* Insert DATA, with priority KEY, into HEAP. */ @@ -75,9 +143,11 @@ fibheap_insert (heap, key, data) void *data; { fibnode_t node; + /* Create the new node, if we fail, return NULL. */ if ((node = fibnode_new ()) == NULL) return NULL; + /* Set the node's data. */ node->data = data; node->key = key; @@ -85,8 +155,8 @@ fibheap_insert (heap, key, data) /* Insert it into the root list. */ fibheap_ins_root (heap, node); - /* If their was no minimum, or this key is less than the min, it's the new - min. */ + /* If their was no minimum, or this key is less than the min, + it's the new min. */ if (heap->min == NULL || node->key < heap->min->key) heap->min = node; @@ -123,28 +193,26 @@ fibheap_union (heapa, heapb) fibheap_t heapa; fibheap_t heapb; { - fibnode_t temp; + fibnode_t a_root, b_root, temp; /* If one of the heaps is empty, the union is just the other heap. */ - if (heapa->root == NULL || heapb->root == NULL) + if ((a_root = heapa->root) == NULL) { - if (heapa->root == NULL) - { - free (heapa); - return heapb; - } - else - { - free (heapb); - return heapa; - } + free (heapa); + return heapb; + } + if ((b_root = heapb->root) == NULL) + { + free (heapb); + return heapa; } + /* Merge them to the next nodes on the opposite chain. */ - heapa->root->left->right = heapb->root; - heapb->root->left->right = heapa->root; - temp = heapa->root->left; - heapa->root->left = heapb->root->left; - heapb->root->left = temp; + a_root->left->right = b_root; + b_root->left->right = a_root; + temp = a_root->left; + a_root->left = b_root->left; + b_root->left = temp; heapa->nodes += heapb->nodes; /* And set the new minimum, if it's changed. */ @@ -161,9 +229,8 @@ fibheap_extract_min (heap) fibheap_t heap; { fibnode_t z; - void *ret; + void *ret = NULL; - ret = NULL; /* If we don't have a min set, it means we have no nodes. */ if (heap->min != NULL) { @@ -177,31 +244,6 @@ fibheap_extract_min (heap) return ret; } -/* Replace the DATA associated with NODE. */ -void * -fibheap_replace_data (heap, node, data) - fibheap_t heap; - fibnode_t node; - void *data; -{ - return fibheap_replace_key_data (heap, node, node->key, data); -} - -/* Replace the KEY associated with NODE. */ -fibheapkey_t -fibheap_replace_key (heap, node, key) - fibheap_t heap; - fibnode_t node; - fibheapkey_t key; -{ - int ret; - - ret = node->key; - (void) fibheap_replace_key_data (heap, node, key, node->data); - - return ret; -} - /* Replace both the KEY and the DATA associated with NODE. */ void * fibheap_replace_key_data (heap, node, key, data) @@ -244,19 +286,41 @@ fibheap_replace_key_data (heap, node, key, data) return odata; } +/* Replace the DATA associated with NODE. */ +void * +fibheap_replace_data (heap, node, data) + fibheap_t heap; + fibnode_t node; + void *data; +{ + return fibheap_replace_key_data (heap, node, node->key, data); +} + +/* Replace the KEY associated with NODE. */ +fibheapkey_t +fibheap_replace_key (heap, node, key) + fibheap_t heap; + fibnode_t node; + fibheapkey_t key; +{ + int okey = node->key; + fibheap_replace_key_data (heap, node, key, node->data); + return okey; +} + /* Delete NODE from HEAP. */ void * fibheap_delete_node (heap, node) fibheap_t heap; fibnode_t node; { - void *k; + void *ret = node->data; + /* To perform delete, we just make it the min key, and extract. */ - k = node->data; - fibheap_replace_key (heap, node, LONG_MIN); + fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); fibheap_extract_min (heap); - return k; + return ret; } /* Delete HEAP. */ @@ -278,32 +342,29 @@ fibheap_empty (heap) return heap->nodes == 0; } - /* Extract the minimum node of the heap. */ static fibnode_t fibheap_extr_min_node (heap) fibheap_t heap; { - fibnode_t ret; + fibnode_t ret = heap->min; fibnode_t x, y, orig; - ret = heap->min; - - orig = NULL; /* Attach the child list of the minimum node to the root list of the heap. If there is no child list, we don't do squat. */ - for (x = ret->child; x != orig && x != NULL;) + for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) { if (orig == NULL) orig = x; y = x->right; x->parent = NULL; fibheap_ins_root (heap, x); - x = y; } + /* Remove the old root. */ fibheap_rem_root (heap, ret); heap->nodes--; + /* If we are left with no nodes, then the min is NULL. */ if (heap->nodes == 0) heap->min = NULL; @@ -333,8 +394,9 @@ fibheap_ins_root (heap, node) node->right = node; return; } - /* Otherwise, insert it in the circular root list between the root and it's - right node. */ + + /* Otherwise, insert it in the circular root list between the root + and it's right node. */ fibnode_insert_after (heap->root, node); } @@ -450,33 +512,6 @@ fibheap_cascading_cut (heap, y) } } - -static fibnode_t -fibnode_new () -{ - fibnode_t e; - - if ((e = xmalloc (sizeof *e)) == NULL) - return NULL; - - fibnode_init (e); - - return e; -} - -static void -fibnode_init (node) - fibnode_t node; -{ - node->degree = 0; - node->mark = 0; - node->parent = NULL; - node->child = NULL; - node->left = node; - node->right = node; - node->data = NULL; -} - static void fibnode_insert_after (a, b) fibnode_t a; @@ -498,7 +533,6 @@ fibnode_insert_after (a, b) } } - static fibnode_t fibnode_remove (node) fibnode_t node; @@ -522,31 +556,3 @@ fibnode_remove (node) return ret; } - -static int -fibheap_compare (heap, a, b) - fibheap_t heap ATTRIBUTE_UNUSED; - fibnode_t a; - fibnode_t b; -{ - if (a->key < b->key) - return -1; - if (a->key > b->key) - return 1; - return 0; -} - -static int -fibheap_comp_data (heap, key, data, b) - fibheap_t heap; - fibheapkey_t key; - void *data; - fibnode_t b; -{ - struct fibnode a; - - a.key = key; - a.data = data; - - return fibheap_compare (heap, &a, b); -} -- cgit v1.1