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