| top | |  1 ::
Generic interface to associative maps.
Copyright (C) 2002, 2004 SM Ryan
Wyrmwif Tcl extensions. For non-profit uses only,
provided this copyright is preserved on all copies, this work
may be freely copied, modified, redistributed, compiled, and
incorporated in other works. This work is distributed with
no warranty of any kind; no author or distributor accepts any
responsibility for the consequences of using it, or for whether
it serves any particular purpose or works at all, unless he
or she says so in writing.
| ^ | | | | section top | | | ^ | | | | | | section top | | 3. Associative map type ::
The string representation of an associative map is a one element or even numberred element
list. The internal representation is specific to the map implementation. The object type
is a pointer to the WyrmAssocMapType structure for the implementation
which includes the Tcl object type as a prefix. The type name
always begins with "wyrm.assoc. ...".
wyrm-assoc does not implement a mapping itself.
Rather it provides a common interface to the variety of implementations.
Properties of associative mappings:
- Internal or external.
-
An internal mapping exist only memory and one process;
an external mapping is in file and can be shared by other processes.
- String representation.
-
An internal mapping string representation of an even number of elements;
an external mapping string representation is a one element list which is the file path.
- Entries.
-
A mapping has zero or more entries. An entry is a unique key string, a data string,
and flags packed into an integer. The string representation of an internal mapping
is a list of key-value pairs. If an element has nonzero flags, that is included
in the string representation with the pseudo key '[]'.
- Sorting and Traversal.
-
A mapping can be unsorted, sorted, or sorted and reverse sorted.
A nonempty sorted mapping has a first and last key. Given any key except the
last key, a sorted mapping can return the next key; a reverse sorted mapping
can also give the previous key of any key except the first. An sorted mapping
can find approximate keys: the greatest key, if any, less than or equal a given key,
otherwise the first key. Unsorted mappings do not have to define first, last, next,
and previous keys, but if they do, first-next-last must
traverse all keys in an implementation defined order; if previous is defined,
last-previous-first must also traverse all keys.
- Enumeration.
-
Sorted and unsorted mappings must provide an enumerator of all the elements.
(Sorting mappings may use a generic first-next-last enumeration.)
During an enumeration only the enumerate and enumerateEnd methods will be called;
the mapping is allowed to place itself in a special enumeration state that
is incompatiable with normal operations.
- Modifiable.
-
Internal mappings are modifiable. External mappings can be modifiable
or read only, depending on the implementation and how the mapping is
created.
- type struct WyrmAssocMapType—Associative map type
| - type struct tcl—Tcl object type
| - chars name—Type name, must begin with "wyrm.assoc."...
| - proc void freeIntRepProc—Release all storage, close files, etc.
| - io Obj objPtr—The mapping being freed.
- Memory. All internal allocation not accessible any other way are freed.
|
| - proc void dupIntRepProc—Duplicate internal storage from srcPtr to dupPtr.
| - input Obj srcPtr—Original mapping.
| - output Obj dupPtr—Duplicate mapping.
|
| - proc void updateStringProc—Update the string representation.
| - io Obj mapping—The mapping being displayed.
- Memory. String representation is heap allocated.
|
| - proc int setFromAnyProc—Construct the internal representation from the string.
| - output Intr intr—Error message return; may be NULL.
| - io Obj objPtr—The mapping being synthesised.
|
|
| - proc Obj update—Update string from wyrm_assocUpdate. NULL if updateStringProc is not wyrm_assocUpdate.
| - input Obj obj—The mapping being displayed.
| - output Tcl_DString* S—Receives string representation.
|
| - proc Obj internal—Update internal representation from wyrm_assocInternal. NULL if setFromAnyProc does not call wyrm_assocInternal.
| - output Intr intr—Error message return; may be NULL.
| - io Obj mapping—The mapping being updated.
| - io ptr cookie—Passed through to wyrm_assocInternalEntry.
|
| - proc Obj dump—Format the mapping in some implementation fashion.
- Memory. Caller decrements reference count when done.
| - output Intr intr—Error message return; may be NULL.
| - input Obj base—The mapping being dumped.
| - input int N—Number of additional arguments. May be zero.
| - input Obj* P—Additional arguments. May be null if N is zero.
|
| - long magic—Type positive magic number if an external mapping, used to identify files. Must be zero for an internal mapping.
| - proc Obj new—Construct the internal representation from the base and return it; return NULL on error.
- Memory. Caller decrements reference count when done.
| - output Intr intr—Error message return; may be NULL.
| - io Obj base—The base object mapping being synthesised.
| - input int N—Number of additional arguments. May be zero.
| - input Obj* P—Additional arguments. May be null if N is zero.
|
| - proc int empty—If the mapping is currently empty; TCL_OK if true, TCL_BREAK if not, or TCL_ERROR.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
|
| - proc int first—Return the key of the first element, or NULL if error.
- Memory. Caller decrements.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
|
| - proc int last—Return the key of the last element, or NULL if error.
- Memory. Caller decrements.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
|
| - proc int next—Return the key of the next element after the given one, or NULL if error.
- Memory. Caller decrements.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
| - input Obj key—Key to search for.
|
| - proc int previous—Return the key of the previous element before the given one, or NULL if error.
- Memory. Caller decrements.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
| - input Obj key—Key to search for.
|
| - proc int enumerateBegin—Begin an enumeration of the mapping; returns an enumeration cooke or NULL if error.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
| - input Obj firstHint—Suggested first key if nonnull. The enumerator expects no key less than this.
| - output bool* sorted—Keys are enumerated strictly increasing.
|
| - proc int enumerate—Get the next element of the mapping; return TCL_OK. TCL_ERROR, or TCL_BREAK at end.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
| - io ptr cookie—Enumeration magic cookie.
| - output Obj* key—Enumerated key if TCL_OK.
- Memory. Caller decrements refcount.
| - output Obj* data—Enumerated data if TCL_OK.
- Memory. Caller decrements refcount.
| - output int* flags—Enumerated flags if TCL_OK.
|
| - proc int enumerateEnd—End an enumeration of the mapping; returns TCL_ERROR or TCL_OK.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
| - input ptr cookie—Enumeration magic cookie.
|
| - proc int get—Get information from the keyed element; TCL_OK or TCL_ERROR.
| - output Intr intr—Error message return; may be NULL.
| - input Obj mapping—The mapping being queried.
| - input Obj seek—The key of the element to get. If the mapping is sorted, this may be an approximate key.
| - output Obj *key—The key of the position if not NULL.
- Memory. Decrement reference count to release.
| - output Obj *data—The data of the position or NULL.
- Memory. Decrement reference count to release.
| - output int *flags—The flags of the position or -1.
|
| - proc int put—Put information into the mapping; TCL_OK or TCL_ERROR.
| - output Intr intr—Error message return; may be NULL.
| - io Obj mapping—The mapping being modified.
| - input Obj key—Store in this key's position, adding the key if necessary. If null, store in the current position; NULL if error.
- Memory. Reference count incremented if the mapping retains this object.
| - input Obj data—If nonnull, store this data.
- Memory. Reference count incremented if the mapping retains this object.
| - input int flags—If nonnegative, store these flags.
|
| - proc int delete—Delete the key and data; TCL_OK or TCL_ERROR.
| - output Intr intr—Error message return; may be NULL.
| - io Obj mapping—The mapping being modified.
| - input Obj key—Key to search for.
|
|
|
|
| ^ | | | | | | section top | | - type enum WyrmAssocFlags
| - wyrm_assocFlagCompressKey—Request key compression.
- Enumeration. 0x01
| - wyrm_assocFlagCompressData—Request data compression.
- Enumeration. 0x02
| - wyrm_oavFlagDelegate—OAV delegation.
- Enumeration. 0x04
| - wyrm_oavFlagSubst—Do OAV %-substitutions.
- Enumeration. 0x08
| - wyrm_oavFlagActive—Data is active string.
- Enumeration. 0x10
| - wyrm_oavResumption—Data is an OAV resumption.
- Enumeration. 0x20
|
|
|
enum WyrmAssocFlags {
wyrm_assocFlagCompressKey = 0x01,
wyrm_assocFlagCompressData = 0x02,
wyrm_oavFlagDelegate = 0x04,
wyrm_oavFlagSubst = 0x08,
wyrm_oavFlagActive = 0x010,
wyrm_oavResumption = 0x20,
}; | ^ | Referenced at: 3, 58, 61. | | | | | section top | |
Tcl_ObjType tcl;
void (*update)(Obj obj,Tcl_DString *S);
int (*internal)(Intr intr,Obj obj,ptr cookie,ptr*);
Obj (*dump)(Intr intr,Obj mapping,int N,Obj *P); | ^ | | | | | | section top | | - protocol mapping identification
| - protocol internal mapping identification—when an even numbered length list is used as a mapping
| - proc wyrm_assoc...
| - mapping—Key/data pairs list
|
| - proc (wyrm.assoc.splay).setFromAnyProc—Find the type
|
| - protocol external mapping identification—when a one element list is used as a mapping
| - proc wyrm_assoc...
| | - proc (wyrm.assoc.btree).setFromAnyProc—Find the type
|
| - protocol external mapping identification—when a one element list is used as a mapping
| - proc wyrm_assoc...
| | - proc (wyrm.assoc.btree).setFromAnyProc
|
| - protocol open mapping—explicitly open a mapping
| - proc wyrm_assocNew
| - name—Type name.
| - base—The object to convert to a mapping.
|
| - proc type.open
| |
|
|
|
long magic;
Obj (*new)(Intr intr,Obj base,int N,Obj *P); | ^ | | | | | | section top | | 7 ::
Mappings are not explicitly closed, but are released when the last reference is cleared.
What exactly is released is specific to the implementation.
- protocol release mapping
| - proc Tcl_DecrRefCount
| - proc obj->typePtr->freeIntRepProc
|
|
|
| ^ | | | | section top | | 8 ::
As part of the Tcl type, the implementation must include a method to rebuild the
string implementation. Internal mappings can define the method update and
use the routine wyrm_assocUpdate in the Tcl type. wyrm_assocUpdate
handles the mechanics of the string representation. The update method can then
use wyrm_assocUpdateEntry to format a key, data, and flags into the
string representation.
- protocol update mapping with wyrm_assocUpdateEntry
| - proc Tcl_GetStringFromObj
| - proc obj->typePtr->updateStringProc is wyrm_assocUpdate
| - proc obj->wyrm assoc typePtr->update
| - proc wyrm_assocUpdateEntry
|
|
|
|
|
| ^ | | | | section top | | 9 ::
As part of the Tcl type, the implementation must include a method to build the
internal implementation from the string. Internal mappings can define the
method internal and use the routine wyrm_assocInternal
called from its setFromAnyProc. wyrm_assocInternal
handles the mechanics of the internal representations. The internal method then
uses wyrm_assocInternalEntry to get the key, data, and flags
of each entry.
- protocol update mapping with wyrm_assocInternalEntry
| - proc obj->typePtr->setFromAnyProc calls wyrm_assocInternal
| - proc obj->wyrm assoc typePtr->internal
| - proc wyrm_assocInternalEntry
|
|
|
|
|
| ^ | | | | section top | |
int (*empty)(Intr intr,Obj mapping); | ^ | | | | | | section top | | - protocol traverse mapping
| - protocol random positionning—All mappings.
| | - protocol approximate random positionning—The mapping is sorted.
| - proc get
| - proc next
| - proc previous
|
| - protocol forward scan
| | - protocol reverse scan—The mapping is reverse sorted.
| |
|
|
Obj (*first)(Intr intr,Obj mapping);
Obj (*last)(Intr intr,Obj mapping);
Obj (*next)(Intr intr,Obj mapping,Obj key);
Obj (*previous)(Intr intr,Obj mapping,Obj key); | ^ | | | | | | section top | | - protocol enumerate mapping
| - protocol enumerate to end—All mappings.
| - proc enumerateBegin—Nonnull cookie: begin enumeration; all other protocols may be disabled.
| - proc enumerate—Returns TCL_OK.
| - cookie
| - key—Nonnull.
| - data—Nonnull.
| - flags—Nonnull.
|
| - proc enumerate—Continued....
| - proc enumerate—Returns TCL_BREAK.
| - cookie
| - key—Null.
| - data—Null.
| - flags—Null.
|
| - proc enumerateEnd—All other protocols are enabled.
| |
| - protocol enumerate to error—All mappings.
| - proc enumerateBegin—Nonnull cookie: begin enumeration; all other protocols may be disabled.
| - proc enumerate—Returns TCL_OK.
| - cookie
| - key—Nonnull.
| - data—Nonnull.
| - flags—Nonnull.
|
| - proc enumerate—Continued....
| - proc enumerate—Returns TCL_ERROR.
| - cookie
| - key—Null.
| - data—Null.
| - flags—Null.
|
| - proc enumerateEnd—All other protocols are enabled.
| |
| - protocol enumeration failure—All mappings.
| - proc enumerateBegin—Null cookie: enumeration failed; all other protocols remain enabled.
|
|
|
|
ptr (*enumerateBegin)(Intr intr,Obj mapping,Obj firstHint,bool *sorted);
int (*enumerate)(Intr intr,Obj mapping,ptr cookie,Obj *key,Obj *data,int *flags);
int (*enumerateEnd)(Intr intr,Obj mapping,ptr cookie); | ^ | | | | | | section top | | 13. Input/output protocol ::
An associative mapping is always readable, but it might not be writable.
The contents of a mapping can be gotten if the mapping is non-empty. Each
I/O access has the key of the mapped item that accessed; for a sorted
get, if the key does not exactly exist, a nearby key can be returned
instead. A put will modify an existing item with the same key, or it
will create a new item with the key; a delete can only refer to an
existing item. The get
may return the same object as is already in the mapping; in this case its reference
count will be at least two, once for owned by the mapping, and once for the returned value.
The Tcl_IsShared will detect these cases, and modifiers of Tcl object
can duplicate it and then modift the duplicate.
If a Tcl shared object is modified, wyrm-assoc does not guarentee the
modifications will be retained. If the mapping is read-only, it is not guarenteed
the modification will even be possible.
On a put the collection
will first position itself at the given key, and modify the data at that position. If the
key is not in the mapping, it will be added, and position of that added key modified.
The mapping may retain the put object or a duplicate ofit, in which case
the object will have a reference count of at least two (for the mapping and the caller)
which signals it is shared.
To update data, it should be gotten, duplicated as necessary, and then put,
rather than trying to modify the gotten data and hoping the changes propagate
into the mapping.
An item can be deleted; the key will
no longer appear in a traversal, a get of the key will fail, and if the key or data
were objects their reference counts are decremented to note they are no longer shared
by the mapping.
- protocol input/output
| - protocol read approximate—The mapping is sorted.
| - proc get
| - input seek—Approximate sought key.
| - output key—key = seek or nearby
|
|
| - protocol get exact
| - proc get
| - input seek—Sought key
| - output key—key = seek
|
|
| - protocol put at key
| - proc put
| - input key—Put key.
| - input data—Put data.
| - input flags—Put flags.
|
|
| - protocol delete key
| |
|
|
int (*get)(Intr intr,Obj mapping,Obj seek,Obj *key,Obj *data,int *flags);
int (*put)(Intr intr,Obj mapping,Obj key,Obj data,int flags);
int (*delete)(Intr intr,Obj mapping,Obj key); | ^ | | | | | | section top | | | ^ | | | | | | section top | | | ^ | | | | | | section top | | | ^ | | | | | | section top | |
void wyrm_assocUpdate(Obj mapping);
void wyrm_assocUpdateEntry(Tcl_DString *S,chars key,Obj data,int flags); | ^ | Definition continued at: 19, 21, 66. | | | | | section top | |
void wyrm_assocUpdate(Obj mapping) {
Tcl_DString D; Tcl_DStringInit(&D);
((WyrmAssocMapType*)(mapping->typePtr))->update(mapping,&D);
mapping->length = Tcl_DStringLength(&D);
mapping->bytes = nheap(mapping->length+1,char);
strcpy(mapping->bytes,Tcl_DStringValue(&D));
Tcl_DStringFree(&D);
}
void wyrm_assocUpdateEntry(Tcl_DString *S,chars key,Obj data,int flags) {
chars d = data ? Tcl_GetString(data) : "";
bool flagged = flags>0 || streq(key,"[]");
if (flagged) {
char B[20];
Tcl_DStringAppendElement(S,"[]");
sprintf(B,"%d",flags<0?0:flags);
Tcl_DStringAppendElement(S,B);
}
Tcl_DStringAppendElement(S,key);
Tcl_DStringAppendElement(S,d);
}
| ^ | | | | | | section top | |
typedef int (*WyrmAssocScanner)(ptr context,ptr cookie);
int wyrm_assocInternal(Intr intr,Obj mapping,Tcl_ObjType *requiredType);
int wyrm_assocParseList(Intr intr,int N,Obj *P,WyrmAssocScanner scanner,ptr context);
bool wyrm_assocInternalEntry(ptr cookie,Obj *key,Obj *data,int *flags); | ^ | Definition continued at: 21, 66. | | | | | section top | |
typedef struct {
int N; chars *P; Obj *Q; int i;
} InternalCookie;
int wyrm_assocInternal(Intr intr,Obj mapping,Tcl_ObjType *requiredType) {
int rc;
if (mapping->typePtr!=requiredType) {
InternalCookie cookie; zero(1,InternalCookie,&cookie);
if ((rc=Tcl_SplitList(intr,Tcl_GetString(mapping),&cookie.N,(CONST char***)&cookie.P))!=TCL_OK) {
;
}else if (cookie.N%2) {
rc = TCL_ERROR;
rprintf(intr,"mapping has an odd number of elements");
}else {
ptr internal; rc = ((WyrmAssocMapType*)requiredType)->internal(intr,mapping,&cookie,&internal);
if (rc==TCL_OK) {
if ((mapping)->typePtr && (mapping)->typePtr->freeIntRepProc)
(mapping)->typePtr->freeIntRepProc((mapping));
(mapping)->typePtr = requiredType;
mapping->internalRep.otherValuePtr = internal;
}
}
dispose(cookie.P);
}else {
rc = TCL_OK;
}
return rc;
}
int wyrm_assocParseList(Intr intr,int N,Obj *P,WyrmAssocScanner scanner,ptr context) {
if (N%2) {
rprintf(intr,"mapping has an odd number of elements");
return TCL_ERROR;
}else {
InternalCookie cookie; zero(1,InternalCookie,&cookie);
cookie.N = N; cookie.Q = P; cookie.i = 0;
return scanner(context,&cookie);
}
}
bool wyrm_assocInternalEntry(ptr cookie0,Obj *key,Obj *data,int *flags) {
InternalCookie *cookie = cookie0;
if (cookie->i>=cookie->N) return false;
if (cookie->P) {
if (streq(cookie->P[cookie->i],"[]")) {
*flags = strtol(cookie->P[cookie->i],0,0);
cookie->i += 2;
}else
*flags = 0;
}else {
chars q = Tcl_GetString(cookie->Q[cookie->i]);
if (streq(q,"[]")) {
*flags = strtol(q,0,0);
cookie->i += 2;
}else
*flags = 0;
}
if (cookie->i>=cookie->N) {
*key = incr(Tcl_NewObj());
*data = incr(Tcl_NewObj());
}else if (cookie->P) {
*key = incr(Tcl_NewStringObj(cookie->P[cookie->i],-1));
*data = incr(Tcl_NewStringObj(cookie->P[cookie->i+1],-1));
cookie->i += 2;
}else {
*key = incr(cookie->Q[cookie->i]);
*data = incr(cookie->Q[cookie->i+1]);
cookie->i += 2;
}
return true;
}
| ^ | | | | | | section top | |
ptr wyrm_sortedEnumerateBegin(Intr intr,Obj mapping,Obj firstHint,bool *sorted);
int wyrm_sortedEnumerate(Intr intr,Obj mapping,ptr cookie,Obj *key,Obj *data,int *flags);
int wyrm_sortedEnumerateEnd(Intr intr,Obj mapping,ptr cookie); | ^ | Definition continued at: 66. | | | | | section top | |
ptr wyrm_sortedEnumerateBegin(Intr intr,Obj mapping,Obj firstHint,bool *sorted) {
Obj first,last;
*sorted = true;
if (firstHint) {
if (wyrm_assocGet(intr,mapping,firstHint,&first,0,0)!=TCL_OK) first = 0;
}else {
first = wyrm_assocFirst(intr,mapping);
}
last = first ? wyrm_assocLast(intr,mapping) : 0;
if (first) {
Obj *context = nheap(2,Obj); context[0] = first; context[1] = last;
return context;
}else {
return 0;
}
}
int wyrm_sortedEnumerate(Intr intr,Obj mapping,ptr cookie,Obj *key,Obj *data,int *flags) {
Obj *context = cookie;
*key = *data = 0; *flags = -1;
if (!context || !context[0]) {
return TCL_BREAK;
}else {
int rc = wyrm_assocGet(intr,mapping,context[0],key,data,flags); Obj next;
if (rc==TCL_ERROR) next = 0;
else if (streq(Tcl_GetString(context[0]),Tcl_GetString(context[1]))) next = 0;
else {next = wyrm_assocNext(intr,mapping,context[0]); if (!next) rc = TCL_ERROR;}
decr(context[0]); context[0] = next;
return rc;
}
}
int wyrm_sortedEnumerateEnd(Intr intr,Obj mapping,ptr cookie) {
Obj *context = cookie;
if (context) {decr(context[0]); decr(context[1]);}
return TCL_OK;
}
| ^ | | |
| |