/* * i4storage.cpp -- * * This file contains the implementation of the e4_StorageImpl class * defined in e4graph.h. * * Authors: Jacob Levy and Jean-Claude Wippler. * jyl@best.com jcw@equi4.com * * 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. */ #include "e4graphimpl.h" static bool initialized = false; static e4_HashTable *activeStorages = NULL; /* * This static function is the only public way to get an e4_StorageImpl. */ e4_StorageImpl * e4_StorageImpl::GetStorage(const char *name, const char *drivername, int state, int perms) { e4_HashEntry *hPtr; e4_StorageImpl *s; e4_StorageConstructor scp; int isnew; if (!initialized) { initialized = true; e4_InitializeStorageRegistry(); activeStorages = e4_NewHashTable(E4_STRING_KEY); } hPtr = E4_CREATEHASHENTRY(activeStorages, name, &isnew); if (!isnew) { return (e4_StorageImpl *) E4_GETHASHVALUE(hPtr); } scp = e4_GetStorageConstructor(drivername); if (scp == NULL) { s = NULL; } else { s = (*scp)(name, state, perms); } if (s == NULL) { e4_DeleteHashEntry(hPtr); } else { E4_SETHASHVALUE(hPtr, s); } s->RecordTimeStamp(E4_ECOPENSTG); return s; } /* * This static function retrieves information about which version of * e4Graph was used to write an existing storage. */ bool e4_StorageImpl::GetStorageVersionInfo(const char *name, const char *drivername, int &majorver, int &minorver, e4_ReleaseStatus &rs, int &reliter) { e4_StorageVersionGetter vgp; if (!initialized) { initialized = true; e4_InitializeStorageRegistry(); activeStorages = e4_NewHashTable(E4_STRING_KEY); } vgp = e4_GetStorageVersionGetter(drivername); if (vgp == NULL) { return false; } return (*vgp)(name, majorver, minorver, rs, reliter); } /* * This constructor opens a storage in write mode. */ e4_StorageImpl::e4_StorageImpl(const char *fname, const char *dnm, int pps) : e4_RefCounter() { int i; drivername = new char[strlen(dnm) + 1]; strcpy(drivername, dnm); name = new char[strlen(fname) + 1]; strcpy(name, fname); commit = true; stable = true; gcAtCommit = false; perms = pps; destroyed = false; GCState = NULL; GCStateLength = 0; InitializeNameHash(); InitializeNodeHash(); InitializeVertexHash(); InitializeCallbackHash(); for (i = 0; i < E4_LASTUSERDEFINEDEVENTCODE+1; i++) { eventTimeStamps[i] = 0; } timestamp = 0; } /* * The destructor is virtual so it is called before destructors of derived * classes to clean up the state belonging to the e4_StorageImpl base class. */ e4_StorageImpl::~e4_StorageImpl() { if (name != NULL) { /* * We are supposed to delete the storage occupied by the name * but because of bugs in some compilers we cannot delete it. * This is because attempting to delete it with e.g. VC6 causes * an assert at this point. We therefore just leak the string. */ } /* * Clean up the hash tables for cached data: */ if (nameHash != NULL) { e4_DeleteHashTable(nameHash); free((char *) nameHash); nameHash = NULL; } if (activeNodes != NULL) { e4_DeleteHashTable(activeNodes); free((char *) activeNodes); activeNodes = NULL; } if (activeVertices != NULL) { e4_DeleteHashTable(activeVertices); free((char *) activeVertices); } /* * Check one last time that the callback facility is cleaned up: */ if (callbacks != NULL) { e4_DeleteHashTable(callbacks); free((char *) callbacks); callbacks = NULL; } if (GCStateLength != 0) { free(GCState); } } /* * Helper functions to initialize and manage the caches. */ void e4_StorageImpl::InitializeNameHash() { nameHash = e4_NewHashTable(E4_STRING_KEY); } void e4_StorageImpl::InitializeNodeHash() { activeNodes = e4_NewHashTable(E4_ONE_WORD_KEY); } void e4_StorageImpl::InitializeVertexHash() { activeVertices = e4_NewHashTable(E4_ONE_WORD_KEY); } void e4_StorageImpl::InitializeCallbackHash() { callbacks = e4_NewHashTable(E4_CALLBACKKEYSIZE); callbacksPresent = 0; } /* * Retrieve an instance of e4_VertexImpl for a referenced vertex. */ e4_VertexImpl * e4_StorageImpl::FindReferencedVertex(int index) const { e4_HashEntry *ep; union { void *v; int i; } u; if (activeVertices == NULL) { return NULL; } u.i = index; ep = E4_FINDHASHENTRY(activeVertices, (const char *) u.v); if (ep == NULL) { return NULL; } return (e4_VertexImpl *) E4_GETHASHVALUE(ep); } /* * Find a node in the activeNodes table. This method does not check * whether the node ID is legal. */ e4_NodeImpl * e4_StorageImpl::FindReferencedNode(int index) const { e4_HashEntry *ep; union { void *v; int i; } u; if (activeNodes == NULL) { return NULL; } u.i = index; ep = E4_FINDHASHENTRY(activeNodes, (const char *) u.v); if (ep == NULL) { return NULL; } return (e4_NodeImpl *) E4_GETHASHVALUE(ep); } /* * Find or create an instance of e4_VertexImpl for a given vertex. */ e4_VertexImpl * e4_StorageImpl::GetVertex(int i) const { e4_VertexImpl *f; e4_HashEntry *hPtr; int isNew; union { void *v; int i; } u; if (!DRV_IsLegalVertexID(i) || (activeVertices == NULL)) { return NULL; } u.i = i; hPtr = E4_CREATEHASHENTRY(activeVertices, (const char *) u.v, &isNew); if (isNew) { f = new e4_VertexImpl((e4_StorageImpl *) this, i); E4_SETHASHVALUE(hPtr, f); } else { f = (e4_VertexImpl *) E4_GETHASHVALUE(hPtr); } return f; } /* * Store a node in the activeNodes hash table. */ void e4_StorageImpl::StoreNode(int index, e4_NodeImpl *n) const { e4_HashEntry *hPtr; int isnew; union { void *v; int i; } u; if (activeNodes == NULL) { return; } u.i = index; hPtr = E4_CREATEHASHENTRY(activeNodes, (const char *) u.v, &isnew); E4_SETHASHVALUE(hPtr, n); } /* * Remove a node from the activeNodes hash table. This method should only * be called from the e4_NodeImpl destructor, to avoid infinite recursion. */ void e4_StorageImpl::ForgetNode(int index) { e4_HashEntry *hPtr; e4_NodeImpl *n; union { void *v; int i; } u; if (activeNodes == NULL) { return; } u.i = index; hPtr = E4_FINDHASHENTRY(activeNodes, (const char *) u.v); if (hPtr != NULL) { n = (e4_NodeImpl *) E4_GETHASHVALUE(hPtr); n->SetStorage(NULL); e4_DeleteHashEntry(hPtr); } } /* * Find a node in the activeNodes hash table given its index, if it is * in-memory. If not, check whether the index is legal and create it * if it is. */ e4_NodeImpl * e4_StorageImpl::FindNode(int index) const { if (DRV_IsLegalNodeID(index)) { return FindOrCreateNode(index); } return NULL; } /* * Find a node in the activeNodes hash table given its index, if it is * in-memory. If not, create it. This method does not check whether * the index is legal. */ e4_NodeImpl * e4_StorageImpl::FindOrCreateNode(int index) const { e4_HashEntry *hPtr; e4_NodeImpl *n; union { void *v; int i; } u; if (activeNodes == NULL) { return NULL; } u.i = index; hPtr = E4_FINDHASHENTRY(activeNodes, (const char *) u.v); if (hPtr != NULL) { return (e4_NodeImpl *) E4_GETHASHVALUE(hPtr); } n = new e4_NodeImpl((e4_StorageImpl *) this, index); StoreNode(index, n); return n; } /* * Find a node in the activeNodes hash table given its index, if it is * in-memory. If not, create it and store it in the activeNodes table. * Also return an indication whether the node was newly created. */ e4_NodeImpl * e4_StorageImpl::FindOrCreateNode(int index, bool *isNew) const { e4_HashEntry *hPtr; e4_NodeImpl *n; union { void *v; int i; } u; if (activeNodes == NULL) { return NULL; } u.i = index; hPtr = E4_FINDHASHENTRY(activeNodes, (const char *) u.v); if (hPtr != NULL) { *isNew = false; return (e4_NodeImpl *) E4_GETHASHVALUE(hPtr); } *isNew = true; n = new e4_NodeImpl((e4_StorageImpl *) this, index); StoreNode(index, n); return n; } /* * Store a vertex in the activeVertices hash table. */ void e4_StorageImpl::StoreVertex(int vertexID, e4_VertexImpl *f) const { e4_HashEntry *hPtr; int isNew; union { void *v; int i; } u; if (activeVertices == NULL) { return; } u.i = vertexID; hPtr = E4_CREATEHASHENTRY(activeVertices, (const char *) u.v, &isNew); if (!isNew) { /* * Should abort here. */ } E4_SETHASHVALUE(hPtr, f); } /* * Remove an e4_VertexImpl from the activeVertices hash table. */ void e4_StorageImpl::ForgetVertex(int vertexID) { e4_HashEntry *hPtr; e4_VertexImpl *f; union { void *v; int i; } u; if (activeVertices == NULL) { return; } u.i = vertexID; hPtr = E4_FINDHASHENTRY(activeVertices, (const char *) u.v); if (hPtr != NULL) { f = (e4_VertexImpl *) E4_GETHASHVALUE(hPtr); f->SetStorage(NULL); e4_DeleteHashEntry(hPtr); } } /* * Is the node with this ID referenced by the user of e4Graph? */ bool e4_StorageImpl::IsReferencedNode(int nodeID) const { union { void *v; int i; } u; if (activeNodes == NULL) { return false; } u.i = nodeID; if (E4_FINDHASHENTRY(activeNodes, (const char *) u.v) == NULL) { return false; } return true; } /* * Iterate over all nodes referenced by the user program. */ int e4_StorageImpl::FirstReferencedNodeID(e4_HashSearch *searchP) { e4_HashEntry *ePtr; if (activeNodes == NULL) { return E4_NEXTNONE; } ePtr = e4_FirstHashEntry(activeNodes, searchP); if (ePtr == NULL) { return E4_NEXTNONE; } return (int) ((long) E4_GETHASHKEY(activeNodes, ePtr) & 0xFFFFFFFF); } int e4_StorageImpl::NextReferencedNodeID(e4_HashSearch *searchP) { e4_HashEntry *ePtr; if (activeNodes == NULL) { return E4_NEXTNONE; } ePtr = e4_NextHashEntry(searchP); if (ePtr == NULL) { return E4_NEXTNONE; } return (int) ((long) E4_GETHASHKEY(activeNodes, ePtr) & 0xFFFFFFFF); } /* * Is the vertex with this ID referenced by the user of e4Graph? */ bool e4_StorageImpl::IsReferencedVertex(int vertexID) const { union { void *v; int i; } u; if (activeVertices == NULL) { return false; } u.i = vertexID; if (E4_FINDHASHENTRY(activeVertices, (const char *) u.v) == NULL) { return false; } return true; } /* * Iterate over all vertices referenced by the user program. */ int e4_StorageImpl::FirstReferencedVertexID(e4_HashSearch *searchP) { e4_HashEntry *ePtr; if (activeVertices == NULL) { return E4_NEXTNONE; } ePtr = e4_FirstHashEntry(activeVertices, searchP); if (ePtr == NULL) { return E4_NEXTNONE; } return (int) ((long) E4_GETHASHKEY(activeVertices, ePtr) & 0xFFFFFFFF); } int e4_StorageImpl::NextReferencedVertexID(e4_HashSearch *searchP) { e4_HashEntry *ePtr; if (activeVertices == NULL) { return E4_NEXTNONE; } ePtr = e4_NextHashEntry(searchP); if (ePtr == NULL) { return E4_NEXTNONE; } return (int) ((long) E4_GETHASHKEY(activeVertices, ePtr) & 0xFFFFFFFF); } /* * Add a name to the name hash table. */ void e4_StorageImpl::AddNameToNameHash(const char *nm, int idx) const { e4_HashEntry *hPtr; int isnew; union { void *v; int i; } u; if (nameHash == NULL) { return; } hPtr = E4_CREATEHASHENTRY(nameHash, nm, &isnew); u.i = idx; E4_SETHASHVALUE(hPtr, u.v); } /* * Return a name given its nameID. */ const char * e4_StorageImpl::NameFromNameID(int nameID) const { e4_HashEntry *hPtr; e4_HashSearch search; if (nameHash == NULL) { return NULL; } /* * Search through the hash table until we find the hash entry with * the nameID as its value. If found, return the key which is the * name that hashes to this nameID. */ for (hPtr = e4_FirstHashEntry(nameHash, &search); hPtr != NULL; hPtr = e4_NextHashEntry(&search)) { if ((int) ((long) E4_GETHASHVALUE(hPtr) & 0xFFFFFFFF) == nameID) { return (const char *) E4_GETHASHKEY(nameHash, hPtr); } } /* * Not found, return NULL. */ return NULL; } /* * Get the e4_NodeImpl for the root node of this storage: */ e4_NodeImpl * e4_StorageImpl::GetRootNode() { return FindOrCreateNode(GetRootNodeID()); } /* * Set the root node for this storage. If the old root is detached * and not exported, then recycle memory. */ bool e4_StorageImpl::SetRootNode(e4_NodeImpl *nrp) { int ornID, nrnID; /* * If we cannot modify the storage, do not attempt: */ if ((perms & E4_SPMODIFY) == 0) { return false; } /* * Sanity checks. */ if ((nrp == NULL) || (!nrp->IsValid())) { return false; } nrnID = nrp->GetUniqueID(); /* * Remember the old root node ID. */ ornID = GetRootNodeID(); /* * Set the new root node ID. */ SetRootNodeID(nrnID); MarkUnstable(); /* * If the old root node is detached and not exported, recycle memory. */ if (DRV_IsDetachedNodeID(ornID) && !IsReferencedNode(ornID)) { SetNeedsGC(true); if ((GetState() & E4_AUTOGC) == E4_AUTOGC) { DoPartialGC(); } } return true; } /* * Add a name to the persistent storage and also intern it in the * hash table. */ int e4_StorageImpl::InternName(const char *nm, bool create) const { e4_HashEntry *hPtr; int isnew, idx; union { void *v; int i; } u; if (nameHash == NULL) { return E4_NEXTNONE; } /* * See if we already have this name in the hash table; if so, just * return the hash value. */ hPtr = E4_FINDHASHENTRY(nameHash, nm); if (hPtr != NULL) { return (int) ((long) E4_GETHASHVALUE(hPtr) & 0xFFFFFFFF); } /* * If "create" == false then we don't create the name. */ if (create == false) { return E4_NEXTNONE; } /* * No, we need to add the name to hash table. */ idx = ((e4_StorageImpl *) this)->DRV_AddName(nm); hPtr = E4_CREATEHASHENTRY(nameHash, nm, &isnew); u.i = idx; E4_SETHASHVALUE(hPtr, u.v); return idx; } /* * GC state management: * * These methods remember that certain nodes or vertices are unreachable, * providing starting points for partial GCs. */ void e4_StorageImpl::RegisterGCState(int id, int mask) { if (id < 0) { return; } if (GCStateLength == 0) { GCStateLength = id + 128; GCState = (char *) malloc(GCStateLength); } if (GCStateLength <= id) { GCStateLength = id + 128; GCState = (char *) realloc(GCState, GCStateLength); } GCState[id] |= mask; } void e4_StorageImpl::UnregisterGCState(int id, int mask) { if ((id > -1) && (GCState != NULL) && (GCStateLength > id)) { GCState[id] &= (~(mask)); } } void e4_StorageImpl::RegisterReachableVertexID(int vertexID) { RegisterGCState(vertexID, E4_GCVKR); } void e4_StorageImpl::UnregisterReachableVertexID(int vertexID) { UnregisterGCState(vertexID, E4_GCVKR); } void e4_StorageImpl::RegisterReachableNodeID(int nodeID) { RegisterGCState(nodeID, E4_GCNKR); } void e4_StorageImpl::UnregisterReachableNodeID(int nodeID) { UnregisterGCState(nodeID, E4_GCNKR); } void e4_StorageImpl::RegisterUnreachableVertexID(int vertexID) { RegisterGCState(vertexID, E4_GCVKU); } void e4_StorageImpl::UnregisterUnreachableVertexID(int vertexID) { UnregisterGCState(vertexID, E4_GCVKU); } void e4_StorageImpl::RegisterMaybeUnreachableVertexID(int vertexID) { RegisterGCState(vertexID, E4_GCVRU); } void e4_StorageImpl::UnregisterMaybeUnreachableVertexID(int vertexID) { UnregisterGCState(vertexID, E4_GCVRU); } void e4_StorageImpl::RegisterUnreachableNodeID(int nodeID) { RegisterGCState(nodeID, E4_GCNKU); } void e4_StorageImpl::UnregisterUnreachableNodeID(int nodeID) { UnregisterGCState(nodeID, E4_GCNKU); } void e4_StorageImpl::RegisterMaybeUnreachableNodeID(int nodeID) { RegisterGCState(nodeID, E4_GCNRU); } void e4_StorageImpl::UnregisterMaybeUnreachableNodeID(int nodeID) { UnregisterGCState(nodeID, E4_GCNRU); } void e4_StorageImpl::SetScannedVertexID(int vertexID) { RegisterGCState(vertexID, E4_GCVSN); } void e4_StorageImpl::ClearScannedVertexID(int vertexID) { UnregisterGCState(vertexID, E4_GCVSN); } void e4_StorageImpl::SetScannedNodeID(int nodeID) { RegisterGCState(nodeID, E4_GCNSN); } void e4_StorageImpl::ClearScannedNodeID(int nodeID) { UnregisterGCState(nodeID, E4_GCNSN); } int e4_StorageImpl::FirstGCEntity(int mask) { int i; if (GCStateLength == 0) { return E4_NEXTNONE; } for (i = 0; i < GCStateLength; i++) { if ((GCState[i] & mask) == mask) { return i; } } return E4_NEXTNONE; } int e4_StorageImpl::NextGCEntity(int i, int mask) { if ((GCState == NULL) || (i < 0)) { return E4_NEXTNONE; } for (i++; i < GCStateLength; i++) { if ((GCState[i] & mask) == mask) { return i; } } return E4_NEXTNONE; } int e4_StorageImpl::FirstUnreachableNodeID() { return FirstGCEntity(E4_GCNKU); } int e4_StorageImpl::NextUnreachableNodeID(int i) { return NextGCEntity(i, E4_GCNKU); } int e4_StorageImpl::FirstMaybeUnreachableNodeID() { return FirstGCEntity(E4_GCNRU); } int e4_StorageImpl::NextMaybeUnreachableNodeID(int i) { return NextGCEntity(i, E4_GCNRU); } int e4_StorageImpl::FirstUnreachableVertexID() { return FirstGCEntity(E4_GCVKU); } int e4_StorageImpl::NextUnreachableVertexID(int i) { return NextGCEntity(i, E4_GCVKU); } int e4_StorageImpl::FirstMaybeUnreachableVertexID() { return FirstGCEntity(E4_GCVRU); } int e4_StorageImpl::NextMaybeUnreachableVertexID(int i) { return NextGCEntity(i, E4_GCVRU); } int e4_StorageImpl::FirstReachableNodeID() { return FirstGCEntity(E4_GCNKR); } int e4_StorageImpl::NextReachableNodeID(int i) { return NextGCEntity(i, E4_GCNKR); } int e4_StorageImpl::FirstReachableVertexID() { return FirstGCEntity(E4_GCVKR); } int e4_StorageImpl::NextReachableVertexID(int i) { return NextGCEntity(i, E4_GCVKR); } bool e4_StorageImpl::IsGCState(int i, int mask) { if ((i > -1) && (GCState != NULL) && (GCStateLength > i)) { return ((GCState[i] & mask) == mask) ? true : false; } return false; } bool e4_StorageImpl::IsMaybeUnreachableNodeID(int i) { return IsGCState(i, E4_GCNRU); } bool e4_StorageImpl::IsMaybeUnreachableVertexID(int i) { return IsGCState(i, E4_GCVRU); } bool e4_StorageImpl::IsUnreachableNodeID(int i) { return IsGCState(i, E4_GCNKU); } bool e4_StorageImpl::IsUnreachableVertexID(int i) { return IsGCState(i, E4_GCVKU); } bool e4_StorageImpl::IsReachableNodeID(int i) { return IsGCState(i, E4_GCNKR); } bool e4_StorageImpl::IsReachableVertexID(int i) { return IsGCState(i, E4_GCVKR); } bool e4_StorageImpl::IsScannedNodeID(int i) { return IsGCState(i, E4_GCNSN); } bool e4_StorageImpl::IsScannedVertexID(int i) { return IsGCState(i, E4_GCVSN); } /* * This method does a partial GC on this storage: * * 1. Start with the registered unreachable nodes if any. * 2. For each such node, determine which of its children is unreachable. * 3. Some child node may have other parents besides the known unreachable * node. Mark those child nodes as maybe unreachable. * 4. Iterate until no more unreachable children are discovered. * 5. If some child nodes are marked as maybe unreachable mark the GC as * incomplete, otherwise it is a complete GC. * 4. Recycle all nodes marked as unreachable and all vertices in them etc. */ bool e4_StorageImpl::NewPartialGC(bool FullCleanOfGCState) { int i, emask; bool hascallbacks, detachednodes, detachedvertices; char mask; bool unknownstate; e4_VertexImpl *vp; e4_NodeImpl *np; /* * If there are no nodes/vertices about which we have state, * then no need to do GC. */ if (GCState == NULL) { return false; } /* * If we're doing a full clean then also remove known reachability marks. * Otherwise only remove the scanned marks. */ mask = (char) (E4_GCNSN | E4_GCVSN); if (FullCleanOfGCState) { mask |= (char) (E4_GCNKR | E4_GCVKR | E4_GCNKU | E4_GCVKU); } /* * Clean up state possibly left over from a previous GC. */ for (i = 0; i < GCStateLength; i++) { GCState[i] &= mask; } /* * Span everything that is unreachable, by starting from the known * unreachable entities. */ unknownstate = SpanUnreachable(); /* * Sweep (recycle) everything marked unreachable. */ SweepUnreachable(); /* * Deliver detach callbacks if there are any: */ hascallbacks = HasCallbacks(E4_ECDETNODE); for (i = 0, detachednodes = false; i < GCStateLength; i++) { if (DRV_IsNewlyDetachedNodeID(i)) { detachednodes = true; DRV_MarkDetachNotifiedNodeID(i); if (hascallbacks) { np = FindReferencedNode(i); if (np != NULL) { CauseEventInternal(E4_ECDETNODE, np, NULL); } } } } hascallbacks = HasCallbacks(E4_ECDETVERTEX); for (i = 0, detachedvertices = false; i < GCStateLength; i++) { if (DRV_IsNewlyDetachedVertexID(i)) { detachedvertices = true; DRV_MarkDetachNotifiedVertexID(i); if (hascallbacks) { vp = FindReferencedVertex(i); if (vp != NULL) { CauseEventInternal(E4_ECDETVERTEX, vp, NULL); } } } } /* * Record timestamp: */ emask = 0; if (detachedvertices) { emask |= E4_ECDETVERTEX; } if (detachednodes) { emask |= E4_ECDETNODE; } RecordTimeStamp(emask); /* * Finally return an indication whether any entities are left in an unknown * state. */ return unknownstate; } /* * This method does a full GC on this storage: */ void e4_StorageImpl::NewFullGC() { int i; if (NewPartialGC(true) && NewlyUnreachableEntities()) { (void) NewPartialGC(false); } /* * Remove all known unreachable marks. This is needed * because on partial GC the known unreachable marks * are not cleared by default. */ for (i = 0; i < GCStateLength; i++) { UnregisterUnreachableNodeID(i); UnregisterUnreachableVertexID(i); } } /* * This method recycles unreachable entities. */ void e4_StorageImpl::SweepUnreachable() { int i; /* * Sweep unreachable vertices: */ for (i = 0; i < GCStateLength; i++) { if (DRV_IsLegalVertexID(i) && IsUnreachableVertexID(i)) { DRV_FreeVertex(i); UnregisterUnreachableVertexID(i); } } /* * Sweep unreachable nodes: */ for (i = 0; i < GCStateLength; i++) { if (DRV_IsLegalNodeID(i) && IsUnreachableNodeID(i)) { DRV_FreeNode(i); UnregisterUnreachableNodeID(i); } } } /* * Extend the set of unreachable entities from the current set of * unreachable nodes and vertices. */ bool e4_StorageImpl::SpanUnreachable() { int i, j, k, l, v; bool done, unreachable, changed; /* * Repeatedly extend known unreachable nodes and vertices, until no * more new known unreachable entities are found. */ do { changed = false; for (i = 0; i < GCStateLength; i++) { /* * Find new unreachable nodes and mark all unreferenced * vertices in them as unreachable. */ if (IsUnreachableNodeID(i) && !IsScannedNodeID(i)) { SetScannedNodeID(i); for (j = 0, l = DRV_VertexCountFromNodeID(i); j < l; j++) { if (j == 0) { k = DRV_GetFirstVertexID(i); } else { k = DRV_NextVertexID(i); } if (IsReferencedVertex(k)) { RegisterReachableVertexID(k); SetScannedVertexID(k); } else { RegisterUnreachableVertexID(k); changed = true; } } } /* * Find new unreachable vertices. We use a simple algorithm * to decide whether nodes that are the value of unreachable * vertices are unreachable themselves: * * - if the node is referenced, it is reachable. * - otherwise, if there are detached referenced vertices that * have the node as their value, the node is reachable. * - otherwise, if all parent nodes are unreachable, this node * is also unreachable. * - otherwise, this node is (currently) unknown reachable. */ if (IsUnreachableVertexID(i) && !IsScannedVertexID(i)) { SetScannedVertexID(i); if (DRV_VertexTypeFromVertexID(i) == E4_VTNODE) { /* * The raw value associated with this vertex ID is * the ID of the node. */ (void) DRV_GetRawValue(i, v); /* * If that node is referenced or known reachable, we stop. */ if (IsReferencedNode(v) || IsReachableNodeID(v)) { RegisterReachableNodeID(v); UnregisterMaybeUnreachableNodeID(v); continue; } /* * If that node is the value of at least one detached * referenced vertex, we mark it as known reachable. */ for (k = DRV_GetFirstDetachedVertexIDWithNodeID(v), done = false; (k != E4_NEXTNONE) && (done == false); k = DRV_GetNextDetachedVertexIDAfter(k)) { if (IsReferencedVertex(k) || IsReachableVertexID(k)) { done = true; RegisterReachableNodeID(v); UnregisterMaybeUnreachableNodeID(v); } } if (done) { continue; } /* * At this point we found no referenced detached vertices * whose value is the node v. If all parent nodes of v are * known unreachable, then v is also unreachable. * * Special case: if v has no parents, then it is also * known at this point that v is unreachable. */ for (j = 1, unreachable = true, l = DRV_ParentCount(v); (j < l) && (unreachable); j++) { k = DRV_GetParentNodeID(v, j); if (k == E4_NODENOTFOUND) { continue; } if (!IsUnreachableNodeID(k)) { unreachable = false; } } if (unreachable) { RegisterUnreachableNodeID(v); UnregisterMaybeUnreachableNodeID(v); changed = true; continue; } /* * Otherwise we currently do not know whether the * node v is reachable or not, so mark it unknown * reachable. */ RegisterMaybeUnreachableNodeID(v); } } } } while (changed == true); /* * Return an indication whether we left some entities in the * unknown reachable state. */ for (i = 0; i < GCStateLength; i++) { if ((DRV_IsLegalVertexID(i) && IsMaybeUnreachableVertexID(i)) || (DRV_IsLegalNodeID(i) && IsMaybeUnreachableNodeID(i))) { return true; } } return false; } /* * Span all reachable entities by starting from those referenced by the * user program and the root node. */ void e4_StorageImpl::SpanReachable() { bool changed; int i, j, k, l, v; /* * Mark all vertices and nodes that are referenced by the user program * as reachable. */ for (i = 0; i < GCStateLength; i++) { if (IsReferencedNode(i)) { RegisterReachableNodeID(i); } if (IsReferencedVertex(i)) { RegisterReachableVertexID(i); } } /* * Add the root node. */ RegisterReachableNodeID(GetRootNodeID()); /* * Repeatedly extend reachability for vertices, and then for nodes, * until no more reachable entities are found. */ do { changed = false; for (i = 0; i < GCStateLength; i++) { if (IsReachableVertexID(i) && !IsScannedVertexID(i)) { SetScannedVertexID(i); if (DRV_VertexTypeFromVertexID(i) == E4_VTNODE) { /* * The raw value associated with this vertex ID is * the ID of the node. */ (void) DRV_GetRawValue(i, v); RegisterReachableNodeID(v); changed = true; } } } for (i = 0; i < GCStateLength; i++) { if (IsReachableNodeID(i) && !IsScannedNodeID(i)) { SetScannedNodeID(i); for (j = 0, l = DRV_VertexCountFromNodeID(i); j < l; j++) { if (j == 0) { k = DRV_GetFirstVertexID(i); } else { k = DRV_NextVertexID(i); } RegisterReachableVertexID(k); changed = true; } } } } while (changed); } /* * This method determines, for each entity marked as reachability unknown * whether it is reachable or not. If any entities are found that are known * unreachable, the method returns true, otherwise it returns false. */ bool e4_StorageImpl::NewlyUnreachableEntities() { bool newones = false; bool found; int i; /* * If we find at least one entity that is in an unknown state * then we have to mark everything that's reachable. */ for (i = 0, found = false; i < GCStateLength; i++) { if (IsMaybeUnreachableNodeID(i) || IsMaybeUnreachableVertexID(i)) { found = true; } UnregisterMaybeUnreachableNodeID(i); UnregisterMaybeUnreachableVertexID(i); } if (!found) { return false; } /* * Mark everything that's reachable. */ SpanReachable(); /* * At this point, if there are any in-use entities that are not marked * as reachable, they are unreachable. */ for (i = 0, newones = false; i < GCStateLength; i++) { if (DRV_IsLegalNodeID(i) && !IsReachableNodeID(i)) { RegisterUnreachableNodeID(i); newones = true; } if (DRV_IsLegalVertexID(i) && !IsReachableVertexID(i)) { RegisterUnreachableVertexID(i); newones = true; } } return newones; } /* * This method is called to clean up all references to this e4_StorageImpl * from other instances. */ void e4_StorageImpl::CleanUp() { /* * If we cannot modify the storage, do not attempt to commit at close: */ if ((perms & E4_SPCOMMIT) == E4_SPCOMMIT) { /* * If commit is needed and requested, do it now before the state * is destroyed. */ if (((statemask & E4_COMMITATCLOSE) == E4_COMMITATCLOSE) && IsUnstable()) { Commit(); } } HashCleanup(); } /* * Helper method to clean up the hash tables for various exported entities. */ void e4_StorageImpl::HashCleanup() { e4_HashEntry *hPtr; e4_HashSearch search; e4_NodeImpl *node; e4_VertexImpl *vertex; /* * Clean up my own state, consisting of the hash tables for * caching in-core instances of nodes and vertices. */ if (activeNodes != NULL) { for (hPtr = e4_FirstHashEntry(activeNodes, &search); hPtr != NULL; hPtr = e4_FirstHashEntry(activeNodes, &search)) { node = (e4_NodeImpl *) E4_GETHASHVALUE(hPtr); node->SetStorage(NULL); e4_DeleteHashEntry(hPtr); } } if (activeVertices != NULL) { for (hPtr = e4_FirstHashEntry(activeVertices, &search); hPtr != NULL; hPtr = e4_FirstHashEntry(activeVertices, &search)) { vertex = (e4_VertexImpl *) E4_GETHASHVALUE(hPtr); vertex->SetStorage(NULL); e4_DeleteHashEntry(hPtr); } } if (nameHash != NULL) { for (hPtr = e4_FirstHashEntry(nameHash, &search); hPtr != NULL; hPtr = e4_FirstHashEntry(nameHash, &search)) { e4_DeleteHashEntry(hPtr); } } } /* * This method is called when the reference count goes to (or below) zero. */ void e4_StorageImpl::NotReferenced() { e4_HashEntry *hPtr; CleanUp(); /* * Delete the hash tables associated with this instance so that * we do not leak memory. */ if (activeNodes != NULL) { e4_DeleteHashTable(activeNodes); free((char *) activeNodes); activeNodes = NULL; } if (activeVertices != NULL) { e4_DeleteHashTable(activeVertices); free((char *) activeVertices); activeVertices = NULL; } if (nameHash != NULL) { e4_DeleteHashTable(nameHash); free((char *) nameHash); nameHash = NULL; } if (callbacks != NULL) { e4_DeleteHashTable(callbacks); free((char *) callbacks); callbacks = NULL; } /* * Cause a last GC to clean up detached entities, before we commit. */ DRV_DoGC(E4_AUTOGC); /* * Remove this e4_StorageImpl from the global cache of * e4_StorageImpl instances. */ hPtr = E4_FINDHASHENTRY(activeStorages, name); if (hPtr == NULL) { return; } e4_DeleteHashEntry(hPtr); if (name != NULL) { delete[] name; } if (drivername != NULL) { delete[] drivername; } /* * Call the destructor which is most likely going to be overridden by * the derived class. */ delete this; } /* * Retrieve the first e4_StorageImpl. */ e4_StorageImpl * e4_StorageImpl::GetFirstStorageImpl() { e4_HashEntry *hPtr; e4_HashSearch search; if (activeStorages == NULL) { return NULL; } hPtr = e4_FirstHashEntry(activeStorages, &search); if (hPtr == NULL) { return NULL; } return (e4_StorageImpl *) E4_GETHASHVALUE(hPtr); } /* * Retrieve the next e4_StorageImpl after a given one. */ e4_StorageImpl * e4_StorageImpl::GetNextStorageImpl(e4_StorageImpl *cur) { e4_HashEntry *hPtr; e4_HashSearch search; if (cur == NULL) { return NULL; } if (activeStorages == NULL) { return NULL; } for (hPtr = e4_FirstHashEntry(activeStorages, &search); hPtr != NULL; hPtr = e4_NextHashEntry(&search)) { if (cur == (e4_StorageImpl *) E4_GETHASHVALUE(hPtr)) { hPtr = e4_NextHashEntry(&search); if (hPtr == NULL) { return NULL; } return (e4_StorageImpl *) E4_GETHASHVALUE(hPtr); } } /* * Current one not found, return NULL. */ return NULL; } /* * Add a callback. */ bool e4_StorageImpl::AddCallback(int eventCode, void *fn, void *clientData) { int key[E4_CALLBACKKEYSIZE]; union { void *ptr; int is[2]; } u; e4_HashEntry *ePtr; int isnew; key[0] = eventCode; if (sizeof(int) == sizeof(void *)) { u.ptr = (void *) fn; key[1] = u.is[0]; u.ptr = clientData; key[2] = u.is[0]; } else { u.ptr = fn; key[1] = u.is[0]; key[2] = u.is[1]; u.ptr = clientData; key[3] = u.is[0]; key[4] = u.is[1]; } ePtr = E4_CREATEHASHENTRY(callbacks, (char *) key, &isnew); E4_SETHASHVALUE(ePtr, (void *) NULL); callbacksPresent |= (1 << eventCode); return true; } /* * Remove a callback. */ bool e4_StorageImpl::DelCallback(int eventCode, void *fn, void *clientData) { int key[E4_CALLBACKKEYSIZE]; union { void *ptr; int is[2]; } u; int *keyPtr; e4_HashEntry *ePtr; e4_HashSearch search; key[0] = eventCode; if (sizeof(int) == sizeof(void *)) { u.ptr = (void *) fn; key[1] = u.is[0]; u.ptr = clientData; key[2] = u.is[0]; } else { u.ptr = fn; key[1] = u.is[0]; key[2] = u.is[1]; u.ptr = clientData; key[3] = u.is[0]; key[4] = u.is[1]; } ePtr = E4_FINDHASHENTRY(callbacks, (char *) key); if (ePtr != NULL) { e4_DeleteHashEntry(ePtr); } /* * Now see if there are any other callbacks of this kind left. If not, * then remove the notation that this kind of callback is present for * this storage. */ for (ePtr = e4_FirstHashEntry(callbacks, &search); ePtr != NULL; ePtr = e4_NextHashEntry(&search)) { keyPtr = (int *) E4_GETHASHKEY(callbacks, ePtr); if (keyPtr[0] == eventCode) { return true; } } /* * Did not find any, so remove the notation. */ callbacksPresent &=(~(1 << eventCode)); return true; } /* * Cause callbacks to be called for a specified kind of event on the * given reference. */ void e4_StorageImpl::CauseEventInternal(int eventCode, e4_RefCounter *ref, void *data) { union { void *ptr; int is[2]; } u; int *key; e4_RefCount r(ref); e4_CallbackFunction fn; e4_HashSearch search; e4_HashEntry *ePtr; if (callbacks == NULL) { return; } for (ePtr = e4_FirstHashEntry(callbacks, &search); ePtr != NULL; ePtr = e4_NextHashEntry(&search)) { key = (int *) E4_GETHASHKEY(callbacks, ePtr); if (key[0] == eventCode) { if (sizeof(int) == sizeof(void *)) { u.is[0] = key[1]; fn = (e4_CallbackFunction) u.ptr; u.is[0] = key[2]; (fn)((void *) u.ptr, r, data); } else { u.is[0] = key[1]; u.is[1] = key[2]; fn = (e4_CallbackFunction) u.ptr; u.is[0] = key[3]; u.is[1] = key[4]; (fn)(u.ptr, r, data); } } } } /* * Cause events for user defined event codes: */ bool e4_StorageImpl::CauseEvent(int eventCode, const e4_RefCount &r, void *data) { e4_CallbackFunction fn; union { void *ptr; int is[2]; } u; int *key; e4_HashSearch search; e4_HashEntry *ePtr; /* * No recorded callbacks? */ if (callbacks == NULL) { return false; } /* * Mark a timestamp for the user defined event. */ RecordTimeStamp(eventCode); /* * Deliver the event to all registered callbacks. */ for (ePtr = e4_FirstHashEntry(callbacks, &search); ePtr != NULL; ePtr = e4_NextHashEntry(&search)) { key = (int *) E4_GETHASHKEY(callbacks, ePtr); if (key[0] == eventCode) { if (sizeof(int) == sizeof(void *)) { u.is[0] = key[1]; fn = (e4_CallbackFunction) u.ptr; u.is[0] = key[2]; (fn)((void *) u.ptr, r, data); } else { u.is[0] = key[1]; u.is[1] = key[2]; fn = (e4_CallbackFunction) u.ptr; u.is[0] = key[3]; u.is[1] = key[4]; (fn)(u.ptr, r, data); } } } return true; } /* * Timestamp mechanism: */ void e4_StorageImpl::RecordTimeStamp(int eventMask) { int i; if (eventMask == 0) { return; } timestamp++; for (i = 0; i < E4_LASTUSERDEFINEDEVENTCODE+1; i++) { if ((eventMask & (1 << i)) == (1 << i)) { eventTimeStamps[i] = timestamp; } } } bool e4_StorageImpl::HasOccurredSince(int ts, int eventMask) const { int i; if (eventMask == 0) { return false; } for (i = 0; i < E4_LASTUSERDEFINEDEVENTCODE+1; i++) { if ((eventMask & (1 << i)) == (1 << i)) { if (eventTimeStamps[i] > ts) { return true; } } } return false; } int e4_StorageImpl::GetTimeStampFor(int eventMask) const { int ts = 0; int i; if (eventMask == 0) { return 0; } for (i = 0; i < E4_LASTUSERDEFINEDEVENTCODE+1; i++) { if ((eventMask & (1 << i)) == (1 << i)) { if (eventTimeStamps[i] > ts) { ts = eventTimeStamps[i]; } } } return ts; } /* * Get the node ID of a given node. */ int e4_StorageImpl::GetNodeID(e4_Node n) const { if (n.impl == NULL) { return E4_NEXTNONE; } return ((e4_NodeImpl *) n.impl)->nodeID; } /* * Create a detached node (not attached to any vertex): */ e4_NodeImpl * e4_StorageImpl::CreateDetachedNode() { int id; /* * If we cannot modify the storage, do not attempt: */ if ((perms & E4_SPMODIFY) == 0) { return NULL; } id = DRV_ReserveNodeID(); if (id == E4_NODENOTCREATED) { return NULL; } MarkUnstable(); return FindOrCreateNode(id); } /* * Create a detached vertex (not attached to a node). */ e4_VertexImpl * e4_StorageImpl::CreateDetachedVertex(const char *nm, e4_NodeImpl *nip) { int vertexID; int nodeID; int nameID; e4_VertexImpl *vip; /* * If we cannot modify the storage, do not attempt: */ if ((perms & E4_SPMODIFY) == 0) { return NULL; } nameID = InternName(nm, true); if (nameID == E4_NEXTNONE) { return NULL; } vertexID = DRV_ReserveVertexID(nameID); if (vertexID == E4_VERTEXNOTFOUND) { return NULL; } MarkUnstable(); /* * Must export vertex to user program before setting its value, * otherwise the SeVertexByIndex will fail. */ vip = new e4_VertexImpl(this, vertexID); StoreVertex(vertexID, vip); nodeID = nip->GetUniqueID(); if (!DRV_SetVertexByIndexToNode(vertexID, nodeID)) { return NULL; } return vip; } e4_VertexImpl * e4_StorageImpl::CreateDetachedVertex(const char *nm, int i) { int vertexID; int nameID; e4_VertexImpl *vip; /* * If we cannot modify the storage, do not attempt: */ if ((perms & E4_SPMODIFY) == 0) { return NULL; } nameID = InternName(nm, true); if (nameID == E4_NEXTNONE) { return NULL; } vertexID = DRV_ReserveVertexID(nameID); if (vertexID == E4_VERTEXNOTFOUND) { return NULL; } MarkUnstable(); /* * Must export vertex to user program before setting its value, * otherwise the SeVertexByIndex will fail. */ vip = new e4_VertexImpl(this, vertexID); StoreVertex(vertexID, vip); if (!DRV_SetVertexByIndex(vertexID, i)) { return NULL; } return vip; } e4_VertexImpl * e4_StorageImpl::CreateDetachedVertex(const char *nm, double d) { int vertexID; int nameID; e4_VertexImpl *vip; /* * If we cannot modify the storage, do not attempt: */ if ((perms & E4_SPMODIFY) == 0) { return NULL; } nameID = InternName(nm, true); if (nameID == E4_NEXTNONE) { return NULL; } vertexID = DRV_ReserveVertexID(nameID); if (vertexID == E4_VERTEXNOTFOUND) { return NULL; } MarkUnstable(); /* * Must export vertex to user program before setting its value, * otherwise the SeVertexByIndex will fail. */ vip = new e4_VertexImpl(this, vertexID); StoreVertex(vertexID, vip); if (!DRV_SetVertexByIndex(vertexID, d)) { return NULL; } return vip; } e4_VertexImpl * e4_StorageImpl::CreateDetachedVertex(const char *nm, const char *s) { int vertexID; int nameID; e4_VertexImpl *vip; /* * If we cannot modify the storage, do not attempt: */ if ((perms & E4_SPMODIFY) == 0) { return NULL; } nameID = InternName(nm, true); if (nameID == E4_NEXTNONE) { return NULL; } vertexID = DRV_ReserveVertexID(nameID); if (vertexID == E4_VERTEXNOTFOUND) { return NULL; } MarkUnstable(); /* * Must export vertex to user program before setting its value, * otherwise the SeVertexByIndex will fail. */ vip = new e4_VertexImpl(this, vertexID); StoreVertex(vertexID, vip); if (!DRV_SetVertexByIndex(vertexID, s)) { return NULL; } return vip; } e4_VertexImpl * e4_StorageImpl::CreateDetachedVertex(const char *nm, const void *b, int nb) { int vertexID; int nameID; e4_VertexImpl *vip; /* * If we cannot modify the storage, do not attempt: */ if ((perms & E4_SPMODIFY) == 0) { return NULL; } nameID = InternName(nm, true); if (nameID == E4_NEXTNONE) { return NULL; } vertexID = DRV_ReserveVertexID(nameID); if (vertexID == E4_VERTEXNOTFOUND) { return NULL; } MarkUnstable(); /* * Must export vertex to user program before setting its value, * otherwise the SeVertexByIndex will fail. */ vip = new e4_VertexImpl(this, vertexID); StoreVertex(vertexID, vip); if (!DRV_SetVertexByIndex(vertexID, b, nb)) { return NULL; } return vip; } /* * Helper function for moving a vertex into a node to a position computed * from 'order' and 'rank'. */ bool e4_StorageImpl::MoveVertex(int nodeID, int vertexID, e4_InsertOrder order, int rank) { bool wasdetached; e4_VertexImpl *vp; e4_NodeImpl *nip; int prevVertexID = E4_VERTEXNOTFOUND; int prevNodeID, oldRank, prevRank; wasdetached = DRV_IsDetachedVertexID(vertexID); if (!wasdetached) { prevNodeID = DRV_ContainingNodeIDFromVertexID(vertexID); if (prevNodeID != nodeID) { nip = FindReferencedNode(prevNodeID); if (nip != NULL) { nip->FlushCache(); } } } if (order != E4_IOLAST) { nip = FindReferencedNode(nodeID); if (nip != NULL) { nip->FlushCache(); } } switch (order) { case E4_IOFIRST: if (DRV_MoveVertexToFirst(vertexID, nodeID) == false) { return false; } break; case E4_IOLAST: if (DRV_MoveVertexToLast(vertexID, nodeID) == false) { return false; } break; case E4_IOBEFORE: if ((rank == 0) || (rank == 1)) { return false; } else if (rank == 2) { if (DRV_MoveVertexToFirst(vertexID, nodeID) == false) { return false; } } else if ((rank < 0) || (rank > DRV_VertexCountFromNodeID(nodeID))) { if (DRV_MoveVertexToLast(vertexID, nodeID) == false) { return false; } } else { prevRank = rank - 1; prevVertexID = DRV_VertexIDFromRank(nodeID, prevRank); if (prevVertexID == E4_VERTEXNOTFOUND) { fprintf(stderr, "no prev vertex found\n"); return false; } if (DRV_ContainingNodeIDFromVertexID(vertexID) == nodeID) { oldRank = DRV_RankFromVertexID(nodeID, vertexID); /* * If the vertex is already in the correct rank, nothing to do. */ if (oldRank == rank) { return true; } /* * If the vertex is preceding the position after which it will * be inserted, increment the rank after which it will be * inserted, because the rank of that position will be lowered * by splicing out the vertex from its current position. */ if (oldRank <= prevRank) { prevRank++; prevVertexID = DRV_VertexIDFromRank(nodeID, prevRank); if (prevVertexID == E4_VERTEXNOTFOUND) { return false; } } } if (DRV_MoveVertexAfter(vertexID, prevVertexID, prevRank) == false) { return false; } } break; case E4_IOAT: if (rank == 1) { if (DRV_MoveVertexToFirst(vertexID, nodeID) == false) { return false; } } else if ((rank < 0) || (rank > DRV_VertexCountFromNodeID(nodeID))) { if (DRV_MoveVertexToLast(vertexID, nodeID) == false) { return false; } } else if (rank == 0) { return false; } else { prevRank = rank - 1; prevVertexID = DRV_VertexIDFromRank(nodeID, prevRank); if (prevVertexID == E4_VERTEXNOTFOUND) { fprintf(stderr, "no prev vertex found\n"); return false; } if (DRV_ContainingNodeIDFromVertexID(vertexID) == nodeID) { oldRank = DRV_RankFromVertexID(nodeID, vertexID); /* * If the vertex is already in the correct rank, nothing to do. */ if (oldRank == rank) { return true; } /* * If the vertex is preceding the position after which it will * be inserted, increment the rank after which it will be * inserted, because the rank of that position will be lowered * by splicing out the vertex from its current position. */ if (oldRank <= prevRank) { prevRank++; prevVertexID = DRV_VertexIDFromRank(nodeID, prevRank); if (prevVertexID == E4_VERTEXNOTFOUND) { return false; } } } if (DRV_MoveVertexAfter(vertexID, prevVertexID, prevRank) == false) { return false; } } break; case E4_IOAFTER: if (rank == 0) { if (DRV_MoveVertexToFirst(vertexID, nodeID) == false) { return false; } } else if ((rank < 0) || (rank >= DRV_VertexCountFromNodeID(nodeID))) { if (DRV_MoveVertexToLast(vertexID, nodeID) == false) { return false; } } else { prevRank = rank; prevVertexID = DRV_VertexIDFromRank(nodeID, prevRank); if (prevVertexID == E4_VERTEXNOTFOUND) { return false; } if (DRV_ContainingNodeIDFromVertexID(vertexID) == nodeID) { oldRank = DRV_RankFromVertexID(nodeID, vertexID); /* * If the vertex is already in the correct rank, nothing to do. */ if (oldRank == rank + 1) { return true; } /* * If the vertex is preceding the position after which it will * be inserted, increment the rank after which it will be * inserted, because the rank of that position will be lowered * by splicing out the vertex from its current position. */ if (oldRank <= prevRank) { prevRank++; prevVertexID = DRV_VertexIDFromRank(nodeID, prevRank); if (prevVertexID == E4_VERTEXNOTFOUND) { return false; } } } if (DRV_MoveVertexAfter(vertexID, prevVertexID, prevRank) == false) { return false; } } break; default: return false; } MarkUnstable(); if (wasdetached) { RecordTimeStamp(E4_ECMODNODE | E4_ECATTVERTEX); if (HasCallbacks(E4_ECATTVERTEX)) { vp = FindReferencedVertex(vertexID); if (vp != NULL) { CauseEventInternal(E4_ECATTVERTEX, vp, NULL); vp->ClearFlags(E4_CBDETACHDELIVERED); } } } else { RecordTimeStamp(E4_ECMODNODE); } if (HasCallbacks(E4_ECMODNODE)) { if (nodeID == prevNodeID) { CauseEventInternal(E4_ECMODNODE, this, (void *) E4_ERMNMOVVERTEX); } else { CauseEventInternal(E4_ECMODNODE, this, (void *) E4_ERMNINSVERTEX); } if ((nodeID != prevNodeID) && (prevNodeID != E4_NODENOTFOUND)) { CauseEventInternal(E4_ECMODNODE, FindNode(prevNodeID), (void *) E4_ERMNDETVERTEX); } } return true; }