In libobjc/:

        * objc/hash.h: Moved into objc/deprecated/hash.h; objc/hash.h
        replaced with a placeholder including the file from the
        deprecated/ directory.
        * objc/objc-api.h: Updated includes.
        * objc/typedstream.h: Updated includes.
        * objc-private/hash.h: New file (private copy of hash.h).
        * objc/objc-list.h: Moved into objc/deprecated/objc-list.h;
        objc/objc-list.h replaced with a placeholder including the file
        from the deprecated/ directory.
        * objc-private/objc-list.h: New file (private copy of objc-list.h).
        * init.c: Include objc-private/hash.h and objc-private/objc-list.h
        instead of objc/hash.h and objc/objc-list.h.
        * selector.c: Same change.
        * class.c: Added include <string.h>, which used to be implicitly included
        when hash.h was included.
        * exception.c: Same change.
        * objects.c: Same change.
        * sarray.c: Same change.
        * sendmsg.c: Same change.
        * Makefile.in (OBJC_DEPRECATED_H): Added hash.h and objc-list.h.
        (OBJC_H): Removed hash.h and objc-list.h


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@164373 138bc75d-0d04-0410-961f-82ee72b054a4

2 files changed, 369 insertions, 0 deletions

diff --git a/libobjc/objc-private/hash.h b/libobjc/objc-private/hash.h
new file mode 100644
index 00000000000..7c57a4d2589
--- /dev/null
+++ b/libobjc/objc-private/hash.h
@@ -0,0 +1,214 @@
+/* Hash tables for Objective C method dispatch.
+   Copyright (C) 1993, 1995, 1996, 2004, 2009 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 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/>.  */
+
+/* You need to include this file after including objc.h  */
+
+#ifndef __hash_INCLUDE_GNU
+#define __hash_INCLUDE_GNU
+
+#include <stddef.h>
+#include <string.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+/*
+ * This data structure is used to hold items
+ *  stored in a hash table.  Each node holds 
+ *  a key/value pair.
+ *
+ * Items in the cache are really of type void *.
+ */
+typedef struct cache_node
+{
+  struct cache_node *next;	/* Pointer to next entry on the list.
+				   NULL indicates end of list. */
+  const void *key;		/* Key used to locate the value.  Used
+				   to locate value when more than one
+				   key computes the same hash
+				   value. */
+  void *value;			/* Value stored for the key. */
+} *node_ptr;
+
+
+/*
+ * This data type is the function that computes a hash code given a key.
+ * Therefore, the key can be a pointer to anything and the function specific
+ * to the key type. 
+ *
+ * Unfortunately there is a mutual data structure reference problem with this
+ * typedef.  Therefore, to remove compiler warnings the functions passed to
+ * objc_hash_new will have to be casted to this type. 
+ */
+typedef unsigned int (*hash_func_type) (void *, const void *);
+
+/*
+ * This data type is the function that compares two hash keys and returns an
+ * integer greater than, equal to, or less than 0, according as the first
+ * parameter is lexicographically greater than, equal to, or less than the
+ * second. 
+ */
+
+typedef int (*compare_func_type) (const void *, const void *);
+
+
+/*
+ * This data structure is the cache.
+ *
+ * It must be passed to all of the hashing routines
+ *   (except for new).
+ */
+typedef struct cache
+{
+  /* Variables used to implement the hash itself.  */
+  node_ptr *node_table; /* Pointer to an array of hash nodes.  */
+  /* Variables used to track the size of the hash table so to determine
+    when to resize it.  */
+  unsigned int size; /* Number of buckets allocated for the hash table
+			(number of array entries allocated for
+			"node_table").  Must be a power of two.  */
+  unsigned int used; /* Current number of entries in the hash table.  */
+  unsigned int mask; /* Precomputed mask.  */
+
+  /* Variables used to implement indexing through the hash table.  */
+
+  unsigned int last_bucket; /* Tracks which entry in the array where
+			       the last value was returned.  */
+  /* Function used to compute a hash code given a key. 
+     This function is specified when the hash table is created.  */
+  hash_func_type    hash_func;
+  /* Function used to compare two hash keys to see if they are equal.  */
+  compare_func_type compare_func;
+} *cache_ptr;
+
+
+/* Two important hash tables.  */
+extern cache_ptr module_hash_table, class_hash_table;
+
+/* Allocate and initialize a hash table.  */ 
+
+cache_ptr objc_hash_new (unsigned int size,
+			 hash_func_type hash_func,
+			 compare_func_type compare_func);
+                       
+/* Deallocate all of the hash nodes and the cache itself.  */
+
+void objc_hash_delete (cache_ptr cache);
+
+/* Add the key/value pair to the hash table.  If the
+   hash table reaches a level of fullness then it will be resized. 
+                                                   
+   assert if the key is already in the hash.  */
+
+void objc_hash_add (cache_ptr *cachep, const void *key, void *value);
+     
+/* Remove the key/value pair from the hash table.  
+   assert if the key isn't in the table.  */
+
+void objc_hash_remove (cache_ptr cache, const void *key);
+
+/* Used to index through the hash table.  Start with NULL
+   to get the first entry.
+                                                  
+   Successive calls pass the value returned previously.
+   ** Don't modify the hash during this operation *** 
+                                                  
+   Cache nodes are returned such that key or value can
+   be extracted.  */
+
+node_ptr objc_hash_next (cache_ptr cache, node_ptr node);
+
+/* Used to return a value from a hash table using a given key.  */
+
+void *objc_hash_value_for_key (cache_ptr cache, const void *key);
+
+/* Used to determine if the given key exists in the hash table */
+
+BOOL objc_hash_is_key_in_hash (cache_ptr cache, const void *key);
+
+/************************************************
+
+        Useful hashing functions.  
+        
+        Declared inline for your pleasure.
+        
+************************************************/
+
+/* Calculate a hash code by performing some 
+   manipulation of the key pointer.  (Use the lowest bits
+   except for those likely to be 0 due to alignment.)  */
+
+static inline unsigned int
+objc_hash_ptr (cache_ptr cache, const void *key)
+{
+  return ((size_t)key / sizeof (void *)) & cache->mask;
+}
+
+
+/* Calculate a hash code by iterating over a NULL 
+   terminate string.  */
+static inline unsigned int 
+objc_hash_string (cache_ptr cache, const void *key)
+{
+  unsigned int ret = 0;
+  unsigned int ctr = 0;
+  const char *ckey = (const char *) key;
+        
+  while (*ckey) {
+    ret ^= *ckey++ << ctr;
+    ctr = (ctr + 1) % sizeof (void *);
+  }
+
+  return ret & cache->mask;
+}
+
+
+/* Compare two pointers for equality.  */
+static inline int 
+objc_compare_ptrs (const void *k1, const void *k2)
+{
+  return (k1 == k2);
+}
+
+
+/* Compare two strings.  */
+static inline int 
+objc_compare_strings (const void *k1, const void *k2)
+{
+  if (k1 == k2)
+    return 1;
+  else if (k1 == 0 || k2 == 0)
+    return 0;
+  else
+    return ! strcmp ((const char *) k1, (const char *) k2);
+}
+
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+
+#endif /* not __hash_INCLUDE_GNU */
diff --git a/libobjc/objc-private/objc-list.h b/libobjc/objc-private/objc-list.h
new file mode 100644
index 00000000000..e542bfc0498
--- /dev/null
+++ b/libobjc/objc-private/objc-list.h
@@ -0,0 +1,155 @@
+/* Generic single linked list to keep various information 
+   Copyright (C) 1993, 1994, 1996, 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 __GNU_OBJC_LIST_H
+#define __GNU_OBJC_LIST_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+struct objc_list {
+  void *head;
+  struct objc_list *tail;
+};
+
+/* Return a cons cell produced from (head . tail) */
+
+static inline struct objc_list* 
+list_cons(void* head, struct objc_list* tail)
+{
+  struct objc_list* cell;
+
+  cell = (struct objc_list*)objc_malloc(sizeof(struct objc_list));
+  cell->head = head;
+  cell->tail = tail;
+  return cell;
+}
+
+/* Return the length of a list, list_length(NULL) returns zero */
+
+static inline int
+list_length(struct objc_list* list)
+{
+  int i = 0;
+  while(list)
+    {
+      i += 1;
+      list = list->tail;
+    }
+  return i;
+}
+
+/* Return the Nth element of LIST, where N count from zero.  If N 
+   larger than the list length, NULL is returned  */
+
+static inline void*
+list_nth(int indx, struct objc_list* list)
+{
+  while(indx-- != 0)
+    {
+      if(list->tail)
+	list = list->tail;
+      else
+	return 0;
+    }
+  return list->head;
+}
+
+/* Remove the element at the head by replacing it by its successor */
+
+static inline void
+list_remove_head(struct objc_list** list)
+{
+  if ((*list)->tail)
+    {
+      struct objc_list* tail = (*list)->tail; /* fetch next */
+      *(*list) = *tail;		/* copy next to list head */
+      objc_free(tail);			/* free next */
+    }
+  else				/* only one element in list */
+    {
+      objc_free(*list);
+      (*list) = 0;
+    }
+}
+
+
+/* Remove the element with `car' set to ELEMENT */
+
+static inline void
+list_remove_elem(struct objc_list** list, void* elem)
+{
+  while (*list) {
+    if ((*list)->head == elem)
+      list_remove_head(list);
+    list = &((*list)->tail);
+  }
+}
+
+/* Map FUNCTION over all elements in LIST */
+
+static inline void
+list_mapcar(struct objc_list* list, void(*function)(void*))
+{
+  while(list)
+    {
+      (*function)(list->head);
+      list = list->tail;
+    }
+}
+
+/* Return element that has ELEM as car */
+
+static inline struct objc_list**
+list_find(struct objc_list** list, void* elem)
+{
+  while(*list)
+    {
+    if ((*list)->head == elem)
+      return list;
+    list = &((*list)->tail);
+    }
+  return NULL;
+}
+
+/* Free list (backwards recursive) */
+
+static inline void
+list_free(struct objc_list* list)
+{
+  if(list)
+    {
+      list_free(list->tail);
+      objc_free(list);
+    }
+}
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* not __GNU_OBJC_LIST_H */