/* PSPP - a program for statistical analysis.
- Copyright (C) 2007, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2009, 2010, 2011 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
#include <config.h>
-#include <libpspp/sparse-array.h>
+#include "libpspp/sparse-array.h"
#include <limits.h>
#include <string.h>
-#include <libpspp/assertion.h>
-#include <libpspp/misc.h>
-#include <libpspp/pool.h>
+#include "libpspp/assertion.h"
+#include "libpspp/cast.h"
+#include "libpspp/misc.h"
+#include "libpspp/pool.h"
-#include "count-one-bits.h"
-#include "minmax.h"
+#include "gl/count-one-bits.h"
+#include "gl/minmax.h"
/* Sparse array data structure.
void *
sparse_array_get (const struct sparse_array *spar, unsigned long int key)
{
- if (index_in_range (spar, key))
- {
- struct leaf_node *leaf = find_leaf_node (spar, key);
- if (leaf != NULL && is_in_use (leaf, key))
- return leaf_element (spar, leaf, key);
- }
+ struct leaf_node *leaf = find_leaf_node (spar, key);
+ if (leaf != NULL && is_in_use (leaf, key))
+ return leaf_element (spar, leaf, key);
return NULL;
}
union pointer *p;
int level;
- if (!index_in_range (spar, key))
- return false;
-
/* Find and free element in leaf. */
leaf = find_leaf_node (spar, key);
if (leaf == NULL || !is_in_use (leaf, key))
for (;;)
{
int ofs = idx % LONG_BITS;
- unsigned long int in_use = leaf->in_use[idx / LONG_BITS] << (31 - ofs);
+ unsigned long int in_use;
+
+ in_use = leaf->in_use[idx / LONG_BITS] << (LONG_BITS - 1 - ofs);
if (in_use)
return idx - count_leading_zeros (in_use);
if (idx < LONG_BITS)
static struct leaf_node *
find_leaf_node (const struct sparse_array *spar_, unsigned long int key)
{
- struct sparse_array *spar = (struct sparse_array *) spar_;
+ struct sparse_array *spar = CONST_CAST (struct sparse_array *, spar_);
const union pointer *p;
int level;
- assert (index_in_range (spar, key));
-
/* Check the cache first. */
if (key >> BITS_PER_LEVEL == spar->cache_ofs)
return spar->cache;
+ if (!index_in_range (spar, key))
+ return NULL;
+
/* Descend through internal nodes. */
p = &spar->root;
for (level = spar->height - 1; level > 0; level--)
scan_forward (const struct sparse_array *spar_, unsigned long int start,
unsigned long int *found)
{
- struct sparse_array *spar = (struct sparse_array *) spar_;
+ struct sparse_array *spar = CONST_CAST (struct sparse_array *, spar_);
/* Check the cache. */
if (start >> BITS_PER_LEVEL == spar->cache_ofs)
scan_reverse (const struct sparse_array *spar_, unsigned long int start,
unsigned long int *found)
{
- struct sparse_array *spar = (struct sparse_array *) spar_;
+ struct sparse_array *spar = CONST_CAST (struct sparse_array *, spar_);
/* Check the cache. */
if (start >> BITS_PER_LEVEL == spar->cache_ofs)