/* PSPP - computes sample statistics.
Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
- Written by Ben Pfaff <blp@gnu.org>.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
02110-1301, USA. */
#include <config.h>
+#include <stdbool.h>
#include "hash.h"
#include "message.h"
#include <assert.h>
#include "compiler.h"
#include "misc.h"
#include "str.h"
+#include "pool.h"
+
#include "gettext.h"
#define _(msgid) gettext (msgid)
size_t size; /* Number of entries (a power of 2). */
void **entries; /* Hash table proper. */
- void *aux; /* Auxiliary data for comparison functions. */
+ const void *aux; /* Auxiliary data for comparison functions. */
hsh_compare_func *compare;
hsh_hash_func *hash;
hsh_free_func *free;
so that most hsh_*() functions may no longer be called. */
bool hash_ordered;
#endif
+
+ struct pool *pool; /* The pool used for this hash table */
};
+struct hsh_table *
+hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
+ hsh_free_func *free, const void *aux)
+{
+ return hsh_create_pool (NULL, size, compare, hash, free, aux);
+}
+
+
+
/* Creates a hash table with at least M entries. COMPARE is a
function that compares two entries and returns 0 if they are
identical, nonzero otherwise; HASH returns a nonnegative hash value
for an entry; FREE destroys an entry. */
struct hsh_table *
-hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
- hsh_free_func *free, void *aux)
+hsh_create_pool (struct pool *pool, int size,
+ hsh_compare_func *compare, hsh_hash_func *hash,
+ hsh_free_func *free, const void *aux)
{
struct hsh_table *h;
int i;
assert (compare != NULL);
assert (hash != NULL);
- h = xmalloc (sizeof *h);
+ h = pool_malloc (pool, sizeof *h);
+ h->pool = pool;
h->used = 0;
if (size < 4)
size = 4;
h->size = next_power_of_2 (size);
- h->entries = xnmalloc (h->size, sizeof *h->entries);
+ h->entries = pool_nmalloc (pool, h->size, sizeof *h->entries);
for (i = 0; i < h->size; i++)
h->entries[i] = NULL;
h->aux = aux;
for (i = 0; i < h->size; i++)
if (h->entries[i] != NULL)
h->free (h->entries[i], h->aux);
- free (h->entries);
- free (h);
+ pool_free (h->pool, h->entries);
+ pool_free (h->pool, h);
}
}
-/* Locates an entry matching TARGET. Returns a pointer to the
- entry, or a null pointer on failure. */
+/* Locates an entry matching TARGET. Returns the index for the
+ entry, if found, or the index of an empty entry that indicates
+ where TARGET should go, otherwise. */
static inline unsigned
locate_matching_entry (struct hsh_table *h, const void *target)
{
}
}
+/* Returns the index of an empty entry that indicates
+ where TARGET should go, assuming that TARGET is not equal to
+ any item already in the hash table. */
+static inline unsigned
+locate_empty_entry (struct hsh_table *h, const void *target)
+{
+ unsigned i = h->hash (target, h->aux);
+
+ assert (h->hash_ordered);
+ for (;;)
+ {
+ i &= h->size - 1;
+ if (h->entries[i] == NULL)
+ return i;
+ i--;
+ }
+}
+
/* Changes the capacity of H to NEW_SIZE, which must be a
positive power of 2 at least as large as the number of
elements in H. */
end = begin + h->size;
h->size = new_size;
- h->entries = xnmalloc (h->size, sizeof *h->entries);
+ h->entries = pool_nmalloc (h->pool, h->size, sizeof *h->entries);
for (i = 0; i < h->size; i++)
h->entries[i] = NULL;
for (table_p = begin; table_p < end; table_p++)
{
void *entry = *table_p;
if (entry != NULL)
- h->entries[locate_matching_entry (h, entry)] = entry;
+ h->entries[locate_empty_entry (h, entry)] = entry;
}
- free (begin);
+ pool_free (h->pool, begin);
#ifndef NDEBUG
h->hash_ordered = true;
#endif
}
-/* A "algo_predicate_func" that returns nonzero if DATA points
+/* A "algo_predicate_func" that returns true if DATA points
to a non-null void. */
-static int
-not_null (const void *data_, void *aux UNUSED)
+static bool
+not_null (const void *data_, const void *aux UNUSED)
{
void *const *data = data_;
/* Dereferences void ** pointers and passes them to the hash
comparison function. */
static int
-comparison_helper (const void *a_, const void *b_, void *h_)
+comparison_helper (const void *a_, const void *b_, const void *h_)
{
void *const *a = a_;
void *const *b = b_;
- struct hsh_table *h = h_;
+ const struct hsh_table *h = h_;
assert(a);
assert(b);
void **copy;
assert (h != NULL);
- copy = xnmalloc ((h->used + 1), sizeof *copy);
+ copy = pool_nmalloc (h->pool, (h->used + 1), sizeof *copy);
copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL);
copy[h->used] = NULL;
return copy;
}
/* Deletes the entry in hash table H that matches TARGET.
- Returns nonzero if an entry was deleted.
+ Returns true if an entry was deleted.
Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
Because our load factor is at most 1/2, the average number of
moves that this algorithm makes should be at most 2 - ln 2 ~=
1.65. */
-int
+bool
hsh_delete (struct hsh_table *h, const void *target)
{
unsigned i = locate_matching_entry (h, target);
{
i = (i - 1) & (h->size - 1);
if (h->entries[i] == NULL)
- return 1;
+ return true;
r = h->hash (h->entries[i], h->aux) & (h->size - 1);
}
}
}
else
- return 0;
+ return false;
}
\f
/* Iteration. */
\f
/* Debug helpers. */
-#if GLOBAL_DEBUGGING
+#if DEBUGGING
#undef NDEBUG
#include "message.h"
#include <stdio.h>
projects / pspp-builds.git / blobdiff