X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Frange-set.c;h=78253be6ad94c8556966cfa61015363b60deb0a0;hb=186db0c54bcb0caf4a6df1fcc60b8158bc11ab92;hp=4e7d6d2fc890c4b434acfb54f93d793106d57c5a;hpb=93b4335785430ab6de290b7978e2d506106a8ba5;p=pspp-builds.git diff --git a/src/libpspp/range-set.c b/src/libpspp/range-set.c index 4e7d6d2f..78253be6 100644 --- a/src/libpspp/range-set.c +++ b/src/libpspp/range-set.c @@ -1,20 +1,18 @@ -/* PSPP - computes sample statistics. - Copyright (C) 2007 Free Software Foundation, Inc. +/* PSPP - a program for statistical analysis. + 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 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 . */ /* Bitmap, implemented as a balanced binary tree. */ @@ -38,7 +36,7 @@ #include "xalloc.h" /* A set of ranges. */ -struct range_set +struct range_set { struct pool *pool; /* Pool for freeing range_set. */ struct bt bt; /* Tree of range_set_nodes. */ @@ -50,14 +48,14 @@ struct range_set }; /* A node in the range set. */ -struct range_set_node +struct range_set_node { struct bt_node bt_node; /* Binary tree node. */ unsigned long int start; /* Start of region. */ unsigned long int end; /* One past end of region. */ }; -static struct range_set_node *bt_to_rs_node (const struct bt_node *); +static struct range_set_node *bt_to_rs_node (const struct bt_node *); static int compare_range_set_nodes (const struct bt_node *, const struct bt_node *, const void *aux); @@ -81,7 +79,7 @@ static void destroy_pool (void *); /* Creates and returns a new, empty range set. */ struct range_set * -range_set_create (void) +range_set_create (void) { return range_set_create_pool (NULL); } @@ -89,7 +87,7 @@ range_set_create (void) /* Creates and returns a new, empty range set in the given POOL. */ struct range_set * -range_set_create_pool (struct pool *pool) +range_set_create_pool (struct pool *pool) { struct range_set *rs = xmalloc (sizeof *rs); rs->pool = pool; @@ -100,17 +98,31 @@ range_set_create_pool (struct pool *pool) return rs; } +/* Creates and returns a clone of OLD range set in the given POOL + (which may be null). */ +struct range_set * +range_set_clone (const struct range_set *old, struct pool *pool) +{ + struct range_set *new; + struct range_set_node *node; + + new = range_set_create_pool (pool); + for (node = first_node (old); node != NULL; node = next_node (old, node)) + insert_node (new, node->start, node->end); + return new; +} + /* Destroys range set RS. */ void -range_set_destroy (struct range_set *rs) +range_set_destroy (struct range_set *rs) { - if (rs != NULL) + if (rs != NULL) { if (rs->pool != NULL) pool_unregister (rs->pool, rs); - while (!range_set_is_empty (rs)) + while (!range_set_is_empty (rs)) delete_node (rs, first_node (rs)); - free (rs); + free (rs); } } @@ -118,7 +130,7 @@ range_set_destroy (struct range_set *rs) into RS. */ void range_set_insert (struct range_set *rs, - unsigned long int start, unsigned long int width) + unsigned long int start, unsigned long int width) { unsigned long int end = start + width; struct range_set_node *node; @@ -132,34 +144,34 @@ range_set_insert (struct range_set *rs, rs->cache_end = 0; node = find_node_le (rs, start); - if (node != NULL) + if (node != NULL) { - if (start > node->end) + if (start > node->end) { /* New region does not overlap NODE, but it might overlap the next node. */ insert_just_before (rs, start, end, next_node (rs, node)); } - else if (end > node->end) + else if (end > node->end) { /* New region starts in the middle of NODE and continues past its end, so extend NODE, then merge it with any following node that it now potentially overlaps. */ node->end = end; - merge_node_with_successors (rs, node); + merge_node_with_successors (rs, node); } - else + else { /* New region is completely contained by NODE, so there's nothing to do. */ } } - else + else { /* New region starts before any existing region, but it might overlap the first region. */ - insert_just_before (rs, start, end, first_node (rs)); + insert_just_before (rs, start, end, first_node (rs)); } } @@ -167,7 +179,7 @@ range_set_insert (struct range_set *rs, from RS. */ void range_set_delete (struct range_set *rs, - unsigned long int start, unsigned long int width) + unsigned long int start, unsigned long int width) { unsigned long int end = start + width; struct range_set_node *node; @@ -181,12 +193,12 @@ range_set_delete (struct range_set *rs, rs->cache_end = 0; node = find_node_le (rs, start); - if (node == NULL) + if (node == NULL) node = first_node (rs); - - while (node != NULL && end > node->start) + + while (node != NULL && end > node->start) { - if (start <= node->start) + if (start <= node->start) { if (end >= node->end) { @@ -202,7 +214,7 @@ range_set_delete (struct range_set *rs, } else if (start < node->end) { - if (end < node->end) + if (end < node->end) { /* Region to delete covers middle of the node, so we have to split the node into two pieces. */ @@ -211,7 +223,7 @@ range_set_delete (struct range_set *rs, insert_node (rs, end, old_node_end); break; } - else + else { /* Region to delete covers only right part of node. */ @@ -230,10 +242,10 @@ range_set_delete (struct range_set *rs, 1-bit deleted and *WIDTH to the number actually deleted, which may be less than REQUEST if fewer contiguous 1-bits were present, and returns true. If RS is completely empty, returns - false. */ + false. */ bool range_set_allocate (struct range_set *rs, unsigned long int request, - unsigned long int *start, unsigned long int *width) + unsigned long int *start, unsigned long int *width) { struct range_set_node *node; unsigned long int node_width; @@ -246,12 +258,12 @@ range_set_allocate (struct range_set *rs, unsigned long int request, node_width = node->end - node->start; *start = node->start; - if (request < node_width) + if (request < node_width) { *width = request; node->start += request; } - else + else { *width = node_width; delete_node (rs, node); @@ -262,27 +274,57 @@ range_set_allocate (struct range_set *rs, unsigned long int request, return true; } +/* Scans RS for and deletes the first contiguous run of REQUEST + 1-bits. If successful, sets *START to the position of the + first 1-bit deleted and returns true If RS does not contain a + run of REQUEST or more contiguous 1-bits, returns false and + does not modify RS. */ +bool +range_set_allocate_fully (struct range_set *rs, unsigned long int request, + unsigned long int *start) +{ + struct range_set_node *node; + + assert (request > 0); + + for (node = first_node (rs); node != NULL; node = next_node (rs, node)) + { + unsigned long int node_width = node->end - node->start; + if (node_width >= request) + { + *start = node->start; + if (node_width > request) + node->start += request; + else + delete_node (rs, node); + rs->cache_end = 0; + return true; + } + } + return false; +} + /* Returns true if there is a 1-bit at the given POSITION in RS, false otherwise. */ bool -range_set_contains (const struct range_set *rs_, unsigned long int position) +range_set_contains (const struct range_set *rs_, unsigned long int position) { struct range_set *rs = (struct range_set *) rs_; if (position < rs->cache_end && position >= rs->cache_start) return rs->cache_value; - else + else { struct range_set_node *node = find_node_le (rs, position); if (node != NULL) { - if (position < node->end) + if (position < node->end) { rs->cache_start = node->start; rs->cache_end = node->end; rs->cache_value = true; - return true; + return true; } - else + else { struct range_set_node *next = next_node (rs, node); rs->cache_start = node->end; @@ -304,7 +346,7 @@ range_set_contains (const struct range_set *rs_, unsigned long int position) /* Returns true if RS contains no 1-bits, false otherwise. */ bool -range_set_is_empty (const struct range_set *rs) +range_set_is_empty (const struct range_set *rs) { return bt_count (&rs->bt) == 0; } @@ -314,7 +356,7 @@ range_set_is_empty (const struct range_set *rs) Any call to range_set_insert, range_set_delete, or range_set_allocate invalidates the returned node. */ const struct range_set_node * -range_set_first (const struct range_set *rs) +range_set_first (const struct range_set *rs) { return first_node (rs); } @@ -327,7 +369,7 @@ range_set_first (const struct range_set *rs) Any call to range_set_insert, range_set_delete, or range_set_allocate invalidates the returned node. */ const struct range_set_node * -range_set_next (const struct range_set *rs, const struct range_set_node *node) +range_set_next (const struct range_set *rs, const struct range_set_node *node) { return (node != NULL ? next_node (rs, (struct range_set_node *) node) @@ -336,21 +378,21 @@ range_set_next (const struct range_set *rs, const struct range_set_node *node) /* Returns the position of the first 1-bit in NODE. */ unsigned long int -range_set_node_get_start (const struct range_set_node *node) +range_set_node_get_start (const struct range_set_node *node) { return node->start; } /* Returns one past the position of the last 1-bit in NODE. */ unsigned long int -range_set_node_get_end (const struct range_set_node *node) +range_set_node_get_end (const struct range_set_node *node) { return node->end; } /* Returns the number of contiguous 1-bits in NODE. */ unsigned long int -range_set_node_get_width (const struct range_set_node *node) +range_set_node_get_width (const struct range_set_node *node) { return node->end - node->start; } @@ -358,7 +400,7 @@ range_set_node_get_width (const struct range_set_node *node) /* Returns the range_set_node corresponding to the given BT_NODE. Returns a null pointer if BT_NODE is null. */ static struct range_set_node * -bt_to_rs_node (const struct bt_node *bt_node) +bt_to_rs_node (const struct bt_node *bt_node) { return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL; } @@ -368,7 +410,7 @@ bt_to_rs_node (const struct bt_node *bt_node) static int compare_range_set_nodes (const struct bt_node *a_, const struct bt_node *b_, - const void *aux UNUSED) + const void *aux UNUSED) { const struct range_set_node *a = bt_to_rs_node (a_); const struct range_set_node *b = bt_to_rs_node (b_); @@ -379,7 +421,7 @@ compare_range_set_nodes (const struct bt_node *a_, /* Returns the first range_set_node in RS, or a null pointer if RS is empty. */ static struct range_set_node * -first_node (const struct range_set *rs) +first_node (const struct range_set *rs) { return bt_to_rs_node (bt_first (&rs->bt)); } @@ -387,14 +429,14 @@ first_node (const struct range_set *rs) /* Returns the next range_set_node in RS after NODE, or a null pointer if NODE is the last node in RS. */ static struct range_set_node * -next_node (const struct range_set *rs, const struct range_set_node *node) +next_node (const struct range_set *rs, const struct range_set_node *node) { return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node)); } /* Deletes NODE from RS and frees it. */ static void -delete_node (struct range_set *rs, struct range_set_node *node) +delete_node (struct range_set *rs, struct range_set_node *node) { bt_delete (&rs->bt, &node->bt_node); free (node); @@ -403,7 +445,7 @@ delete_node (struct range_set *rs, struct range_set_node *node) /* Deletes NODE from RS, frees it, and returns the following node. */ static struct range_set_node * -delete_node_get_next (struct range_set *rs, struct range_set_node *node) +delete_node_get_next (struct range_set *rs, struct range_set_node *node) { struct range_set_node *next = next_node (rs, node); delete_node (rs, node); @@ -416,7 +458,7 @@ delete_node_get_next (struct range_set *rs, struct range_set_node *node) in RS. If POSITION would duplicate an existing region's start, returns that region. */ static struct range_set_node * -find_node_le (const struct range_set *rs, unsigned long int position) +find_node_le (const struct range_set *rs, unsigned long int position) { struct range_set_node tmp; tmp.start = position; @@ -427,7 +469,7 @@ find_node_le (const struct range_set *rs, unsigned long int position) region into RS, and returns the new region. */ static struct range_set_node * insert_node (struct range_set *rs, - unsigned long int start, unsigned long int end) + unsigned long int start, unsigned long int end) { struct range_set_node *node = xmalloc (sizeof *node); struct bt_node *dummy; @@ -444,7 +486,7 @@ insert_node (struct range_set *rs, preceding NODE, and START precedes NODE's start; if NODE is null, then the new region is known to follow any and all regions already in RS. */ -static void +static void insert_just_before (struct range_set *rs, unsigned long int start, unsigned long int end, struct range_set_node *node) @@ -454,25 +496,25 @@ insert_just_before (struct range_set *rs, { /* New region overlaps NODE, so just extend NODE. */ node->start = start; - if (end > node->end) + if (end > node->end) { node->end = end; - merge_node_with_successors (rs, node); + merge_node_with_successors (rs, node); } } - else + else { /* New region does not overlap NODE. */ - insert_node (rs, start, end); + insert_node (rs, start, end); } } /* Merges NODE in RS with its successors. */ static void -merge_node_with_successors (struct range_set *rs, struct range_set_node *node) +merge_node_with_successors (struct range_set *rs, struct range_set_node *node) { struct range_set_node *next; - + while ((next = next_node (rs, node)) != NULL && node->end >= next->start) { if (next->end > node->end) @@ -484,7 +526,7 @@ merge_node_with_successors (struct range_set *rs, struct range_set_node *node) /* Destroys range set RS. Helper function for range_set_create_pool. */ static void -destroy_pool (void *rs_) +destroy_pool (void *rs_) { struct range_set *rs = rs_; rs->pool = NULL;