/* This is -*- C -*- */
/* $Id: guppi-seq-boolean-core.c,v 1.1 2002/01/08 06:29:00 trow Exp $ */
/*
* guppi-seq-boolean-core.c
*
* Copyright (C) 2000 EMC Capital Management, Inc.
* Copyright (C) 2001 The Free Software Foundation
*
* Developed by Jon Trowbridge <trow@gnu.org> and
* Havoc Pennington <hp@pobox.com>.
*
* 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 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307
* USA
*/
#include <config.h>
#include "guppi-seq-boolean-core.h"
#include <libgnome/gnome-defs.h>
#include <libgnome/gnome-config.h>
#include <libgnome/gnome-i18n.h>
#include <guppi-string.h>
#include <guppi-convenient.h>
#include <guppi-memory.h>
static GtkObjectClass *parent_class = NULL;
static void
guppi_seq_boolean_core_finalize (GtkObject * obj)
{
GuppiSeqBooleanCore *seq = GUPPI_SEQ_BOOLEAN_CORE (obj);
guppi_unref0 (seq->garray);
if (parent_class->finalize)
parent_class->finalize (obj);
}
/***************************************************************************/
#define ASIZE(core) (((core)->size >> 5) + (((core)->size&31)?1:0))
#define BITVEC_GET(data, i) ((data)[(i)>>5] & (1 << ((i)&31)))
#define BITVEC_SET(data, i) ((data)[(i)>>5] |= (1 << ((i)&31)))
#define BITVEC_UNSET(data, i) ((data)[(i)>>5] &= ~(1 << ((i)&31)))
#define LAST_MASK(size) ((guint32)(~0) >> (32-((size)&31)))
static gboolean
v_seq_boolean_get (GuppiSeqBoolean *seq, gint i)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
guint32 *data = (guint32 *) guppi_garray_data (core->garray);
i -= core->index_basis;
return BITVEC_GET (data, i);
}
static void
v_seq_boolean_set (GuppiSeqBoolean *seq_bool, gint i, gboolean x)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq_bool);
guint32 *data = (guint32 *) guppi_garray_data (core->garray);
i -= core->index_basis;
if (x)
BITVEC_SET (data, i);
else
BITVEC_UNSET (data, i);
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->set)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->set (seq_bool, i, x);
}
static void
v_seq_boolean_set_all (GuppiSeqBoolean *seq_bool, gboolean x)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq_bool);
guint32 *data = (guint32 *) guppi_garray_data (core->garray);
gint i, N;
N = ASIZE (core);
if (x) {
for (i = 0; i < N - 1; ++i)
data[i] = ~0;
} else {
for (i = 0; i < N - 1; ++i)
data[i] = 0;
}
data[N - 1] = x ? LAST_MASK (core->size) : 0;
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->set_all)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->set_all (seq_bool, x);
}
static void
v_seq_boolean_set_many (GuppiSeqBoolean *seq_bool, const gint *indices, gsize N, gboolean x)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq_bool);
guint32 *data = (guint32 *) guppi_garray_data (core->garray);
gint i, k;
if (x) {
for (i = 0; i < N; ++i) {
k = indices[i] - core->index_basis;
if (0 <= k && k < core->size)
BITVEC_SET (data, k);
}
} else {
for (i = 0; i < N; ++i) {
k = indices[i] - core->index_basis;
if (0 <= k && k < core->size)
BITVEC_UNSET (data, k);
}
}
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->set_many)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->set_many (seq_bool, indices, N, x);
}
static void
v_seq_boolean_insert (GuppiSeqBoolean *seq_bool, gint i, gboolean x)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq_bool);
guint32 *data;
gint j, old_size, N, bottom;
if (guppi_garray_size (core->garray) <= ASIZE (core)) {
old_size = guppi_garray_size (core->garray);
guppi_garray_set_size (core->garray, MAX (32, 2 * ASIZE (core)));
data = (guint32 *) guppi_garray_data (core->garray);
for (j = old_size; j < guppi_garray_size (core->garray); ++j)
data[j] = 0;
}
data = (guint32 *) guppi_garray_data (core->garray);
if (core->size == 0)
core->index_basis = i;
i -= core->index_basis;
++core->size;
N = ASIZE (core);
bottom = i >> 5;
for (j = N - 1; j >= bottom; --j) {
if (j + 1 < N)
data[j + 1] |= data[j] >> 1;
if (j != bottom || (i & 31) == 0)
data[j] = data[j] << 1;
else {
guint32 bottom_mask = ((guint32) (~0)) >> (32 - (i & 31));
data[j] = (data[j] & bottom_mask) | ((data[j] << 1) & ~bottom_mask);
}
}
if (x)
BITVEC_SET (data, i);
else
BITVEC_UNSET (data, i);
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->insert)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->insert (seq_bool, i, x);
}
static void
v_seq_boolean_insert_many (GuppiSeqBoolean *seq_bool, gint i, gboolean x, gsize step)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq_bool);
guint32 *data;
gint old_size, j, sz;
gint step_big, step_small, N, bottom;
/* grow the array, if necessary */
sz = 1 + ((core->size + step) >> 5);
if (guppi_garray_size (core->garray) <= sz) {
old_size = guppi_garray_size (core->garray);
guppi_garray_set_size (core->garray, MAX (32, 2 * sz));
data = (guint32 *) guppi_garray_data (core->garray);
for (j = old_size; j < guppi_garray_size (core->garray); ++j)
data[j] = 0;
}
data = (guint32 *) guppi_garray_data (core->garray);
if (core->size == 0)
core->index_basis = i;
i -= core->index_basis;
core->size += step;
N = ASIZE (core);
bottom = i >> 5;
step_big = step >> 5;
step_small = step & 31;
for (j = N - 1 - step_big; j >= bottom; --j) {
if (step_small && j + step_big + 1 < N)
data[j + step_big + 1] |= data[j] >> (32 - step_small);
if (j == bottom && step_big == 0 && (i & 31) != 0) {
guint32 bottom_mask = ((guint32) (~0)) >> (32 - (i & 31));
data[j] =
(data[j] & bottom_mask) | ((data[j] << step_small) & ~bottom_mask);
} else
data[j + step_big] = data[j] << step_small;
}
/* initialize the inserted slots */
/* this could be optimized to operate an guint32 at a time, but
* I'll opt for obvious correctness right now... */
if (x) {
for (j = 0; j < step; ++j)
BITVEC_SET (data, i + j);
} else {
for (j = 0; j < step; ++j)
BITVEC_UNSET (data, i + j);
}
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->insert_many)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->insert_many (seq_bool, i, x, step);
}
static void
v_seq_boolean_bitwise_and (GuppiSeqBoolean *seq,
GuppiSeqBoolean *other)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
GuppiSeqBooleanCore *other_core = GUPPI_SEQ_BOOLEAN_CORE (other); /* FIXME */
gint i;
guint32 *data;
const guint32 *other_data;
if (core->index_basis == other_core->index_basis &&
core->size == other_core->size) {
data = (guint32 *) guppi_garray_data (core->garray);
other_data = (const guint32 *) guppi_garray_data (other_core->garray);
for (i = 0; i < ASIZE (core); ++i)
data[i] &= other_data[i];
goto finished;
}
/* We'll implement the hard case later. */
g_assert_not_reached ();
finished:
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_and)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_and (seq, other);
}
static void
v_seq_boolean_bitwise_or (GuppiSeqBoolean *seq,
GuppiSeqBoolean *other)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
GuppiSeqBooleanCore *other_core = GUPPI_SEQ_BOOLEAN_CORE (other); /* FIXME */
gint i;
guint32 *data;
const guint32 *other_data;
if (core->index_basis == other_core->index_basis &&
core->size == other_core->size) {
data = (guint32 *) guppi_garray_data (core->garray);
other_data = (const guint32 *) guppi_garray_data (other_core->garray);
for (i = 0; i < ASIZE (core); ++i)
data[i] |= other_data[i];
goto finished;
}
/* We'll implement the hard case later. */
g_assert_not_reached ();
finished:
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_or)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_or (seq, other);
}
static void
v_seq_boolean_bitwise_xor (GuppiSeqBoolean *seq,
GuppiSeqBoolean *other)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
GuppiSeqBooleanCore *other_core = GUPPI_SEQ_BOOLEAN_CORE (other);
gint i;
guint32 *data;
const guint32 *other_data;
if (core->index_basis == other_core->index_basis &&
core->size == other_core->size) {
data = (guint32 *) guppi_garray_data (core->garray);
other_data = (const guint32 *) guppi_garray_data (other_core->garray);
for (i = 0; i < ASIZE (core); ++i)
data[i] ^= other_data[i];
goto finished;
}
/* We'll implement the hard case later. */
g_assert_not_reached ();
finished:
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_xor)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_xor (seq, other);
}
static void
v_seq_boolean_bitwise_not (GuppiSeqBoolean *seq)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
gint i, N;
guint32 *data;
data = (guint32 *) guppi_garray_data (core->garray);
N = ASIZE (core);
for (i = 0; i < N; ++i)
data[i] = ~data[i];
/* Make sure surplus bits are zero */
data[N - 1] &= LAST_MASK (core->size);
if (GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_not)
GUPPI_SEQ_BOOLEAN_CLASS (parent_class)->bitwise_not (seq);
}
static gint
v_seq_boolean_next_true (GuppiSeqBoolean *seq, gint i)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
const guint32 *data;
gint j, k;
guint32 q;
if (core->size == 0)
return 1;
data = (const guint32 *) guppi_garray_data (core->garray);
i -= core->index_basis;
if (i < 0) {
if (data[0] & 1)
return core->index_basis;
i = 0;
}
j = i >> 5;
k = i & 31;
++i;
/* Check of our first guint32 */
if (k != 31 && (q = (data[j] >> (k + 1)))) {
while (!(q & 1)) {
q = q >> 1;
++i;
}
return i + core->index_basis;
}
++j;
while (j < ASIZE (core) && data[j] == 0)
++j;
if (j >= ASIZE (core))
return core->index_basis + core->size;
q = data[j];
i = j << 5;
while (!(q & 1)) {
q = q >> 1;
++i;
}
return i + core->index_basis;
}
static gsize
v_seq_boolean_true_count (GuppiSeqBoolean *seq)
{
const GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
guint32 *data;
static guint8 *bitcount = NULL;
gint q, i, count, N;
guint32 last_mask;
/* Initialize our bit-count dictionary, which pre-tallies the number
of on-bits in each integer 0..255 */
if (bitcount == NULL) {
bitcount = guppi_new (guint8, 256);
guppi_permanent_alloc (bitcount);
for (i = 0; i < 256; ++i) {
count = 0;
q = i;
while (q) {
if (q & 1)
++count;
q = q >> 1;
}
bitcount[i] = count;
}
}
data = (guint32 *) guppi_garray_data (core->garray);
N = ASIZE (core);
/* Be paranoid and insure that the surplus bits are zero. */
last_mask = LAST_MASK (core->size);
data[N - 1] &= last_mask;
count = 0;
for (i = 0; i < N; ++i) {
q = data[i];
count += bitcount[q & 0xff] + bitcount[(q >> 8) & 0xff] +
bitcount[(q >> 16) & 0xff] + bitcount[(q >> 24) & 0xff];
}
return (gsize) count;
}
#if 0
/* This could probably be optimized some more. */
static gint
v_seq_boolean_range_query (GuppiSeqScalar *seq,
GuppiSeqBoolean *seq_bool,
double min, double max, gboolean do_and)
{
gconstpointer ptr;
gint stride;
GuppiSeqBooleanCore *core;
guint32 *data;
gint i, i0, i1;
double x;
gint hits = 0;
ptr = guppi_seq_scalar_raw (seq, &stride);
if (ptr == NULL)
return -1;
core = GUPPI_SEQ_BOOLEAN_CORE (seq_bool);
guppi_seq_indices (GUPPI_SEQ (seq), &i0, &i1);
data = (guint32 *) guppi_garray_data (core->garray);
i0 = MAX (i0, core->index_basis);
i1 = MIN (i1, core->index_basis - 1 + core->size);
/* Adjust to point at first raw data element */
ptr = (gconstpointer) (((guint8 *) ptr) + i0 * stride);
if (do_and) {
/* AND behavior */
guint32 mask = 1;
gint offset = 0;
guint32 data_chunk = data[offset];
i = i0;
while (i <= i1) {
if (data_chunk & mask) {
x = *(const double *) ptr;
if (x < min || max < x) {
data_chunk &= ~mask;
} else {
++hits;
}
}
mask = mask << 1;
if (mask == 0) {
data[offset] = data_chunk;
mask = 1;
++offset;
while ((data_chunk = data[offset]) == 0 && i <= i1) {
++offset;
ptr = (gconstpointer) (((guint8 *) ptr) + (stride << 5));
i += 32;
}
}
ptr = (gconstpointer) (((guint8 *) ptr) + stride);
++i;
}
if (mask != 1)
data[offset] = data_chunk;
} else {
/* overwrite behavior */
guint32 mask = 1;
gint offset = 0;
guint32 data_chunk = 0;
for (i = i0; i <= i1; ++i) {
if (mask == 1)
data_chunk = 0;
x = *(const double *) ptr;
if (min <= x && x <= max) {
data_chunk |= mask;
++hits;
}
mask = mask << 1;
if (mask == 0) {
mask = 1;
data[offset] = data_chunk;
++offset;
}
ptr = (gconstpointer) (((guint8 *) ptr) + stride);
}
if (mask != 1)
data[offset] = data_chunk;
}
return hits;
}
#endif
static void
v_seq_size_hint (GuppiSeq *seq, gsize n)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
if (guppi_garray_size (core->garray) < 1 + (n >> 5))
guppi_garray_set_size (core->garray, 1 + (n >> 5));
if (GUPPI_SEQ_CLASS (parent_class)->size_hint)
GUPPI_SEQ_CLASS (parent_class)->size_hint (seq, n);
}
static void
v_seq_get_bounds (GuppiSeq *seq, gint *min, gint *max)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
if (min)
*min = core->index_basis;
if (max)
*max = core->index_basis - 1 + core->size;
}
static void
v_seq_shift_indices (GuppiSeq *seq, gint delta)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
core->index_basis += delta;
if (GUPPI_SEQ_CLASS (parent_class)->shift_indices)
GUPPI_SEQ_CLASS (parent_class)->shift_indices (seq, delta);
}
static void
v_seq_insert_generic (GuppiSeq *seq, gint i, gsize N)
{
v_seq_boolean_insert_many (GUPPI_SEQ_BOOLEAN (seq), i, FALSE, N);
if (GUPPI_SEQ_CLASS (parent_class)->insert_generic)
GUPPI_SEQ_CLASS (parent_class)->insert_generic (seq, i, N);
}
static void
v_seq_delete_many (GuppiSeq *seq, gint i, gsize N)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (seq);
guint32 *data = (guint32 *) guppi_garray_data (core->garray);
gint j, step_small, step_big, top, bottom;
i -= core->index_basis;
N = MIN (N, core->size - i);
if (N == 0)
return;
top = ASIZE (core);
bottom = i >> 5;
step_big = N >> 5;
step_small = N & 31;
if (i & 31) {
guint32 mask = ((guint32) (~0)) >> (32 - (i & 31));
guint32 q = data[bottom];
q &= mask;
if (bottom + step_big < top)
q |= (data[bottom + step_big] >> step_small) & ~mask;
if (bottom + step_big + 1 < top)
q |= (data[bottom + step_big + 1] << (32 - step_small)) & ~mask;
data[bottom] = q;
++bottom;
}
for (j = bottom; j + step_big < top; ++j) {
data[j] = data[j + step_big] >> step_small;
if (j + step_big + 1 < top && step_small)
data[j] |= data[j + step_big + 1] << (32 - step_small);
}
core->size -= N;
if (GUPPI_SEQ_CLASS (parent_class)->delete_many)
GUPPI_SEQ_CLASS (parent_class)->delete_many (seq, i, N);
}
static GuppiData *
v_data_copy (GuppiData *d)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (d);
GuppiSeqBooleanCore *copy;
gint i;
guint32 *data;
guint32 *copy_data;
copy = GUPPI_SEQ_BOOLEAN_CORE (guppi_type_new (GUPPI_TYPE_SEQ_BOOLEAN_CORE));
copy->index_basis = core->index_basis;
copy->size = core->size;
copy->garray = guppi_garray_new (sizeof (guint32));
guppi_garray_set_size (copy->garray, ASIZE (copy));
data = (guint32 *) guppi_garray_data (core->garray);
copy_data = (guint32 *) guppi_garray_data (copy->garray);
for (i = 0; i < ASIZE (core); ++i)
copy_data[i] = data[i];
return GUPPI_DATA (copy);
}
static gint
v_data_size_in_bytes (GuppiData *d)
{
GuppiSeqBooleanCore *core = GUPPI_SEQ_BOOLEAN_CORE (d);
gint sib = guppi_garray_size (core->garray) * sizeof (guint32) + sizeof (GuppiSeqBooleanCore);
if (GUPPI_DATA_CLASS (parent_class)->get_size_in_bytes)
sib += GUPPI_DATA_CLASS (parent_class)->get_size_in_bytes (d);
return sib;
}
/***************************************************************************/
static void
guppi_seq_boolean_core_class_init (GuppiSeqBooleanCoreClass *klass)
{
GtkObjectClass *object_class = (GtkObjectClass *) klass;
GuppiDataClass *data_class = GUPPI_DATA_CLASS (klass);
GuppiSeqClass *seq_class = GUPPI_SEQ_CLASS (klass);
GuppiSeqBooleanClass *seq_boolean_class = GUPPI_SEQ_BOOLEAN_CLASS (klass);
parent_class = gtk_type_class (GUPPI_TYPE_SEQ_BOOLEAN);
object_class->finalize = guppi_seq_boolean_core_finalize;
seq_boolean_class->get = v_seq_boolean_get;
seq_boolean_class->set = v_seq_boolean_set;
seq_boolean_class->set_all = v_seq_boolean_set_all;
seq_boolean_class->set_many = v_seq_boolean_set_many;
seq_boolean_class->insert = v_seq_boolean_insert;
seq_boolean_class->insert_many = v_seq_boolean_insert_many;
seq_boolean_class->bitwise_and = v_seq_boolean_bitwise_and;
seq_boolean_class->bitwise_or = v_seq_boolean_bitwise_or;
seq_boolean_class->bitwise_xor = v_seq_boolean_bitwise_xor;
seq_boolean_class->bitwise_not = v_seq_boolean_bitwise_not;
seq_boolean_class->next_true = v_seq_boolean_next_true;
seq_boolean_class->true_count = v_seq_boolean_true_count;
seq_class->size_hint = v_seq_size_hint;
seq_class->get_bounds = v_seq_get_bounds;
seq_class->shift_indices = v_seq_shift_indices;
seq_class->insert_generic = v_seq_insert_generic;
seq_class->delete_many = v_seq_delete_many;
seq_class->support_missing_values = TRUE;
data_class->copy = v_data_copy;
data_class->get_size_in_bytes = v_data_size_in_bytes;
data_class->is_leaf_type = TRUE;
}
static void
guppi_seq_boolean_core_init (GuppiSeqBooleanCore *obj)
{
obj->index_basis = 0;
obj->size = 0;
obj->garray = guppi_garray_new (sizeof (guint32));
}
GtkType guppi_seq_boolean_core_get_type (void)
{
static GtkType guppi_seq_boolean_core_type = 0;
if (!guppi_seq_boolean_core_type) {
static const GtkTypeInfo guppi_seq_boolean_core_info = {
"GuppiSeqBooleanCore",
sizeof (GuppiSeqBooleanCore),
sizeof (GuppiSeqBooleanCoreClass),
(GtkClassInitFunc) guppi_seq_boolean_core_class_init,
(GtkObjectInitFunc) guppi_seq_boolean_core_init,
NULL, NULL, (GtkClassInitFunc) NULL
};
guppi_seq_boolean_core_type = gtk_type_unique (GUPPI_TYPE_SEQ_BOOLEAN,
&guppi_seq_boolean_core_info);
}
return guppi_seq_boolean_core_type;
}
GuppiSeqBoolean *
guppi_seq_boolean_core_new (void)
{
return GUPPI_SEQ_BOOLEAN (guppi_type_new (guppi_seq_boolean_core_get_type ()));
}
/* $Id: guppi-seq-boolean-core.c,v 1.1 2002/01/08 06:29:00 trow Exp $ */
syntax highlighted by Code2HTML, v. 0.9.1