/* 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 and * Havoc Pennington . * * 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 #include "guppi-seq-boolean-core.h" #include #include #include #include #include #include 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 $ */