X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fsparse-array.c;h=28398d5cc86321e9e648a9c0ac30c052c1d26641;hb=02d26302aea9cb2c25c8cbb50bd120674de1f862;hp=7af219bcb080cd0a75b8b6bf9f823d2f397618a1;hpb=c3ac5a8af9c449072c7e872ca70a78c1755ae309;p=pspp-builds.git diff --git a/src/libpspp/sparse-array.c b/src/libpspp/sparse-array.c index 7af219bc..28398d5c 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 Free Software Foundation, Inc. + Copyright (C) 2007, 2009 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 @@ -25,6 +25,9 @@ #include #include +#include "count-one-bits.h" +#include "minmax.h" + /* Sparse array data structure. The sparse array is implemented in terms of a "radix tree", a @@ -48,6 +51,7 @@ /* Maximum height. */ #define LONG_BITS (sizeof (unsigned long int) * CHAR_BIT) +#define LONG_MASK ((unsigned long int) LONG_BITS - 1) #define MAX_HEIGHT DIV_RND_UP (LONG_BITS, BITS_PER_LEVEL) /* Bit-mask for index. */ @@ -113,7 +117,6 @@ static inline bool is_in_use (const struct leaf_node *, unsigned int); static inline bool any_in_use (const struct leaf_node *); static inline void set_in_use (struct leaf_node *, unsigned int); static inline void unset_in_use (struct leaf_node *, unsigned int); -static inline int scan_in_use (struct leaf_node *, unsigned int); static inline void *leaf_element (const struct sparse_array *, struct leaf_node *, unsigned int); static inline size_t leaf_size (const struct sparse_array *); @@ -121,10 +124,20 @@ static inline size_t leaf_size (const struct sparse_array *); 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 *, - unsigned long int, unsigned long int *); -static void *do_scan (struct sparse_array *, union pointer *, int, - unsigned long int, unsigned long int *); + +static int scan_in_use_forward (struct leaf_node *, unsigned int); +static void *do_scan_forward (struct sparse_array *, union pointer *, int, + unsigned long int, unsigned long int *); +static void *scan_forward (const struct sparse_array *, + unsigned long int start, + unsigned long int *found); + +static int scan_in_use_reverse (struct leaf_node *, unsigned int); +static void *do_scan_reverse (struct sparse_array *, union pointer *, int, + unsigned long int, unsigned long int *); +static void *scan_reverse (const struct sparse_array *, + unsigned long int start, + unsigned long int *found); /* Creates and returns a new sparse array that will contain elements that are ELEM_SIZE bytes in size. */ @@ -281,12 +294,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; } @@ -306,9 +316,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)) @@ -355,46 +362,46 @@ sparse_array_remove (struct sparse_array *spar, unsigned long int key) return true; } -/* Scans SPAR in increasing order of keys for in-use elements. - If SKIP is NULL, the scan starts from key 0; - otherwise, it starts just after key *SKIP. - If an element is found, returns it and stores the element's - key into *FOUND; otherwise, returns a null pointer and does - not modify *FOUND. */ +/* Returns a pointer to the in-use element with the smallest + index and sets *IDXP to its index or, if SPAR has no in-use + elements, returns NULL without modifying *IDXP. */ void * -sparse_array_scan (const struct sparse_array *spar_, unsigned long int *skip, - unsigned long int *found) +sparse_array_first (const struct sparse_array *spar, unsigned long int *idxp) { - struct sparse_array *spar = (struct sparse_array *) spar_; - unsigned long int start; + return scan_forward (spar, 0, idxp); +} - /* Find our starting point. */ - if (skip != NULL) - { - start = *skip + 1; - if (start == 0) - return NULL; - } - else - start = 0; +/* Returns a pointer to the in-use element with the smallest + index greater than SKIP and sets *IDXP to its index or, if + SPAR has no in-use elements with index greater than SKIP, + returns NULL without modifying *IDXP. */ +void * +sparse_array_next (const struct sparse_array *spar, unsigned long int skip, + unsigned long int *idxp) +{ + return skip < ULONG_MAX ? scan_forward (spar, skip + 1, idxp) : NULL; +} - /* Check the cache. */ - if (start >> BITS_PER_LEVEL == spar->cache_ofs) - { - void *p = scan_leaf (spar, spar->cache, start, found); - if (p) - return p; - start &= ~LEVEL_MASK; - start += PTRS_PER_LEVEL; - if (start == 0) - return NULL; - } +/* Returns a pointer to the in-use element with the greatest + index and sets *IDXP to its index or, if SPAR has no in-use + elements, returns NULL without modifying *IDXP. */ +void * +sparse_array_last (const struct sparse_array *spar, unsigned long int *idxp) +{ + return scan_reverse (spar, ULONG_MAX, idxp); +} - /* Do the scan. */ - if (!index_in_range (spar, start)) - return NULL; - return do_scan (spar, &spar->root, spar->height - 1, start, found); +/* Returns a pointer to the in-use element with the greatest + index less than SKIP and sets *IDXP to its index or, if SPAR + has no in-use elements with index less than SKIP, returns NULL + without modifying *IDXP. */ +void * +sparse_array_prev (const struct sparse_array *spar, unsigned long int skip, + unsigned long int *idxp) +{ + return skip > 0 ? scan_reverse (spar, skip - 1, idxp) : NULL; } + /* Returns true iff KEY is in the range of keys currently represented by SPAR. */ @@ -447,6 +454,9 @@ unset_in_use (struct leaf_node *leaf, unsigned int key) static inline int count_trailing_zeros (unsigned long int x) { +#if __GNUC__ >= 4 + return __builtin_ctzl (x); +#else /* not GCC 4+ */ /* This algorithm is from _Hacker's Delight_ section 5.4. */ int n = 1; @@ -469,24 +479,69 @@ count_trailing_zeros (unsigned long int x) COUNT_STEP (2); return n - (x & 1); +#endif /* not GCC 4+ */ } /* Returns the least index of the in-use element in LEAF greater - than or equal to IDX. */ -static inline int -scan_in_use (struct leaf_node *leaf, unsigned int idx) + than or equal to IDX. Bits in IDX not in LEVEL_MASK are + considered to have value 0. */ +static int +scan_in_use_forward (struct leaf_node *leaf, unsigned int idx) { - for (; idx < PTRS_PER_LEVEL; idx = (idx & ~(LONG_BITS - 1)) + LONG_BITS) + idx &= LEVEL_MASK; + for (; idx < PTRS_PER_LEVEL; idx = (idx & ~LONG_MASK) + LONG_BITS) { int ofs = idx % LONG_BITS; unsigned long int in_use = leaf->in_use[idx / LONG_BITS] >> ofs; if (!in_use) continue; - return count_trailing_zeros (in_use) + idx; + return idx + count_trailing_zeros (in_use); } return -1; } +/* Returns the number of leading 0-bits in X. + Undefined if X is zero. */ +static inline int +count_leading_zeros (unsigned long int x) +{ +#if __GNUC__ >= 4 + return __builtin_clzl (x); +#else + x |= x >> 1; + x |= x >> 2; + x |= x >> 4; + x |= x >> 8; + x |= x >> 16; +#if ULONG_MAX >> 31 >> 1 + x |= x >> 32; +#endif +#if ULONG_MAX >> 31 >> 31 >> 2 + x |= x >> 64; +#endif + return LONG_BITS - count_one_bits_l (x); +#endif +} + +/* Returns the greatest index of the in-use element in LEAF less + than or equal to IDX. Bits in IDX not in LEVEL_MASK are + considered to have value 0. */ +static int +scan_in_use_reverse (struct leaf_node *leaf, unsigned int idx) +{ + idx &= LEVEL_MASK; + for (;;) + { + int ofs = idx % LONG_BITS; + unsigned long int in_use = leaf->in_use[idx / LONG_BITS] << (31 - ofs); + if (in_use) + return idx - count_leading_zeros (in_use); + if (idx < LONG_BITS) + return -1; + idx = (idx | LONG_MASK) - LONG_BITS; + } +} + /* Returns the address of element with the given KEY in LEAF, which is a node in SPAR. */ static inline void * @@ -497,6 +552,18 @@ leaf_element (const struct sparse_array *spar, struct leaf_node *leaf, return (char *) leaf + SIZEOF_ALIGNED (*leaf) + (spar->elem_size * key); } +/* As leaf_element, returns the address of element with the given + KEY in LEAF, which is a node in SPAR. Also, updates SPAR's + cache to contain LEAF. */ +static void * +cache_leaf_element (struct sparse_array *spar, struct leaf_node *leaf, + unsigned long int key) +{ + spar->cache = leaf; + spar->cache_ofs = key >> BITS_PER_LEVEL; + return leaf_element (spar, leaf, key); +} + /* Returns the size of a leaf node in SPAR. */ static inline size_t leaf_size (const struct sparse_array *spar) @@ -514,12 +581,13 @@ find_leaf_node (const struct sparse_array *spar_, unsigned long int key) 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--) @@ -553,24 +621,36 @@ decrease_height (struct sparse_array *spar) } } -/* Scans leaf node LEAF, which is in SPAR, for the in-use element - with the least key greater than or equal to START. If such an - element is found, returns a pointer to it and stores its key - in *FOUND; otherwise, returns a null pointer and does not - modify *FOUND. */ -static void * -scan_leaf (struct sparse_array *spar, struct leaf_node *leaf, - unsigned long int start, unsigned long int *found) +/* Scans P, which is at LEVEL and within SPAR, and its subnodes, + for the in-use element with the least key greater than or + equal to START. If such an element is found, returns a + pointer to it and stores its key in *FOUND; otherwise, returns + a null pointer and does not modify *FOUND. */ +static inline void * +scan_internal_node_forward (struct sparse_array *spar, + struct internal_node *node, + int level, unsigned long int start, + unsigned long int *found) { - int idx = scan_in_use (leaf, start & LEVEL_MASK); - if (idx >= 0) + int shift = level * BITS_PER_LEVEL; + int count = node->count; + int i; + + for (i = (start >> shift) & LEVEL_MASK; i < PTRS_PER_LEVEL; i++) { - *found = (start & ~LEVEL_MASK) | idx; - spar->cache = leaf; - spar->cache_ofs = *found >> BITS_PER_LEVEL; - return leaf_element (spar, leaf, idx); - } + union pointer *q = &node->down[i]; + if (level > 1 ? q->internal != NULL : q->leaf != NULL) + { + void *element = do_scan_forward (spar, q, level - 1, start, found); + if (element) + return element; + if (--count == 0) + return NULL; + } + start &= ~((1ul << shift) - 1); + start += 1ul << shift; + } return NULL; } @@ -579,44 +659,134 @@ scan_leaf (struct sparse_array *spar, struct leaf_node *leaf, equal to START. If such an element is found, returns a pointer to it and stores its key in *FOUND; otherwise, returns a null pointer and does not modify *FOUND. */ +static void * +do_scan_forward (struct sparse_array *spar, union pointer *p, int level, + unsigned long int start, unsigned long int *found) +{ + if (level == 0) + { + int idx = scan_in_use_forward (p->leaf, start); + if (idx >= 0) + { + unsigned long int key = *found = (start & ~LEVEL_MASK) | idx; + return cache_leaf_element (spar, p->leaf, key); + } + } + return scan_internal_node_forward (spar, p->internal, level, start, found); +} + +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_; + + /* Check the cache. */ + if (start >> BITS_PER_LEVEL == spar->cache_ofs) + { + int idx = scan_in_use_forward (spar->cache, start); + if (idx >= 0) + { + *found = (start & ~LEVEL_MASK) | idx; + return leaf_element (spar, spar->cache, idx); + } + start = (start & ~LEVEL_MASK) + PTRS_PER_LEVEL; + if (start == 0) + return NULL; + } + + /* Do the scan. */ + if (!index_in_range (spar, start)) + return NULL; + return do_scan_forward (spar, &spar->root, spar->height - 1, start, found); +} + +/* Scans P, which is at LEVEL and within SPAR, and its subnodes, + for the in-use element with the greatest key less than or + equal to START. If such an element is found, returns a + pointer to it and stores its key in *FOUND; otherwise, returns + a null pointer and does not modify *FOUND. */ static inline void * -scan_internal_node (struct sparse_array *spar, struct internal_node *node, - int level, unsigned long int start, - unsigned long int *found) +scan_internal_node_reverse (struct sparse_array *spar, + struct internal_node *node, + int level, unsigned long int start, + 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 >= 0; i--) { union pointer *q = &node->down[i]; if (level > 1 ? q->internal != NULL : q->leaf != NULL) { - void *element = do_scan (spar, q, level - 1, start, found); + void *element = do_scan_reverse (spar, q, level - 1, start, found); if (element) return element; if (--count == 0) return NULL; } - start &= ~((1ul << shift) - 1); - start += 1ul << shift; + start |= (1ul << shift) - 1; + start -= 1ul << shift; } return NULL; } /* Scans P, which is at LEVEL and within SPAR, and its subnodes, - for the in-use element with the least key greater than or + for the in-use element with the greatest key less than or equal to START. If such an element is found, returns a pointer to it and stores its key in *FOUND; otherwise, returns a null pointer and does not modify *FOUND. */ static void * -do_scan (struct sparse_array *spar, union pointer *p, int level, - unsigned long int start, unsigned long int *found) +do_scan_reverse (struct sparse_array *spar, union pointer *p, int level, + unsigned long int start, unsigned long int *found) { - return (level == 0 - ? scan_leaf (spar, p->leaf, start, found) - : scan_internal_node (spar, p->internal, level, start, found)); + if (level == 0) + { + int idx = scan_in_use_reverse (p->leaf, start); + if (idx >= 0) + { + unsigned long int key = *found = (start & ~LEVEL_MASK) | idx; + return cache_leaf_element (spar, p->leaf, key); + } + else + return NULL; + } + return scan_internal_node_reverse (spar, p->internal, level, start, found); } +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_; + + /* Check the cache. */ + if (start >> BITS_PER_LEVEL == spar->cache_ofs) + { + int idx = scan_in_use_reverse (spar->cache, start); + if (idx >= 0) + { + *found = (start & ~LEVEL_MASK) | idx; + return leaf_element (spar, spar->cache, idx); + } + start |= LEVEL_MASK; + if (start < PTRS_PER_LEVEL) + return NULL; + start -= PTRS_PER_LEVEL; + } + else + { + if (spar->height == 0) + return NULL; + else if (spar->height < MAX_HEIGHT) + { + unsigned long int max_key; + max_key = (1ul << (spar->height * BITS_PER_LEVEL)) - 1; + start = MIN (start, max_key); + } + } + return do_scan_reverse (spar, &spar->root, spar->height - 1, start, found); +}