* PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
@ 2007-11-13 17:18 H.J. Lu
2007-11-13 22:35 ` Alan Modra
0 siblings, 1 reply; 10+ messages in thread
From: H.J. Lu @ 2007-11-13 17:18 UTC (permalink / raw)
To: binutils
Current linker is broken on 32bit host with 64bit BFD. The problem
is splay-tree doesn't support 64bit value on bit host, but arange-set.c
uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
to lack of #ifdef in gengtype in gcc. This patch will abort the
linker if it detects such situation.
H.J.
---
2007-11-13 H.J. Lu <hongjiu.lu@intel.com>
PR ld/5303
* arange-set.c (arange_set_new): Abort if size of bfd_vma >
size of splay_tree types.
--- bfd/arange-set.c.vma 2007-09-21 09:16:17.000000000 -0700
+++ bfd/arange-set.c 2007-11-13 09:11:23.000000000 -0800
@@ -194,6 +194,14 @@ arange_set_new (arange_set_allocate_fn a
splay_tree sp;
splay_tree_delete_value_fn fn;
+ if (sizeof (bfd_vma) > sizeof (splay_tree_key)
+ || sizeof (bfd_vma) > sizeof (splay_tree_value))
+ {
+ (*_bfd_error_handler)
+ (_("size of bfd_vma > size of splay_tree types"));
+ abort ();
+ }
+
/* Allocate space for arange structure. */
set = (arange_set)
(*allocate_fn) (sizeof (struct arange_set_s), data);
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2007-11-13 17:18 PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host H.J. Lu
@ 2007-11-13 22:35 ` Alan Modra
2007-11-13 23:32 ` H.J. Lu
0 siblings, 1 reply; 10+ messages in thread
From: Alan Modra @ 2007-11-13 22:35 UTC (permalink / raw)
To: H.J. Lu, Doug Kwan; +Cc: binutils
On Tue, Nov 13, 2007 at 09:18:45AM -0800, H.J. Lu wrote:
> Current linker is broken on 32bit host with 64bit BFD. The problem
> is splay-tree doesn't support 64bit value on bit host, but arange-set.c
> uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
> also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
> to lack of #ifdef in gengtype in gcc. This patch will abort the
> linker if it detects such situation.
Aborting isn't a solution. I'll revert Doug's patch in a week or so
if someone can't find a proper solution, eg. fallback to old scheme
if splay tree support is inadeqaute.
--
Alan Modra
Australia Development Lab, IBM
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2007-11-13 22:35 ` Alan Modra
@ 2007-11-13 23:32 ` H.J. Lu
2007-11-14 16:30 ` H.J. Lu
0 siblings, 1 reply; 10+ messages in thread
From: H.J. Lu @ 2007-11-13 23:32 UTC (permalink / raw)
To: Doug Kwan, binutils; +Cc: gcc-patches, mark
[-- Attachment #1: Type: text/plain, Size: 1116 bytes --]
On Wed, Nov 14, 2007 at 09:05:08AM +1030, Alan Modra wrote:
> On Tue, Nov 13, 2007 at 09:18:45AM -0800, H.J. Lu wrote:
> > Current linker is broken on 32bit host with 64bit BFD. The problem
> > is splay-tree doesn't support 64bit value on bit host, but arange-set.c
> > uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
> > also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
> > to lack of #ifdef in gengtype in gcc. This patch will abort the
> > linker if it detects such situation.
>
> Aborting isn't a solution. I'll revert Doug's patch in a week or so
> if someone can't find a proper solution, eg. fallback to old scheme
> if splay tree support is inadeqaute.
>
Here are 2 patches to update splay tree. The idea is to provide both
long and long long interfaces for splay-tree if they are different.
The default interface is the smallest one which can hold a pointer.
Gcc support is tricky since gengtype doesn't support #ifdef. I
have to use splay-tree-default.h and let gcc override it. I will
post a patch for arange-set.c if these 2 patches are approved.
Thanks.
H.J.
[-- Attachment #2: gcc-longlong-1.patch --]
[-- Type: text/plain, Size: 4558 bytes --]
2007-11-13 H.J. Lu <hongjiu.lu@intel.com>
PR ld/5303
* Makefile.in (SPLAY_TREE_H): Add splay-tree-default.h.
(splay-tree-default.h): New target.
* configure.ac (ptr_t): Set to long or long long to hold a
pointer. Substitute it.
(all_outputs): Add splay-tree-default.h.
* configure: Regenerated.
* splay-tree-default.h.in: New file.
--- gcc/Makefile.in.longlong 2007-11-13 10:06:50.000000000 -0800
+++ gcc/Makefile.in 2007-11-13 14:05:18.000000000 -0800
@@ -367,7 +367,7 @@ STRIP_FOR_TARGET := $(shell \
# Where to find some libiberty headers.
HASHTAB_H = $(srcdir)/../include/hashtab.h
OBSTACK_H = $(srcdir)/../include/obstack.h
-SPLAY_TREE_H= $(srcdir)/../include/splay-tree.h
+SPLAY_TREE_H= $(srcdir)/../include/splay-tree.h splay-tree-default.h
FIBHEAP_H = $(srcdir)/../include/fibheap.h
PARTITION_H = $(srcdir)/../include/partition.h
MD5_H = $(srcdir)/../include/md5.h
@@ -1442,6 +1442,9 @@ $(srcdir)/configure: @MAINT@ $(srcdir)/c
$(srcdir)/acinclude.m4
(cd $(srcdir) && autoconf)
+splay-tree-default.h: $(srcdir)/splay-tree-default.h.in
+ CONFIG_FILES=splay-tree-default.h CONFIG_HEADERS= ./config.status
+
gccbug: $(srcdir)/gccbug.in
CONFIG_FILES=gccbug CONFIG_HEADERS= ./config.status
--- gcc/configure.ac.longlong 2007-11-13 10:06:50.000000000 -0800
+++ gcc/configure.ac 2007-11-13 14:27:36.000000000 -0800
@@ -307,6 +307,14 @@ AC_CHECK_SIZEOF(int)
AC_CHECK_SIZEOF(long)
AC_CHECK_TYPES([long long], [AC_CHECK_SIZEOF(long long)])
AC_CHECK_TYPES([__int64], [AC_CHECK_SIZEOF(__int64)])
+if test "$ac_cv_sizeof_long" = "$ac_cv_sizeof_void_p"; then
+ ptr_t=long
+elif test "$ac_cv_type_long_long" = "$ac_cv_sizeof_void_p"; then
+ ptr_t=long_long
+else
+ ptr_t=long
+fi
+AC_SUBST(ptr_t)
# ---------------------
# Warnings and checking
@@ -3547,7 +3555,7 @@ lang_tree_files=
# `language' must be a single word so is spelled singularly.
all_languages=
all_compilers=
-all_outputs='Makefile gccbug libada-mk'
+all_outputs='Makefile gccbug splay-tree-default.h libada-mk'
# List of language makefile fragments.
all_lang_makefrags=
# List of language subdirectory makefiles. Deprecated.
--- gcc/splay-tree-default.h.in.longlong 2007-11-13 13:57:44.000000000 -0800
+++ gcc/splay-tree-default.h.in 2007-11-13 14:16:04.000000000 -0800
@@ -0,0 +1,46 @@
+/* Default splay-tree interface
+ Copyright 2007 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC 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, or (at your option)
+ any later version.
+
+ GCC 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 GCC; see the file COPYING. If not, write to
+ the Free Software Foundation, 51 Franklin Street - Fifth Floor,
+ Boston, MA 02110-1301, USA. */
+
+typedef splay_tree_@ptr_t@ splay_tree;
+
+#define splay_tree_key splay_tree_@ptr_t@_key
+#define splay_tree_value splay_tree_@ptr_t@_value
+#define splay_tree_node_s splay_tree_@ptr_t@_node_s
+#define splay_tree_node splay_tree_@ptr_t@_node
+#define splay_tree_compare_fn splay_tree_@ptr_t@_compare_fn
+#define splay_tree_delete_key_fn splay_tree_@ptr_t@_delete_key_fn
+#define splay_tree_delete_value_fn splay_tree_@ptr_t@_delete_key_fn
+#define splay_tree_foreach_fn splay_tree_@ptr_t@_foreach_fn
+#define splay_tree_allocate_fn splay_tree_@ptr_t@_allocate_fn
+#define splay_tree_deallocate_fn splay_tree_@ptr_t@_deallocate_fn
+#define splay_tree_s splay_tree_@ptr_t@_s
+#define splay_tree_new splay_tree_@ptr_t@_new
+#define splay_tree_new_with_allocator splay_tree_@ptr_t@_new_with_allocator
+#define splay_tree_delete splay_tree_@ptr_t@_delete
+#define splay_tree_insert splay_tree_@ptr_t@_insert
+#define splay_tree_remove splay_tree_@ptr_t@_remove
+#define splay_tree_lookup splay_tree_@ptr_t@_lookup
+#define splay_tree_predecessor splay_tree_@ptr_t@_predecessor
+#define splay_tree_successor splay_tree_@ptr_t@_successor
+#define splay_tree_max splay_tree_@ptr_t@_max
+#define splay_tree_min splay_tree_@ptr_t@_min
+#define splay_tree_foreach splay_tree_@ptr_t@_foreach
+#define splay_tree_compare_ints splay_tree_@ptr_t@_compare_ints
+#define splay_tree_compare_pointers splay_tree_@ptr_t@_compare_pointers
[-- Attachment #3: src-ll-1.patch --]
[-- Type: text/plain, Size: 29368 bytes --]
include/
2007-11-13 H.J. Lu <hongjiu.lu@intel.com>
PR ld/5303
* splay-tree-default.h: New file.
* splay-tree.h (libi_uhostptr_t): Removed.
(libi_shostptr_t): Likewise.
(splay_tree_uhostptr_t): New.
Provide long and long long interfaces.
Include splay-tree-default.h.
libiberty/
2007-11-13 H.J. Lu <hongjiu.lu@intel.com>
PR ld/5303
* Makefile.in (CFILES): Add splay-tree-long.c and
splay-tree-long-long.c.
(REQUIRED_OFILES): Replace ./splay-tree.o with
./splay-tree-long.o and ./splay-tree-long-long.o.
(./splay-tree-long.o): New dependency.
(./splay-tree-long-long.o): Likewise.
* configure.ac: Check size of long, void * and long, long.
* config.in: Regenerated.
* configure: Likewise.
* splay-tree-long-long.c: New file.
* splay-tree-long.c: Likewise.
* splay-tree.c: Don't include config.h.
(splay_tree_delete_helper): Add cast to splay_tree_uhostptr_t.
(splay_tree_compare_pointers): Likewise.
--- gcc/include/splay-tree-default.h.ll 2007-11-13 13:52:25.000000000 -0800
+++ gcc/include/splay-tree-default.h 2007-11-13 13:54:27.000000000 -0800
@@ -0,0 +1,92 @@
+/* Default splay-tree interface
+ Copyright 2007 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC 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, or (at your option)
+ any later version.
+
+ GCC 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 GCC; see the file COPYING. If not, write to
+ the Free Software Foundation, 51 Franklin Street - Fifth Floor,
+ Boston, MA 02110-1301, USA. */
+
+#ifndef splay_tree_key
+
+/* Use long long if size of pointer is the same as long long. */
+# ifndef USE_SPLAY_TREE_LONG_LONG
+# if defined HAVE_LONG_LONG && defined SIZEOF_VOID_P \
+ && defined SIZEOF_LONG_LONG && SIZEOF_VOID_P == SIZEOF_LONG_LONG
+# define USE_SPLAY_TREE_LONG_LONG
+# endif
+# endif
+
+/* Use long if size of long long is the same as long. */
+# ifdef USE_SPLAY_TREE_LONG_LONG
+# if defined SIZEOF_LONG && defined SIZEOF_LONG_LONG \
+ && SIZEOF_LONG == SIZEOF_LONG_LONG
+# undef USE_SPLAY_TREE_LONG_LONG
+# endif
+# endif
+
+# ifdef USE_SPLAY_TREE_LONG_LONG
+# define splay_tree_key splay_tree_long_long_key
+# define splay_tree_value splay_tree_long_long_value
+# define splay_tree_node_s splay_tree_long_long_node_s
+# define splay_tree_node splay_tree_long_long_node
+# define splay_tree_compare_fn splay_tree_long_long_compare_fn
+# define splay_tree_delete_key_fn splay_tree_long_long_delete_key_fn
+# define splay_tree_delete_value_fn splay_tree_long_long_delete_key_fn
+# define splay_tree_foreach_fn splay_tree_long_long_foreach_fn
+# define splay_tree_allocate_fn splay_tree_long_long_allocate_fn
+# define splay_tree_deallocate_fn splay_tree_long_long_deallocate_fn
+# define splay_tree_s splay_tree_long_long_s
+# define splay_tree splay_tree_long_long
+# define splay_tree_new splay_tree_long_long_new
+# define splay_tree_new_with_allocator splay_tree_long_long_new_with_allocator
+# define splay_tree_delete splay_tree_long_long_delete
+# define splay_tree_insert splay_tree_long_long_insert
+# define splay_tree_remove splay_tree_long_long_remove
+# define splay_tree_lookup splay_tree_long_long_lookup
+# define splay_tree_predecessor splay_tree_long_long_predecessor
+# define splay_tree_successor splay_tree_long_long_successor
+# define splay_tree_max splay_tree_long_long_max
+# define splay_tree_min splay_tree_long_long_min
+# define splay_tree_foreach splay_tree_long_long_foreach
+# define splay_tree_compare_ints splay_tree_long_long_compare_ints
+# define splay_tree_compare_pointers splay_tree_long_long_compare_pointers
+# else
+# define splay_tree_key splay_tree_long_key
+# define splay_tree_value splay_tree_long_value
+# define splay_tree_node_s splay_tree_long_node_s
+# define splay_tree_node splay_tree_long_node
+# define splay_tree_compare_fn splay_tree_long_compare_fn
+# define splay_tree_delete_key_fn splay_tree_long_delete_key_fn
+# define splay_tree_delete_value_fn splay_tree_long_delete_value_fn
+# define splay_tree_foreach_fn splay_tree_long_foreach_fn
+# define splay_tree_allocate_fn splay_tree_long_allocate_fn
+# define splay_tree_deallocate_fn splay_tree_long_deallocate_fn
+# define splay_tree_s splay_tree_long_s
+# define splay_tree splay_tree_long
+# define splay_tree_new splay_tree_long_new
+# define splay_tree_new_with_allocator splay_tree_long_new_with_allocator
+# define splay_tree_delete splay_tree_long_delete
+# define splay_tree_insert splay_tree_long_insert
+# define splay_tree_remove splay_tree_long_remove
+# define splay_tree_lookup splay_tree_long_lookup
+# define splay_tree_predecessor splay_tree_long_predecessor
+# define splay_tree_successor splay_tree_long_successor
+# define splay_tree_max splay_tree_long_max
+# define splay_tree_min splay_tree_long_min
+# define splay_tree_foreach splay_tree_long_foreach
+# define splay_tree_compare_ints splay_tree_long_compare_ints
+# define splay_tree_compare_pointers splay_tree_long_compare_pointers
+# endif
+#endif /* splay_tree_key */
--- gcc/include/splay-tree.h.ll 2007-07-26 09:21:25.000000000 -0700
+++ gcc/include/splay-tree.h 2007-11-13 13:54:05.000000000 -0800
@@ -36,114 +36,243 @@ extern "C" {
#include "ansidecl.h"
-#ifndef _WIN64
- typedef unsigned long int libi_uhostptr_t;
- typedef long int libi_shostptr_t;
-#else
- typedef unsigned long long libi_uhostptr_t;
- typedef long long libi_shostptr_t;
-#endif
-
#ifndef GTY
#define GTY(X)
#endif
+/* The key and data types should be be sufficiently wide that any
+ pointer or scalar can be cast to these types, and then cast back,
+ without loss of precision. There is a version for long. If size of
+ long long is different from long, there is a version for long long.
+
+ We need to map the default version to long or long long:
+ 1. The one asked by user. Or
+ 2. The one which can hold pointers. Or
+ 3. The long version.
+ */
+
+#if defined SIZEOF_LONG && SIZEOF_VOID_P == SIZEOF_LONG
+typedef unsigned long splay_tree_uhostptr_t;
+#elif defined HAVE_LONG_LONG && defined SIZEOF_LONG_LONG \
+ && SIZEOF_VOID_P == SIZEOF_LONG_LONG
+typedef unsigned long long splay_tree_uhostptr_t;
+#endif
+
/* Use typedefs for the key and data types to facilitate changing
- these types, if necessary. These types should be sufficiently wide
- that any pointer or scalar can be cast to these types, and then
- cast back, without loss of precision. */
-typedef libi_uhostptr_t splay_tree_key;
-typedef libi_uhostptr_t splay_tree_value;
+ these types, if necessary. */
+typedef unsigned long int splay_tree_long_key;
+typedef unsigned long int splay_tree_long_value;
+
+/* Forward declaration for a node in the tree. */
+typedef struct splay_tree_long_node_s *splay_tree_long_node;
+
+/* The type of a function which compares two splay-tree keys. The
+ function should return values as for qsort. */
+typedef int (*splay_tree_long_compare_fn)
+ (splay_tree_long_key, splay_tree_long_key);
+
+/* The type of a function used to deallocate any resources associated
+ with the key. */
+typedef void (*splay_tree_long_delete_key_fn) (splay_tree_long_key);
+
+/* The type of a function used to deallocate any resources associated
+ with the value. */
+typedef void (*splay_tree_long_delete_value_fn) (splay_tree_long_value);
+
+/* The type of a function used to iterate over the tree. */
+typedef int (*splay_tree_long_foreach_fn) (splay_tree_long_node, void*);
+
+/* The type of a function used to allocate memory for tree root and
+ node structures. The first argument is the number of bytes needed;
+ the second is a data pointer the splay tree functions pass through
+ to the allocator. This function must never return zero. */
+typedef void *(*splay_tree_long_allocate_fn) (int, void *);
+
+/* The type of a function used to free memory allocated using the
+ corresponding splay_tree_long_allocate_fn. The first argument is the
+ memory to be freed; the latter is a data pointer the splay tree
+ functions pass through to the freer. */
+typedef void (*splay_tree_long_deallocate_fn) (void *, void *);
+
+/* The nodes in the splay tree. */
+struct splay_tree_long_node_s GTY(())
+{
+ /* The key. */
+ splay_tree_long_key GTY ((use_param1)) key;
+
+ /* The value. */
+ splay_tree_long_value GTY ((use_param2)) value;
+
+ /* The left and right children, respectively. */
+ splay_tree_long_node GTY ((use_params)) left;
+ splay_tree_long_node GTY ((use_params)) right;
+};
+
+/* The splay tree itself. */
+struct splay_tree_long_s GTY(())
+{
+ /* The root of the tree. */
+ splay_tree_long_node GTY ((use_params)) root;
+
+ /* The comparision function. */
+ splay_tree_long_compare_fn comp;
+
+ /* The deallocate-key function. NULL if no cleanup is necessary. */
+ splay_tree_long_delete_key_fn delete_key;
+
+ /* The deallocate-value function. NULL if no cleanup is necessary. */
+ splay_tree_long_delete_value_fn delete_value;
+
+ /* Allocate/free functions, and a data pointer to pass to them. */
+ splay_tree_long_allocate_fn allocate;
+ splay_tree_long_deallocate_fn deallocate;
+ void * GTY((skip)) allocate_data;
+};
+
+typedef struct splay_tree_long_s *splay_tree_long;
+
+extern splay_tree_long splay_tree_long_new
+ (splay_tree_long_compare_fn, splay_tree_long_delete_key_fn,
+ splay_tree_long_delete_value_fn);
+extern splay_tree_long splay_tree_long_new_with_allocator
+ (splay_tree_long_compare_fn, splay_tree_long_delete_key_fn,
+ splay_tree_long_delete_value_fn, splay_tree_long_allocate_fn,
+ splay_tree_long_deallocate_fn, void *);
+extern void splay_tree_long_delete (splay_tree_long);
+extern splay_tree_long_node splay_tree_long_insert
+ (splay_tree_long, splay_tree_long_key, splay_tree_long_value);
+extern void splay_tree_long_remove (splay_tree_long, splay_tree_long_key);
+extern splay_tree_long_node splay_tree_long_lookup
+ (splay_tree_long, splay_tree_long_key);
+extern splay_tree_long_node splay_tree_long_predecessor
+ (splay_tree_long, splay_tree_long_key);
+extern splay_tree_long_node splay_tree_long_successor
+ (splay_tree_long, splay_tree_long_key);
+extern splay_tree_long_node splay_tree_long_max (splay_tree_long);
+extern splay_tree_long_node splay_tree_long_min (splay_tree_long);
+extern int splay_tree_long_foreach (splay_tree_long,
+ splay_tree_long_foreach_fn, void*);
+extern int splay_tree_long_compare_ints (splay_tree_long_key,
+ splay_tree_long_key);
+extern int splay_tree_long_compare_pointers (splay_tree_long_key,
+ splay_tree_long_key);
+
+/* Don't declare the long long version if the size of long log is the
+ the same as long. */
+#if defined HAVE_LONG_LONG && defined SIZEOF_LONG_LONG \
+ && defined SIZEOF_LONG && SIZEOF_LONG != SIZEOF_LONG_LONG
+typedef unsigned long long int splay_tree_long_long_key;
+typedef unsigned long long int splay_tree_long_long_value;
/* Forward declaration for a node in the tree. */
-typedef struct splay_tree_node_s *splay_tree_node;
+typedef struct splay_tree_long_long_node_s *splay_tree_long_long_node;
/* The type of a function which compares two splay-tree keys. The
function should return values as for qsort. */
-typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key);
+typedef int (*splay_tree_long_long_compare_fn)
+ (splay_tree_long_long_key, splay_tree_long_long_key);
/* The type of a function used to deallocate any resources associated
with the key. */
-typedef void (*splay_tree_delete_key_fn) (splay_tree_key);
+typedef void (*splay_tree_long_long_delete_key_fn)
+ (splay_tree_long_long_key);
/* The type of a function used to deallocate any resources associated
with the value. */
-typedef void (*splay_tree_delete_value_fn) (splay_tree_value);
+typedef void (*splay_tree_long_long_delete_value_fn)
+ (splay_tree_long_long_value);
/* The type of a function used to iterate over the tree. */
-typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*);
+typedef int (*splay_tree_long_long_foreach_fn)
+ (splay_tree_long_long_node, void*);
/* The type of a function used to allocate memory for tree root and
node structures. The first argument is the number of bytes needed;
the second is a data pointer the splay tree functions pass through
to the allocator. This function must never return zero. */
-typedef void *(*splay_tree_allocate_fn) (int, void *);
+typedef void *(*splay_tree_long_long_allocate_fn)
+ (int, void *);
/* The type of a function used to free memory allocated using the
- corresponding splay_tree_allocate_fn. The first argument is the
+ corresponding splay_tree_long_long_allocate_fn. The first argument is the
memory to be freed; the latter is a data pointer the splay tree
functions pass through to the freer. */
-typedef void (*splay_tree_deallocate_fn) (void *, void *);
+typedef void (*splay_tree_long_long_deallocate_fn)
+ (void *, void *);
/* The nodes in the splay tree. */
-struct splay_tree_node_s GTY(())
+struct splay_tree_long_long_node_s GTY(())
{
/* The key. */
- splay_tree_key GTY ((use_param1)) key;
+ splay_tree_long_long_key GTY ((use_param1)) key;
/* The value. */
- splay_tree_value GTY ((use_param2)) value;
+ splay_tree_long_long_value GTY ((use_param2)) value;
/* The left and right children, respectively. */
- splay_tree_node GTY ((use_params)) left;
- splay_tree_node GTY ((use_params)) right;
+ splay_tree_long_long_node GTY ((use_params)) left;
+ splay_tree_long_long_node GTY ((use_params)) right;
};
/* The splay tree itself. */
-struct splay_tree_s GTY(())
+struct splay_tree_long_long_s GTY(())
{
/* The root of the tree. */
- splay_tree_node GTY ((use_params)) root;
+ splay_tree_long_long_node GTY ((use_params)) root;
/* The comparision function. */
- splay_tree_compare_fn comp;
+ splay_tree_long_long_compare_fn comp;
/* The deallocate-key function. NULL if no cleanup is necessary. */
- splay_tree_delete_key_fn delete_key;
+ splay_tree_long_long_delete_key_fn delete_key;
/* The deallocate-value function. NULL if no cleanup is necessary. */
- splay_tree_delete_value_fn delete_value;
+ splay_tree_long_long_delete_value_fn delete_value;
/* Allocate/free functions, and a data pointer to pass to them. */
- splay_tree_allocate_fn allocate;
- splay_tree_deallocate_fn deallocate;
+ splay_tree_long_long_allocate_fn allocate;
+ splay_tree_long_long_deallocate_fn deallocate;
void * GTY((skip)) allocate_data;
};
-typedef struct splay_tree_s *splay_tree;
+typedef struct splay_tree_long_long_s *splay_tree_long_long;
+
+extern splay_tree_long_long splay_tree_long_long_new
+ (splay_tree_long_long_compare_fn, splay_tree_long_long_delete_key_fn,
+ splay_tree_long_long_delete_value_fn);
+extern splay_tree_long_long splay_tree_long_long_new_with_allocator
+ (splay_tree_long_long_compare_fn, splay_tree_long_long_delete_key_fn,
+ splay_tree_long_long_delete_value_fn, splay_tree_long_long_allocate_fn,
+ splay_tree_long_long_deallocate_fn, void *);
+extern void splay_tree_long_long_delete
+ (splay_tree_long_long);
+extern splay_tree_long_long_node splay_tree_long_long_insert
+ (splay_tree_long_long, splay_tree_long_long_key,
+ splay_tree_long_long_value);
+extern void splay_tree_long_long_remove
+ (splay_tree_long_long, splay_tree_long_long_key);
+extern splay_tree_long_long_node splay_tree_long_long_lookup
+ (splay_tree_long_long, splay_tree_long_long_key);
+extern splay_tree_long_long_node splay_tree_long_long_predecessor
+ (splay_tree_long_long, splay_tree_long_long_key);
+extern splay_tree_long_long_node splay_tree_long_long_successor
+ (splay_tree_long_long, splay_tree_long_long_key);
+extern splay_tree_long_long_node splay_tree_long_long_max
+ (splay_tree_long_long);
+extern splay_tree_long_long_node splay_tree_long_long_min
+ (splay_tree_long_long);
+extern int splay_tree_long_long_foreach
+ (splay_tree_long_long, splay_tree_long_long_foreach_fn, void*);
+extern int splay_tree_long_long_compare_ints
+ (splay_tree_long_long_key, splay_tree_long_long_key);
+extern int splay_tree_long_long_compare_pointers
+ (splay_tree_long_long_key, splay_tree_long_long_key);
+#endif
+
+/* We put the default interface in splay-tree-default.h so that gcc
+ can provide its own to work with gengtype. */
-extern splay_tree splay_tree_new (splay_tree_compare_fn,
- splay_tree_delete_key_fn,
- splay_tree_delete_value_fn);
-extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn,
- splay_tree_delete_key_fn,
- splay_tree_delete_value_fn,
- splay_tree_allocate_fn,
- splay_tree_deallocate_fn,
- void *);
-extern void splay_tree_delete (splay_tree);
-extern splay_tree_node splay_tree_insert (splay_tree,
- splay_tree_key,
- splay_tree_value);
-extern void splay_tree_remove (splay_tree, splay_tree_key);
-extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
-extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
-extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
-extern splay_tree_node splay_tree_max (splay_tree);
-extern splay_tree_node splay_tree_min (splay_tree);
-extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*);
-extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key);
-extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key);
+#include "splay-tree-default.h"
#ifdef __cplusplus
}
--- gcc/libiberty/Makefile.in.ll 2007-07-26 09:21:25.000000000 -0700
+++ gcc/libiberty/Makefile.in 2007-11-13 14:28:56.000000000 -0800
@@ -144,7 +144,8 @@ CFILES = alloca.c argv.c asprintf.c atex
physmem.c putenv.c \
random.c regex.c rename.c rindex.c \
safe-ctype.c setenv.c sigsetmask.c snprintf.c sort.c spaces.c \
- splay-tree.c stpcpy.c stpncpy.c strcasecmp.c strchr.c strdup.c \
+ splay-tree.c splay-tree-long.c splay-tree-long-long.c \
+ stpcpy.c stpncpy.c strcasecmp.c strchr.c strdup.c \
strerror.c strncasecmp.c strncmp.c strrchr.c strsignal.c \
strstr.c strtod.c strtol.c strtoul.c strndup.c strverscmp.c \
tmpnam.c \
@@ -169,8 +170,9 @@ REQUIRED_OFILES = ./regex.o ./cplus-dem.
./objalloc.o ./obstack.o \
./partition.o ./pexecute.o ./physmem.o \
./pex-common.o ./pex-one.o @pexecute@ \
- ./safe-ctype.o ./sort.o ./spaces.o ./splay-tree.o ./strerror.o \
- ./strsignal.o \
+ ./safe-ctype.o ./sort.o ./spaces.o \
+ ./splay-tree-long.o ./splay-tree-long-long.o \
+ ./strerror.o ./strsignal.o \
./unlink-if-ordinary.o \
./xatexit.o ./xexit.o ./xmalloc.o ./xmemdup.o ./xstrdup.o \
./xstrerror.o ./xstrndup.o
@@ -493,6 +495,16 @@ $(CONFIGURED_OFILES): stamp-picdir
# configure.
.NOEXPORT:
+# "make maint-deps" doesn't work properly on splay-tree-long.c and
+# splay-tree-long-long.c. Add their dependencies by hand.
+./splay-tree-long.o: $(srcdir)/splay-tree.c $(INCDIR)/ansidecl.h \
+ $(INCDIR)/libiberty.h $(INCDIR)/splay-tree.h \
+ $(INCDIR)/splay-tree-default.h
+
+./splay-tree-long-long.o: $(srcdir)/splay-tree.c $(INCDIR)/ansidecl.h \
+ $(INCDIR)/libiberty.h $(INCDIR)/splay-tree.h \
+ $(INCDIR)/splay-tree-default.h
+
# The dependencies in the remainder of this file are automatically
# generated by "make maint-deps". Manual edits will be lost.
@@ -969,8 +981,20 @@ $(CONFIGURED_OFILES): stamp-picdir
else true; fi
$(COMPILE.c) $(srcdir)/spaces.c $(OUTPUT_OPTION)
-./splay-tree.o: $(srcdir)/splay-tree.c stamp-h $(INCDIR)/ansidecl.h \
- $(INCDIR)/libiberty.h $(INCDIR)/splay-tree.h
+./splay-tree-long-long.o: $(srcdir)/splay-tree-long-long.c stamp-h
+ if [ x"$(PICFLAG)" != x ]; then \
+ $(COMPILE.c) $(PICFLAG) $(srcdir)/splay-tree-long-long.c -o pic/$@; \
+ else true; fi
+ $(COMPILE.c) $(srcdir)/splay-tree-long-long.c $(OUTPUT_OPTION)
+
+./splay-tree-long.o: $(srcdir)/splay-tree-long.c stamp-h
+ if [ x"$(PICFLAG)" != x ]; then \
+ $(COMPILE.c) $(PICFLAG) $(srcdir)/splay-tree-long.c -o pic/$@; \
+ else true; fi
+ $(COMPILE.c) $(srcdir)/splay-tree-long.c $(OUTPUT_OPTION)
+
+./splay-tree.o: $(srcdir)/splay-tree.c $(INCDIR)/ansidecl.h $(INCDIR)/libiberty.h \
+ $(INCDIR)/splay-tree.h
if [ x"$(PICFLAG)" != x ]; then \
$(COMPILE.c) $(PICFLAG) $(srcdir)/splay-tree.c -o pic/$@; \
else true; fi
--- gcc/libiberty/config.in.ll 2005-11-04 14:15:48.000000000 -0800
+++ gcc/libiberty/config.in 2007-11-13 10:09:21.000000000 -0800
@@ -124,6 +124,9 @@
/* Define to 1 if you have the <limits.h> header file. */
#undef HAVE_LIMITS_H
+/* Define to 1 if the system has the type `long long'. */
+#undef HAVE_LONG_LONG
+
/* Define to 1 if you have the <machine/hal_sysinfo.h> header file. */
#undef HAVE_MACHINE_HAL_SYSINFO_H
@@ -406,6 +409,15 @@
/* The size of a `int', as computed by sizeof. */
#undef SIZEOF_INT
+/* The size of a `long', as computed by sizeof. */
+#undef SIZEOF_LONG
+
+/* The size of a `long long', as computed by sizeof. */
+#undef SIZEOF_LONG_LONG
+
+/* The size of a `void *', as computed by sizeof. */
+#undef SIZEOF_VOID_P
+
/* Define if you know the direction of stack growth for your system; otherwise
it will be automatically deduced at run-time. STACK_DIRECTION > 0 => grows
toward higher addresses STACK_DIRECTION < 0 => grows toward lower addresses
--- gcc/libiberty/configure.ac.ll 2007-07-26 09:21:25.000000000 -0700
+++ gcc/libiberty/configure.ac 2007-11-13 10:09:21.000000000 -0800
@@ -253,8 +253,11 @@ libiberty_AC_DECLARE_ERRNO
# Determine the size of an int for struct fibnode.
AC_CHECK_SIZEOF([int])
+AC_CHECK_SIZEOF([long])
+AC_CHECK_SIZEOF([void *])
AC_CHECK_TYPE(uintptr_t, unsigned long)
+AC_CHECK_TYPES([long long], [AC_CHECK_SIZEOF(long long)])
# Look for a 64-bit type.
AC_MSG_CHECKING([for a 64-bit type])
--- gcc/libiberty/splay-tree-long-long.c.ll 2007-11-13 10:09:21.000000000 -0800
+++ gcc/libiberty/splay-tree-long-long.c 2007-11-13 10:09:21.000000000 -0800
@@ -0,0 +1,54 @@
+/* Copyright 2007 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC 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, or (at your option)
+ any later version.
+
+ GCC 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 GCC; see the file COPYING. If not, write to
+ the Free Software Foundation, 51 Franklin Street - Fifth Floor,
+ Boston, MA 02110-1301, USA. */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#if defined HAVE_LONG_LONG && defined SIZEOF_LONG_LONG \
+ && defined SIZEOF_LONG && SIZEOF_LONG != SIZEOF_LONG_LONG
+#define splay_tree_key splay_tree_long_long_key
+#define splay_tree_value splay_tree_long_long_value
+#define splay_tree_node_s splay_tree_long_long_node_s
+#define splay_tree_node splay_tree_long_long_node
+#define splay_tree_compare_fn splay_tree_long_long_compare_fn
+#define splay_tree_delete_key_fn splay_tree_long_long_delete_key_fn
+#define splay_tree_delete_value_fn splay_tree_long_long_delete_key_fn
+#define splay_tree_foreach_fn splay_tree_long_long_foreach_fn
+#define splay_tree_allocate_fn splay_tree_long_long_allocate_fn
+#define splay_tree_deallocate_fn splay_tree_long_long_deallocate_fn
+#define splay_tree_s splay_tree_long_long_s
+#define splay_tree splay_tree_long_long
+#define splay_tree_new splay_tree_long_long_new
+#define splay_tree_new_with_allocator splay_tree_long_long_new_with_allocator
+#define splay_tree_delete splay_tree_long_long_delete
+#define splay_tree_insert splay_tree_long_long_insert
+#define splay_tree_remove splay_tree_long_long_remove
+#define splay_tree_lookup splay_tree_long_long_lookup
+#define splay_tree_predecessor splay_tree_long_long_predecessor
+#define splay_tree_successor splay_tree_long_long_successor
+#define splay_tree_max splay_tree_long_long_max
+#define splay_tree_min splay_tree_long_long_min
+#define splay_tree_foreach splay_tree_long_long_foreach
+#define splay_tree_compare_ints splay_tree_long_long_compare_ints
+#define splay_tree_compare_pointers splay_tree_long_long_compare_pointers
+
+#include "splay-tree.c"
+
+#endif
--- gcc/libiberty/splay-tree-long.c.ll 2007-11-13 10:09:21.000000000 -0800
+++ gcc/libiberty/splay-tree-long.c 2007-11-13 10:09:21.000000000 -0800
@@ -0,0 +1,50 @@
+/* Copyright 2007 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC 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, or (at your option)
+ any later version.
+
+ GCC 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 GCC; see the file COPYING. If not, write to
+ the Free Software Foundation, 51 Franklin Street - Fifth Floor,
+ Boston, MA 02110-1301, USA. */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#define splay_tree_key splay_tree_long_key
+#define splay_tree_value splay_tree_long_value
+#define splay_tree_node_s splay_tree_long_node_s
+#define splay_tree_node splay_tree_long_node
+#define splay_tree_compare_fn splay_tree_long_compare_fn
+#define splay_tree_delete_key_fn splay_tree_long_delete_key_fn
+#define splay_tree_delete_value_fn splay_tree_long_delete_key_fn
+#define splay_tree_foreach_fn splay_tree_long_foreach_fn
+#define splay_tree_allocate_fn splay_tree_long_allocate_fn
+#define splay_tree_deallocate_fn splay_tree_long_deallocate_fn
+#define splay_tree_s splay_tree_long_s
+#define splay_tree splay_tree_long
+#define splay_tree_new splay_tree_long_new
+#define splay_tree_new_with_allocator splay_tree_long_new_with_allocator
+#define splay_tree_delete splay_tree_long_delete
+#define splay_tree_insert splay_tree_long_insert
+#define splay_tree_remove splay_tree_long_remove
+#define splay_tree_lookup splay_tree_long_lookup
+#define splay_tree_predecessor splay_tree_long_predecessor
+#define splay_tree_successor splay_tree_long_successor
+#define splay_tree_max splay_tree_long_max
+#define splay_tree_min splay_tree_long_min
+#define splay_tree_foreach splay_tree_long_foreach
+#define splay_tree_compare_ints splay_tree_long_compare_ints
+#define splay_tree_compare_pointers splay_tree_long_compare_pointers
+
+#include "splay-tree.c"
--- gcc/libiberty/splay-tree.c.ll 2005-11-09 09:52:30.000000000 -0800
+++ gcc/libiberty/splay-tree.c 2007-11-13 10:09:21.000000000 -0800
@@ -24,10 +24,6 @@ Boston, MA 02110-1301, USA. */
Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
Algorithms. Harper-Collins, Inc. 1991. */
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
@@ -64,7 +60,7 @@ splay_tree_delete_helper (splay_tree sp,
VDEL (node->value);
/* We use the "key" field to hold the "next" pointer. */
- node->key = (splay_tree_key)pending;
+ node->key = (splay_tree_key) (splay_tree_uhostptr_t)pending;
pending = (splay_tree_node)node;
/* Now, keep processing the pending list until there aren't any
@@ -86,19 +82,21 @@ splay_tree_delete_helper (splay_tree sp,
{
KDEL (active->left->key);
VDEL (active->left->value);
- active->left->key = (splay_tree_key)pending;
+ active->left->key
+ = (splay_tree_key) (splay_tree_uhostptr_t)pending;
pending = (splay_tree_node)(active->left);
}
if (active->right)
{
KDEL (active->right->key);
VDEL (active->right->value);
- active->right->key = (splay_tree_key)pending;
+ active->right->key
+ = (splay_tree_key) (splay_tree_uhostptr_t)pending;
pending = (splay_tree_node)(active->right);
}
temp = active;
- active = (splay_tree_node)(temp->key);
+ active = (splay_tree_node) (splay_tree_uhostptr_t)(temp->key);
(*sp->deallocate) ((char*) temp, sp->allocate_data);
}
}
@@ -517,9 +515,9 @@ splay_tree_compare_ints (splay_tree_key
int
splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
{
- if ((char*) k1 < (char*) k2)
+ if ((splay_tree_uhostptr_t) k1 < (splay_tree_uhostptr_t) k2)
return -1;
- else if ((char*) k1 > (char*) k2)
+ else if ((splay_tree_uhostptr_t) k1 > (splay_tree_uhostptr_t) k2)
return 1;
else
return 0;
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2007-11-13 23:32 ` H.J. Lu
@ 2007-11-14 16:30 ` H.J. Lu
2007-12-03 15:40 ` Doug Kwan (關振德)
0 siblings, 1 reply; 10+ messages in thread
From: H.J. Lu @ 2007-11-14 16:30 UTC (permalink / raw)
To: Doug Kwan, binutils; +Cc: gcc-patches, mark
On Tue, Nov 13, 2007 at 03:32:38PM -0800, H.J. Lu wrote:
> On Wed, Nov 14, 2007 at 09:05:08AM +1030, Alan Modra wrote:
> > On Tue, Nov 13, 2007 at 09:18:45AM -0800, H.J. Lu wrote:
> > > Current linker is broken on 32bit host with 64bit BFD. The problem
> > > is splay-tree doesn't support 64bit value on bit host, but arange-set.c
> > > uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
> > > also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
> > > to lack of #ifdef in gengtype in gcc. This patch will abort the
> > > linker if it detects such situation.
> >
> > Aborting isn't a solution. I'll revert Doug's patch in a week or so
> > if someone can't find a proper solution, eg. fallback to old scheme
> > if splay tree support is inadeqaute.
> >
>
> Here are 2 patches to update splay tree. The idea is to provide both
> long and long long interfaces for splay-tree if they are different.
> The default interface is the smallest one which can hold a pointer.
> Gcc support is tricky since gengtype doesn't support #ifdef. I
> have to use splay-tree-default.h and let gcc override it. I will
> post a patch for arange-set.c if these 2 patches are approved.
>
> Thanks.
>
>
Here is the patch for bfd.
H.J.
----
2007-11-14 H.J. Lu <hongjiu.lu@intel.com>
PR ld/5303
* arange-set.c (USE_SPLAY_TREE_LONG_LONG): Define if BFD64 is
defined.
Don't include "splay-tree.h".
(arange_set_delete_value_container): Add cast to
arange_set_uhostptr_t.
(arange_set_node_high): Likewise.
(arange_set_node_set_high): Likewise.
(arange_set_node_value): Likewise.
(arange_set_node_set_value): Likewise.
(arange_set_splay_tree_insert): Likewise.
* arange-set.h: Include "splay-tree.h".
(arange_set_uhostptr_t): Defined as splay_tree_uhostptr_t.
* configure.in: Check if long long exists.
* config.in: Regenerated.
* configure: Likewise.
--- bfd/arange-set.c.vma 2007-09-21 09:16:17.000000000 -0700
+++ bfd/arange-set.c 2007-11-13 06:46:18.000000000 -0800
@@ -23,8 +23,12 @@
#include "bfd.h"
#include "libiberty.h"
#include "libbfd.h"
+
+#ifdef BFD64
+#define USE_SPLAY_TREE_LONG_LONG
+#endif
+
#include "arange-set.h"
-#include "splay-tree.h"
/* Implementation of an arange-set. The set is implemented using the
splay tree support in libiberty. The advantage of using this is
@@ -142,7 +146,8 @@ arange_set_delete_value_container (splay
{
arange_value_container_t *container;
- container = (arange_value_container_t*) value;
+ container
+ = (arange_value_container_t*) (arange_set_uhostptr_t)value;
arange_set_delete_value (container->set, container->value);
arange_set_deallocate (container->set, container);
}
@@ -255,7 +260,8 @@ arange_set_node_high (arange_set set, sp
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container
+ = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
return container->high;
}
@@ -271,7 +277,8 @@ arange_set_node_set_high (arange_set set
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container
+ = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
container->high = address;
}
else
@@ -296,7 +303,8 @@ arange_set_node_value (arange_set set, s
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container
+ = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
return container->value;
}
@@ -315,7 +323,8 @@ arange_set_node_set_value (arange_set se
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container
+ = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
container->value = value;
}
}
@@ -445,7 +454,7 @@ arange_set_splay_tree_insert (arange_set
container->set = set;
container->value = value;
- sp_value = (splay_tree_value) container;
+ sp_value = (splay_tree_value) (arange_set_uhostptr_t)container;
}
else
sp_value = (splay_tree_value) high;
--- bfd/arange-set.h.vma 2007-09-21 09:16:17.000000000 -0700
+++ bfd/arange-set.h 2007-11-13 06:41:48.000000000 -0800
@@ -75,16 +75,13 @@
#include "sysdep.h"
#include "bfd.h"
+#include "splay-tree.h"
/* An arange_set is a pointer to an arange_set_s struct, whose implementation
is opaque to clients using the arange set. */
typedef struct arange_set_s *arange_set;
-#ifndef _WIN64
- typedef unsigned long int arange_set_uhostptr_t;
-#else
- typedef unsigned long long arange_set_uhostptr_t;
-#endif
+typedef splay_tree_uhostptr_t arange_set_uhostptr_t;
/* Type of value attached to an arange. This should be wide enough to be
converted from and back to any type without loss. */
--- bfd/config.in.vma 2007-10-30 11:48:31.000000000 -0700
+++ bfd/config.in 2007-11-13 06:31:39.000000000 -0800
@@ -105,6 +105,9 @@
/* Define to 1 if you have the <inttypes.h> header file. */
#undef HAVE_INTTYPES_H
+/* Define to 1 if the system has the type `long long'. */
+#undef HAVE_LONG_LONG
+
/* Define if <sys/procfs.h> has lwpstatus_t. */
#undef HAVE_LWPSTATUS_T
--- bfd/configure.in.vma 2007-10-30 11:48:31.000000000 -0700
+++ bfd/configure.in 2007-11-13 06:31:22.000000000 -0800
@@ -135,7 +135,7 @@ BFD_HOST_64_BIT=
BFD_HOST_U_64_BIT=
BFD_HOSTPTR_T="unsigned long"
-AC_CHECK_SIZEOF(long long)
+AC_CHECK_TYPES([long long], [AC_CHECK_SIZEOF(long long)])
AC_CHECK_SIZEOF(void *)
AC_CHECK_SIZEOF(long)
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2007-11-14 16:30 ` H.J. Lu
@ 2007-12-03 15:40 ` Doug Kwan (關振德)
2007-12-04 11:35 ` H.J. Lu
0 siblings, 1 reply; 10+ messages in thread
From: Doug Kwan (關振德) @ 2007-12-03 15:40 UTC (permalink / raw)
To: H.J. Lu; +Cc: binutils, gcc-patches, mark
Hi H.J.
Thanks for fixing this. I was on vacation in the last 3 weeks and
out of the country. I only returned to work to day. My apology for not
having tested this on the 32-bit host/64-bit target in the first
place.
-Doug
2007/11/14, H.J. Lu <hjl@lucon.org>:
> On Tue, Nov 13, 2007 at 03:32:38PM -0800, H.J. Lu wrote:
> > On Wed, Nov 14, 2007 at 09:05:08AM +1030, Alan Modra wrote:
> > > On Tue, Nov 13, 2007 at 09:18:45AM -0800, H.J. Lu wrote:
> > > > Current linker is broken on 32bit host with 64bit BFD. The problem
> > > > is splay-tree doesn't support 64bit value on bit host, but arange-set.c
> > > > uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
> > > > also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
> > > > to lack of #ifdef in gengtype in gcc. This patch will abort the
> > > > linker if it detects such situation.
> > >
> > > Aborting isn't a solution. I'll revert Doug's patch in a week or so
> > > if someone can't find a proper solution, eg. fallback to old scheme
> > > if splay tree support is inadeqaute.
> > >
> >
> > Here are 2 patches to update splay tree. The idea is to provide both
> > long and long long interfaces for splay-tree if they are different.
> > The default interface is the smallest one which can hold a pointer.
> > Gcc support is tricky since gengtype doesn't support #ifdef. I
> > have to use splay-tree-default.h and let gcc override it. I will
> > post a patch for arange-set.c if these 2 patches are approved.
> >
> > Thanks.
> >
> >
>
> Here is the patch for bfd.
>
>
> H.J.
> ----
> 2007-11-14 H.J. Lu <hongjiu.lu@intel.com>
>
> PR ld/5303
> * arange-set.c (USE_SPLAY_TREE_LONG_LONG): Define if BFD64 is
> defined.
> Don't include "splay-tree.h".
> (arange_set_delete_value_container): Add cast to
> arange_set_uhostptr_t.
> (arange_set_node_high): Likewise.
> (arange_set_node_set_high): Likewise.
> (arange_set_node_value): Likewise.
> (arange_set_node_set_value): Likewise.
> (arange_set_splay_tree_insert): Likewise.
>
> * arange-set.h: Include "splay-tree.h".
> (arange_set_uhostptr_t): Defined as splay_tree_uhostptr_t.
>
> * configure.in: Check if long long exists.
> * config.in: Regenerated.
> * configure: Likewise.
>
> --- bfd/arange-set.c.vma 2007-09-21 09:16:17.000000000 -0700
> +++ bfd/arange-set.c 2007-11-13 06:46:18.000000000 -0800
> @@ -23,8 +23,12 @@
> #include "bfd.h"
> #include "libiberty.h"
> #include "libbfd.h"
> +
> +#ifdef BFD64
> +#define USE_SPLAY_TREE_LONG_LONG
> +#endif
> +
> #include "arange-set.h"
> -#include "splay-tree.h"
>
> /* Implementation of an arange-set. The set is implemented using the
> splay tree support in libiberty. The advantage of using this is
> @@ -142,7 +146,8 @@ arange_set_delete_value_container (splay
> {
> arange_value_container_t *container;
>
> - container = (arange_value_container_t*) value;
> + container
> + = (arange_value_container_t*) (arange_set_uhostptr_t)value;
> arange_set_delete_value (container->set, container->value);
> arange_set_deallocate (container->set, container);
> }
> @@ -255,7 +260,8 @@ arange_set_node_high (arange_set set, sp
>
> if (set->value_p)
> {
> - container = (arange_value_container_t*) node->value;
> + container
> + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> return container->high;
> }
>
> @@ -271,7 +277,8 @@ arange_set_node_set_high (arange_set set
>
> if (set->value_p)
> {
> - container = (arange_value_container_t*) node->value;
> + container
> + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> container->high = address;
> }
> else
> @@ -296,7 +303,8 @@ arange_set_node_value (arange_set set, s
>
> if (set->value_p)
> {
> - container = (arange_value_container_t*) node->value;
> + container
> + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> return container->value;
> }
>
> @@ -315,7 +323,8 @@ arange_set_node_set_value (arange_set se
>
> if (set->value_p)
> {
> - container = (arange_value_container_t*) node->value;
> + container
> + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> container->value = value;
> }
> }
> @@ -445,7 +454,7 @@ arange_set_splay_tree_insert (arange_set
> container->set = set;
>
> container->value = value;
> - sp_value = (splay_tree_value) container;
> + sp_value = (splay_tree_value) (arange_set_uhostptr_t)container;
> }
> else
> sp_value = (splay_tree_value) high;
> --- bfd/arange-set.h.vma 2007-09-21 09:16:17.000000000 -0700
> +++ bfd/arange-set.h 2007-11-13 06:41:48.000000000 -0800
> @@ -75,16 +75,13 @@
>
> #include "sysdep.h"
> #include "bfd.h"
> +#include "splay-tree.h"
>
> /* An arange_set is a pointer to an arange_set_s struct, whose implementation
> is opaque to clients using the arange set. */
> typedef struct arange_set_s *arange_set;
>
> -#ifndef _WIN64
> - typedef unsigned long int arange_set_uhostptr_t;
> -#else
> - typedef unsigned long long arange_set_uhostptr_t;
> -#endif
> +typedef splay_tree_uhostptr_t arange_set_uhostptr_t;
>
> /* Type of value attached to an arange. This should be wide enough to be
> converted from and back to any type without loss. */
> --- bfd/config.in.vma 2007-10-30 11:48:31.000000000 -0700
> +++ bfd/config.in 2007-11-13 06:31:39.000000000 -0800
> @@ -105,6 +105,9 @@
> /* Define to 1 if you have the <inttypes.h> header file. */
> #undef HAVE_INTTYPES_H
>
> +/* Define to 1 if the system has the type `long long'. */
> +#undef HAVE_LONG_LONG
> +
> /* Define if <sys/procfs.h> has lwpstatus_t. */
> #undef HAVE_LWPSTATUS_T
>
> --- bfd/configure.in.vma 2007-10-30 11:48:31.000000000 -0700
> +++ bfd/configure.in 2007-11-13 06:31:22.000000000 -0800
> @@ -135,7 +135,7 @@ BFD_HOST_64_BIT=
> BFD_HOST_U_64_BIT=
> BFD_HOSTPTR_T="unsigned long"
>
> -AC_CHECK_SIZEOF(long long)
> +AC_CHECK_TYPES([long long], [AC_CHECK_SIZEOF(long long)])
> AC_CHECK_SIZEOF(void *)
> AC_CHECK_SIZEOF(long)
>
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2007-12-03 15:40 ` Doug Kwan (關振德)
@ 2007-12-04 11:35 ` H.J. Lu
2007-12-04 15:41 ` Hector Oron
2007-12-04 19:40 ` Doug Kwan (關振德)
0 siblings, 2 replies; 10+ messages in thread
From: H.J. Lu @ 2007-12-04 11:35 UTC (permalink / raw)
To: Doug Kwan (關振德); +Cc: binutils, gcc-patches, mark, dj
Hi Doug,
Thanks for your comments.
Although this bug doesn't affect gcc since gcc doesn't store 64bit
values in splay-tree on 32bit hosts, splay-tree is shared by both gcc
and binutils. Could someone from gcc review my patches to gcc and
splay-tree? Mark, DJ, can you look into them?
Thanks.
H.J.
---
On Mon, Dec 03, 2007 at 07:39:38AM -0800, Doug Kwan (關振德) wrote:
> Hi H.J.
>
> Thanks for fixing this. I was on vacation in the last 3 weeks and
> out of the country. I only returned to work to day. My apology for not
> having tested this on the 32-bit host/64-bit target in the first
> place.
>
> -Doug
>
> 2007/11/14, H.J. Lu <hjl@lucon.org>:
> > On Tue, Nov 13, 2007 at 03:32:38PM -0800, H.J. Lu wrote:
> > > On Wed, Nov 14, 2007 at 09:05:08AM +1030, Alan Modra wrote:
> > > > On Tue, Nov 13, 2007 at 09:18:45AM -0800, H.J. Lu wrote:
> > > > > Current linker is broken on 32bit host with 64bit BFD. The problem
> > > > > is splay-tree doesn't support 64bit value on bit host, but arange-set.c
> > > > > uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
> > > > > also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
> > > > > to lack of #ifdef in gengtype in gcc. This patch will abort the
> > > > > linker if it detects such situation.
> > > >
> > > > Aborting isn't a solution. I'll revert Doug's patch in a week or so
> > > > if someone can't find a proper solution, eg. fallback to old scheme
> > > > if splay tree support is inadeqaute.
> > > >
> > >
> > > Here are 2 patches to update splay tree. The idea is to provide both
> > > long and long long interfaces for splay-tree if they are different.
> > > The default interface is the smallest one which can hold a pointer.
> > > Gcc support is tricky since gengtype doesn't support #ifdef. I
> > > have to use splay-tree-default.h and let gcc override it. I will
> > > post a patch for arange-set.c if these 2 patches are approved.
> > >
> > > Thanks.
> > >
> > >
> >
> > Here is the patch for bfd.
> >
> >
> > H.J.
> > ----
> > 2007-11-14 H.J. Lu <hongjiu.lu@intel.com>
> >
> > PR ld/5303
> > * arange-set.c (USE_SPLAY_TREE_LONG_LONG): Define if BFD64 is
> > defined.
> > Don't include "splay-tree.h".
> > (arange_set_delete_value_container): Add cast to
> > arange_set_uhostptr_t.
> > (arange_set_node_high): Likewise.
> > (arange_set_node_set_high): Likewise.
> > (arange_set_node_value): Likewise.
> > (arange_set_node_set_value): Likewise.
> > (arange_set_splay_tree_insert): Likewise.
> >
> > * arange-set.h: Include "splay-tree.h".
> > (arange_set_uhostptr_t): Defined as splay_tree_uhostptr_t.
> >
> > * configure.in: Check if long long exists.
> > * config.in: Regenerated.
> > * configure: Likewise.
> >
> > --- bfd/arange-set.c.vma 2007-09-21 09:16:17.000000000 -0700
> > +++ bfd/arange-set.c 2007-11-13 06:46:18.000000000 -0800
> > @@ -23,8 +23,12 @@
> > #include "bfd.h"
> > #include "libiberty.h"
> > #include "libbfd.h"
> > +
> > +#ifdef BFD64
> > +#define USE_SPLAY_TREE_LONG_LONG
> > +#endif
> > +
> > #include "arange-set.h"
> > -#include "splay-tree.h"
> >
> > /* Implementation of an arange-set. The set is implemented using the
> > splay tree support in libiberty. The advantage of using this is
> > @@ -142,7 +146,8 @@ arange_set_delete_value_container (splay
> > {
> > arange_value_container_t *container;
> >
> > - container = (arange_value_container_t*) value;
> > + container
> > + = (arange_value_container_t*) (arange_set_uhostptr_t)value;
> > arange_set_delete_value (container->set, container->value);
> > arange_set_deallocate (container->set, container);
> > }
> > @@ -255,7 +260,8 @@ arange_set_node_high (arange_set set, sp
> >
> > if (set->value_p)
> > {
> > - container = (arange_value_container_t*) node->value;
> > + container
> > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > return container->high;
> > }
> >
> > @@ -271,7 +277,8 @@ arange_set_node_set_high (arange_set set
> >
> > if (set->value_p)
> > {
> > - container = (arange_value_container_t*) node->value;
> > + container
> > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > container->high = address;
> > }
> > else
> > @@ -296,7 +303,8 @@ arange_set_node_value (arange_set set, s
> >
> > if (set->value_p)
> > {
> > - container = (arange_value_container_t*) node->value;
> > + container
> > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > return container->value;
> > }
> >
> > @@ -315,7 +323,8 @@ arange_set_node_set_value (arange_set se
> >
> > if (set->value_p)
> > {
> > - container = (arange_value_container_t*) node->value;
> > + container
> > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > container->value = value;
> > }
> > }
> > @@ -445,7 +454,7 @@ arange_set_splay_tree_insert (arange_set
> > container->set = set;
> >
> > container->value = value;
> > - sp_value = (splay_tree_value) container;
> > + sp_value = (splay_tree_value) (arange_set_uhostptr_t)container;
> > }
> > else
> > sp_value = (splay_tree_value) high;
> > --- bfd/arange-set.h.vma 2007-09-21 09:16:17.000000000 -0700
> > +++ bfd/arange-set.h 2007-11-13 06:41:48.000000000 -0800
> > @@ -75,16 +75,13 @@
> >
> > #include "sysdep.h"
> > #include "bfd.h"
> > +#include "splay-tree.h"
> >
> > /* An arange_set is a pointer to an arange_set_s struct, whose implementation
> > is opaque to clients using the arange set. */
> > typedef struct arange_set_s *arange_set;
> >
> > -#ifndef _WIN64
> > - typedef unsigned long int arange_set_uhostptr_t;
> > -#else
> > - typedef unsigned long long arange_set_uhostptr_t;
> > -#endif
> > +typedef splay_tree_uhostptr_t arange_set_uhostptr_t;
> >
> > /* Type of value attached to an arange. This should be wide enough to be
> > converted from and back to any type without loss. */
> > --- bfd/config.in.vma 2007-10-30 11:48:31.000000000 -0700
> > +++ bfd/config.in 2007-11-13 06:31:39.000000000 -0800
> > @@ -105,6 +105,9 @@
> > /* Define to 1 if you have the <inttypes.h> header file. */
> > #undef HAVE_INTTYPES_H
> >
> > +/* Define to 1 if the system has the type `long long'. */
> > +#undef HAVE_LONG_LONG
> > +
> > /* Define if <sys/procfs.h> has lwpstatus_t. */
> > #undef HAVE_LWPSTATUS_T
> >
> > --- bfd/configure.in.vma 2007-10-30 11:48:31.000000000 -0700
> > +++ bfd/configure.in 2007-11-13 06:31:22.000000000 -0800
> > @@ -135,7 +135,7 @@ BFD_HOST_64_BIT=
> > BFD_HOST_U_64_BIT=
> > BFD_HOSTPTR_T="unsigned long"
> >
> > -AC_CHECK_SIZEOF(long long)
> > +AC_CHECK_TYPES([long long], [AC_CHECK_SIZEOF(long long)])
> > AC_CHECK_SIZEOF(void *)
> > AC_CHECK_SIZEOF(long)
> >
> >
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2007-12-04 11:35 ` H.J. Lu
@ 2007-12-04 15:41 ` Hector Oron
2007-12-04 19:40 ` Doug Kwan (關振德)
1 sibling, 0 replies; 10+ messages in thread
From: Hector Oron @ 2007-12-04 15:41 UTC (permalink / raw)
To: H.J. Lu; +Cc: binutils
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=GB2312, Size: 7730 bytes --]
Hello H.J.,
I write you because i'm a newbie and i haven't been on-list since
some days ago.
I posted a simple patch [1] that addreses ld and 64bit libraries.
Could that patch address this problem?
Cheers
[1] http://sources.redhat.com/ml/binutils/2007-11/msg00239.html
2007/12/4, H.J. Lu <hjl@lucon.org>:
> Hi Doug,
>
> Thanks for your comments.
>
> Although this bug doesn't affect gcc since gcc doesn't store 64bit
> values in splay-tree on 32bit hosts, splay-tree is shared by both gcc
> and binutils. Could someone from gcc review my patches to gcc and
> splay-tree? Mark, DJ, can you look into them?
>
> Thanks.
>
>
> H.J.
> ---
> On Mon, Dec 03, 2007 at 07:39:38AM -0800, Doug Kwan (êPÕñµÂ) wrote:
> > Hi H.J.
> >
> > Thanks for fixing this. I was on vacation in the last 3 weeks and
> > out of the country. I only returned to work to day. My apology for not
> > having tested this on the 32-bit host/64-bit target in the first
> > place.
> >
> > -Doug
> >
> > 2007/11/14, H.J. Lu <hjl@lucon.org>:
> > > On Tue, Nov 13, 2007 at 03:32:38PM -0800, H.J. Lu wrote:
> > > > On Wed, Nov 14, 2007 at 09:05:08AM +1030, Alan Modra wrote:
> > > > > On Tue, Nov 13, 2007 at 09:18:45AM -0800, H.J. Lu wrote:
> > > > > > Current linker is broken on 32bit host with 64bit BFD. The problem
> > > > > > is splay-tree doesn't support 64bit value on bit host, but arange-set.c
> > > > > > uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
> > > > > > also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
> > > > > > to lack of #ifdef in gengtype in gcc. This patch will abort the
> > > > > > linker if it detects such situation.
> > > > >
> > > > > Aborting isn't a solution. I'll revert Doug's patch in a week or so
> > > > > if someone can't find a proper solution, eg. fallback to old scheme
> > > > > if splay tree support is inadeqaute.
> > > > >
> > > >
> > > > Here are 2 patches to update splay tree. The idea is to provide both
> > > > long and long long interfaces for splay-tree if they are different.
> > > > The default interface is the smallest one which can hold a pointer.
> > > > Gcc support is tricky since gengtype doesn't support #ifdef. I
> > > > have to use splay-tree-default.h and let gcc override it. I will
> > > > post a patch for arange-set.c if these 2 patches are approved.
> > > >
> > > > Thanks.
> > > >
> > > >
> > >
> > > Here is the patch for bfd.
> > >
> > >
> > > H.J.
> > > ----
> > > 2007-11-14 H.J. Lu <hongjiu.lu@intel.com>
> > >
> > > PR ld/5303
> > > * arange-set.c (USE_SPLAY_TREE_LONG_LONG): Define if BFD64 is
> > > defined.
> > > Don't include "splay-tree.h".
> > > (arange_set_delete_value_container): Add cast to
> > > arange_set_uhostptr_t.
> > > (arange_set_node_high): Likewise.
> > > (arange_set_node_set_high): Likewise.
> > > (arange_set_node_value): Likewise.
> > > (arange_set_node_set_value): Likewise.
> > > (arange_set_splay_tree_insert): Likewise.
> > >
> > > * arange-set.h: Include "splay-tree.h".
> > > (arange_set_uhostptr_t): Defined as splay_tree_uhostptr_t.
> > >
> > > * configure.in: Check if long long exists.
> > > * config.in: Regenerated.
> > > * configure: Likewise.
> > >
> > > --- bfd/arange-set.c.vma 2007-09-21 09:16:17.000000000 -0700
> > > +++ bfd/arange-set.c 2007-11-13 06:46:18.000000000 -0800
> > > @@ -23,8 +23,12 @@
> > > #include "bfd.h"
> > > #include "libiberty.h"
> > > #include "libbfd.h"
> > > +
> > > +#ifdef BFD64
> > > +#define USE_SPLAY_TREE_LONG_LONG
> > > +#endif
> > > +
> > > #include "arange-set.h"
> > > -#include "splay-tree.h"
> > >
> > > /* Implementation of an arange-set. The set is implemented using the
> > > splay tree support in libiberty. The advantage of using this is
> > > @@ -142,7 +146,8 @@ arange_set_delete_value_container (splay
> > > {
> > > arange_value_container_t *container;
> > >
> > > - container = (arange_value_container_t*) value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)value;
> > > arange_set_delete_value (container->set, container->value);
> > > arange_set_deallocate (container->set, container);
> > > }
> > > @@ -255,7 +260,8 @@ arange_set_node_high (arange_set set, sp
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > return container->high;
> > > }
> > >
> > > @@ -271,7 +277,8 @@ arange_set_node_set_high (arange_set set
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > container->high = address;
> > > }
> > > else
> > > @@ -296,7 +303,8 @@ arange_set_node_value (arange_set set, s
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > return container->value;
> > > }
> > >
> > > @@ -315,7 +323,8 @@ arange_set_node_set_value (arange_set se
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > container->value = value;
> > > }
> > > }
> > > @@ -445,7 +454,7 @@ arange_set_splay_tree_insert (arange_set
> > > container->set = set;
> > >
> > > container->value = value;
> > > - sp_value = (splay_tree_value) container;
> > > + sp_value = (splay_tree_value) (arange_set_uhostptr_t)container;
> > > }
> > > else
> > > sp_value = (splay_tree_value) high;
> > > --- bfd/arange-set.h.vma 2007-09-21 09:16:17.000000000 -0700
> > > +++ bfd/arange-set.h 2007-11-13 06:41:48.000000000 -0800
> > > @@ -75,16 +75,13 @@
> > >
> > > #include "sysdep.h"
> > > #include "bfd.h"
> > > +#include "splay-tree.h"
> > >
> > > /* An arange_set is a pointer to an arange_set_s struct, whose implementation
> > > is opaque to clients using the arange set. */
> > > typedef struct arange_set_s *arange_set;
> > >
> > > -#ifndef _WIN64
> > > - typedef unsigned long int arange_set_uhostptr_t;
> > > -#else
> > > - typedef unsigned long long arange_set_uhostptr_t;
> > > -#endif
> > > +typedef splay_tree_uhostptr_t arange_set_uhostptr_t;
> > >
> > > /* Type of value attached to an arange. This should be wide enough to be
> > > converted from and back to any type without loss. */
> > > --- bfd/config.in.vma 2007-10-30 11:48:31.000000000 -0700
> > > +++ bfd/config.in 2007-11-13 06:31:39.000000000 -0800
> > > @@ -105,6 +105,9 @@
> > > /* Define to 1 if you have the <inttypes.h> header file. */
> > > #undef HAVE_INTTYPES_H
> > >
> > > +/* Define to 1 if the system has the type `long long'. */
> > > +#undef HAVE_LONG_LONG
> > > +
> > > /* Define if <sys/procfs.h> has lwpstatus_t. */
> > > #undef HAVE_LWPSTATUS_T
> > >
> > > --- bfd/configure.in.vma 2007-10-30 11:48:31.000000000 -0700
> > > +++ bfd/configure.in 2007-11-13 06:31:22.000000000 -0800
> > > @@ -135,7 +135,7 @@ BFD_HOST_64_BIT=
> > > BFD_HOST_U_64_BIT=
> > > BFD_HOSTPTR_T="unsigned long"
> > >
> > > -AC_CHECK_SIZEOF(long long)
> > > +AC_CHECK_TYPES([long long], [AC_CHECK_SIZEOF(long long)])
> > > AC_CHECK_SIZEOF(void *)
> > > AC_CHECK_SIZEOF(long)
> > >
> > >
>
--
H¨¦ctor Or¨®n
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2007-12-04 11:35 ` H.J. Lu
2007-12-04 15:41 ` Hector Oron
@ 2007-12-04 19:40 ` Doug Kwan (關振德)
1 sibling, 0 replies; 10+ messages in thread
From: Doug Kwan (關振德) @ 2007-12-04 19:40 UTC (permalink / raw)
To: H.J. Lu; +Cc: binutils, gcc-patches, mark, dj
Hi HJ,
I don't have right to check into the binutils source tree. So my
comments cannot be counted as a review :).
There are other ways to fix this without affecting gcc. This is a
speed optimization. The easiest way is to turn this off when spray
tree nodes cannot store 64-bit target addresses. Currently there is
only one use of the arange set data structure inside lib BFD and there
is logic to determine when this is turned on. We can simply change
that.
Another way to fix this is always allocate a structure to store
target VMA and have the spray tree storing pointers to structures
instead of storing VMA directly. That uses a bit more memory and
cycles. I can do the changes if we think this is a better approach.
-Doug
2007/12/4, H.J. Lu <hjl@lucon.org>:
> Hi Doug,
>
> Thanks for your comments.
>
> Although this bug doesn't affect gcc since gcc doesn't store 64bit
> values in splay-tree on 32bit hosts, splay-tree is shared by both gcc
> and binutils. Could someone from gcc review my patches to gcc and
> splay-tree? Mark, DJ, can you look into them?
>
> Thanks.
>
>
> H.J.
> ---
> On Mon, Dec 03, 2007 at 07:39:38AM -0800, Doug Kwan (關振德) wrote:
> > Hi H.J.
> >
> > Thanks for fixing this. I was on vacation in the last 3 weeks and
> > out of the country. I only returned to work to day. My apology for not
> > having tested this on the 32-bit host/64-bit target in the first
> > place.
> >
> > -Doug
> >
> > 2007/11/14, H.J. Lu <hjl@lucon.org>:
> > > On Tue, Nov 13, 2007 at 03:32:38PM -0800, H.J. Lu wrote:
> > > > On Wed, Nov 14, 2007 at 09:05:08AM +1030, Alan Modra wrote:
> > > > > On Tue, Nov 13, 2007 at 09:18:45AM -0800, H.J. Lu wrote:
> > > > > > Current linker is broken on 32bit host with 64bit BFD. The problem
> > > > > > is splay-tree doesn't support 64bit value on bit host, but arange-set.c
> > > > > > uses splay-tree on bfd_vma. Fixing it isn't easy since splay-tree is
> > > > > > also used in gcc. We can't use #ifdef in splay-tree.h in gcc due
> > > > > > to lack of #ifdef in gengtype in gcc. This patch will abort the
> > > > > > linker if it detects such situation.
> > > > >
> > > > > Aborting isn't a solution. I'll revert Doug's patch in a week or so
> > > > > if someone can't find a proper solution, eg. fallback to old scheme
> > > > > if splay tree support is inadeqaute.
> > > > >
> > > >
> > > > Here are 2 patches to update splay tree. The idea is to provide both
> > > > long and long long interfaces for splay-tree if they are different.
> > > > The default interface is the smallest one which can hold a pointer.
> > > > Gcc support is tricky since gengtype doesn't support #ifdef. I
> > > > have to use splay-tree-default.h and let gcc override it. I will
> > > > post a patch for arange-set.c if these 2 patches are approved.
> > > >
> > > > Thanks.
> > > >
> > > >
> > >
> > > Here is the patch for bfd.
> > >
> > >
> > > H.J.
> > > ----
> > > 2007-11-14 H.J. Lu <hongjiu.lu@intel.com>
> > >
> > > PR ld/5303
> > > * arange-set.c (USE_SPLAY_TREE_LONG_LONG): Define if BFD64 is
> > > defined.
> > > Don't include "splay-tree.h".
> > > (arange_set_delete_value_container): Add cast to
> > > arange_set_uhostptr_t.
> > > (arange_set_node_high): Likewise.
> > > (arange_set_node_set_high): Likewise.
> > > (arange_set_node_value): Likewise.
> > > (arange_set_node_set_value): Likewise.
> > > (arange_set_splay_tree_insert): Likewise.
> > >
> > > * arange-set.h: Include "splay-tree.h".
> > > (arange_set_uhostptr_t): Defined as splay_tree_uhostptr_t.
> > >
> > > * configure.in: Check if long long exists.
> > > * config.in: Regenerated.
> > > * configure: Likewise.
> > >
> > > --- bfd/arange-set.c.vma 2007-09-21 09:16:17.000000000 -0700
> > > +++ bfd/arange-set.c 2007-11-13 06:46:18.000000000 -0800
> > > @@ -23,8 +23,12 @@
> > > #include "bfd.h"
> > > #include "libiberty.h"
> > > #include "libbfd.h"
> > > +
> > > +#ifdef BFD64
> > > +#define USE_SPLAY_TREE_LONG_LONG
> > > +#endif
> > > +
> > > #include "arange-set.h"
> > > -#include "splay-tree.h"
> > >
> > > /* Implementation of an arange-set. The set is implemented using the
> > > splay tree support in libiberty. The advantage of using this is
> > > @@ -142,7 +146,8 @@ arange_set_delete_value_container (splay
> > > {
> > > arange_value_container_t *container;
> > >
> > > - container = (arange_value_container_t*) value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)value;
> > > arange_set_delete_value (container->set, container->value);
> > > arange_set_deallocate (container->set, container);
> > > }
> > > @@ -255,7 +260,8 @@ arange_set_node_high (arange_set set, sp
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > return container->high;
> > > }
> > >
> > > @@ -271,7 +277,8 @@ arange_set_node_set_high (arange_set set
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > container->high = address;
> > > }
> > > else
> > > @@ -296,7 +303,8 @@ arange_set_node_value (arange_set set, s
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > return container->value;
> > > }
> > >
> > > @@ -315,7 +323,8 @@ arange_set_node_set_value (arange_set se
> > >
> > > if (set->value_p)
> > > {
> > > - container = (arange_value_container_t*) node->value;
> > > + container
> > > + = (arange_value_container_t*) (arange_set_uhostptr_t)node->value;
> > > container->value = value;
> > > }
> > > }
> > > @@ -445,7 +454,7 @@ arange_set_splay_tree_insert (arange_set
> > > container->set = set;
> > >
> > > container->value = value;
> > > - sp_value = (splay_tree_value) container;
> > > + sp_value = (splay_tree_value) (arange_set_uhostptr_t)container;
> > > }
> > > else
> > > sp_value = (splay_tree_value) high;
> > > --- bfd/arange-set.h.vma 2007-09-21 09:16:17.000000000 -0700
> > > +++ bfd/arange-set.h 2007-11-13 06:41:48.000000000 -0800
> > > @@ -75,16 +75,13 @@
> > >
> > > #include "sysdep.h"
> > > #include "bfd.h"
> > > +#include "splay-tree.h"
> > >
> > > /* An arange_set is a pointer to an arange_set_s struct, whose implementation
> > > is opaque to clients using the arange set. */
> > > typedef struct arange_set_s *arange_set;
> > >
> > > -#ifndef _WIN64
> > > - typedef unsigned long int arange_set_uhostptr_t;
> > > -#else
> > > - typedef unsigned long long arange_set_uhostptr_t;
> > > -#endif
> > > +typedef splay_tree_uhostptr_t arange_set_uhostptr_t;
> > >
> > > /* Type of value attached to an arange. This should be wide enough to be
> > > converted from and back to any type without loss. */
> > > --- bfd/config.in.vma 2007-10-30 11:48:31.000000000 -0700
> > > +++ bfd/config.in 2007-11-13 06:31:39.000000000 -0800
> > > @@ -105,6 +105,9 @@
> > > /* Define to 1 if you have the <inttypes.h> header file. */
> > > #undef HAVE_INTTYPES_H
> > >
> > > +/* Define to 1 if the system has the type `long long'. */
> > > +#undef HAVE_LONG_LONG
> > > +
> > > /* Define if <sys/procfs.h> has lwpstatus_t. */
> > > #undef HAVE_LWPSTATUS_T
> > >
> > > --- bfd/configure.in.vma 2007-10-30 11:48:31.000000000 -0700
> > > +++ bfd/configure.in 2007-11-13 06:31:22.000000000 -0800
> > > @@ -135,7 +135,7 @@ BFD_HOST_64_BIT=
> > > BFD_HOST_U_64_BIT=
> > > BFD_HOSTPTR_T="unsigned long"
> > >
> > > -AC_CHECK_SIZEOF(long long)
> > > +AC_CHECK_TYPES([long long], [AC_CHECK_SIZEOF(long long)])
> > > AC_CHECK_SIZEOF(void *)
> > > AC_CHECK_SIZEOF(long)
> > >
> > >
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
2008-02-09 16:22 H.J. Lu
@ 2008-02-09 18:27 ` DJ Delorie
0 siblings, 0 replies; 10+ messages in thread
From: DJ Delorie @ 2008-02-09 18:27 UTC (permalink / raw)
To: hjl.tools; +Cc: binutils, gcc-patches
> Ok to install to both gcc and binutils?
No.
> * splay-tree.c: Include <stddef.h>. Don't include any header
> files if BFD_ARCH_SIZE is defind.
This is just wrong. The right thing to do is add a 64-bit splay tree
in libiberty. CLEANLY.
^ permalink raw reply [flat|nested] 10+ messages in thread
* PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host
@ 2008-02-09 16:22 H.J. Lu
2008-02-09 18:27 ` DJ Delorie
0 siblings, 1 reply; 10+ messages in thread
From: H.J. Lu @ 2008-02-09 16:22 UTC (permalink / raw)
To: binutils; +Cc: gcc-patches
splay-tree can only handle types with size up to 32bit on 32bit host.
But BFD uses splay-tree on bfd_vma, which can be 64bit. So currently,
binutils is broken for 64bit targets on 32bit hosts. This patch
adds a splay-tree for BFD and use it for BFD, instead of the one
in libiberty. Ok to install to both gcc and binutils?
H.J.
----
bfd/
2008-02-09 H.J. Lu <hongjiu.lu@intel.com>
PR ld/5303
* Makefile.am (BFD32_LIBS): Add splay-tree.lo
(BFD32_LIBS_CFILES): Add splay-tree.c.
Run "make dep-am".
* Makefile.in: Regenerated.
* arange-set.c: Don't incldue splay-tree.h.
(arange_set_delete_value_container): Add cast to ptrdiff_t.
(arange_set_node_high): Likewise.
(arange_set_node_set_high): Likewise.
(arange_set_node_value): Likewise.
(arange_set_node_set_value): Likewise.
(arange_set_splay_tree_insert): Likewise.
* bfd-in.h: Define splay tree interface for bfd_vma.
* bfd-in2.: Regenerated.
* splay-tree.c: New.
libiberty/
2008-02-09 H.J. Lu <hongjiu.lu@intel.com>
PR ld/5303
* splay-tree.c: Include <stddef.h>. Don't include any header
files if BFD_ARCH_SIZE is defind.
(splay_tree_delete_helper): Cast to ptrdiff_t instead.
(splay_tree_compare_pointers): Likewise.
--- binutils/bfd/Makefile.am.splay 2007-11-09 11:30:56.000000000 -0800
+++ binutils/bfd/Makefile.am 2008-02-09 07:28:49.000000000 -0800
@@ -42,7 +42,7 @@ BFD32_LIBS = \
format.lo init.lo libbfd.lo opncls.lo reloc.lo \
section.lo syms.lo targets.lo hash.lo linker.lo \
srec.lo binary.lo tekhex.lo ihex.lo stabs.lo stab-syms.lo \
- merge.lo dwarf2.lo simple.lo arange-set.lo
+ merge.lo dwarf2.lo simple.lo arange-set.lo splay-tree.lo
BFD64_LIBS = archive64.lo
@@ -52,7 +52,7 @@ BFD32_LIBS_CFILES = \
format.c init.c libbfd.c opncls.c reloc.c \
section.c syms.c targets.c hash.c linker.c \
srec.c binary.c tekhex.c ihex.c stabs.c stab-syms.c \
- merge.c dwarf2.c simple.c arange-set.c
+ merge.c dwarf2.c simple.c arange-set.c splay-tree.c
BFD64_LIBS_CFILES = archive64.c
@@ -1053,7 +1053,9 @@ dwarf2.lo: dwarf2.c $(INCDIR)/filenames.
simple.lo: simple.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h \
$(INCDIR)/bfdlink.h
arange-set.lo: arange-set.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
- $(INCDIR)/hashtab.h arange-set.h $(INCDIR)/splay-tree.h
+ $(INCDIR)/hashtab.h arange-set.h
+splay-tree.lo: splay-tree.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
+ ../libiberty/splay-tree.c
archive64.lo: archive64.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h \
$(INCDIR)/aout/ar.h
cpu-alpha.lo: cpu-alpha.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h
@@ -1580,7 +1582,7 @@ elf-eh-frame.lo: elf-eh-frame.c $(INCDIR
elf-vxworks.lo: elf-vxworks.c $(INCDIR)/filenames.h \
$(INCDIR)/hashtab.h elf-bfd.h $(INCDIR)/elf/common.h \
$(INCDIR)/elf/internal.h $(INCDIR)/elf/external.h $(INCDIR)/bfdlink.h \
- $(INCDIR)/elf/vxworks.h elf-vxworks.h
+ elf-vxworks.h $(INCDIR)/elf/vxworks.h
epoc-pe-arm.lo: epoc-pe-arm.c pe-arm.c $(INCDIR)/filenames.h \
coff-arm.c $(INCDIR)/hashtab.h $(INCDIR)/coff/arm.h \
$(INCDIR)/coff/external.h $(INCDIR)/coff/internal.h \
--- binutils/bfd/Makefile.in.splay 2007-11-09 11:30:56.000000000 -0800
+++ binutils/bfd/Makefile.in 2008-02-09 07:28:49.000000000 -0800
@@ -84,7 +84,8 @@ am__objects_1 = archive.lo archures.lo b
cache.lo coffgen.lo corefile.lo format.lo init.lo libbfd.lo \
opncls.lo reloc.lo section.lo syms.lo targets.lo hash.lo \
linker.lo srec.lo binary.lo tekhex.lo ihex.lo stabs.lo \
- stab-syms.lo merge.lo dwarf2.lo simple.lo arange-set.lo
+ stab-syms.lo merge.lo dwarf2.lo simple.lo arange-set.lo \
+ splay-tree.lo
am_libbfd_la_OBJECTS = $(am__objects_1)
libbfd_la_OBJECTS = $(am_libbfd_la_OBJECTS)
DEFAULT_INCLUDES = -I. -I$(srcdir) -I.
@@ -202,11 +203,8 @@ WARN_CFLAGS = @WARN_CFLAGS@
WIN32LDFLAGS = @WIN32LDFLAGS@
WIN32LIBADD = @WIN32LIBADD@
XGETTEXT = @XGETTEXT@
-ac_ct_AR = @ac_ct_AR@
ac_ct_CC = @ac_ct_CC@
ac_ct_DUMPBIN = @ac_ct_DUMPBIN@
-ac_ct_RANLIB = @ac_ct_RANLIB@
-ac_ct_STRIP = @ac_ct_STRIP@
all_backends = @all_backends@
am__fastdepCC_FALSE = @am__fastdepCC_FALSE@
am__fastdepCC_TRUE = @am__fastdepCC_TRUE@
@@ -232,6 +230,7 @@ build_vendor = @build_vendor@
datadir = @datadir@
datarootdir = @datarootdir@
docdir = @docdir@
+dvidir = @dvidir@
exec_prefix = @exec_prefix@
host = @host@
host_alias = @host_alias@
@@ -245,13 +244,16 @@ infodir = @infodir@
install_sh = @install_sh@
libdir = @libdir@
libexecdir = @libexecdir@
+localedir = @localedir@
localstatedir = @localstatedir@
lt_ECHO = @lt_ECHO@
mandir = @mandir@
mkdir_p = @mkdir_p@
oldincludedir = @oldincludedir@
+pdfdir = @pdfdir@
prefix = @prefix@
program_transform_name = @program_transform_name@
+psdir = @psdir@
sbindir = @sbindir@
sharedstatedir = @sharedstatedir@
sysconfdir = @sysconfdir@
@@ -292,7 +294,7 @@ BFD32_LIBS = \
format.lo init.lo libbfd.lo opncls.lo reloc.lo \
section.lo syms.lo targets.lo hash.lo linker.lo \
srec.lo binary.lo tekhex.lo ihex.lo stabs.lo stab-syms.lo \
- merge.lo dwarf2.lo simple.lo arange-set.lo
+ merge.lo dwarf2.lo simple.lo arange-set.lo splay-tree.lo
BFD64_LIBS = archive64.lo
BFD32_LIBS_CFILES = \
@@ -301,7 +303,7 @@ BFD32_LIBS_CFILES = \
format.c init.c libbfd.c opncls.c reloc.c \
section.c syms.c targets.c hash.c linker.c \
srec.c binary.c tekhex.c ihex.c stabs.c stab-syms.c \
- merge.c dwarf2.c simple.c arange-set.c
+ merge.c dwarf2.c simple.c arange-set.c splay-tree.c
BFD64_LIBS_CFILES = archive64.c
@@ -1633,7 +1635,9 @@ dwarf2.lo: dwarf2.c $(INCDIR)/filenames.
simple.lo: simple.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h \
$(INCDIR)/bfdlink.h
arange-set.lo: arange-set.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
- $(INCDIR)/hashtab.h arange-set.h $(INCDIR)/splay-tree.h
+ $(INCDIR)/hashtab.h arange-set.h
+splay-tree.lo: splay-tree.c $(INCDIR)/filenames.h $(INCDIR)/libiberty.h \
+ ../libiberty/splay-tree.c
archive64.lo: archive64.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h \
$(INCDIR)/aout/ar.h
cpu-alpha.lo: cpu-alpha.c $(INCDIR)/filenames.h $(INCDIR)/hashtab.h
@@ -2160,7 +2164,7 @@ elf-eh-frame.lo: elf-eh-frame.c $(INCDIR
elf-vxworks.lo: elf-vxworks.c $(INCDIR)/filenames.h \
$(INCDIR)/hashtab.h elf-bfd.h $(INCDIR)/elf/common.h \
$(INCDIR)/elf/internal.h $(INCDIR)/elf/external.h $(INCDIR)/bfdlink.h \
- $(INCDIR)/elf/vxworks.h elf-vxworks.h
+ elf-vxworks.h $(INCDIR)/elf/vxworks.h
epoc-pe-arm.lo: epoc-pe-arm.c pe-arm.c $(INCDIR)/filenames.h \
coff-arm.c $(INCDIR)/hashtab.h $(INCDIR)/coff/arm.h \
$(INCDIR)/coff/external.h $(INCDIR)/coff/internal.h \
--- binutils/bfd/arange-set.c.splay 2007-09-21 09:16:17.000000000 -0700
+++ binutils/bfd/arange-set.c 2008-02-09 07:50:45.000000000 -0800
@@ -24,7 +24,6 @@
#include "libiberty.h"
#include "libbfd.h"
#include "arange-set.h"
-#include "splay-tree.h"
/* Implementation of an arange-set. The set is implemented using the
splay tree support in libiberty. The advantage of using this is
@@ -142,7 +141,7 @@ arange_set_delete_value_container (splay
{
arange_value_container_t *container;
- container = (arange_value_container_t*) value;
+ container = (arange_value_container_t*) (ptrdiff_t) value;
arange_set_delete_value (container->set, container->value);
arange_set_deallocate (container->set, container);
}
@@ -255,7 +254,7 @@ arange_set_node_high (arange_set set, sp
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container = (arange_value_container_t*) (ptrdiff_t) node->value;
return container->high;
}
@@ -271,7 +270,7 @@ arange_set_node_set_high (arange_set set
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container = (arange_value_container_t*) (ptrdiff_t) node->value;
container->high = address;
}
else
@@ -296,7 +295,7 @@ arange_set_node_value (arange_set set, s
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container = (arange_value_container_t*) (ptrdiff_t) node->value;
return container->value;
}
@@ -315,7 +314,7 @@ arange_set_node_set_value (arange_set se
if (set->value_p)
{
- container = (arange_value_container_t*) node->value;
+ container = (arange_value_container_t*) (ptrdiff_t) node->value;
container->value = value;
}
}
@@ -445,7 +444,7 @@ arange_set_splay_tree_insert (arange_set
container->set = set;
container->value = value;
- sp_value = (splay_tree_value) container;
+ sp_value = (splay_tree_value) (ptrdiff_t) container;
}
else
sp_value = (splay_tree_value) high;
--- binutils/bfd/bfd-in.h.splay 2008-01-25 09:01:03.000000000 -0800
+++ binutils/bfd/bfd-in.h 2008-02-09 07:41:55.000000000 -0800
@@ -984,3 +984,130 @@ struct coff_comdat_info
extern struct coff_comdat_info *bfd_coff_get_comdat_section
(bfd *, struct bfd_section *);
+#define splay_tree_key bfd_splay_tree_key
+#define splay_tree_value bfd_splay_tree_value
+#define splay_tree_node_s bfd_splay_tree_node_s
+#define splay_tree_node bfd_splay_tree_node
+#define splay_tree_compare_fn bfd_splay_tree_compare_fn
+#define splay_tree_delete_key_fn bfd_splay_tree_delete_key_fn
+#define splay_tree_delete_value_fn bfd_splay_tree_delete_value_fn
+#define splay_tree_foreach_fn bfd_splay_tree_foreach_fn
+#define splay_tree_allocate_fn bfd_splay_tree_allocate_fn
+#define splay_tree_deallocate_fn bfd_splay_tree_deallocate_fn
+#define splay_tree_s bfd_splay_tree_s
+#define splay_tree bfd_splay_tree
+#define splay_tree_new bfd_splay_tree_new
+#define splay_tree_new_with_allocator bfd_splay_tree_new_with_allocator
+#define splay_tree_delete bfd_splay_tree_delete
+#define splay_tree_insert bfd_splay_tree_insert
+#define splay_tree_remove bfd_splay_tree_remove
+#define splay_tree_lookup bfd_splay_tree_lookup
+#define splay_tree_predecessor bfd_splay_tree_predecessor
+#define splay_tree_successor bfd_splay_tree_successor
+#define splay_tree_max bfd_splay_tree_max
+#define splay_tree_min bfd_splay_tree_min
+#define splay_tree_foreach bfd_splay_tree_foreach
+#define splay_tree_compare_ints bfd_splay_tree_compare_ints
+#define splay_tree_compare_pointers bfd_splay_tree_compare_pointers
+
+#ifndef GTY
+#define GTY(X)
+#endif
+
+/* Use typedefs for the key and data types to facilitate changing
+ these types, if necessary. These types should be sufficiently wide
+ that any pointer or scalar can be cast to these types, and then
+ cast back, without loss of precision. */
+typedef bfd_vma splay_tree_key;
+typedef bfd_vma splay_tree_value;
+
+/* Forward declaration for a node in the tree. */
+typedef struct splay_tree_node_s *splay_tree_node;
+
+/* The type of a function which compares two splay-tree keys. The
+ function should return values as for qsort. */
+typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key);
+
+/* The type of a function used to deallocate any resources associated
+ with the key. */
+typedef void (*splay_tree_delete_key_fn) (splay_tree_key);
+
+/* The type of a function used to deallocate any resources associated
+ with the value. */
+typedef void (*splay_tree_delete_value_fn) (splay_tree_value);
+
+/* The type of a function used to iterate over the tree. */
+typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*);
+
+/* The type of a function used to allocate memory for tree root and
+ node structures. The first argument is the number of bytes needed;
+ the second is a data pointer the splay tree functions pass through
+ to the allocator. This function must never return zero. */
+typedef void *(*splay_tree_allocate_fn) (int, void *);
+
+/* The type of a function used to free memory allocated using the
+ corresponding splay_tree_allocate_fn. The first argument is the
+ memory to be freed; the latter is a data pointer the splay tree
+ functions pass through to the freer. */
+typedef void (*splay_tree_deallocate_fn) (void *, void *);
+
+/* The nodes in the splay tree. */
+struct splay_tree_node_s GTY(())
+{
+ /* The key. */
+ splay_tree_key GTY ((use_param1)) key;
+
+ /* The value. */
+ splay_tree_value GTY ((use_param2)) value;
+
+ /* The left and right children, respectively. */
+ splay_tree_node GTY ((use_params)) left;
+ splay_tree_node GTY ((use_params)) right;
+};
+
+/* The splay tree itself. */
+struct splay_tree_s GTY(())
+{
+ /* The root of the tree. */
+ splay_tree_node GTY ((use_params)) root;
+
+ /* The comparision function. */
+ splay_tree_compare_fn comp;
+
+ /* The deallocate-key function. NULL if no cleanup is necessary. */
+ splay_tree_delete_key_fn delete_key;
+
+ /* The deallocate-value function. NULL if no cleanup is necessary. */
+ splay_tree_delete_value_fn delete_value;
+
+ /* Allocate/free functions, and a data pointer to pass to them. */
+ splay_tree_allocate_fn allocate;
+ splay_tree_deallocate_fn deallocate;
+ void * GTY((skip)) allocate_data;
+};
+
+typedef struct splay_tree_s *splay_tree;
+
+extern splay_tree splay_tree_new (splay_tree_compare_fn,
+ splay_tree_delete_key_fn,
+ splay_tree_delete_value_fn);
+extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn,
+ splay_tree_delete_key_fn,
+ splay_tree_delete_value_fn,
+ splay_tree_allocate_fn,
+ splay_tree_deallocate_fn,
+ void *);
+extern void splay_tree_delete (splay_tree);
+extern splay_tree_node splay_tree_insert (splay_tree,
+ splay_tree_key,
+ splay_tree_value);
+extern void splay_tree_remove (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_max (splay_tree);
+extern splay_tree_node splay_tree_min (splay_tree);
+extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*);
+extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key);
+extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key);
+
--- binutils/bfd/bfd-in2.h.splay 2008-02-04 11:50:44.000000000 -0800
+++ binutils/bfd/bfd-in2.h 2008-02-09 07:45:56.000000000 -0800
@@ -991,6 +991,133 @@ struct coff_comdat_info
extern struct coff_comdat_info *bfd_coff_get_comdat_section
(bfd *, struct bfd_section *);
+#define splay_tree_key bfd_splay_tree_key
+#define splay_tree_value bfd_splay_tree_value
+#define splay_tree_node_s bfd_splay_tree_node_s
+#define splay_tree_node bfd_splay_tree_node
+#define splay_tree_compare_fn bfd_splay_tree_compare_fn
+#define splay_tree_delete_key_fn bfd_splay_tree_delete_key_fn
+#define splay_tree_delete_value_fn bfd_splay_tree_delete_value_fn
+#define splay_tree_foreach_fn bfd_splay_tree_foreach_fn
+#define splay_tree_allocate_fn bfd_splay_tree_allocate_fn
+#define splay_tree_deallocate_fn bfd_splay_tree_deallocate_fn
+#define splay_tree_s bfd_splay_tree_s
+#define splay_tree bfd_splay_tree
+#define splay_tree_new bfd_splay_tree_new
+#define splay_tree_new_with_allocator bfd_splay_tree_new_with_allocator
+#define splay_tree_delete bfd_splay_tree_delete
+#define splay_tree_insert bfd_splay_tree_insert
+#define splay_tree_remove bfd_splay_tree_remove
+#define splay_tree_lookup bfd_splay_tree_lookup
+#define splay_tree_predecessor bfd_splay_tree_predecessor
+#define splay_tree_successor bfd_splay_tree_successor
+#define splay_tree_max bfd_splay_tree_max
+#define splay_tree_min bfd_splay_tree_min
+#define splay_tree_foreach bfd_splay_tree_foreach
+#define splay_tree_compare_ints bfd_splay_tree_compare_ints
+#define splay_tree_compare_pointers bfd_splay_tree_compare_pointers
+
+#ifndef GTY
+#define GTY(X)
+#endif
+
+/* Use typedefs for the key and data types to facilitate changing
+ these types, if necessary. These types should be sufficiently wide
+ that any pointer or scalar can be cast to these types, and then
+ cast back, without loss of precision. */
+typedef bfd_vma splay_tree_key;
+typedef bfd_vma splay_tree_value;
+
+/* Forward declaration for a node in the tree. */
+typedef struct splay_tree_node_s *splay_tree_node;
+
+/* The type of a function which compares two splay-tree keys. The
+ function should return values as for qsort. */
+typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key);
+
+/* The type of a function used to deallocate any resources associated
+ with the key. */
+typedef void (*splay_tree_delete_key_fn) (splay_tree_key);
+
+/* The type of a function used to deallocate any resources associated
+ with the value. */
+typedef void (*splay_tree_delete_value_fn) (splay_tree_value);
+
+/* The type of a function used to iterate over the tree. */
+typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*);
+
+/* The type of a function used to allocate memory for tree root and
+ node structures. The first argument is the number of bytes needed;
+ the second is a data pointer the splay tree functions pass through
+ to the allocator. This function must never return zero. */
+typedef void *(*splay_tree_allocate_fn) (int, void *);
+
+/* The type of a function used to free memory allocated using the
+ corresponding splay_tree_allocate_fn. The first argument is the
+ memory to be freed; the latter is a data pointer the splay tree
+ functions pass through to the freer. */
+typedef void (*splay_tree_deallocate_fn) (void *, void *);
+
+/* The nodes in the splay tree. */
+struct splay_tree_node_s GTY(())
+{
+ /* The key. */
+ splay_tree_key GTY ((use_param1)) key;
+
+ /* The value. */
+ splay_tree_value GTY ((use_param2)) value;
+
+ /* The left and right children, respectively. */
+ splay_tree_node GTY ((use_params)) left;
+ splay_tree_node GTY ((use_params)) right;
+};
+
+/* The splay tree itself. */
+struct splay_tree_s GTY(())
+{
+ /* The root of the tree. */
+ splay_tree_node GTY ((use_params)) root;
+
+ /* The comparision function. */
+ splay_tree_compare_fn comp;
+
+ /* The deallocate-key function. NULL if no cleanup is necessary. */
+ splay_tree_delete_key_fn delete_key;
+
+ /* The deallocate-value function. NULL if no cleanup is necessary. */
+ splay_tree_delete_value_fn delete_value;
+
+ /* Allocate/free functions, and a data pointer to pass to them. */
+ splay_tree_allocate_fn allocate;
+ splay_tree_deallocate_fn deallocate;
+ void * GTY((skip)) allocate_data;
+};
+
+typedef struct splay_tree_s *splay_tree;
+
+extern splay_tree splay_tree_new (splay_tree_compare_fn,
+ splay_tree_delete_key_fn,
+ splay_tree_delete_value_fn);
+extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn,
+ splay_tree_delete_key_fn,
+ splay_tree_delete_value_fn,
+ splay_tree_allocate_fn,
+ splay_tree_deallocate_fn,
+ void *);
+extern void splay_tree_delete (splay_tree);
+extern splay_tree_node splay_tree_insert (splay_tree,
+ splay_tree_key,
+ splay_tree_value);
+extern void splay_tree_remove (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_max (splay_tree);
+extern splay_tree_node splay_tree_min (splay_tree);
+extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*);
+extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key);
+extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key);
+
/* Extracted from init.c. */
void bfd_init (void);
--- binutils/bfd/splay-tree.c.splay 2008-02-09 07:28:49.000000000 -0800
+++ binutils/bfd/splay-tree.c 2008-02-09 07:28:49.000000000 -0800
@@ -0,0 +1,24 @@
+/* A splay-tree for BFD.
+ Copyright 2008 Free Software Foundation, Inc.
+
+ This file is part of BFD, the Binary File Descriptor library.
+
+ 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 3 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. */
+
+#include "sysdep.h"
+#include "bfd.h"
+#include "libiberty.h"
+#include "../libiberty/splay-tree.c"
--- binutils/libiberty/splay-tree.c.splay 2008-01-21 16:52:44.000000000 -0800
+++ binutils/libiberty/splay-tree.c 2008-02-09 07:57:54.000000000 -0800
@@ -24,6 +24,8 @@ Boston, MA 02110-1301, USA. */
Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
Algorithms. Harper-Collins, Inc. 1991. */
+/* Include those header files only when built outside of BFD. */
+#ifndef BFD_ARCH_SIZE
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
@@ -32,10 +34,12 @@ Boston, MA 02110-1301, USA. */
#include <stdlib.h>
#endif
+#include <stddef.h>
#include <stdio.h>
#include "libiberty.h"
#include "splay-tree.h"
+#endif
static void splay_tree_delete_helper (splay_tree, splay_tree_node);
static inline void rotate_left (splay_tree_node *,
@@ -64,7 +68,7 @@ splay_tree_delete_helper (splay_tree sp,
VDEL (node->value);
/* We use the "key" field to hold the "next" pointer. */
- node->key = (splay_tree_key)pending;
+ node->key = (splay_tree_key) (ptrdiff_t) pending;
pending = (splay_tree_node)node;
/* Now, keep processing the pending list until there aren't any
@@ -86,19 +90,19 @@ splay_tree_delete_helper (splay_tree sp,
{
KDEL (active->left->key);
VDEL (active->left->value);
- active->left->key = (splay_tree_key)pending;
+ active->left->key = (splay_tree_key) (ptrdiff_t) pending;
pending = (splay_tree_node)(active->left);
}
if (active->right)
{
KDEL (active->right->key);
VDEL (active->right->value);
- active->right->key = (splay_tree_key)pending;
+ active->right->key = (splay_tree_key) (ptrdiff_t) pending;
pending = (splay_tree_node)(active->right);
}
temp = active;
- active = (splay_tree_node)(temp->key);
+ active = (splay_tree_node) (ptrdiff_t) (temp->key);
(*sp->deallocate) ((char*) temp, sp->allocate_data);
}
}
@@ -517,9 +521,9 @@ splay_tree_compare_ints (splay_tree_key
int
splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
{
- if ((char*) k1 < (char*) k2)
+ if ((ptrdiff_t) k1 < (ptrdiff_t) k2)
return -1;
- else if ((char*) k1 > (char*) k2)
+ else if ((ptrdiff_t) k1 > (ptrdiff_t) k2)
return 1;
else
return 0;
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2008-02-09 18:27 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-11-13 17:18 PATCH: PR ld/5303: splay-tree doesn't support 64bit value on 32bit host H.J. Lu
2007-11-13 22:35 ` Alan Modra
2007-11-13 23:32 ` H.J. Lu
2007-11-14 16:30 ` H.J. Lu
2007-12-03 15:40 ` Doug Kwan (關振德)
2007-12-04 11:35 ` H.J. Lu
2007-12-04 15:41 ` Hector Oron
2007-12-04 19:40 ` Doug Kwan (關振德)
2008-02-09 16:22 H.J. Lu
2008-02-09 18:27 ` DJ Delorie
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).