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
|
/*
* tclStrIdxTree.h --
*
* Declarations of string index tries and other primitives currently
* back-ported from tclSE.
*
* Copyright (c) 2016 Serg G. Brester (aka sebres)
*
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*/
#ifndef _TCLSTRIDXTREE_H
#define _TCLSTRIDXTREE_H
#include "tclInt.h"
/*
* Main structures declarations of index tree and entry
*/
typedef struct TclStrIdx TclStrIdx;
/*
* Top level structure of the tree, or first two fields of the interior
* structure.
*
* Note that this is EXACTLY two pointers so it is the same size as the
* twoPtrValue of a Tcl_ObjInternalRep. This is how the top level structure
* of the tree is always allocated. (This type constraint is asserted in
* TclStrIdxTreeNewObj() so it's guaranteed.)
*
* Also note that if firstPtr is not NULL, lastPtr must also be not NULL.
* The case where firstPtr is not NULL and lastPtr is NULL is special (a
* smart pointer to one of these) and is not actually a valid instance of
* this structure.
*/
typedef struct TclStrIdxTree {
TclStrIdx *firstPtr;
TclStrIdx *lastPtr;
} TclStrIdxTree;
/*
* An interior node of the tree. Always directly allocated.
*/
struct TclStrIdx {
TclStrIdxTree childTree;
TclStrIdx *nextPtr;
TclStrIdx *prevPtr;
Tcl_Obj *key;
Tcl_Size length;
void *value;
};
/*
*----------------------------------------------------------------------
*
* TclUtfFindEqual, TclUtfFindEqualNC --
*
* Find largest part of string cs in string cin (case sensitive and not).
*
* Results:
* Return position of UTF character in cs after last equal character.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static inline const char *
TclUtfFindEqual(
const char *cs, /* UTF string to find in cin. */
const char *cse, /* End of cs */
const char *cin, /* UTF string will be browsed. */
const char *cine) /* End of cin */
{
const char *ret = cs;
Tcl_UniChar ch1, ch2;
do {
cs += TclUtfToUniChar(cs, &ch1);
cin += TclUtfToUniChar(cin, &ch2);
if (ch1 != ch2) {
break;
}
} while ((ret = cs) < cse && cin < cine);
return ret;
}
static inline const char *
TclUtfFindEqualNC(
const char *cs, /* UTF string to find in cin. */
const char *cse, /* End of cs */
const char *cin, /* UTF string will be browsed. */
const char *cine, /* End of cin */
const char **cinfnd) /* Return position in cin */
{
const char *ret = cs;
Tcl_UniChar ch1, ch2;
do {
cs += TclUtfToUniChar(cs, &ch1);
cin += TclUtfToUniChar(cin, &ch2);
if (ch1 != ch2) {
ch1 = Tcl_UniCharToLower(ch1);
ch2 = Tcl_UniCharToLower(ch2);
if (ch1 != ch2) {
break;
}
}
*cinfnd = cin;
} while ((ret = cs) < cse && cin < cine);
return ret;
}
static inline const char *
TclUtfFindEqualNCInLwr(
const char *cs, /* UTF string (in anycase) to find in cin. */
const char *cse, /* End of cs */
const char *cin, /* UTF string (in lowercase) will be browsed. */
const char *cine, /* End of cin */
const char **cinfnd) /* Return position in cin */
{
const char *ret = cs;
Tcl_UniChar ch1, ch2;
do {
cs += TclUtfToUniChar(cs, &ch1);
cin += TclUtfToUniChar(cin, &ch2);
if (ch1 != ch2) {
ch1 = Tcl_UniCharToLower(ch1);
if (ch1 != ch2) {
break;
}
}
*cinfnd = cin;
} while ((ret = cs) < cse && cin < cine);
return ret;
}
/*
* Primitives to safe set, reset and free references.
*/
#define TclUnsetObjRef(obj) \
do { \
if (obj != NULL) { \
Tcl_DecrRefCount(obj); \
obj = NULL; \
} \
} while (0)
#define TclInitObjRef(obj, val) \
do { \
obj = (val); \
if (obj) { \
Tcl_IncrRefCount(obj); \
} \
} while (0)
#define TclSetObjRef(obj, val) \
do { \
Tcl_Obj *nval = (val); \
if (obj != nval) { \
Tcl_Obj *prev = obj; \
TclInitObjRef(obj, nval); \
if (prev != NULL) { \
Tcl_DecrRefCount(prev); \
} \
} \
} while (0)
/*
* Prototypes of module functions.
*/
MODULE_SCOPE const char*TclStrIdxTreeSearch(TclStrIdxTree **foundParent,
TclStrIdx **foundItem, TclStrIdxTree *tree,
const char *start, const char *end);
MODULE_SCOPE int TclStrIdxTreeBuildFromList(TclStrIdxTree *idxTree,
Tcl_Size lstc, Tcl_Obj **lstv, void **values);
MODULE_SCOPE Tcl_Obj * TclStrIdxTreeNewObj(void);
MODULE_SCOPE TclStrIdxTree*TclStrIdxTreeGetFromObj(Tcl_Obj *objPtr);
#ifdef TEST_STR_IDX_TREE
/* currently unused, debug resp. test purposes only */
MODULE_SCOPE Tcl_ObjCmdProc TclStrIdxTreeTestObjCmd;
#endif
#endif /* _TCLSTRIDXTREE_H */
|
