From 54d533d306f88b283ef8a412b04358db4f54f00e Mon Sep 17 00:00:00 2001
From: nicola <nicola@138bc75d-0d04-0410-961f-82ee72b054a4>
Date: Sat, 18 Sep 2010 09:34:58 +0000
Subject: [PATCH] In libobjc/:         * hash.c: Include objc-private/hash.h
 instead of objc/hash.h.

        * objc/sarray.h: Moved into objc/deprecated/sarray.h;
        objc/sarray.h replaced with a placeholder including the file from
        the deprecated/ directory.
        * objc-private/sarray.h: New file (private copy of sarray.h).
        * hash.c: Include <assert.h> instead of "assert.h"
        * sarray.c: Include <assert.h> instead of "assert.h".  Include
        objc-private/sarray.h instead of objc/sarray.h.
        * selector.c: Include objc-private/sarray.h instead of
        objc/sarray.h.
        * sendmsg.c: Include <assert.h>.  Include objc-private/sarray.h
        instead of objc/sarray.h.
        * Makefile.in (OBJC_DEPRECATED_H): Added sarray.h.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@164389 138bc75d-0d04-0410-961f-82ee72b054a4
---
 libobjc/ChangeLog                |  17 +++
 libobjc/Makefile.in              |   3 +-
 libobjc/hash.c                   |   4 +-
 libobjc/objc-private/sarray.h    | 239 ++++++++++++++++++++++++++++++++++++++
 libobjc/objc/deprecated/sarray.h | 240 ++++++++++++++++++++++++++++++++++++++
 libobjc/objc/sarray.h            | 243 +--------------------------------------
 libobjc/sarray.c                 |   4 +-
 libobjc/selector.c               |   2 +-
 libobjc/sendmsg.c                |   3 +-
 9 files changed, 506 insertions(+), 249 deletions(-)
 create mode 100644 libobjc/objc-private/sarray.h
 create mode 100644 libobjc/objc/deprecated/sarray.h

diff --git a/libobjc/ChangeLog b/libobjc/ChangeLog
index 71af2b760b3..4c238076b10 100644
--- a/libobjc/ChangeLog
+++ b/libobjc/ChangeLog
@@ -1,3 +1,20 @@
+2010-09-18  Nicola Pero  <nicola.pero@meta-innovation.com>
+
+	* hash.c: Include objc-private/hash.h instead of objc/hash.h.
+
+	* objc/sarray.h: Moved into objc/deprecated/sarray.h;
+	objc/sarray.h replaced with a placeholder including the file from
+	the deprecated/ directory.
+	* objc-private/sarray.h: New file (private copy of sarray.h).
+	* hash.c: Include <assert.h> instead of "assert.h"
+	* sarray.c: Include <assert.h> instead of "assert.h".  Include
+	objc-private/sarray.h instead of objc/sarray.h.
+	* selector.c: Include objc-private/sarray.h instead of
+	objc/sarray.h.
+	* sendmsg.c: Include <assert.h>.  Include objc-private/sarray.h
+	instead of objc/sarray.h.
+	* Makefile.in (OBJC_DEPRECATED_H): Added sarray.h.	
+
 2010-09-17  Nicola Pero  <nicola.pero@meta-innovation.com>
 
 	* objc-private/objc-list.h (list_remove_elem): Unused function
diff --git a/libobjc/Makefile.in b/libobjc/Makefile.in
index 2fac2a574a4..71a3a2e21c2 100644
--- a/libobjc/Makefile.in
+++ b/libobjc/Makefile.in
@@ -120,11 +120,11 @@ OBJC_H = \
   message.h \
   objc-api.h \
   objc-decls.h \
-  sarray.h \
   thr.h \
   \
   hash.h \
   objc-list.h \
+  sarray.h \
   typedstream.h
 
 # User-visible header files containing deprecated APIs, from the
@@ -139,6 +139,7 @@ OBJC_DEPRECATED_H = \
   objc_malloc.h \
   objc_unexpected_exception.h \
   objc_valloc.h \
+  sarray.h \
   struct_objc_class.h \
   struct_objc_protocol.h \
   struct_objc_selector.h \
diff --git a/libobjc/hash.c b/libobjc/hash.c
index 9e0a608c130..602fc84a874 100644
--- a/libobjc/hash.c
+++ b/libobjc/hash.c
@@ -23,11 +23,11 @@ see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 <http://www.gnu.org/licenses/>.  */
 
 #include "objc-private/common.h"
-#include "assert.h"
+#include <assert.h> /* For assert */
 
 #include "objc/objc.h"
 #include "objc/objc-api.h"
-#include "objc/hash.h"
+#include "objc-private/hash.h"
 #include "objc-private/runtime.h"		/* for DEBUG_PRINTF */
 
 /* These two macros determine when a hash table is full and
diff --git a/libobjc/objc-private/sarray.h b/libobjc/objc-private/sarray.h
new file mode 100644
index 00000000000..f81b08e71e7
--- /dev/null
+++ b/libobjc/objc-private/sarray.h
@@ -0,0 +1,239 @@
+/* Sparse Arrays for Objective C dispatch tables
+   Copyright (C) 1993, 1995, 1996, 2004, 2009 Free Software Foundation, Inc.
+   Contributed by Kresten Krab Thorup.
+
+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 3, 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.
+
+Under Section 7 of GPL version 3, you are granted additional
+permissions described in the GCC Runtime Library Exception, version
+3.1, as published by the Free Software Foundation.
+
+You should have received a copy of the GNU General Public License and
+a copy of the GCC Runtime Library Exception along with this program;
+see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef __sarray_INCLUDE_GNU
+#define __sarray_INCLUDE_GNU
+
+#define OBJC_SPARSE2		/* 2-level sparse array */
+/* #define OBJC_SPARSE3 */      /* 3-level sparse array */
+
+#ifdef OBJC_SPARSE2
+extern const char* __objc_sparse2_id;
+#endif
+
+#ifdef OBJC_SPARSE3
+extern const char* __objc_sparse3_id;
+#endif
+
+#include <stddef.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+extern int nbuckets;		/* for stats */
+extern int nindices;
+extern int narrays;
+extern int idxsize;
+
+/* An unsigned integer of same size as a pointer */
+#define SIZET_BITS (sizeof(size_t)*8)
+
+#if defined(__sparc__) || defined(OBJC_SPARSE2)
+#define PRECOMPUTE_SELECTORS
+#endif
+
+#ifdef OBJC_SPARSE3
+
+/* Buckets are 8 words each */
+#define BUCKET_BITS 3
+#define BUCKET_SIZE (1<<BUCKET_BITS)
+#define BUCKET_MASK (BUCKET_SIZE-1)
+
+/* Indices are 16 words each */
+#define INDEX_BITS 4
+#define INDEX_SIZE (1<<INDEX_BITS)
+#define INDEX_MASK (INDEX_SIZE-1)
+
+#define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
+
+#else /* OBJC_SPARSE2 */
+
+/* Buckets are 32 words each */
+#define BUCKET_BITS 5
+#define BUCKET_SIZE (1<<BUCKET_BITS)
+#define BUCKET_MASK (BUCKET_SIZE-1)
+
+#endif /* OBJC_SPARSE2 */
+
+typedef size_t sidx;
+
+#ifdef PRECOMPUTE_SELECTORS
+
+struct soffset {
+#ifdef OBJC_SPARSE3
+  unsigned int unused : SIZET_BITS/4;
+  unsigned int eoffset : SIZET_BITS/4;
+  unsigned int boffset : SIZET_BITS/4;
+  unsigned int ioffset : SIZET_BITS/4;
+#else /* OBJC_SPARSE2 */
+#ifdef __sparc__
+  unsigned long boffset : (SIZET_BITS - 2) - BUCKET_BITS;
+  unsigned int eoffset : BUCKET_BITS;
+  unsigned int unused  : 2;
+#else
+  unsigned int boffset : SIZET_BITS/2;
+  unsigned int eoffset : SIZET_BITS/2;
+#endif
+#endif /* OBJC_SPARSE2 */
+};
+
+union sofftype {
+  struct soffset off;
+  sidx idx;
+};
+
+#endif /* not PRECOMPUTE_SELECTORS */
+
+union sversion {
+  int	version;
+  void *next_free;
+};
+
+struct sbucket {
+  void* elems[BUCKET_SIZE];	/* elements stored in array */
+  union sversion	version;		/* used for copy-on-write */
+};
+
+#ifdef OBJC_SPARSE3
+
+struct sindex {
+  struct sbucket* buckets[INDEX_SIZE];
+  union sversion	version;		/* used for copy-on-write */
+};
+
+#endif /* OBJC_SPARSE3 */
+
+struct sarray {
+#ifdef OBJC_SPARSE3
+  struct sindex** indices;
+  struct sindex* empty_index;
+#else /* OBJC_SPARSE2 */
+  struct sbucket** buckets;
+#endif  /* OBJC_SPARSE2 */
+  struct sbucket* empty_bucket;
+  union sversion	version;		/* used for copy-on-write */
+  short ref_count;
+  struct sarray* is_copy_of;
+  size_t capacity;
+};
+
+struct sarray* sarray_new(int, void* default_element);
+void sarray_free(struct sarray*);
+struct sarray* sarray_lazy_copy(struct sarray*);
+void sarray_realloc(struct sarray*, int new_size);
+void sarray_at_put(struct sarray*, sidx indx, void* elem);
+void sarray_at_put_safe(struct sarray*, sidx indx, void* elem);
+
+struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
+void sarray_remove_garbage(void);
+
+
+#ifdef PRECOMPUTE_SELECTORS
+/* Transform soffset values to ints and vica verca */
+static inline unsigned int
+soffset_decode(sidx indx)
+{
+  union sofftype x;
+  x.idx = indx;
+#ifdef OBJC_SPARSE3
+  return x.off.eoffset
+    + (x.off.boffset*BUCKET_SIZE)
+      + (x.off.ioffset*INDEX_CAPACITY);
+#else /* OBJC_SPARSE2 */
+  return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
+#endif /* OBJC_SPARSE2 */
+}
+
+static inline sidx
+soffset_encode(size_t offset)
+{
+  union sofftype x;
+  x.off.eoffset = offset%BUCKET_SIZE;
+#ifdef OBJC_SPARSE3
+  x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
+  x.off.ioffset = offset/INDEX_CAPACITY;
+#else /* OBJC_SPARSE2 */
+  x.off.boffset = offset/BUCKET_SIZE;
+#endif
+  return (sidx)x.idx;
+}
+
+#else /* not PRECOMPUTE_SELECTORS */
+
+static inline size_t
+soffset_decode(sidx indx)
+{
+  return indx;
+}
+
+static inline sidx
+soffset_encode(size_t offset)
+{
+  return offset;
+}
+#endif /* not PRECOMPUTE_SELECTORS */
+
+/* Get element from the Sparse array `array' at offset `indx' */
+
+static inline void* sarray_get(struct sarray* array, sidx indx)
+{
+#ifdef PRECOMPUTE_SELECTORS
+  union sofftype x;
+  x.idx = indx;
+#ifdef OBJC_SPARSE3
+  return 
+    array->
+      indices[x.off.ioffset]->
+	buckets[x.off.boffset]->
+	  elems[x.off.eoffset];
+#else /* OBJC_SPARSE2 */
+  return array->buckets[x.off.boffset]->elems[x.off.eoffset];
+#endif /* OBJC_SPARSE2 */
+#else /* not PRECOMPUTE_SELECTORS */
+#ifdef OBJC_SPARSE3
+  return array->
+    indices[indx/INDEX_CAPACITY]->
+      buckets[(indx/BUCKET_SIZE)%INDEX_SIZE]->
+	elems[indx%BUCKET_SIZE];
+#else /* OBJC_SPARSE2 */
+  return array->buckets[indx/BUCKET_SIZE]->elems[indx%BUCKET_SIZE];
+#endif /* not OBJC_SPARSE3 */
+#endif /* not PRECOMPUTE_SELECTORS */
+}
+
+static inline void* sarray_get_safe(struct sarray* array, sidx indx)
+{
+  if(soffset_decode(indx) < array->capacity)
+    return sarray_get(array, indx);
+  else
+    return (array->empty_bucket->elems[0]);
+}
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* __sarray_INCLUDE_GNU */
diff --git a/libobjc/objc/deprecated/sarray.h b/libobjc/objc/deprecated/sarray.h
new file mode 100644
index 00000000000..aa2f3350a45
--- /dev/null
+++ b/libobjc/objc/deprecated/sarray.h
@@ -0,0 +1,240 @@
+/* Sparse Arrays for Objective C dispatch tables
+   Copyright (C) 1993, 1995, 1996, 2004, 2009 Free Software Foundation, Inc.
+   Contributed by Kresten Krab Thorup.
+
+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 3, 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.
+
+Under Section 7 of GPL version 3, you are granted additional
+permissions described in the GCC Runtime Library Exception, version
+3.1, as published by the Free Software Foundation.
+
+You should have received a copy of the GNU General Public License and
+a copy of the GCC Runtime Library Exception along with this program;
+see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+<http://www.gnu.org/licenses/>.  */
+
+
+#ifndef __sarray_INCLUDE_GNU
+#define __sarray_INCLUDE_GNU
+
+#define OBJC_SPARSE2		/* 2-level sparse array */
+/* #define OBJC_SPARSE3 */      /* 3-level sparse array */
+
+#ifdef OBJC_SPARSE2
+extern const char* __objc_sparse2_id;
+#endif
+
+#ifdef OBJC_SPARSE3
+extern const char* __objc_sparse3_id;
+#endif
+
+#include <stddef.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+extern int nbuckets;		/* for stats */
+extern int nindices;
+extern int narrays;
+extern int idxsize;
+
+/* An unsigned integer of same size as a pointer */
+#define SIZET_BITS (sizeof(size_t)*8)
+
+#if defined(__sparc__) || defined(OBJC_SPARSE2)
+#define PRECOMPUTE_SELECTORS
+#endif
+
+#ifdef OBJC_SPARSE3
+
+/* Buckets are 8 words each */
+#define BUCKET_BITS 3
+#define BUCKET_SIZE (1<<BUCKET_BITS)
+#define BUCKET_MASK (BUCKET_SIZE-1)
+
+/* Indices are 16 words each */
+#define INDEX_BITS 4
+#define INDEX_SIZE (1<<INDEX_BITS)
+#define INDEX_MASK (INDEX_SIZE-1)
+
+#define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
+
+#else /* OBJC_SPARSE2 */
+
+/* Buckets are 32 words each */
+#define BUCKET_BITS 5
+#define BUCKET_SIZE (1<<BUCKET_BITS)
+#define BUCKET_MASK (BUCKET_SIZE-1)
+
+#endif /* OBJC_SPARSE2 */
+
+typedef size_t sidx;
+
+#ifdef PRECOMPUTE_SELECTORS
+
+struct soffset {
+#ifdef OBJC_SPARSE3
+  unsigned int unused : SIZET_BITS/4;
+  unsigned int eoffset : SIZET_BITS/4;
+  unsigned int boffset : SIZET_BITS/4;
+  unsigned int ioffset : SIZET_BITS/4;
+#else /* OBJC_SPARSE2 */
+#ifdef __sparc__
+  unsigned long boffset : (SIZET_BITS - 2) - BUCKET_BITS;
+  unsigned int eoffset : BUCKET_BITS;
+  unsigned int unused  : 2;
+#else
+  unsigned int boffset : SIZET_BITS/2;
+  unsigned int eoffset : SIZET_BITS/2;
+#endif
+#endif /* OBJC_SPARSE2 */
+};
+
+union sofftype {
+  struct soffset off;
+  sidx idx;
+};
+
+#endif /* not PRECOMPUTE_SELECTORS */
+
+union sversion {
+  int	version;
+  void *next_free;
+};
+
+struct sbucket {
+  void* elems[BUCKET_SIZE];	/* elements stored in array */
+  union sversion	version;		/* used for copy-on-write */
+};
+
+#ifdef OBJC_SPARSE3
+
+struct sindex {
+  struct sbucket* buckets[INDEX_SIZE];
+  union sversion	version;		/* used for copy-on-write */
+};
+
+#endif /* OBJC_SPARSE3 */
+
+struct sarray {
+#ifdef OBJC_SPARSE3
+  struct sindex** indices;
+  struct sindex* empty_index;
+#else /* OBJC_SPARSE2 */
+  struct sbucket** buckets;
+#endif  /* OBJC_SPARSE2 */
+  struct sbucket* empty_bucket;
+  union sversion	version;		/* used for copy-on-write */
+  short ref_count;
+  struct sarray* is_copy_of;
+  size_t capacity;
+};
+
+struct sarray* sarray_new(int, void* default_element);
+void sarray_free(struct sarray*);
+struct sarray* sarray_lazy_copy(struct sarray*);
+void sarray_realloc(struct sarray*, int new_size);
+void sarray_at_put(struct sarray*, sidx indx, void* elem);
+void sarray_at_put_safe(struct sarray*, sidx indx, void* elem);
+
+struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
+void sarray_remove_garbage(void);
+
+
+#ifdef PRECOMPUTE_SELECTORS
+/* Transform soffset values to ints and vica verca */
+static inline unsigned int
+soffset_decode(sidx indx)
+{
+  union sofftype x;
+  x.idx = indx;
+#ifdef OBJC_SPARSE3
+  return x.off.eoffset
+    + (x.off.boffset*BUCKET_SIZE)
+      + (x.off.ioffset*INDEX_CAPACITY);
+#else /* OBJC_SPARSE2 */
+  return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
+#endif /* OBJC_SPARSE2 */
+}
+
+static inline sidx
+soffset_encode(size_t offset)
+{
+  union sofftype x;
+  x.off.eoffset = offset%BUCKET_SIZE;
+#ifdef OBJC_SPARSE3
+  x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
+  x.off.ioffset = offset/INDEX_CAPACITY;
+#else /* OBJC_SPARSE2 */
+  x.off.boffset = offset/BUCKET_SIZE;
+#endif
+  return (sidx)x.idx;
+}
+
+#else /* not PRECOMPUTE_SELECTORS */
+
+static inline size_t
+soffset_decode(sidx indx)
+{
+  return indx;
+}
+
+static inline sidx
+soffset_encode(size_t offset)
+{
+  return offset;
+}
+#endif /* not PRECOMPUTE_SELECTORS */
+
+/* Get element from the Sparse array `array' at offset `indx' */
+
+static inline void* sarray_get(struct sarray* array, sidx indx)
+{
+#ifdef PRECOMPUTE_SELECTORS
+  union sofftype x;
+  x.idx = indx;
+#ifdef OBJC_SPARSE3
+  return 
+    array->
+      indices[x.off.ioffset]->
+	buckets[x.off.boffset]->
+	  elems[x.off.eoffset];
+#else /* OBJC_SPARSE2 */
+  return array->buckets[x.off.boffset]->elems[x.off.eoffset];
+#endif /* OBJC_SPARSE2 */
+#else /* not PRECOMPUTE_SELECTORS */
+#ifdef OBJC_SPARSE3
+  return array->
+    indices[indx/INDEX_CAPACITY]->
+      buckets[(indx/BUCKET_SIZE)%INDEX_SIZE]->
+	elems[indx%BUCKET_SIZE];
+#else /* OBJC_SPARSE2 */
+  return array->buckets[indx/BUCKET_SIZE]->elems[indx%BUCKET_SIZE];
+#endif /* not OBJC_SPARSE3 */
+#endif /* not PRECOMPUTE_SELECTORS */
+}
+
+static inline void* sarray_get_safe(struct sarray* array, sidx indx)
+{
+  if(soffset_decode(indx) < array->capacity)
+    return sarray_get(array, indx);
+  else
+    return (array->empty_bucket->elems[0]);
+}
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* __sarray_INCLUDE_GNU */
diff --git a/libobjc/objc/sarray.h b/libobjc/objc/sarray.h
index 32a7ef2aa43..ff51e47f918 100644
--- a/libobjc/objc/sarray.h
+++ b/libobjc/objc/sarray.h
@@ -1,243 +1,2 @@
-/* Sparse Arrays for Objective C dispatch tables
-   Copyright (C) 1993, 1995, 1996, 2004, 2009 Free Software Foundation, Inc.
-   Contributed by Kresten Krab Thorup.
+#include "deprecated/sarray.h"
 
-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 3, 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.
-
-Under Section 7 of GPL version 3, you are granted additional
-permissions described in the GCC Runtime Library Exception, version
-3.1, as published by the Free Software Foundation.
-
-You should have received a copy of the GNU General Public License and
-a copy of the GCC Runtime Library Exception along with this program;
-see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
-<http://www.gnu.org/licenses/>.  */
-
-
-#ifndef __sarray_INCLUDE_GNU
-#define __sarray_INCLUDE_GNU
-
-#include "thr.h"
-
-#define OBJC_SPARSE2		/* 2-level sparse array */
-/* #define OBJC_SPARSE3 */      /* 3-level sparse array */
-
-#ifdef OBJC_SPARSE2
-extern const char* __objc_sparse2_id;
-#endif
-
-#ifdef OBJC_SPARSE3
-extern const char* __objc_sparse3_id;
-#endif
-
-#include <stddef.h>
-#include <assert.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif /* __cplusplus */
-
-extern int nbuckets;		/* for stats */
-extern int nindices;
-extern int narrays;
-extern int idxsize;
-
-/* An unsigned integer of same size as a pointer */
-#define SIZET_BITS (sizeof(size_t)*8)
-
-#if defined(__sparc__) || defined(OBJC_SPARSE2)
-#define PRECOMPUTE_SELECTORS
-#endif
-
-#ifdef OBJC_SPARSE3
-
-/* Buckets are 8 words each */
-#define BUCKET_BITS 3
-#define BUCKET_SIZE (1<<BUCKET_BITS)
-#define BUCKET_MASK (BUCKET_SIZE-1)
-
-/* Indices are 16 words each */
-#define INDEX_BITS 4
-#define INDEX_SIZE (1<<INDEX_BITS)
-#define INDEX_MASK (INDEX_SIZE-1)
-
-#define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
-
-#else /* OBJC_SPARSE2 */
-
-/* Buckets are 32 words each */
-#define BUCKET_BITS 5
-#define BUCKET_SIZE (1<<BUCKET_BITS)
-#define BUCKET_MASK (BUCKET_SIZE-1)
-
-#endif /* OBJC_SPARSE2 */
-
-typedef size_t sidx;
-
-#ifdef PRECOMPUTE_SELECTORS
-
-struct soffset {
-#ifdef OBJC_SPARSE3
-  unsigned int unused : SIZET_BITS/4;
-  unsigned int eoffset : SIZET_BITS/4;
-  unsigned int boffset : SIZET_BITS/4;
-  unsigned int ioffset : SIZET_BITS/4;
-#else /* OBJC_SPARSE2 */
-#ifdef __sparc__
-  unsigned long boffset : (SIZET_BITS - 2) - BUCKET_BITS;
-  unsigned int eoffset : BUCKET_BITS;
-  unsigned int unused  : 2;
-#else
-  unsigned int boffset : SIZET_BITS/2;
-  unsigned int eoffset : SIZET_BITS/2;
-#endif
-#endif /* OBJC_SPARSE2 */
-};
-
-union sofftype {
-  struct soffset off;
-  sidx idx;
-};
-
-#endif /* not PRECOMPUTE_SELECTORS */
-
-union sversion {
-  int	version;
-  void *next_free;
-};
-
-struct sbucket {
-  void* elems[BUCKET_SIZE];	/* elements stored in array */
-  union sversion	version;		/* used for copy-on-write */
-};
-
-#ifdef OBJC_SPARSE3
-
-struct sindex {
-  struct sbucket* buckets[INDEX_SIZE];
-  union sversion	version;		/* used for copy-on-write */
-};
-
-#endif /* OBJC_SPARSE3 */
-
-struct sarray {
-#ifdef OBJC_SPARSE3
-  struct sindex** indices;
-  struct sindex* empty_index;
-#else /* OBJC_SPARSE2 */
-  struct sbucket** buckets;
-#endif  /* OBJC_SPARSE2 */
-  struct sbucket* empty_bucket;
-  union sversion	version;		/* used for copy-on-write */
-  short ref_count;
-  struct sarray* is_copy_of;
-  size_t capacity;
-};
-
-struct sarray* sarray_new(int, void* default_element);
-void sarray_free(struct sarray*);
-struct sarray* sarray_lazy_copy(struct sarray*);
-void sarray_realloc(struct sarray*, int new_size);
-void sarray_at_put(struct sarray*, sidx indx, void* elem);
-void sarray_at_put_safe(struct sarray*, sidx indx, void* elem);
-
-struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
-void sarray_remove_garbage(void);
-
-
-#ifdef PRECOMPUTE_SELECTORS
-/* Transform soffset values to ints and vica verca */
-static inline unsigned int
-soffset_decode(sidx indx)
-{
-  union sofftype x;
-  x.idx = indx;
-#ifdef OBJC_SPARSE3
-  return x.off.eoffset
-    + (x.off.boffset*BUCKET_SIZE)
-      + (x.off.ioffset*INDEX_CAPACITY);
-#else /* OBJC_SPARSE2 */
-  return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
-#endif /* OBJC_SPARSE2 */
-}
-
-static inline sidx
-soffset_encode(size_t offset)
-{
-  union sofftype x;
-  x.off.eoffset = offset%BUCKET_SIZE;
-#ifdef OBJC_SPARSE3
-  x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
-  x.off.ioffset = offset/INDEX_CAPACITY;
-#else /* OBJC_SPARSE2 */
-  x.off.boffset = offset/BUCKET_SIZE;
-#endif
-  return (sidx)x.idx;
-}
-
-#else /* not PRECOMPUTE_SELECTORS */
-
-static inline size_t
-soffset_decode(sidx indx)
-{
-  return indx;
-}
-
-static inline sidx
-soffset_encode(size_t offset)
-{
-  return offset;
-}
-#endif /* not PRECOMPUTE_SELECTORS */
-
-/* Get element from the Sparse array `array' at offset `indx' */
-
-static inline void* sarray_get(struct sarray* array, sidx indx)
-{
-#ifdef PRECOMPUTE_SELECTORS
-  union sofftype x;
-  x.idx = indx;
-#ifdef OBJC_SPARSE3
-  return 
-    array->
-      indices[x.off.ioffset]->
-	buckets[x.off.boffset]->
-	  elems[x.off.eoffset];
-#else /* OBJC_SPARSE2 */
-  return array->buckets[x.off.boffset]->elems[x.off.eoffset];
-#endif /* OBJC_SPARSE2 */
-#else /* not PRECOMPUTE_SELECTORS */
-#ifdef OBJC_SPARSE3
-  return array->
-    indices[indx/INDEX_CAPACITY]->
-      buckets[(indx/BUCKET_SIZE)%INDEX_SIZE]->
-	elems[indx%BUCKET_SIZE];
-#else /* OBJC_SPARSE2 */
-  return array->buckets[indx/BUCKET_SIZE]->elems[indx%BUCKET_SIZE];
-#endif /* not OBJC_SPARSE3 */
-#endif /* not PRECOMPUTE_SELECTORS */
-}
-
-static inline void* sarray_get_safe(struct sarray* array, sidx indx)
-{
-  if(soffset_decode(indx) < array->capacity)
-    return sarray_get(array, indx);
-  else
-    return (array->empty_bucket->elems[0]);
-}
-
-#ifdef __cplusplus
-}
-#endif /* __cplusplus */
-
-#endif /* __sarray_INCLUDE_GNU */
diff --git a/libobjc/sarray.c b/libobjc/sarray.c
index e919b7a4481..8d5303701e0 100644
--- a/libobjc/sarray.c
+++ b/libobjc/sarray.c
@@ -23,14 +23,14 @@ see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 <http://www.gnu.org/licenses/>.  */
 
 #include "objc-private/common.h"
-#include "objc/sarray.h"
+#include "objc-private/sarray.h"
 #include "objc/objc.h"
 #include "objc/objc-api.h"
 #include "objc/thr.h"
 #include "objc-private/runtime.h"
 #include <stdio.h>
 #include <string.h> /* For memset */
-#include "assert.h"
+#include <assert.h> /* For assert */
 
 int nbuckets = 0;					/* !T:MUTEX */
 int nindices = 0;					/* !T:MUTEX */
diff --git a/libobjc/selector.c b/libobjc/selector.c
index 2eaabfeb343..10b7ab63dad 100644
--- a/libobjc/selector.c
+++ b/libobjc/selector.c
@@ -29,7 +29,7 @@ see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 #include "objc-private/hash.h"
 #include "objc-private/objc-list.h" 
 #include "objc-private/runtime.h"
-#include "objc/sarray.h"
+#include "objc-private/sarray.h"
 #include "objc/encoding.h"
 
 /* Initial selector hash table size. Value doesn't matter much */
diff --git a/libobjc/sendmsg.c b/libobjc/sendmsg.c
index 15cdae65768..5e466c6cce0 100644
--- a/libobjc/sendmsg.c
+++ b/libobjc/sendmsg.c
@@ -37,9 +37,10 @@ see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 #include "objc/objc-api.h"
 #include "objc/thr.h"
 #include "objc-private/runtime.h"
-#include "objc/sarray.h"
+#include "objc-private/sarray.h"
 #include "objc/encoding.h"
 #include "runtime-info.h"
+#include <assert.h> /* For assert */
 #include <string.h> /* For strlen */
 
 /* This is how we hack STRUCT_VALUE to be 1 or 0.   */
-- 
2.11.0