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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
|
/*
* spvec.h - Sparse vector
*
* Copyright (c) 2009-2020 Shiro Kawai <shiro@acm.org>
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* 3. Neither the name of the authors nor the names of its contributors
* may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef GAUCHE_SPVEC_H
#define GAUCHE_SPVEC_H
#include <gauche.h>
#include <gauche/extend.h>
#if defined(EXTSPARSE_EXPORTS)
#define LIBGAUCHE_EXT_BODY
#endif
#include <gauche/extern.h> /* redefine SCM_EXTERN */
#include "ctrie.h"
typedef struct SparseVectorDescriptorRec SparseVectorDescriptor;
/* NB: All Scheme-level sparse vector classes use the single C-level
object, ScmSparseVector.
ScmSparseVector uses CompactTrie as a backing storage. The 'leaf'
of the CompactTrie may contain 1 to 16 elements of the vector,
depending on the type of the sparse vector.
*/
typedef struct SparseVectorRec {
SCM_HEADER;
SparseVectorDescriptor *desc;
CompactTrie trie;
u_long numEntries;
u_long flags; /* reserved */
ScmObj defaultValue;
} SparseVector;
/* Iterator. */
typedef struct SparseVectorIterRec {
SparseVector *sv;
Leaf *leaf;
int leafIndex;
CompactTrieIter citer;
} SparseVectorIter;
/* SparseVectorDescriptor has common information per class (it should be
a part of each class, but we just hack for the time being.)
The constructor of each class sets appropriate descriptor to the instance.
ref(L,I) - Returns an element at index I in leaf L.
SCM_UNBOUND if the element doesn't exist.
set(L,I,X) - Sets X as a value at index I in leaf L. Returns TRUE
if that caused new element creation.
delete(L, I) - Deletes I-th entry. Returns the original value,
or SCM_UNBOUND if the entry wasn't exist.
clear(L,_) - Clears subtype-dependent part of the leaf structure.
iter(L,&I) - Returns the next object after I's index in the leaf L,
and updates I. SCM_UNBOUND if the next object is not in L.
I is intra-leaf index, not the vector-wide index.
dump(P,L,I,_) - Dumps leaf data.
The numEntries field is taken care of by generic routine.
*/
struct SparseVectorDescriptorRec {
ScmObj (*ref)(Leaf*, u_long index);
int (*set)(Leaf*, u_long index, ScmObj value);
Leaf *(*allocate)(void *data);
ScmObj (*delete)(Leaf*, u_long index);
void (*clear)(Leaf*, void*);
Leaf *(*copy)(Leaf*, void*);
ScmObj (*iter)(Leaf*, int*);
void (*dump)(ScmPort *out, Leaf *leaf, int indent, void *data);
int shift; /* # of shift bits to access Leaf */
};
/* Max # of bits for index. Theoretrically we can extend this
as much as we like; current limitation is only for simplicity. */
#define SPARSE_VECTOR_MAX_INDEX_BITS (SIZEOF_LONG*8)
/* Flags for constructors (currently unused) */
enum {
SPARSE_VECTOR_ORDERED = (1L<<0)
};
/* Generic API. */
extern ScmObj MakeSparseVector(ScmClass *klass, ScmObj defaultValue, u_long flags);
extern ScmObj SparseVectorRef(SparseVector *sv, u_long index, ScmObj fallback);
extern void SparseVectorSet(SparseVector *sv, u_long index, ScmObj value);
extern ScmObj SparseVectorDelete(SparseVector *sv, u_long index);
extern void SparseVectorClear(SparseVector *sv);
extern ScmObj SparseVectorCopy(const SparseVector *src);
extern ScmObj SparseVectorInc(SparseVector *sv, u_long index, ScmObj delta,
ScmObj fallback);
extern void SparseVectorDump(SparseVector *sv);
extern void SparseVectorIterInit(SparseVectorIter *iter, SparseVector *sv);
extern ScmObj SparseVectorIterNext(SparseVectorIter *iter);
extern void Scm_Init_spvec(ScmModule *mod);
/*
* Class stuff
*/
SCM_CLASS_DECL(Scm_SparseVectorBaseClass);
#define SCM_CLASS_SPARSE_VECTOR_BASE (&Scm_SparseVectorBaseClass)
#define SPARSE_VECTOR_BASE_P(obj) SCM_ISA(obj, SCM_CLASS_SPARSE_VECTOR_BASE)
SCM_CLASS_DECL(Scm_SparseVectorClass);
#define SCM_CLASS_SPARSE_VECTOR (&Scm_SparseVectorClass)
#define SPARSE_VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_VECTOR)
SCM_CLASS_DECL(Scm_SparseS8VectorClass);
#define SCM_CLASS_SPARSE_S8VECTOR (&Scm_SparseS8VectorClass)
#define SPARSE_S8VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_S8VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S8VECTOR)
SCM_CLASS_DECL(Scm_SparseU8VectorClass);
#define SCM_CLASS_SPARSE_U8VECTOR (&Scm_SparseU8VectorClass)
#define SPARSE_U8VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_U8VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U8VECTOR)
SCM_CLASS_DECL(Scm_SparseS16VectorClass);
#define SCM_CLASS_SPARSE_S16VECTOR (&Scm_SparseS16VectorClass)
#define SPARSE_S16VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_S16VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S16VECTOR)
SCM_CLASS_DECL(Scm_SparseU16VectorClass);
#define SCM_CLASS_SPARSE_U16VECTOR (&Scm_SparseU16VectorClass)
#define SPARSE_U16VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_U16VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U16VECTOR)
SCM_CLASS_DECL(Scm_SparseS32VectorClass);
#define SCM_CLASS_SPARSE_S32VECTOR (&Scm_SparseS32VectorClass)
#define SPARSE_S32VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_S32VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S32VECTOR)
SCM_CLASS_DECL(Scm_SparseU32VectorClass);
#define SCM_CLASS_SPARSE_U32VECTOR (&Scm_SparseU32VectorClass)
#define SPARSE_U32VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_U32VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U32VECTOR)
SCM_CLASS_DECL(Scm_SparseS64VectorClass);
#define SCM_CLASS_SPARSE_S64VECTOR (&Scm_SparseS64VectorClass)
#define SPARSE_S64VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_S64VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S64VECTOR)
SCM_CLASS_DECL(Scm_SparseU64VectorClass);
#define SCM_CLASS_SPARSE_U64VECTOR (&Scm_SparseU64VectorClass)
#define SPARSE_U64VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_U64VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U64VECTOR)
SCM_CLASS_DECL(Scm_SparseF16VectorClass);
#define SCM_CLASS_SPARSE_F16VECTOR (&Scm_SparseF16VectorClass)
#define SPARSE_F16VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_F16VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F16VECTOR)
SCM_CLASS_DECL(Scm_SparseF32VectorClass);
#define SCM_CLASS_SPARSE_F32VECTOR (&Scm_SparseF32VectorClass)
#define SPARSE_F32VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_F32VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F32VECTOR)
SCM_CLASS_DECL(Scm_SparseF64VectorClass);
#define SCM_CLASS_SPARSE_F64VECTOR (&Scm_SparseF64VectorClass)
#define SPARSE_F64VECTOR(obj) ((SparseVector*)(obj))
#define SPARSE_F64VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F64VECTOR)
SCM_CLASS_DECL(Scm_SparseMatrixBaseClass);
#define SCM_CLASS_SPARSE_MATRIX_BASE (&Scm_SparseMatrixBaseClass)
#define SPARSE_MATRIX_BASE_P(obj) SCM_ISA(obj, SCM_CLASS_SPARSE_MATRIX_BASE)
SCM_CLASS_DECL(Scm_SparseMatrixClass);
#define SCM_CLASS_SPARSE_MATRIX (&Scm_SparseMatrixClass)
#define SPARSE_MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_MATRIX)
SCM_CLASS_DECL(Scm_SparseS8MatrixClass);
#define SCM_CLASS_SPARSE_S8MATRIX (&Scm_SparseS8MatrixClass)
#define SPARSE_S8MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_S8MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S8MATRIX)
SCM_CLASS_DECL(Scm_SparseU8MatrixClass);
#define SCM_CLASS_SPARSE_U8MATRIX (&Scm_SparseU8MatrixClass)
#define SPARSE_U8MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_U8MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U8MATRIX)
SCM_CLASS_DECL(Scm_SparseS16MatrixClass);
#define SCM_CLASS_SPARSE_S16MATRIX (&Scm_SparseS16MatrixClass)
#define SPARSE_S16MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_S16MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S16MATRIX)
SCM_CLASS_DECL(Scm_SparseU16MatrixClass);
#define SCM_CLASS_SPARSE_U16MATRIX (&Scm_SparseU16MatrixClass)
#define SPARSE_U16MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_U16MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U16MATRIX)
SCM_CLASS_DECL(Scm_SparseS32MatrixClass);
#define SCM_CLASS_SPARSE_S32MATRIX (&Scm_SparseS32MatrixClass)
#define SPARSE_S32MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_S32MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S32MATRIX)
SCM_CLASS_DECL(Scm_SparseU32MatrixClass);
#define SCM_CLASS_SPARSE_U32MATRIX (&Scm_SparseU32MatrixClass)
#define SPARSE_U32MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_U32MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U32MATRIX)
SCM_CLASS_DECL(Scm_SparseS64MatrixClass);
#define SCM_CLASS_SPARSE_S64MATRIX (&Scm_SparseS64MatrixClass)
#define SPARSE_S64MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_S64MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S64MATRIX)
SCM_CLASS_DECL(Scm_SparseU64MatrixClass);
#define SCM_CLASS_SPARSE_U64MATRIX (&Scm_SparseU64MatrixClass)
#define SPARSE_U64MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_U64MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U64MATRIX)
SCM_CLASS_DECL(Scm_SparseF16MatrixClass);
#define SCM_CLASS_SPARSE_F16MATRIX (&Scm_SparseF16MatrixClass)
#define SPARSE_F16MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_F16MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F16MATRIX)
SCM_CLASS_DECL(Scm_SparseF32MatrixClass);
#define SCM_CLASS_SPARSE_F32MATRIX (&Scm_SparseF32MatrixClass)
#define SPARSE_F32MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_F32MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F32MATRIX)
SCM_CLASS_DECL(Scm_SparseF64MatrixClass);
#define SCM_CLASS_SPARSE_F64MATRIX (&Scm_SparseF64MatrixClass)
#define SPARSE_F64MATRIX(obj) ((SparseVector*)(obj))
#define SPARSE_F64MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F64MATRIX)
#endif /*GAUCHE_SPVEC_H*/
|
