/* * spvec.h - Sparse vector * * Copyright (c) 2009-2024 Shiro Kawai * * 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 #include #if defined(EXTSPARSE_EXPORTS) #define LIBGAUCHE_EXT_BODY #endif #include /* 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*/