summaryrefslogtreecommitdiff
path: root/dviware/catdvi/sparse.h
diff options
context:
space:
mode:
Diffstat (limited to 'dviware/catdvi/sparse.h')
-rw-r--r--dviware/catdvi/sparse.h161
1 files changed, 161 insertions, 0 deletions
diff --git a/dviware/catdvi/sparse.h b/dviware/catdvi/sparse.h
new file mode 100644
index 0000000000..4d924de6cd
--- /dev/null
+++ b/dviware/catdvi/sparse.h
@@ -0,0 +1,161 @@
+/* catdvi - get text from DVI files
+ Copyright (C) 2001, 2002 Bjoern Brill <brill@fs.math.uni-frankfurt.de>
+
+ 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., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#ifndef SPARSE_H
+#define SPARSE_H
+
+/* Implements "sparse arrays" of void * and sint32.
+ *
+ * The assigned entries are stored as the leaves of a dynamically growing
+ * (2^SPAR_BITS_PER_STAGE)-ary tree. Branches not leading to an assigned
+ * entry are not created, and looking them up returns a default value.
+ *
+ * Two structures with accompanying methods are defined,
+ * sparp_t (for void *) and spars32_t (for sint32). Almost all of the code
+ * is shared and factored out into a common "base class" spar_t.
+ *
+ * Note sparp_t is not at all interested in what the void *'s it holds
+ * may point to.
+ *
+ * The default value is NULL in the case of void * and settable in the
+ * constructor call in the case of sint32.
+ */
+
+#include "bytesex.h" /* for sint32, uint32 */
+
+/******************************* spar_t *******************************/
+typedef uint32 spar_index_t;
+ /* Could be changed to any unsigned integral type */
+
+#define SPAR_BITS_PER_STAGE 8
+ /* Configurable. Need not divide (bits per spar_index_t) */
+
+typedef union spar_node_t {
+ union spar_node_t * children;
+ /* payload */
+ void * p;
+ sint32 s32;
+} spar_node_t;
+
+typedef struct spar_t {
+ int height;
+ int max_shift;
+ spar_index_t max_index;
+ spar_node_t root;
+ spar_node_t default_leaf;
+} spar_t;
+
+/* constructor */
+void spar_init(spar_t * this, spar_node_t default_entry);
+
+/* destructor */
+void spar_done(spar_t * this);
+
+/* Get pointer to const leaf node (array entry) with index i.
+ * Returns pointer to some node with default value if unassigned.
+ */
+const spar_node_t * spar_const_entry(const spar_t * this, spar_index_t i);
+
+/* Get pointer to leaf node (array entry) with index i, creating it
+ * if necessary. Newly created nodes have the default value. The pointer
+ * target is assignable.
+ *
+ * Consecutive calls to this function (and to spar_const_entry()) with
+ * the same arguments will always return the same address.
+ */
+spar_node_t * spar_assignable_entry(spar_t * this, spar_index_t i);
+
+/******************************* sparp_t *******************************/
+typedef spar_index_t sparp_index_t;
+
+typedef struct sparp_t {
+ spar_t p_spar;
+} sparp_t;
+
+/* constructor */
+void sparp_init(sparp_t * this);
+
+/* destructor */
+void sparp_done(sparp_t * this);
+
+/* Read array entry with index i.
+ * This behaves like a function with prototype
+ * void * sparp_read(sparp_t * this, sparp_index_t i);
+ */
+#define sparp_read(this, i) (spar_const_entry(&((this)->p_spar), i)->p)
+
+/* Write array entry with index i.
+ * This behaves like a function with prototype
+ * void sparp_write(sparp_t * this, sparp_index_t i, void * v);
+ */
+#define sparp_write(this, i, v) \
+ ((void) (spar_assignable_entry(&((this)->p_spar), i)->p = v))
+
+/* Get pointer to array entry with index i, creating it
+ * if necessary. Newly created entries have value NULL. The pointer
+ * target is assignable.
+ *
+ * Consecutive calls to this function with
+ * the same arguments will always return the same address.
+ *
+ * This behaves like a function with prototype
+ * void ** sparp_assignable_entry(sparp_t * this, sparp_index_t i);
+ */
+#define sparp_assignable_entry(this, i) \
+ (&(spar_assignable_entry(&((this)->p_spar), i)->p))
+
+/******************************* spars32_t *******************************/
+typedef spar_index_t spars32_index_t;
+
+typedef struct spars32_t {
+ spar_t s32_spar;
+} spars32_t;
+
+/* constructor */
+void spars32_init(spars32_t * this, sint32 default_value);
+
+/* destructor */
+void spars32_done(spars32_t * this);
+
+/* Read array entry with index i.
+ * This behaves like a function with prototype
+ * sint32 spars32_read(spars32_t * this, spars32_index_t i);
+ */
+#define spars32_read(this, i) (spar_const_entry(&((this)->s32_spar), i)->s32)
+
+/* Write array entry with index i.
+ * This behaves like a function with prototype
+ * void spars32_write(spars32_t * this, spars32_index_t i, sint32 v);
+ */
+#define spars32_write(this, i, v) \
+ ((void) (spar_assignable_entry(&((this)->s32_spar), i)->s32 = v))
+
+/* Get pointer to array entry with index i, creating it
+ * if necessary. Newly created entries have default value. The pointer
+ * target is assignable.
+ *
+ * Consecutive calls to this function with
+ * the same arguments will always return the same address.
+ *
+ * This behaves like a function with prototype
+ * sint32* spars32_assignable_entry(spars32_t * this, spars32_index_t i);
+ */
+#define spars32_assignable_entry(this, i) \
+ (&(spar_assignable_entry(&((this)->s32_spar), i)->s32))
+
+#endif