Copyright (c) 2000-2003, JYL Software Inc. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE, EVEN IF JYL SOFTWARE INC. IS MADE AWARE OF THE POSSIBILITY OF SUCH DAMAGE. Contributors: JYL Jacob Levy DVM David Van Maren GS Geoff Shapiro GPS George Peter Staplin MK Michael Krimerman DAS Daniel A. Steffen JPF John P. Fletcher AKU Andreas Kupries JH Jeff Hobbs SL Steve Landers NCB Nick Brawn JM Joe Mistachkin JG Jesse GrosJeans Release: 1.0a11 February 22, 2004 This is the eleventh release, the eleventh Alpha release. This is a bug fix release, with several new features related to GC and events. I decided to skip 1.0a10 since Daniel Steffen released AquaTclBI for MacOS 10.x which contained a snapshot of the CVS repository and called that "e4graph 1.0a10". This way we avoid confusion between two different sourcebases; the 1.0a10 code in AquaTclBI contains several bugs that are fixed in this release. CONTRIBUTIONS: DVM and GS contributed many useful ideas, time, thought and discussions, regarding fixing several performance issues with the garbage collector. COMPATIBILITY: This release upgrades the use of expat to expat 1.95.7, released October 10, 2003. BUG FIXES: * Fixed a bug where GC was only happening if E4_AUTOGC was set, irrespective of other modes. Now GC happens correctly when other modes are set without E4_AUTOGC (JYL, DVM). * Fixed a bug in vertex moving if the moved vertex ended up at the same index as it originated at (JYL, DAS). * Fixed several bugs related to vertex moving with indices that are out of range. Now the semantics have been normalized to mean that a target rank of 1 or 0 means that the moved vertex ends up as the first vertex in the node, and target ranks larger than the number of vertices in the node means that the vertex ends up as the last vertex. Also, negative ranks cause the moved vertex to end up as the last vertex in the node (JYL). * Fixed a bug with inserting with E4_IOAT when the position > 1 and does not exist yet in the node where the new value is inserted (JYL, JG). * Fixed a bug that allowed use of zero and negative ranks to retrieve vertices. This is now disallowed (JYL, DVM). * Fixed a bug where some storages could only be opened if both E4_SPMODIFY and E4_SPCOMMIT were set. Now it is possible to open a storage with only E4_SPMODIFY set (JYL, DVM). * Fixed a series of bugs with vertex movement and callbacks related thereto. Now the vertex after which to move the moved vertex is determined before any changes are made, so that the specified rank is predictably followed. Previously the result for moving a vertex within one node was not easy to predict. Also, now both the node into which the vertex is inserted and the node from which the vertex is removed will receive node modify callbacks with the correct node modify callback reason, and only one such callback is delivered if they are the same node. Finally, when the vertex to be moved and the vertex at which it is to be inserted are the same, no action is taken (JYL). * Now no longer invoking vertex add callbacks unless the new vertex is returned to the user program. Previously was incorrectly causing callbacks to fire for these vertices even if the program did not reference them (JYL). * Now invoking vertex modification callbacks in all cases when the modified vertex is referenced by the user program. Previously was missing some cases and in other cases was invoking callbacks on vertices not referenced by the user program (JYL). * Now invoking vertex and node modification callbacks for when user data is modified (JYL, DVM). * Fixed a bug where a storage would get marked as unstable (needs to be committed) when APIs that test for the existence of named vertices are invoked (JYL, DVM). MODIFIED FUNCTIONALITY: * The semantics of the E4_ECDETVERTEX and E4_ECDETNODE callbacks have been changed to be asynchronous. The callbacks are delivered to referenced entities at detach time or some time later (JYL, DVM). NEW FUNCTIONALITY: * Enabled building and installing static versions of e4graph library and test program on Unix and MacOS X 10.x. The static library is named libe4graphs.a, to avoid conflicts (JYL, JG). * Added a timestamp mechanism that enables polling for events that have occurred in the past. It is an alternative to the callback mechanism (JYL, DVM). * Enabled user control over caching of information mapping vertex names and ranks to vertices in a node. This cache is instrumental in speeding up access to vertices in a node (JYL, DVM). * Added a permission that controls whether a storage can be committed. Now you can allow a storage to be modified but prevent changes from being committed. This allows you to share access to a storage and make private modifications, if the storage driver supports such private modifications (JYL, DVM). * Added a permission that controls whether the needed data structures can be created in a new storage. If this permission is not set, then opening a new storage will fail (DVM, JYL). * Added a permission that controls whether the format of a storage can be updated at opening time. If a storage was in the past committed by an older version of e4Graph, using an older data format, then parts of the data may need to be reformatted to be usable by the current library. This is done automatically at opening time, if allowed by this permission. If this step is needed and the permission is not given, the open will fail (DVM, JYL). NEW CONSTANTS, STRUCTURES, AND APIs: * New timestamp mechanism (JYL, DVM): int e4_Storage::GetTimeStamp() const Retrieves the timestamp for the last recorded event. Returns -1 if the storage is invalid. int e4_Storage::GetTimeStampFor(int eventmask) const Retrieves the timestamp for the last event that occurred and whose event code is present in eventmask, which is formed by OR-ing together any of the event codes defined for callbacks. Returns -1 if the storage is invalid. Returns 0 if none of the events whose eventcode is present in eventmask has occurred. bool e4_Storage::HasOccurredSince(int timestamp, int eventmask) const Returns true if any of the events whose event code is present in eventmask have since the given timestamp. Returns false if the storage is invalid, or if the timestamp is in the future or negative. Use a timestamp of 0 to query whether the events have ever occurred. bool e4_Storage::CauseEvent(int ec, const e4_RefCount &r, void *csdata, int ×tamp) Causes the event identified by ec to be reported via callbacks. Also returns the timestamp for the event, in the fourth argument. * New APIs for controlling the caching behavior of individual instances of e4_Node. Note that the global caching behavior of each storage is still controlled by the storage state flag E4_NOVERTEXCACHE. The caching behavior is non-persistent, so it only affects the behavior of nodes referenced by the user program and resets to the default when a node is not referenced. Several constant flags control the behavior: E4_CACHEINCREMENTAL The default value. If this is the value set for a node, the cache is computed incrementally. E4_AUTOCACHENAMES If set, the cache of mappings from vertex names to vertex IDs is maintained up to date at all times. E4_AUTOCACHERANKS If set, the cache of mappings from vertex ranks to vertex IDs is maintained up to date at all times. The above flags are managed by the following APIs: int e4_Node::SetAdvisoryCachingPolicy(bool set, int mask) const int e4_Node::GetAdvisoryCachingPolicy() const The e4_Node::SetAdvisoryCachingPolicy call returns the previous combination of flags set (JYL, DVM). * New event codes for events that occur during a storage lifecycle. These events are not reported via callbacks; timestamps for these events are however recorded (JYL, DVM): E4_ECOPENSTG The storage was opened. E4_ECCOPYTOSTG The storage was used as the target of a CopyTo call. E4_ECCOPYFRMSTG The storage was used as the source of a CopyTo call. E4_ECSETSTGROOT The root node of the storage was set to a new node. E4_ECCOMMITSTG The storage was committed. * New event mask that defines all the events that modify a storage (JYL, DVM): E4_ECMODSTORAGE OR-ed combination of all the event codes for events that modify a storage. * New callback reason for vertex and node modification, for denoting user data modification (JYL, DVM): E4_ERMNMODUSERDATA The user data for the given node was modified. E4_ERMVMODUSERDATA The user data for the given vertex was modified. * New storage permission (JYL): E4_SPCOMMIT If set, allows storage to be committed. E4_SPINITIALIZE If set, allows needed data structures to be created in a new storage. E4_SPUPDATEFORMAT If set, allows data structures to be updated from an older storage format if needed. * New node modify callback reason (JYL): E4_ERNMINSVERTEX A vertex was inserted into this node. MODIFIED APIs: * Modified storage permission constant (JYL): E4_SPDEFAULTMASK E4_SPMODIFY, E4_SPCOMMIT, E4_SPCOPYTO, E4_SPCOPYFROM, E4_SPINITIALIZE, and E4_SPUPDATEFORMAT, OR-ed together E4_SPMODIFY Now controls only whether modifications to the storage are allowed after opening. Use E4_SPUPDATEFORMAT and E4_SPINITIALIZE to control whether modifications are to be allowed during storage opening. INTERNAL CHANGES: * Moved all management of storage stability from the driver layer to the impl layer, so that storage drivers do not have to manage it, and so that the same behavior consistently exists across all storage drivers (JYL). * Rewrote the GC mechanism and moved it into the impl layer so that all drivers benefit and no driver has to implement GCs. GC is now deferred by default until needed, and a partial GC is attempted before a complete one is invoked, to save processing time (JYL, DVM). * Major cleanup so that drivers do not have to be concerned with issuing callbacks. All of the callback mechanism has been moved into the impl layer (JYL). Release: 1.0a9 Sep 7th, 2003 This is the ninth release, the ninth Alpha release. This is a bug fix release, with few new features. CONTRIBUTIONS: Contributions of compute resources on MacOS X and FreeBSD are gratefully acknowledged -- thanks to NCB and JM. COMPATIBILITY: This release requires Metakit 2.4.9.2, released Feb 18, 2003. This release requires Tcl 8.4, if you want to build the Tcl binding. This release is known not to work with Tcl 8.4.3, because of Tcl Bug 726018 (check the bug database on tcl.sourceforge.net). Use Tcl 8.4.4 for best results. This release requires Python 2.2.3 or later, if you want to build the Python binding. BUG FIXES: * Fixed a bug in vertex ID caching that caused random ranks to be computed (there was an uninitialized variable whose value was being returned) (DVM, JYL). * Fixed several uninitialized variable uses (JYL, DVM). * Fixed a bug where the vertex cache was updated incorrectly with out-of-date information after it had already been flushed (JYL). * Fixed a bug in e4xmlbase64.c where the parsing and generation of BASE64 encoded strings was not working properly on strings without newlines (JYL, GS). * Fixed a bug in installation where the pkgIndex.tcl was not being installed when building from source (JYL, GPS). * Binary distributions did not include the pkgIndex.tcl file so it wasn't possible to package require tgraph with a binary installation (JYL, GPS). NEW FUNCTIONALITY: * Added version information about the version of e4Graph that wrote a storage, stored within the storage (JYL). NEW CONSTANTS, STRUCTURES, AND APIs: * New C++ APIs to return the version information for the version of e4Graph that wrote a given storage (JYL): static const char *e4_Storage::storage_version(const char *fname, const char *dname); static bool e4_Storage::storage_version_info(const char *fname, const char *dname, int &majver, int &minver, e4_ReleaeStatus &rs, int &reliter); * New Tcl APIs to return the version string for the version of e4Graph that wrote a given storage (JYL): tgraph::version returns the version of e4Graph currently running. tgraph::version storagename returns the version of e4Graph used to write that storage. Release: 1.0a8 August 2nd, 2003 This is the eight release, the eight Alpha release. This is a major feature enhancement release. PORTABILITY: This release is the first to support MacOS X 10. The build instructions are very similar to those for a stock Unix system (DAS, JYL, SL). This release is the first to support an experimental Python 2.2 binding for e4Graph, on all platforms (MK, JYL). COMPATIBILITY: This release requires Metakit 2.4.9.2, released Feb 18, 2003. This release requires Tcl 8.4, if you want to build the Tcl binding. This release is known not to work with Tcl 8.4.3, because of Tcl Bug 726018 (check the bug database on tcl.sourceforge.net). Use Tcl 8.4.4 for best results. This release requires Python 2.2.3. You need an installation of Python 2.2.3 or later if you want to build the Python binding. BUG FIXES: * Fixed several bugs in XML input/output (DAS, JPF, JYL). * Fixed Tcl binding crash when internal representation is lost due to misuse of tgraph objects, e.g. doing "llength $mynode" followed by "$mynode isvalid", which used to crash Tcl. Now the command "$mynode" is invalid after the call to "llength". (reported by DAS, fixed by JYL). * Fixed Tcl binding crash which happened when a vertex was cached and became unreachable. Fixed by proper refcounting (JYL). * Fixed Tcl binding caching of nodes to avoid caching nodes that do not have other references from the Tcl program so that the node would become unreachable if detached in the storage. Prior to this a node would not become unreachable and hence contained vertices would not become detached, because the node was kept reachable by being cached (JYL). * Now system callbacks happen before Tcl script callbacks in the Tcl binding. Prior to this a Tcl script could see an inconsistent state because the system level actions implied by the callback had not yet been done (JYL). NEW FUNCTIONALITY: * Support for storage permissions. Now you can open a storage for read-only access and prevent e4_Storage::CopyTo from using a storage as the source and/or target for copying (GS, JYL). * Completely overhauled the event mechanism. Now the event mechanism is generic, and there are no event-type-specific callback function types -- all event callback functions have the same signature. The event mechanism has also been opened up so that applications using e4Graph can define their own events and cause them to occur at appropriate times. To facilitate this, I exposed the (pre-existing but internal) event type mechanism that identifies event types as integers. User programs can define new event types and obtain event type IDs, and later use these IDs to cause the corresponding event type to be invoked. Event type IDs for user defined events can later be revoked when the event is no longer used. As a result of this change, all the previous event mechanism related APIs have been removed and new APIs have replaced the ones that were provided in 1.0a7 (JYL). * New predefined event type for when a storage transitions between being stable and unstable (i.e. between having all changes committed and containing changes not yet committed) (JYL). * New APIs to define user defined event types and cause them to occur (JYL). * Added vertex ID caching in the core, to speed up vertex lookup. Previously this used to be available only to the Tcl binding, and this change makes the caching available to all language bindings (JYL). * New APIs to advance visitors without retrieving the next entity. This allows writing of tight counting loops, for example (JYL, DVM). * New API for visiting all vertices whose value is a given node (DVM, JYL). * Support for parsing XML streams, as defined in http://www.ietf.org/html.charters/xmpp-charter.html (JYL) MODIFIED FUNCTIONALITY: * Improved Unix build system, used on stock Unix systems as well as on MacOS X 10.2 (JYL, DAS). * Removed s.IsDirty(), s.MarkDirty(). Use s.IsStable() and s.MarkUnstable() instead (JYL). * Removed Tcl binding "storage markdirty" and "storage isdirty" APIs. Instead use "storage markunstable" and "storage isstable" (JYL). * All event-type-specific event callback function types have been removed and replaced with a single event callback function type (JYL). * Modified semantics of e4_StorageVisitor::CurrentStorage and other visitor APIs that return the current entity being visited. Now the APIs always return true and retrieve the current entity as long as it is valid, even when the visitor is "done" (JYL, DVM). NEW CONSTANTS, STRUCTURES, AND APIs: * New storage permissions related constants. These constants can be ORed together to combine permissions. If not specified, the storage is opened with permissions equal to those specified in E4_SPDEFAULTMASK (JYL, GS): E4_SPMODIFY If set, allows storage to be modified. Otherwise storage is read-only. E4_SPCOPYTO If set, allows storage to be used as target for CopyTo. E4_SPCOPYFROM If set, allows storage to be used as source for CopyTo. E4_SPDEFAULTMASK E4_SPMODIFY, E4_SPCOPYTO, E4_SPCOPYFROM OR-ed together * New constant for storage state manipulation with e4_Storage::GetState and e4_Storage::SetState (JYL, GS): E4_NOVERTEXCACHE If on, this storage does not allow nodes to cache vertex IDs. * New API for pre-caching vertex IDs in a node (JYL): e4_Node::PreCache() const; * New e4_Storage constructor for specifying permissions (JYL, GS): e4_Storage::e4_Storage(const char *name, const char *drivername, int state, int permissions); * New API for querying the permissions specified when the storage was opened (JYL, GS): int e4_Storage::GetPermissions() const; * New event mechanism APIs: Predefined event codes: E4_ECADDNODE A new node was added to the storage. E4_ECDETNODE A node became detached. E4_ECATTNODE A node became attached. E4_ECMODNODE A node was modified. E4_ECADDVERTEX A new vertex was added to the storage. E4_ECDETVERTEX A vertex became detached. E4_ECATTVERTEX A vertex became attached. E4_ECMODVERTEX A vertex was modified. E4_ECCHANGESTG A storage became stable or unstable. E4_FIRSTUSERDEFINEDEVENTCODE Event code for first user defined event. E4_LASTUSERDEFINEDEVENTCODE Event code for last user defined event. Event callback function type: typedef void (*e4_CallbackFunction)(void *clientData, const e4_RefCount &r, void *callSiteData); All callback functions registered to handle events have the above signature. The first argument is a datum specified at the time the callback function is registered (see below). The second datum is the entity on which the event occurs. You should cast it to the appropriate entity (e4_Storage, e4_Node or e4_Vertex). The third datum is a value supplied by the event causing code at the callsite where the event occurred. Some event codes may be associated with event-type-specific data that is passed from the callsite to the event callback function. Here's an example of a callback function that takes an e4_Node: void myCB(void *clientData, const e4_RefCount &r, void *csData) { e4_Node n = (e4_Node) r; if (!n.IsValid()) { cerr << "Oh bother.. got an invalid node\n"; } DoSomethingWith(n); } Callbacks are associated with specific events via the following APIs: bool e4_Storage::DeclareCallback(int eventCode, e4_CallbackFunction fn, void *clientData); bool e4_Storage::DeleteCallback(int eventCode, e4_CallbackFunction fn, void *clientData); Events are caused by the calling the following API on a storage: bool e4_Storage::CauseEvent(int eventCode, const e4_RefCount &r, void *callSiteData); User code cannot cause events for predefined event codes. Doing so will make the API return false. User defined event codes are managed using the following API: static bool e4_Storage::DefineEventCode(int &eventCode); static bool e4_Storage::UndefineEventCode(int eventCode); static bool e4_Storage::IsEventCodeDefined(int eventCode); To define a new event code for use by your application, call DefineEventCode. The output parameter eventCode will be set to an integer value that can be used in a call to CauseEvent. Event codes are defined for all storages. The DefineEventCode API normally returns true; if there are no more available event codes (i.e. the next event code that would be allocated is larger than E4_LASTUSERDEFINEDEVENTCODE) then DefineEventCode returns false. User applications cannot undefine predefined event codes. Doing so will make UndefineEventCode return false. User applications can use IsDefineEventCode to detect whether an event code is defined (JYL). * New enumeration for the reasons a node modification event occurs: typedef enum e4_ModNodeEventReason { E4_ERMNADDVERTEX, E4_ERMNDETVERTEX, E4_ERMNRENVERTEX, E4_ERMNMOVVERTEX } e4_ModNodeEventReason; A value in this enumeration is passed as the callSiteData parameter for callback functions registered for E4_ECMODNODE events (JYL). * New constructors for e4_VertexVisitor to select visiting all vertices that have a certain node as their value (all "parent vertices"): e4_VertexVisitor::e4_VertexVisitor(const e4_Node &child, const e4_Node &parent, e4_DetachChoice dc); e4_VertexVisitor::e4_VertexVisitor(const e4_Node &child, const e4_Node &parent, e4_DetachChoice dc, const char *nm); * New method of e4_VertexVisitor to reset an iterator to visit vertices that have a given node as their value: e4_VertexVisitor::SetParentVertex(const e4_Node &child, const e4_Node &parent, e4_DetachChoice dc, const char *nm); * New visit method added to the e4_VisitMethod enumeration: the E4_VMPARENT visit method causes an e4_VertexVisitor to visit vertices that have a given node as their value: typedef enum e4_VisitMethod { E4_VMUNKNOWN, E4_VMSTORAGE, E4_VMNODE, E4_VMNODERANDOM, E4_VMPARENT } e4_VisitMethod; * New enumeration for the reasons a vertex modification event occurs: typedef enum e4_ModVertexEventReason { E4_ERMVMODVALUE, E4_ERMVRENAME, E4_ERMVREPARENT, E4_ERMVDETVERTEX } e4_ModVertexEventReason; A value in this enumeration is passed as the callSiteData parameter for callback functions registered for E4_ECMODVERTEX events (JYL). * New APIs for retrieving the vertices in a parent that contain a specific child node as their value (JYL, DVM): bool e4_Node::GetVertexRefFromParent(int nth, int ith, e4_Vertex &v) const; bool e4_Node::GetVertexRefFromParent(e4_Node p, int ith, e4_Vertex &v) const; * New APIs to advance visitors to the next entity without retrieving it, for writing tight loops (JYL, DVM): bool e4_StorageVisitor::Advance(); bool e4_NodeVisitor::Advance(); bool e4_VertexVisitor::Advance(); * New APIs for retrieving the rank and name of vertices in a parent that contain a child node as their value (JYL, DVM): int e4_Node::GetRankInParent(int nth, int ith) const; int e4_Node::GetRankInParent(e4_Node p, int ith) const; const char *e4_Node::GetNameInParent(int nth, int ith) const; const char *e4_Node::GetNameInParent(e4_Node p, int ith) const; * New APIs to manage an event fired when a vertex is completely parsed, in e4XML: bool e4_XMLParser::DeclareVertexCompletionCallback( e4_CallbackFunction fn, void *clientData); bool e4_XMLParser::DeleteVertexCompletionCallback( e4_CallbackFunction fn, void *clientData); bool e4_XMLParser::CauseVertexCompletionEvent( const e4_Vertex &v, void *csdata); This allows the implementation of stream-oriented XML parsing protocols such as those proposed by the Jabber project (see e.g. http://www.ietf.org/html.charters/xmpp-charter.html) (JYL) * New enumeration defining the possible release status codes (JYL): typedef enum e4_ReleaseStatus { E4_ALPHARELEASE, E4_BETARELEASE, E4_FINALRELEASE, E4_PATCHRELEASE } e4_ReleaseStatus; * New APIs to return the numeric parts of the release name: static int e4_Storage::major_version() const; static int e4_Storage::minor_version() const; static e4_ReleaseStatus e4_Storage::release_status() const; static int e4_Storage::release_iteration() const; These static functions can be used by language bindings and clients using e4Graph to determine whether they are bound to a suitable version of the package, and to select which features to use (JYL). * New Tcl API for registering an event callback scripts when a storage becomes stable or unstable. $storage callback add storage change