-/* 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 <http://www.gnu.org/licenses/>. */
/* Bitmap, implemented as a balanced binary tree. */
#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. */
};
/* 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);
/* 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);
}
/* 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;
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);
}
}
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;
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));
}
}
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;
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)
{
}
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. */
insert_node (rs, end, old_node_end);
break;
}
- else
+ else
{
/* Region to delete covers only right part of
node. */
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;
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);
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;
/* 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;
}
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);
}
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)
/* 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;
}
/* 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;
}
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_);
/* 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));
}
/* 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);
/* 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);
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;
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;
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)
{
/* 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)
/* 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;
projects / pspp-builds.git / blobdiff