X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fsparse-array.c;h=65a4612259f7e0510feb8cb55bbd7e619ce3e1d5;hb=81579d9e9f994fb2908f50af41c3eb033d216e58;hp=ebc81ff45137734736069abf6eaaa0d13d4b0fae;hpb=a68e3f51236286fe02c6c4b6d40efa1bcec36349;p=pspp-builds.git diff --git a/src/libpspp/sparse-array.c b/src/libpspp/sparse-array.c index ebc81ff4..65a46122 100644 --- a/src/libpspp/sparse-array.c +++ b/src/libpspp/sparse-array.c @@ -1,5 +1,5 @@ /* 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 @@ -16,17 +16,18 @@ #include -#include +#include "libpspp/sparse-array.h" #include #include -#include -#include -#include +#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. @@ -294,12 +295,9 @@ sparse_array_insert (struct sparse_array *spar, unsigned long int key) 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; } @@ -319,9 +317,6 @@ sparse_array_remove (struct sparse_array *spar, unsigned long int key) 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)) @@ -539,7 +534,9 @@ scan_in_use_reverse (struct leaf_node *leaf, unsigned int idx) 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) @@ -583,16 +580,17 @@ leaf_size (const struct sparse_array *spar) 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--) @@ -684,7 +682,7 @@ static void * 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) @@ -766,7 +764,7 @@ static void * 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)