Initial commit

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