1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
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
|
