Merge tree-ssa-20020619-branch into mainline.

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

1 files changed, 427 insertions, 0 deletions

diff --git a/libbanshee/engine/hash.c b/libbanshee/engine/hash.c
new file mode 100644
index 00000000000..bf315cee4a5
--- /dev/null
+++ b/libbanshee/engine/hash.c
@@ -0,0 +1,427 @@
+/*
+ * Copyright (c) 2000-2001
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ */
+
+#include <string.h>
+#include "hash.h"
+#include "util.h"
+
+struct bucket
+{
+  hash_key key;
+  hash_data data;
+  struct bucket *next;
+};
+
+#define scan_bucket(b, var) for (var = b; var; var = var->next)
+
+struct Hash_table
+{
+  region r;          /* Region for this table */
+  hash_fn hash;      /* Function for hashing keys */
+  keyeq_fn cmp;      /* Function for comparing keys */
+
+  int size;          /* Number of buckets */
+  int elts;          /* Number of elements */
+  bool internal_rgn; /* TRUE if the ht uses an internal region */
+  bucket *table;     /* Array of (size) buckets */
+};
+
+static void rehash(hash_table ht) deletes; 
+
+/* Make a new hash table, with size buckets initially.  The actual
+   table is allocated in a local region, which is discarded on rehashing. */
+hash_table make_hash_table(region r, int size, hash_fn hash,
+			   keyeq_fn cmp, bool internal_rgn)
+{
+  hash_table result;
+
+  assert(size > 0);
+  result = ralloc(r, struct Hash_table);
+  
+  if (internal_rgn)
+    result->r = newregion();
+  else
+    result->r = r;
+
+  result->internal_rgn = internal_rgn;
+  result->hash = hash;
+  result->cmp = cmp;
+  result->size = size;
+  result->elts = 0;
+  result->table = rarrayalloc(result->r, size, bucket);
+
+  return result;
+}
+
+/* Hash a string */
+static int string_hash(char *str)
+{
+  char *c;
+  int h;
+
+  c = str;
+  h = 0;
+  if (!c)
+    return 0;
+  while (*c)
+    h = 33*h + 720 + *c++; /* SML/NJ's string hash function */
+  return h;
+}
+
+/* Return TRUE iff s1 == s2 */
+static bool string_eq(char *s1, char *s2)
+{
+  return !strcmp(s1, s2);
+}
+
+/* Make a hash table for strings. */
+hash_table make_string_hash_table(region rhash, int size, bool internal_rgn)
+{
+  return make_hash_table(rhash, size, (hash_fn) string_hash,
+			 (keyeq_fn) string_eq,internal_rgn);
+}
+
+/* Zero out ht.  Doesn't reclaim bucket space. */
+void hash_table_reset(hash_table ht) deletes
+{
+  int i;
+  
+  if (ht->internal_rgn)
+    {
+      deleteregion(ht->r);
+      ht->r = newregion();  
+    }
+
+  ht->elts = 0;
+  for (i = 0; i < ht->size; i++)
+    ht->table[i] = NULL;
+}
+
+void hash_table_delete(hash_table ht) deletes
+{
+  if (ht->internal_rgn)
+    deleteregion(ht->r);
+}
+
+
+/* Return the number of entries in ht */
+int hash_table_size(hash_table ht)
+{
+  return ht->elts;
+}
+
+/* Return the bucket corresponding to k in ht */
+static inline bucket *find_bucket(hash_table ht, hash_key k)
+{
+  int hash;
+
+  hash = ht->hash(k);
+  if (hash < 0)
+    hash = -1*hash;
+  return &ht->table[hash % ht->size];
+}
+
+/* Lookup k in ht.  Returns corresponding data in *d, and function
+   result is TRUE if the k was in ht, false otherwise. */
+bool hash_table_lookup(hash_table ht, hash_key k, hash_data *d)
+{
+  bucket cur;
+
+  cur = *find_bucket(ht, k);
+  while (cur)
+    {
+      if (ht->cmp(k, cur->key))
+	{
+	  if (d)
+	    *d = cur->data;
+	  return TRUE;
+	}
+      cur = cur->next;
+    }
+  return FALSE;
+}
+
+
+/* Add k:d to ht.  If k was already in ht, replace old entry by k:d.
+   Rehash if necessary.  Returns TRUE if k was not already in ht. */
+bool hash_table_insert(hash_table ht, hash_key k, hash_data d) deletes
+{
+  bucket *cur;
+
+  if (ht->elts > ht->size*15)
+    rehash(ht);
+  cur = find_bucket(ht, k);
+  while (*cur)
+    {
+      if (ht->cmp(k, (*cur)->key))
+	{
+	  (*cur)->data = d;
+	  return FALSE; /* Replace */
+	}
+      cur = &(*cur)->next;
+    }
+  *cur = ralloc(ht->r, struct bucket);
+  (*cur)->key = k;
+  (*cur)->data = d;
+  (*cur)->next = NULL;
+  ht->elts++;
+  return TRUE; /* New key */
+}
+
+/* Remove mapping for k in ht.  Returns TRUE if k was in ht. */
+bool hash_table_remove(hash_table ht, hash_key k) 
+{
+  bucket *cur;
+  bucket *prev = NULL;
+
+  cur = find_bucket(ht, k);
+  while (*cur)
+    {
+      if (ht->cmp(k, (*cur)->key))
+	{
+	  if (!*prev)
+	    (*prev)->next = (*cur)->next;
+	  else
+	    *cur = NULL;
+	  ht->elts--;
+	  return TRUE;
+	}
+      prev = cur;
+      cur = &(*cur)->next;
+    }
+  return FALSE;
+}
+
+/* Return a copy of ht */
+hash_table hash_table_copy(region r, hash_table ht)
+{
+  int i;
+  hash_table result;
+  bucket cur, newbucket, *prev;
+
+  result = make_hash_table(r, ht->size, ht->hash, ht->cmp,ht->internal_rgn);
+  result->elts = ht->elts;
+  
+  for (i = 0; i < ht->size; i++)
+    {
+      prev = &result->table[i];
+      scan_bucket(ht->table[i], cur)
+	{
+	  newbucket = ralloc(result->r, struct bucket);
+	  newbucket->key = cur->key;
+	  newbucket->data = cur->data;
+	  newbucket->next = NULL;
+	  assert(!*prev);
+	  *prev = newbucket;
+	  prev = &newbucket->next;
+	}
+    }
+  return result;
+  /*
+  hash_table result;
+  hash_table_scanner hts;
+  hash_key k;
+  hash_data d;
+  
+  result = make_hash_table(r, ht->size, ht->hash, ht->cmp);
+  hash_table_scan(ht, &hts);
+  while (hash_table_next(&hts, &k, &d))
+    insist(hash_table_insert(result, k, d));
+  
+  return result;
+  */
+}
+
+/* Increase size of ht (double it) and reinsert all the elements */
+static void rehash(hash_table ht) deletes
+{
+  int old_table_size, i;
+  bucket *old_table, cur;
+  region old_region;
+
+#ifdef DEBUG
+  printf("Rehash table size=%d, elts=%d\n", ht->size, ht->elts);
+#endif
+
+  old_table_size = ht->size;
+  old_table = ht->table;
+  old_region = ht->r;
+
+  if (ht->internal_rgn)
+    ht->r = newregion();
+
+  ht->size = ht->size*2;
+  ht->elts = 0;
+  ht->table = rarrayalloc(ht->r, ht->size, bucket);
+
+  for (i = 0; i < old_table_size; i++)
+    scan_bucket(old_table[i], cur)
+      insist(hash_table_insert(ht, cur->key, cur->data));
+
+  if (ht->internal_rgn)
+    deleteregion(old_region);
+}
+
+/* Begin scanning ht */
+void hash_table_scan(hash_table ht, hash_table_scanner *hts)
+{
+  hts->ht = ht;
+  hts->i = 0;
+  hts->cur = hts->ht->table[0];
+}
+
+/* Get next elt in table, storing the elt in *k and *d if k and d are
+   non-NULL, respectively.  Returns TRUE if there is a next elt, FALSE
+   otherwise. */
+bool hash_table_next(hash_table_scanner *hts, hash_key *k, hash_data *d)
+{
+  while (hts->cur == NULL)
+    {
+      hts->i++;
+      if (hts->i < hts->ht->size)
+	hts->cur = hts->ht->table[hts->i];
+      else
+	break;
+    }
+
+  if (hts->i == hts->ht->size)
+    {
+      return FALSE;
+    }
+  else
+    {
+      if (k)
+	*k = hts->cur->key;
+      if (d)
+	*d = hts->cur->data;
+      hts->cur = hts->cur->next;
+    }
+  return TRUE;
+}
+
+/* Apply f to all elements of ht, in some arbitrary order */
+void hash_table_apply(hash_table ht, hash_apply_fn f, void *arg)
+{
+  int i;
+  bucket cur;
+
+  for (i = 0; i < ht->size; i++)
+    scan_bucket(ht->table[i], cur)
+      f(cur->key, cur->data, arg);
+}
+
+/* Map f to all elements on ht, creating a new hash table */
+hash_table hash_table_map(hash_table ht, hash_map_fn f, void *arg)
+{
+  int i;
+  hash_table result;
+  bucket cur, newbucket, *prev;
+
+  result = make_hash_table(ht->r, ht->size, ht->hash, ht->cmp,ht->internal_rgn);
+  result->elts = ht->elts;
+  
+  for (i = 0; i < ht->size; i++)
+    {
+      prev = &result->table[i];
+      scan_bucket(ht->table[i], cur)
+	{
+	  newbucket = ralloc(ht->r, struct bucket);
+	  newbucket->key = cur->key;
+	  newbucket->data = f(cur->key, cur->data, arg);
+	  newbucket->next = NULL;
+	  assert(!*prev);
+	  *prev = newbucket;
+	  prev = &newbucket->next;
+	}
+    }
+  return result;
+  /*
+  hash_table result;
+  int i;
+  bucket cur;
+
+  result = make_hash_table(ht->r, ht->size, ht->hash, ht->cmp);
+  for (i = 0; i < ht->size; i++)
+    scan_bucket(ht->table[i], cur)
+      insist(hash_table_insert(result, cur->key, f(cur->key, cur->data, arg)));
+  return result;
+  */
+}
+
+static keycmp_fn cur_cmp = NULL;
+
+static int entry_cmp(const void *a, const void *b)
+{
+  struct sorted_entry *ae = (struct sorted_entry *) a;
+  struct sorted_entry *be = (struct sorted_entry *) b;
+  return cur_cmp(ae->k, be->k);
+}
+
+/* Begin scanning ht in sorted order according to f */
+void hash_table_scan_sorted(hash_table ht, keycmp_fn f,
+			    hash_table_scanner_sorted *htss)
+{
+  hash_table_scanner hts;
+  int i;
+
+  htss->r = newregion();
+  htss->size = hash_table_size(ht);
+  htss->entries = rarrayalloc(htss->r, htss->size, struct sorted_entry);
+  htss->i = 0;
+
+  hash_table_scan(ht, &hts);
+  i = 0;
+  while (hash_table_next(&hts, &htss->entries[i].k,
+			 &htss->entries[i].d))
+    i++;
+  assert(i == htss->size);
+  cur_cmp = f;
+  qsort(htss->entries, htss->size, sizeof(struct sorted_entry), entry_cmp);
+  cur_cmp = NULL;
+}
+
+/* Just like hash_table_next, but scans in sorted order */
+bool hash_table_next_sorted(hash_table_scanner_sorted *htss, hash_key *k,
+			    hash_data *d) deletes
+{
+  if (htss->i < htss->size)
+    {
+      *k = htss->entries[htss->i].k;
+      *d = htss->entries[htss->i].d;
+      htss->i++;
+      return TRUE;
+    }
+  else
+    {
+      deleteregion(htss->r);
+      htss->r = NULL;
+      return FALSE;
+    }
+}