1 /* treemap.h -*- coding: utf-8 -*- 2 * 3 * Copyright (c) 2010-2021 Takashi Kato <ktakashi@ymail.com> 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * $Id: $ 29 */ 30 #ifndef SAGITTARIUS_PRIVATE_TREEMAP_H_ 31 #define SAGITTARIUS_PRIVATE_TREEMAP_H_ 32 33 #include "sagittariusdefs.h" 34 #include "collection.h" 35 36 /* For C use compare function */ 37 typedef SgDictEntry SgTreeEntry; 38 typedef int SgTreeCompareProc(SgTreeMap *, intptr_t, intptr_t); 39 typedef SgTreeEntry* SgTreeRefProc(SgTreeMap *, intptr_t); 40 typedef SgTreeEntry* SgTreeSearchProc(SgTreeMap *, intptr_t, SgDictOp); 41 typedef SgObject SgTreeCopyProc(const SgTreeMap *); 42 43 /* only for c */ 44 typedef struct SgTreeIterRec SgTreeIter; 45 typedef SgTreeIter* SgTreeIterInitProc(SgTreeIter *, SgTreeMap *, 46 SgTreeEntry *, int ascP); 47 48 /* 49 header: 50 ........ ........ .....S.. ....0111 : S: Scheme 51 */ 52 struct SgTreeMapRec 53 { 54 SG_HEADER; 55 /* These are could be Scheme object or C pointer */ 56 intptr_t root; 57 int entryCount; 58 int schemep; 59 union { 60 struct { 61 SgTreeCompareProc *cmp; 62 SgTreeSearchProc *search; 63 SgTreeCopyProc *copy; 64 SgTreeIterInitProc *iter; 65 /* NavigationMap (optional)*/ 66 SgTreeRefProc *higher; 67 SgTreeRefProc *lower; 68 } c; 69 /* for now we don't support this */ 70 #if 0 71 struct { 72 SgObject cmp; 73 SgObject search; 74 SgObject copy; 75 /* NavigationMap (optional)*/ 76 SgObject higher; 77 SgObject lower; 78 } scm; 79 #endif 80 } procs; 81 void *data; 82 }; 83 84 SG_CLASS_DECL(Sg_TreeMapClass); 85 #define SG_CLASS_TREE_MAP (&Sg_TreeMapClass) 86 87 #define SG_TREEMAP_PROC(__tc, __type, __proc) \ 88 (SG_TREEMAP(__tc)->procs.__type.__proc) 89 90 #define SG_TREEMAP_C_PROC(__tc, __proc) \ 91 SG_TREEMAP_PROC(__tc, c, __proc) 92 93 #define SG_TREEMAP_SCM_PROC(__tc, __proc) \ 94 SG_TREEMAP_PROC(__tc, scm, __proc) 95 96 /* this is not Scheme object */ 97 struct SgTreeIterRec 98 { 99 SgTreeMap *t; 100 SgTreeEntry *e; /* current entry of this iterator */ 101 int end; /* if this iterator is at end or not */ 102 /* for scalabilty */ 103 SgTreeEntry* (*next)(SgTreeIter *); 104 }; 105 106 enum SgTreeFlags{ 107 SG_TREE_NO_OVERWRITE = (1L<<0), /* do not overwrite the existing entry */ 108 SG_TREE_NO_CREATE = (1L<<1) /* do not create new one if no match */ 109 }; 110 111 #define SG_TREEMAP(obj) ((SgTreeMap*)obj) 112 #define SG_TREEMAP_P(obj) SG_XTYPEP(obj, SG_CLASS_TREE_MAP) 113 #define SG_SCHEME_TREEMAP_P(obj) \ 114 (SG_TREEMAP_P(obj) && SG_TREEMAP(obj)->schemep) 115 116 SG_CDECL_BEGIN 117 118 /* C APIs */ 119 SG_EXTERN SgTreeEntry* Sg_TreeMapCoreSearch(SgTreeMap *tm, intptr_t key, 120 SgDictOp op, int flags); 121 SG_EXTERN SgObject Sg_MakeDefaultTreeMap(SgTreeCompareProc *cmp); 122 SG_EXTERN SgObject Sg_TreeMapCopy(const SgTreeMap *src); 123 SG_EXTERN SgObject Sg_TreeMapRef(SgTreeMap *tm, SgObject key, 124 SgObject fallback); 125 SG_EXTERN SgObject Sg_TreeMapSet(SgTreeMap *tm, SgObject key, SgObject value, 126 int flags); 127 SG_EXTERN SgObject Sg_TreeMapDelete(SgTreeMap *tm, SgObject key); 128 SG_EXTERN void Sg_TreeMapClear(SgTreeMap *tm); 129 130 /* generic constructors */ 131 SG_EXTERN SgObject Sg_MakeGenericCTreeMap(SgTreeCompareProc *cmp, 132 SgTreeSearchProc *search, 133 SgTreeCopyProc *copy, 134 SgTreeIterInitProc *iter, 135 SgTreeRefProc *higher, 136 SgTreeRefProc *lower, 137 void *data); 138 /* for now not supported */ 139 /* 140 SG_EXTERN SgObject Sg_MakeGenericSchemeTreeMap(SgObject cmp, 141 SgObject search, 142 SgObject copy); 143 */ 144 145 /* iterator these APIs are only for C */ 146 SG_EXTERN void Sg_TreeIterInit(SgTreeIter *iter, 147 SgTreeMap *tm, SgTreeEntry *start); 148 SG_EXTERN void Sg_TreeReverseIterInit(SgTreeIter *iter, 149 SgTreeMap *tm, 150 SgTreeEntry *start); 151 SG_EXTERN SgTreeEntry* Sg_TreeIterNext(SgTreeIter *iter); 152 SG_EXTERN int Sg_TreeIterHasNext(SgTreeIter *iter); 153 SG_EXTERN SgObject Sg_TreeMapEntries(SgTreeMap *tm); 154 SG_EXTERN SgObject Sg_TreeMapKeys(SgTreeMap *tm); 155 SG_EXTERN SgObject Sg_TreeMapValues(SgTreeMap *tm); 156 157 SG_EXTERN SgTreeEntry* Sg_TreeMapHigherEntry(SgTreeMap *tm, SgObject key); 158 SG_EXTERN SgTreeEntry* Sg_TreeMapLowerEntry(SgTreeMap *tm, SgObject key); 159 SG_EXTERN SgTreeEntry* Sg_TreeMapFirstEntry(SgTreeMap *tm); 160 SG_EXTERN SgTreeEntry* Sg_TreeMapLastEntry(SgTreeMap *tm); 161 162 /* Supported implementation tree constructors */ 163 SG_EXTERN SgObject Sg_MakeRBTreeMap(SgTreeCompareProc *cmp); 164 SG_EXTERN SgObject Sg_MakeSchemeRBTreeMap(SgObject cmp); 165 166 /* common procedures(only C) */ 167 SG_EXTERN int Sg_TreeMapEq(SgTreeMap *a, SgTreeMap *b); 168 169 SG_CDECL_END 170 171 #endif /* SAGITTARIUS_TREEMAP_HPP_ */ 172