-/* PSPP - computes sample statistics.
+/* PSPP - a program for statistical analysis.
Copyright (C) 2007 Free Software Foundation, Inc.
- 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 2 of the
- License, or (at your option) any later version.
+ 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.
+ 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. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include <config.h>
/* Pointer to an internal node or a leaf node.
Pointers in internal nodes at level 1 point to leaf nodes;
other pointers point to internal nodes. */
-union pointer
+union pointer
{
struct internal_node *internal;
struct leaf_node *leaf;
};
/* A sparse array. */
-struct sparse_array
+struct sparse_array
{
struct pool *pool; /* Pool used for allocations. */
size_t elem_size; /* Element size, rounded for alignment. */
static struct leaf_node *find_leaf_node (const struct sparse_array *,
unsigned long int);
static void decrease_height (struct sparse_array *);
-static void *scan_leaf (struct sparse_array *, struct leaf_node *,
+static void *scan_leaf (struct sparse_array *, struct leaf_node *,
unsigned long int, unsigned long int *);
static void *do_scan (struct sparse_array *, union pointer *, int,
unsigned long int, unsigned long int *);
/* Creates and returns a new sparse array that will contain
elements that are ELEM_SIZE bytes in size. */
struct sparse_array *
-sparse_array_create (size_t elem_size)
+sparse_array_create (size_t elem_size)
{
return sparse_array_create_pool (NULL, elem_size);
}
elements that are ELEM_SIZE bytes in size. Data in the sparse
array will be allocated from POOL, which may be null. */
struct sparse_array *
-sparse_array_create_pool (struct pool *pool, size_t elem_size)
+sparse_array_create_pool (struct pool *pool, size_t elem_size)
{
struct sparse_array *spar = pool_malloc (pool, sizeof *spar);
spar->pool = pool;
/* Destroys SPAR node pointed to by P at the given LEVEL. */
static void
-do_destroy (struct sparse_array *spar, union pointer *p, int level)
+do_destroy (struct sparse_array *spar, union pointer *p, int level)
{
- if (level > 0)
+ if (level > 0)
{
struct internal_node *node = p->internal;
int count = node->count;
int i;
- for (i = 0; ; i++)
+ for (i = 0; ; i++)
{
union pointer *q = &p->internal->down[i];
- if (level > 1 ? q->internal != NULL : q->leaf != NULL)
+ if (level > 1 ? q->internal != NULL : q->leaf != NULL)
{
do_destroy (spar, q, level - 1);
if (--count == 0)
- break;
+ break;
}
}
pool_free (spar->pool, p->internal);
destruction is necessary, it should be done before destroying
the sparse array. */
void
-sparse_array_destroy (struct sparse_array *spar)
+sparse_array_destroy (struct sparse_array *spar)
{
do_destroy (spar, &spar->root, spar->height - 1);
pool_free (spar->pool, spar);
/* Returns the number of elements in SPAR. */
unsigned long int
-sparse_array_count (const struct sparse_array *spar)
+sparse_array_count (const struct sparse_array *spar)
{
return spar->count;
}
/* Increases SPAR's height by 1, allowing it to hold
PTRS_PER_LEVEL times more elements. */
static void
-increase_height (struct sparse_array *spar)
+increase_height (struct sparse_array *spar)
{
assert (spar->height < MAX_HEIGHT);
spar->height++;
- if (spar->height == 1)
+ if (spar->height == 1)
spar->root.leaf = pool_zalloc (spar->pool, leaf_size (spar));
- else
+ else
{
struct internal_node *new_root;
new_root = pool_zalloc (spar->pool, sizeof *new_root);
p = &spar->root;
for (level = spar->height - 1; level > 0; level--)
{
- if (p->internal == NULL)
+ if (p->internal == NULL)
{
p->internal = pool_zalloc (spar->pool, sizeof *p->internal);
- ++*count;
+ ++*count;
}
count = &p->internal->count;
}
/* Create leaf if necessary. */
- if (p->leaf == NULL)
+ if (p->leaf == NULL)
{
p->leaf = pool_zalloc (spar->pool, leaf_size (spar));
++*count;
/* Inserts into SPAR an element with the given KEY, which must not
already exist in SPAR.
- Returns the new element for the caller to initialize. */
+ Returns the new element for the caller to initialize. */
void *
-sparse_array_insert (struct sparse_array *spar, unsigned long int key)
+sparse_array_insert (struct sparse_array *spar, unsigned long int key)
{
struct leaf_node *leaf;
-
+
while (!index_in_range (spar, key))
increase_height (spar);
/* Finds and returns the element in SPAR with the given KEY.
Returns a null pointer if KEY does not exist in SPAR. */
void *
-sparse_array_get (const struct sparse_array *spar, unsigned long int key)
+sparse_array_get (const struct sparse_array *spar, unsigned long int key)
{
- if (index_in_range (spar, key))
+ if (index_in_range (spar, key))
{
struct leaf_node *leaf = find_leaf_node (spar, key);
if (leaf != NULL && is_in_use (leaf, key))
element's content must be considered freed and of
indeterminate value after it is removed. */
bool
-sparse_array_remove (struct sparse_array *spar, unsigned long int key)
+sparse_array_remove (struct sparse_array *spar, unsigned long int key)
{
union pointer *path[MAX_HEIGHT], **last;
struct leaf_node *leaf;
union pointer *p;
int level;
-
+
if (!index_in_range (spar, key))
return false;
not modify *FOUND. */
void *
sparse_array_scan (const struct sparse_array *spar_, unsigned long int *skip,
- unsigned long int *found)
+ unsigned long int *found)
{
struct sparse_array *spar = (struct sparse_array *) spar_;
unsigned long int start;
start = 0;
/* Check the cache. */
- if (start >> BITS_PER_LEVEL == spar->cache_ofs)
+ if (start >> BITS_PER_LEVEL == spar->cache_ofs)
{
void *p = scan_leaf (spar, spar->cache, start, found);
if (p)
/* Returns true iff KEY is in the range of keys currently
represented by SPAR. */
static inline bool
-index_in_range (const struct sparse_array *spar, unsigned long int key)
+index_in_range (const struct sparse_array *spar, unsigned long int key)
{
return (spar->height == 0 ? false
: spar->height >= MAX_HEIGHT ? true
/* Returns true iff LEAF contains an in-use element with the
given KEY. */
static inline bool
-is_in_use (const struct leaf_node *leaf, unsigned int key)
+is_in_use (const struct leaf_node *leaf, unsigned int key)
{
key &= LEVEL_MASK;
return (leaf->in_use[key / LONG_BITS] & (1ul << (key % LONG_BITS))) != 0;
}
-/* Returns true iff LEAF contains any in-use elements. */
+/* Returns true iff LEAF contains any in-use elements. */
static inline bool
-any_in_use (const struct leaf_node *leaf)
+any_in_use (const struct leaf_node *leaf)
{
size_t i;
for (i = 0; i < sizeof leaf->in_use / sizeof *leaf->in_use; i++)
/* Marks element KEY in LEAF as in-use. */
static inline void
-set_in_use (struct leaf_node *leaf, unsigned int key)
+set_in_use (struct leaf_node *leaf, unsigned int key)
{
key &= LEVEL_MASK;
leaf->in_use[key / LONG_BITS] |= 1ul << (key % LONG_BITS);
/* Marks element KEY in LEAF as not in-use. */
static inline void
-unset_in_use (struct leaf_node *leaf, unsigned int key)
+unset_in_use (struct leaf_node *leaf, unsigned int key)
{
key &= LEVEL_MASK;
leaf->in_use[key / LONG_BITS] &= ~(1ul << (key % LONG_BITS));
/* Returns the number of trailing 0-bits in X.
Undefined if X is zero. */
static inline int
-count_trailing_zeros (unsigned long int x)
+count_trailing_zeros (unsigned long int x)
{
/* This algorithm is from _Hacker's Delight_ section 5.4. */
int n = 1;
static inline int
scan_in_use (struct leaf_node *leaf, unsigned int idx)
{
- for (; idx < PTRS_PER_LEVEL; idx = (idx & ~(LONG_BITS - 1)) + LONG_BITS)
+ for (; idx < PTRS_PER_LEVEL; idx = (idx & ~(LONG_BITS - 1)) + LONG_BITS)
{
int ofs = idx % LONG_BITS;
unsigned long int in_use = leaf->in_use[idx / LONG_BITS] >> ofs;
which is a node in SPAR. */
static inline void *
leaf_element (const struct sparse_array *spar, struct leaf_node *leaf,
- unsigned int key)
+ unsigned int key)
{
key &= LEVEL_MASK;
return (char *) leaf + SIZEOF_ALIGNED (*leaf) + (spar->elem_size * key);
/* Returns the size of a leaf node in SPAR. */
static inline size_t
-leaf_size (const struct sparse_array *spar)
+leaf_size (const struct sparse_array *spar)
{
return SIZEOF_ALIGNED (struct leaf_node) + spar->elem_size * PTRS_PER_LEVEL;
}
/* Update cache. */
spar->cache = p->leaf;
spar->cache_ofs = key >> BITS_PER_LEVEL;
-
+
return p->leaf;
}
eliminating levels that contain only a single entry for all
0-bits. */
static void
-decrease_height (struct sparse_array *spar)
+decrease_height (struct sparse_array *spar)
{
while (spar->height > 1
&& spar->root.internal->count == 1
- && spar->root.internal->down[0].internal)
+ && spar->root.internal->down[0].internal)
{
struct internal_node *p = spar->root.internal;
spar->height--;
in *FOUND; otherwise, returns a null pointer and does not
modify *FOUND. */
static void *
-scan_leaf (struct sparse_array *spar, struct leaf_node *leaf,
+scan_leaf (struct sparse_array *spar, struct leaf_node *leaf,
unsigned long int start, unsigned long int *found)
{
int idx = scan_in_use (leaf, start & LEVEL_MASK);
spar->cache_ofs = *found >> BITS_PER_LEVEL;
return leaf_element (spar, leaf, idx);
}
-
+
return NULL;
}
static inline void *
scan_internal_node (struct sparse_array *spar, struct internal_node *node,
int level, unsigned long int start,
- unsigned long int *found)
+ unsigned long int *found)
{
int shift = level * BITS_PER_LEVEL;
int count = node->count;
int i;
- for (i = (start >> shift) & LEVEL_MASK; i < PTRS_PER_LEVEL; i++)
+ for (i = (start >> shift) & LEVEL_MASK; i < PTRS_PER_LEVEL; i++)
{
union pointer *q = &node->down[i];
if (level > 1 ? q->internal != NULL : q->leaf != NULL)
return element;
if (--count == 0)
return NULL;
- }
+ }
start &= ~((1ul << shift) - 1);
start += 1ul << shift;
projects / pspp-builds.git / blobdiff