mirror of
https://github.com/tcltk/tcl.git
synced 2026-05-29 00:27:49 +08:00
160 lines
4.1 KiB
C
160 lines
4.1 KiB
C
/*
|
||
* 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;
|
||
}
|
||
|
||
/*
|
||
* 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_ObjCmdProc2 TclStrIdxTreeTestObjCmd;
|
||
#endif
|
||
|
||
#endif /* _TCLSTRIDXTREE_H */
|