Debian Codegraph @

ext/sparse/spvec.h

raw
1 /*
2 * spvec.h - Sparse vector
3 *
4 * Copyright (c) 2009-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #ifndef GAUCHE_SPVEC_H
35 #define GAUCHE_SPVEC_H
36
37 #include <gauche.h>
38 #include <gauche/extend.h>
39
40 #if defined(EXTSPARSE_EXPORTS)
41 #define LIBGAUCHE_EXT_BODY
42 #endif
43 #include <gauche/extern.h> /* redefine SCM_EXTERN */
44
45 #include "ctrie.h"
46
47 typedef struct SparseVectorDescriptorRec SparseVectorDescriptor;
48
49 /* NB: All Scheme-level sparse vector classes use the single C-level
50 object, ScmSparseVector.
51
52 ScmSparseVector uses CompactTrie as a backing storage. The 'leaf'
53 of the CompactTrie may contain 1 to 16 elements of the vector,
54 depending on the type of the sparse vector.
55 */
56 typedef struct SparseVectorRec {
57 SCM_HEADER;
58 SparseVectorDescriptor *desc;
59 CompactTrie trie;
60 u_long numEntries;
61 u_long flags; /* reserved */
62 ScmObj defaultValue;
63 } SparseVector;
64
65 /* Iterator. */
66 typedef struct SparseVectorIterRec {
67 SparseVector *sv;
68 Leaf *leaf;
69 int leafIndex;
70 CompactTrieIter citer;
71 } SparseVectorIter;
72
73 /* SparseVectorDescriptor has common information per class (it should be
74 a part of each class, but we just hack for the time being.)
75 The constructor of each class sets appropriate descriptor to the instance.
76
77 ref(L,I) - Returns an element at index I in leaf L.
78 SCM_UNBOUND if the element doesn't exist.
79 set(L,I,X) - Sets X as a value at index I in leaf L. Returns TRUE
80 if that caused new element creation.
81 delete(L, I) - Deletes I-th entry. Returns the original value,
82 or SCM_UNBOUND if the entry wasn't exist.
83 clear(L,_) - Clears subtype-dependent part of the leaf structure.
84 iter(L,&I) - Returns the next object after I's index in the leaf L,
85 and updates I. SCM_UNBOUND if the next object is not in L.
86 I is intra-leaf index, not the vector-wide index.
87 dump(P,L,I,_) - Dumps leaf data.
88
89 The numEntries field is taken care of by generic routine.
90 */
91 struct SparseVectorDescriptorRec {
92 ScmObj (*ref)(Leaf*, u_long index);
93 int (*set)(Leaf*, u_long index, ScmObj value);
94 Leaf *(*allocate)(void *data);
95 ScmObj (*delete)(Leaf*, u_long index);
96 void (*clear)(Leaf*, void*);
97 Leaf *(*copy)(Leaf*, void*);
98 ScmObj (*iter)(Leaf*, int*);
99 void (*dump)(ScmPort *out, Leaf *leaf, int indent, void *data);
100
101 int shift; /* # of shift bits to access Leaf */
102 };
103
104 /* Max # of bits for index. Theoretrically we can extend this
105 as much as we like; current limitation is only for simplicity. */
106 #define SPARSE_VECTOR_MAX_INDEX_BITS (SIZEOF_LONG*8)
107
108 /* Flags for constructors (currently unused) */
109 enum {
110 SPARSE_VECTOR_ORDERED = (1L<<0)
111 };
112
113 /* Generic API. */
114 extern ScmObj MakeSparseVector(ScmClass *klass, ScmObj defaultValue, u_long flags);
115 extern ScmObj SparseVectorRef(SparseVector *sv, u_long index, ScmObj fallback);
116 extern void SparseVectorSet(SparseVector *sv, u_long index, ScmObj value);
117 extern ScmObj SparseVectorDelete(SparseVector *sv, u_long index);
118 extern void SparseVectorClear(SparseVector *sv);
119 extern ScmObj SparseVectorCopy(const SparseVector *src);
120 extern ScmObj SparseVectorInc(SparseVector *sv, u_long index, ScmObj delta,
121 ScmObj fallback);
122 extern void SparseVectorDump(SparseVector *sv);
123
124 extern void SparseVectorIterInit(SparseVectorIter *iter, SparseVector *sv);
125 extern ScmObj SparseVectorIterNext(SparseVectorIter *iter);
126
127 extern void Scm_Init_spvec(ScmModule *mod);
128
129 /*
130 * Class stuff
131 */
132 SCM_CLASS_DECL(Scm_SparseVectorBaseClass);
133 #define SCM_CLASS_SPARSE_VECTOR_BASE (&Scm_SparseVectorBaseClass)
134 #define SPARSE_VECTOR_BASE_P(obj) SCM_ISA(obj, SCM_CLASS_SPARSE_VECTOR_BASE)
135
136 SCM_CLASS_DECL(Scm_SparseVectorClass);
137 #define SCM_CLASS_SPARSE_VECTOR (&Scm_SparseVectorClass)
138 #define SPARSE_VECTOR(obj) ((SparseVector*)(obj))
139 #define SPARSE_VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_VECTOR)
140
141 SCM_CLASS_DECL(Scm_SparseS8VectorClass);
142 #define SCM_CLASS_SPARSE_S8VECTOR (&Scm_SparseS8VectorClass)
143 #define SPARSE_S8VECTOR(obj) ((SparseVector*)(obj))
144 #define SPARSE_S8VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S8VECTOR)
145
146 SCM_CLASS_DECL(Scm_SparseU8VectorClass);
147 #define SCM_CLASS_SPARSE_U8VECTOR (&Scm_SparseU8VectorClass)
148 #define SPARSE_U8VECTOR(obj) ((SparseVector*)(obj))
149 #define SPARSE_U8VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U8VECTOR)
150
151 SCM_CLASS_DECL(Scm_SparseS16VectorClass);
152 #define SCM_CLASS_SPARSE_S16VECTOR (&Scm_SparseS16VectorClass)
153 #define SPARSE_S16VECTOR(obj) ((SparseVector*)(obj))
154 #define SPARSE_S16VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S16VECTOR)
155
156 SCM_CLASS_DECL(Scm_SparseU16VectorClass);
157 #define SCM_CLASS_SPARSE_U16VECTOR (&Scm_SparseU16VectorClass)
158 #define SPARSE_U16VECTOR(obj) ((SparseVector*)(obj))
159 #define SPARSE_U16VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U16VECTOR)
160
161 SCM_CLASS_DECL(Scm_SparseS32VectorClass);
162 #define SCM_CLASS_SPARSE_S32VECTOR (&Scm_SparseS32VectorClass)
163 #define SPARSE_S32VECTOR(obj) ((SparseVector*)(obj))
164 #define SPARSE_S32VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S32VECTOR)
165
166 SCM_CLASS_DECL(Scm_SparseU32VectorClass);
167 #define SCM_CLASS_SPARSE_U32VECTOR (&Scm_SparseU32VectorClass)
168 #define SPARSE_U32VECTOR(obj) ((SparseVector*)(obj))
169 #define SPARSE_U32VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U32VECTOR)
170
171 SCM_CLASS_DECL(Scm_SparseS64VectorClass);
172 #define SCM_CLASS_SPARSE_S64VECTOR (&Scm_SparseS64VectorClass)
173 #define SPARSE_S64VECTOR(obj) ((SparseVector*)(obj))
174 #define SPARSE_S64VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S64VECTOR)
175
176 SCM_CLASS_DECL(Scm_SparseU64VectorClass);
177 #define SCM_CLASS_SPARSE_U64VECTOR (&Scm_SparseU64VectorClass)
178 #define SPARSE_U64VECTOR(obj) ((SparseVector*)(obj))
179 #define SPARSE_U64VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U64VECTOR)
180
181 SCM_CLASS_DECL(Scm_SparseF16VectorClass);
182 #define SCM_CLASS_SPARSE_F16VECTOR (&Scm_SparseF16VectorClass)
183 #define SPARSE_F16VECTOR(obj) ((SparseVector*)(obj))
184 #define SPARSE_F16VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F16VECTOR)
185
186 SCM_CLASS_DECL(Scm_SparseF32VectorClass);
187 #define SCM_CLASS_SPARSE_F32VECTOR (&Scm_SparseF32VectorClass)
188 #define SPARSE_F32VECTOR(obj) ((SparseVector*)(obj))
189 #define SPARSE_F32VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F32VECTOR)
190
191 SCM_CLASS_DECL(Scm_SparseF64VectorClass);
192 #define SCM_CLASS_SPARSE_F64VECTOR (&Scm_SparseF64VectorClass)
193 #define SPARSE_F64VECTOR(obj) ((SparseVector*)(obj))
194 #define SPARSE_F64VECTOR_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F64VECTOR)
195
196 SCM_CLASS_DECL(Scm_SparseMatrixBaseClass);
197 #define SCM_CLASS_SPARSE_MATRIX_BASE (&Scm_SparseMatrixBaseClass)
198 #define SPARSE_MATRIX_BASE_P(obj) SCM_ISA(obj, SCM_CLASS_SPARSE_MATRIX_BASE)
199
200 SCM_CLASS_DECL(Scm_SparseMatrixClass);
201 #define SCM_CLASS_SPARSE_MATRIX (&Scm_SparseMatrixClass)
202 #define SPARSE_MATRIX(obj) ((SparseVector*)(obj))
203 #define SPARSE_MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_MATRIX)
204
205 SCM_CLASS_DECL(Scm_SparseS8MatrixClass);
206 #define SCM_CLASS_SPARSE_S8MATRIX (&Scm_SparseS8MatrixClass)
207 #define SPARSE_S8MATRIX(obj) ((SparseVector*)(obj))
208 #define SPARSE_S8MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S8MATRIX)
209
210 SCM_CLASS_DECL(Scm_SparseU8MatrixClass);
211 #define SCM_CLASS_SPARSE_U8MATRIX (&Scm_SparseU8MatrixClass)
212 #define SPARSE_U8MATRIX(obj) ((SparseVector*)(obj))
213 #define SPARSE_U8MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U8MATRIX)
214
215 SCM_CLASS_DECL(Scm_SparseS16MatrixClass);
216 #define SCM_CLASS_SPARSE_S16MATRIX (&Scm_SparseS16MatrixClass)
217 #define SPARSE_S16MATRIX(obj) ((SparseVector*)(obj))
218 #define SPARSE_S16MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S16MATRIX)
219
220 SCM_CLASS_DECL(Scm_SparseU16MatrixClass);
221 #define SCM_CLASS_SPARSE_U16MATRIX (&Scm_SparseU16MatrixClass)
222 #define SPARSE_U16MATRIX(obj) ((SparseVector*)(obj))
223 #define SPARSE_U16MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U16MATRIX)
224
225 SCM_CLASS_DECL(Scm_SparseS32MatrixClass);
226 #define SCM_CLASS_SPARSE_S32MATRIX (&Scm_SparseS32MatrixClass)
227 #define SPARSE_S32MATRIX(obj) ((SparseVector*)(obj))
228 #define SPARSE_S32MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S32MATRIX)
229
230 SCM_CLASS_DECL(Scm_SparseU32MatrixClass);
231 #define SCM_CLASS_SPARSE_U32MATRIX (&Scm_SparseU32MatrixClass)
232 #define SPARSE_U32MATRIX(obj) ((SparseVector*)(obj))
233 #define SPARSE_U32MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U32MATRIX)
234
235 SCM_CLASS_DECL(Scm_SparseS64MatrixClass);
236 #define SCM_CLASS_SPARSE_S64MATRIX (&Scm_SparseS64MatrixClass)
237 #define SPARSE_S64MATRIX(obj) ((SparseVector*)(obj))
238 #define SPARSE_S64MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_S64MATRIX)
239
240 SCM_CLASS_DECL(Scm_SparseU64MatrixClass);
241 #define SCM_CLASS_SPARSE_U64MATRIX (&Scm_SparseU64MatrixClass)
242 #define SPARSE_U64MATRIX(obj) ((SparseVector*)(obj))
243 #define SPARSE_U64MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_U64MATRIX)
244
245 SCM_CLASS_DECL(Scm_SparseF16MatrixClass);
246 #define SCM_CLASS_SPARSE_F16MATRIX (&Scm_SparseF16MatrixClass)
247 #define SPARSE_F16MATRIX(obj) ((SparseVector*)(obj))
248 #define SPARSE_F16MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F16MATRIX)
249
250 SCM_CLASS_DECL(Scm_SparseF32MatrixClass);
251 #define SCM_CLASS_SPARSE_F32MATRIX (&Scm_SparseF32MatrixClass)
252 #define SPARSE_F32MATRIX(obj) ((SparseVector*)(obj))
253 #define SPARSE_F32MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F32MATRIX)
254
255 SCM_CLASS_DECL(Scm_SparseF64MatrixClass);
256 #define SCM_CLASS_SPARSE_F64MATRIX (&Scm_SparseF64MatrixClass)
257 #define SPARSE_F64MATRIX(obj) ((SparseVector*)(obj))
258 #define SPARSE_F64MATRIX_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SPARSE_F64MATRIX)
259
260 #endif /*GAUCHE_SPVEC_H*/