/* * mkstorage.cpp -- * * This file contains the implementation of the * e4_MetakitStorageImpl class. * * 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 the e4Graph types used directly here. */ #include "e4graphimpl.h" /* * Include the type information specific to this storage driver. */ #include "mkstorage.h" /* * These constants define bits for recording state information about * an entity (vertex or node) in a storage. * * MK4_INUSE Persistent, notes that the entity is * in use. * MK4_REACHABLE Transient, used during GC to note * that this entity is reachable. * MK4_DETACHED Persistent, notes that this entity * is detached. It will become unreachable * if the user program drops the last * reference to it. * MK4_DETACHNOTIFY Transient, notes that this detached * entity has had a detach notification * delivered to it. */ #define MK4_INUSE (1<<0) #define MK4_REACHABLE (1<<1) #define MK4_DETACHED (1<<2) #define MK4_DETACHNOTIFY (1<<3) /* * Properties for indexing entities in a storage (common across 1.0, 1.1, * 1.2 and 1.3): */ c4_IntProp pUserData("userData"); c4_IntProp pNameID("nameID"); c4_IntProp pNext("next"); c4_IntProp pPrev("prev"); c4_ViewProp pMarkers("e4GraphMarkers"); c4_IntProp pRoot("root"); c4_ViewProp pNodes("e4GraphNodes"); c4_IntProp pFirstVertex("firstVertex"); c4_IntProp pLastVertex("lastVertex"); c4_IntProp pParentID("parentID"); c4_IntProp pVertexCount("vertexCount"); c4_IntProp pRefCount("refCount"); c4_IntProp pNodeMarkers("nodeMarkers"); c4_ViewProp pVertices("e4GraphVertices"); c4_IntProp pNodeID("nodeID"); c4_IntProp pVertexType("vertexType"); c4_IntProp pRowID("row"); c4_ViewProp pInts("e4GraphInts"); c4_IntProp pIntVal("i"); c4_ViewProp pDoubles("e4GraphDoubles"); c4_DoubleProp pDoubleVal("d"); c4_ViewProp pStrings("e4GraphStrings"); c4_StringProp pStringVal("s"); c4_ViewProp pNames("e4GraphNames"); c4_StringProp pNameVal("n"); c4_ViewProp pBinary("e4Graphbinary"); c4_BytesProp pBinaryVal("b"); c4_ViewProp pUnused("e4GraphUnused"); c4_IntProp pFirst("first"); c4_ViewProp pParents("e4GraphParents"); c4_IntProp pCount("count"); /* * In 1.4 the marker properties are defined but unused. We need them * to be defined to be able to convert storages written in an older * version to the newer format. */ /* * Properties present only since 1.3: */ /* * The "detachedvertices" property (occurs in nodes) points at the head * of a list of detached vertices that have this node as their value. These * detached vertices are chained through their "nextinparent" property. */ c4_IntProp pDetachedVertices("detachedvertices"); /* * Properties present only since 1.2: */ /* * The "vertexchain" property (occurs in parent records) contains the start * of a chain of vertices in a parent node that have a specific child node * as their value. */ c4_IntProp pVertexChain("vertexchain"); /* * The "nextinparent" property (occurs in vertices) contains the next vertex * in a chain of vertices. */ c4_IntProp pNextInParent("nextinparent"); /* * Properties present only since 1.1: */ /* * The "flags" property (occurs on all items in a storage) replaces and * generalizes the "used" property that was removed since 1.1. */ c4_IntProp pFlags("flags"); /* * Properties present only in 1.0, removed later: */ c4_IntProp pUsed("used"); /* * This class static factory method is used to create a new * instance of e4_MetakitStorageImpl or return an existing one. */ e4_StorageImpl * e4_MetakitStorageImpl::GetStorage(const char *fname, int state, int pps) { return new e4_MetakitStorageImpl(fname, state, pps); } /* * This class static method retrieves information out of a storage * about what version of e4Graph was used to write the storage. */ bool e4_MetakitStorageImpl::GetVersionInfo(const char *fname, int &maj, int &min, e4_ReleaseStatus &rs, int &ri) { c4_Storage *storage = new c4_Storage(fname, 0); c4_View mi; if (storage == NULL) { return false; } /* * Check that the open succeeded. */ if (!storage->Strategy().IsValid()) { delete storage; return false; } /* * Obtain the meta-information view. */ mi = storage->GetAs(MK4_GRAPHUNUSED1_5); if (mi.GetSize() < MK4_GRAPHUNUSEDSIZE_1_5) { delete storage; return false; } /* * Extract the values for which version of e4Graph was used * to write this storage. */ maj = (int) pFirst(mi[MK4_GRAPHE4GRAPHMAJORVERSION]); min = (int) pFirst(mi[MK4_GRAPHE4GRAPHMINORVERSION]); rs = (e4_ReleaseStatus) (int) pFirst(mi[MK4_GRAPHE4GRAPHRELSTATUS]); ri = (int) pFirst(mi[MK4_GRAPHE4GRAPHRELITER]); delete storage; return true; } /* * The default constructor throws. */ e4_MetakitStorageImpl::e4_MetakitStorageImpl() : e4_StorageImpl("", E4_METAKIT, E4_SPDEFAULTMASK) { throw "can't instantiate e4_MetaktStorageImpl"; } /* * This constructor opens a storage according to the provided permissions. */ e4_MetakitStorageImpl::e4_MetakitStorageImpl(const char *fname, int state, int pps) : e4_StorageImpl(fname, E4_METAKIT, pps), needsGC(false), idStack1(NULL), idStack2(NULL) { int openmode = ((pps & E4_SPCOMMIT) == E4_SPCOMMIT) ? 1 : 0; const char *desc; /* * Open the storage in exclusive read-write mode or in read-only mode * depending on the passed permissions. */ storage = new c4_Storage(fname, openmode); if (storage == NULL) { return; } /* * Check that the open succeeded. */ if (!storage->Strategy().IsValid()) { delete storage; storage = NULL; return; } /* * If we're not allowed to initialize this storage, make a quick * check that the file already contains a Metakit storage. If not * then return without doing anything further. */ if ((pps & E4_SPINITIALIZE) == 0) { desc = storage->Description(); if ((desc == NULL) || (*desc == '\0')) { delete storage; storage = NULL; return; } } /* * Check that initialization succeeded. */ if (!Initialize(state, ((pps & E4_SPINITIALIZE) == E4_SPINITIALIZE), ((pps & E4_SPUPDATEFORMAT) == E4_SPUPDATEFORMAT))) { delete storage; storage = NULL; return; } } /* * Helper function for initializing a storage. */ bool e4_MetakitStorageImpl::Initialize(int state, bool caninit, bool canupdate) { int i, j, cnt, flags; unused = storage->GetAs(MK4_GRAPHUNUSED1_4); if (unused.GetSize() == 0) { /* * If this is a totally new storage and we cannot set up * our data structures, return false. */ if (!caninit) { return false; } unused.SetSize(MK4_GRAPHUNUSEDSIZE_1_5); pFirst(unused[MK4_GRAPHSTORAGEMAJORVER]) = (int) E4_MKSTORAGE_MAJORVER; pFirst(unused[MK4_GRAPHSTORAGEMINORVER]) = (int) E4_MKSTORAGE_MINORVER; for (i = MK4_GRAPHFIRSTUNUSEDMARKER; i < MK4_GRAPHUNUSEDSIZE_1_5; i++) { pFirst(unused[i]) = (int) E4_NEXTNONE; } /* * Need better source of randomness than the address of the storage! */ pFirst(unused[MK4_GRAPHHASHCODE]) = (int) ((long) this & 0xFFFFFFFF); /* * The storage is initially clean -- no leaked data. */ pFirst(unused[MK4_GRAPHUNREACHABLENODES]) = 0; /* * Initialize the root node. */ pFirst(unused[MK4_GRAPHROOTNODE]) = E4_NEXTNONE; /* * Write the (current) version of e4Graph that was used to create * the storage, into the unused view. */ pFirst(unused[MK4_GRAPHE4GRAPHMAJORVERSION]) = (int) E4GRAPH_MAJOR; pFirst(unused[MK4_GRAPHE4GRAPHMINORVERSION]) = (int) E4GRAPH_MINOR; pFirst(unused[MK4_GRAPHE4GRAPHRELSTATUS]) = (int) E4GRAPH_RELEASESTATUS; pFirst(unused[MK4_GRAPHE4GRAPHRELITER]) = (int) E4GRAPH_RELEASEITER; } /* * Ensure the data stored in the storage just opened is in a * format compatible with the current version of the driver. */ if ((int) pFirst(unused[MK4_GRAPHSTORAGEMAJORVER]) != E4_MKSTORAGE_MAJORVER) { fprintf(stderr, "**Warning**: version mismatch: storage version %d.%d, ", (int) pFirst(unused[MK4_GRAPHSTORAGEMAJORVER]), (int) pFirst(unused[MK4_GRAPHSTORAGEMINORVER])); fprintf(stderr, "expected version: %d.X. ABORTING\n", E4_MKSTORAGE_MAJORVER); return false; } /* * Check if the minor version is older than what we expect. If it is * then fix the storage transparently to be of the format expected by * the newer minor version, if possible. */ switch ((int) pFirst(unused[MK4_GRAPHSTORAGEMINORVER])) { case 0: /* * Attempt to convert format 1.0 to format 1.1: */ if (!canupdate) { return false; } UpdateFormat1_0to1_1(); /* * Fall through: */ case 1: /* * Attempt to convert format 1.1 to format 1.2: */ if (!canupdate) { return false; } UpdateFormat1_1to1_2(); /* * Fall through: */ case 2: if (!canupdate) { return false; } UpdateFormat1_2to1_3(); /* * Fall through: */ case 3: /* * Attempt to convert format 1.3 to format 1.4: */ if (!canupdate) { return false; } UpdateFormat1_3to1_4(); /* * Fall through: */ case 4: /* * Attempt to convert format 1.4 to format 1.5: */ if (!canupdate) { return false; } UpdateFormat1_4to1_5(); /* * Fall through: */ case 5: /* * Get the storage structure as expected by the current minor * version. */ nodes = storage->GetAs(MK4_GRAPHNODES1_5); vertices = storage->GetAs(MK4_GRAPHVERTICES1_5); doubles = storage->GetAs(MK4_GRAPHDOUBLES1_5); strings = storage->GetAs(MK4_GRAPHSTRINGS1_5); binary = storage->GetAs(MK4_GRAPHBINARY1_5); names = storage->GetAs(MK4_GRAPHNAMES1_5); parents = storage->GetAs(MK4_GRAPHPARENTS1_5); break; default: fprintf(stderr, "Expected version %d.%d or earlier, got %d.%d. ABORTING\n", E4_MKSTORAGE_MAJORVER, E4_MKSTORAGE_MINORVER, E4_MKSTORAGE_MAJORVER, (int) pFirst(unused[MK4_GRAPHSTORAGEMINORVER])); return false; } /* * Hash all the names. */ PopulateNameHash(); for (cnt = 0, i = 0; i < nodes.GetSize(); i++) { if (((int) pFlags(nodes[i]) & MK4_INUSE) == MK4_INUSE) { cnt++; } } /* * Initialize the array of statistics. */ for (i = 0; i < (int) E4_SPLAST; i++) { for (j = 0; j < (int) E4_SSLAST; j++) { statistics[i][j] = 0; } } statistics[(int) E4_SPNODE][(int) E4_SSAVAIL] = nodes.GetSize(); statistics[(int) E4_SPVERTEX][(int) E4_SSAVAIL] = vertices.GetSize(); statistics[(int) E4_SPNAME][(int) E4_SSAVAIL] = names.GetSize(); statistics[(int) E4_SPSTRING][(int) E4_SSAVAIL] = strings.GetSize(); statistics[(int) E4_SPDOUBLE][(int) E4_SSAVAIL] = doubles.GetSize(); statistics[(int) E4_SPBINARY][(int) E4_SSAVAIL] = binary.GetSize(); for (i = 0, cnt = 0; i < nodes.GetSize(); i++) { if (((int) pFlags(nodes[i]) & MK4_INUSE) == MK4_INUSE) { cnt++; } } statistics[(int) E4_SPNODE][(int) E4_SSUSED] = cnt; for (i = 0, cnt = 0; i < vertices.GetSize(); i++) { if (((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) { cnt++; } } statistics[(int) E4_SPVERTEX][(int) E4_SSUSED] = cnt; for (i = 0, cnt = 0; i < names.GetSize(); i++) { if (((int) pFlags(names[i]) & MK4_INUSE) == MK4_INUSE) { cnt++; } } statistics[(int) E4_SPNAME][(int) E4_SSUSED] = cnt; for (i = 0, cnt = 0; i < strings.GetSize(); i++) { if (((int) pFlags(strings[i]) & MK4_INUSE) == MK4_INUSE) { cnt++; } } statistics[(int) E4_SPSTRING][(int) E4_SSUSED] = cnt; for (i = 0, cnt = 0; i < doubles.GetSize(); i++) { if (((int) pFlags(doubles[i]) & MK4_INUSE) == MK4_INUSE) { cnt++; } } statistics[(int) E4_SPDOUBLE][(int) E4_SSUSED] = cnt; for (i = 0, cnt = 0; i < binary.GetSize(); i++) { if (((int) pFlags(binary[i]) & MK4_INUSE) == MK4_INUSE) { cnt++; } } statistics[(int) E4_SPBINARY][(int) E4_SSUSED] = cnt; /* * Initialize the deletion stacks. */ idStack1 = new e4_IntStack(); idStack2 = new e4_IntStack(); /* * Initialize the GC counters and boolean needsGC indicator. */ needsGC = false; /* * Set the state passed in. */ if (state == -1) { state = E4_DEFAULTSTATE; } SetState(state); /* * Clean up any remaining detached entities after the last commit, * if requested. */ if ((GetState() & E4_OPENGC) == E4_OPENGC) { CleanupDetached(); } /* * If there's no root node, reserve it now. */ if ((int) pFirst(unused[MK4_GRAPHROOTNODE]) == E4_NEXTNONE) { /* * If we do not have permission to reserve it, bail out. */ if (!caninit) { return false; } pFirst(unused[MK4_GRAPHROOTNODE]) = i = DRV_ReserveNodeID(); /* * Special handling -- we do not want to fire a detach * event on the root node we just created, so mark it * as already having had an event fired on it. */ flags = (int) pFlags(nodes[i]); flags |= MK4_DETACHNOTIFY; pFlags(nodes[i]) = flags; } /* * Initially the storage is clean. */ MarkStable(); return true; } /* * Clean up any remaining detached entities after the last commit. This * is done when a storage is re-opened. * * NOTE: We just find the first detached entity and delete it. The GC * mechanism will find all other detached unreachable entities. */ void e4_MetakitStorageImpl::CleanupDetached() { int i, l, r, flags; /* * Search for any detached vertices. */ for (i = 0, l = vertices.GetSize(); i < l; i++) { flags = (int) pFlags(vertices[i]); if ((flags & (MK4_INUSE | MK4_DETACHED)) == (MK4_INUSE | MK4_DETACHED)) { flags &= ~(MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(vertices[i]) = flags; DRV_DoGC(E4_AUTOGC); /* * If we found one, we did the GC, so we're done -- GC will * have taken care of any other detached vertices or nodes. */ return; } } /* * Search for any detached nodes. Skip the root node because it * might be detached but is still reachable. */ for (i = 0, r = (int) pFirst(unused[MK4_GRAPHROOTNODE]), l = nodes.GetSize(); i < l; i++) { /* * Skip the root node. */ if (i == r) { continue; } /* * Check if this node is detached. */ flags = (int) pFlags(nodes[i]); if ((flags & (MK4_INUSE | MK4_DETACHED)) == (MK4_INUSE | MK4_DETACHED)) { flags &= ~(MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(nodes[i]) = flags; DRV_DoGC(E4_AUTOGC); /* * If we found one, we did the GC, so we're done -- GC will * have taken care of any other detached vertices or nodes. */ return; } } } /* * Helper method to update the format from 1.4 to 1.5: */ void e4_MetakitStorageImpl::UpdateFormat1_4to1_5() { /* * Get the unused view, enlarge it to the right number * of slots, and add the e4Graph version number. */ unused = storage->GetAs(MK4_GRAPHUNUSED1_4); unused.SetSize(MK4_GRAPHUNUSEDSIZE_1_5); pFirst(unused[MK4_GRAPHE4GRAPHMAJORVERSION]) = (int) E4GRAPH_MAJOR; pFirst(unused[MK4_GRAPHE4GRAPHMINORVERSION]) = (int) E4GRAPH_MINOR; pFirst(unused[MK4_GRAPHE4GRAPHRELSTATUS]) = (int) E4GRAPH_RELEASESTATUS; pFirst(unused[MK4_GRAPHE4GRAPHRELITER]) = (int) E4GRAPH_RELEASEITER; /* * Commit the update: */ storage->Commit(); } /* * Helper method to update the format from 1.3 to 1.4: */ void e4_MetakitStorageImpl::UpdateFormat1_3to1_4() { int i, l, r, v, rank; /* * Get the markers view using the 1.3 format: */ markers = storage->GetAs(MK4_GRAPHMARKERS1_3); /* * Extract the root node. */ r = (int) pFirst(unused[MK4_GRAPHROOTNODE]); /* * For each marker, add a vertex to the root node with the marked * node as its value. */ for (i = 0, l = markers.GetSize(); i < l; i++) { /* * Only look at in use markers: */ if (((int) pFlags(markers[i]) & MK4_INUSE) == 0) { continue; } /* * Add a new vertex to the root: */ v = DRV_AddVertex(r, E4_IOLAST, rank); if (v == E4_VERTEXNOTCREATED) { /* * Should abort. */ } /* * Now set its value to the node marked by the i'th marker: */ DRV_SetVertex(v, (int) pNameID(markers[i]), E4_VTNODE, pRoot(markers[i])); } /* * Discard the markers data. */ markers.SetSize(0); /* * Now get the remaining views with the new format: */ nodes = storage->GetAs(MK4_GRAPHNODES1_4); vertices = storage->GetAs(MK4_GRAPHVERTICES1_4); doubles = storage->GetAs(MK4_GRAPHDOUBLES1_4); strings = storage->GetAs(MK4_GRAPHSTRINGS1_4); binary = storage->GetAs(MK4_GRAPHBINARY1_4); names = storage->GetAs(MK4_GRAPHNAMES1_4); parents = storage->GetAs(MK4_GRAPHNAMES1_4); pFirst(unused[MK4_GRAPHSTORAGEMINORVER]) = E4_MKSTORAGE_MINORVER; /* * Commit the changed format. */ storage->Commit(); } /* * Helper method to update the format from 1.2 to 1.3: */ void e4_MetakitStorageImpl::UpdateFormat1_2to1_3() { int i, l; /* * Get the nodes view using the 1.2 format: */ nodes = storage->GetAs(MK4_GRAPHNODES1_2); /* * Now add the "detachedvertices" property with the value * E4_NEXTNONE to each node. */ for (i = 0, l = nodes.GetSize(); i < l; i++) { pDetachedVertices(nodes[i]) = E4_NEXTNONE; } /* * Now get the views with the new format: */ markers = storage->GetAs(MK4_GRAPHMARKERS1_3); nodes = storage->GetAs(MK4_GRAPHNODES1_3); vertices = storage->GetAs(MK4_GRAPHVERTICES1_3); doubles = storage->GetAs(MK4_GRAPHDOUBLES1_3); strings = storage->GetAs(MK4_GRAPHSTRINGS1_3); binary = storage->GetAs(MK4_GRAPHBINARY1_3); names = storage->GetAs(MK4_GRAPHNAMES1_3); parents = storage->GetAs(MK4_GRAPHNAMES1_3); pFirst(unused[MK4_GRAPHSTORAGEMINORVER]) = E4_MKSTORAGE_MINORVER; /* * Commit the changed format. */ storage->Commit(); } /* * Helper method to update the format from 1.1 to 1.2: */ void e4_MetakitStorageImpl::UpdateFormat1_1to1_2() { int i, l, pid, parentID, vv, pv; /* * Get all the views using the 1.1 format: */ markers = storage->GetAs(MK4_GRAPHMARKERS1_1); nodes = storage->GetAs(MK4_GRAPHNODES1_1); vertices = storage->GetAs(MK4_GRAPHVERTICES1_1); doubles = storage->GetAs(MK4_GRAPHDOUBLES1_1); strings = storage->GetAs(MK4_GRAPHSTRINGS1_1); binary = storage->GetAs(MK4_GRAPHBINARY1_1); names = storage->GetAs(MK4_GRAPHNAMES1_1); parents = storage->GetAs(MK4_GRAPHPARENTS1_1); /* * Add the new properties: */ vertices.AddProperty(pNextInParent); parents.AddProperty(pVertexChain); /* * For each node, traverse its parents and form a chain of * all vertices in that parent whose value is this node. */ for (i = 0, l = nodes.GetSize(); i < l; i++) { /* * If this index is not used, skip it. */ if (((int) pFlags(nodes[i]) & MK4_INUSE) == 0) { continue; } /* * Found a node that is in use. Update its parent list so * that each parent record will contain the list of vertices * in that parent that point at this node. */ for (pid = (int) pParentID(nodes[i]); pid != E4_NEXTNONE; pid = (int) pNext(parents[pid])) { /* * Get the parent node. */ parentID = (int) pNodeID(parents[pid]); /* * Iterate over its vertices, looking for vertices that * have the current node as their value. */ for (vv = (int) pFirstVertex(nodes[parentID]), pv = E4_NEXTNONE; vv != E4_NEXTNONE; vv = (int) pNext(vertices[vv])) { /* * See if this vertex has the current node as its value. */ if (((int) pVertexType(vertices[vv]) == E4_VTNODE) && ((int) pRowID(vertices[vv]) == i)) { /* * Put this vertex into the list of vertices * reached from the parent record. */ if (pv == E4_NEXTNONE) { pVertexChain(parents[pid]) = vv; } else { pNextInParent(vertices[pv]) = vv; } /* * Remember previous link in chain. */ pv = vv; } } } } /* * Now get the views with the new format: */ markers = storage->GetAs(MK4_GRAPHMARKERS1_2); nodes = storage->GetAs(MK4_GRAPHNODES1_2); vertices = storage->GetAs(MK4_GRAPHVERTICES1_2); doubles = storage->GetAs(MK4_GRAPHDOUBLES1_2); strings = storage->GetAs(MK4_GRAPHSTRINGS1_2); binary = storage->GetAs(MK4_GRAPHBINARY1_2); names = storage->GetAs(MK4_GRAPHNAMES1_2); parents = storage->GetAs(MK4_GRAPHNAMES1_2); pFirst(unused[MK4_GRAPHSTORAGEMINORVER]) = E4_MKSTORAGE_MINORVER; storage->Commit(); } /* * Helper method to update the format from 1.0 to 1.1: */ void e4_MetakitStorageImpl::UpdateFormat1_0to1_1() { int i, l; /* * Get all the views using the 1.0 format: */ markers = storage->GetAs(MK4_GRAPHMARKERS1_0); nodes = storage->GetAs(MK4_GRAPHNODES1_0); vertices = storage->GetAs(MK4_GRAPHVERTICES1_0); doubles = storage->GetAs(MK4_GRAPHDOUBLES1_0); strings = storage->GetAs(MK4_GRAPHSTRINGS1_0); binary = storage->GetAs(MK4_GRAPHBINARY1_0); names = storage->GetAs(MK4_GRAPHNAMES1_0); parents = storage->GetAs(MK4_GRAPHPARENTS1_0); /* * Add the new property "flags": */ markers.AddProperty(pFlags); nodes.AddProperty(pFlags); vertices.AddProperty(pFlags); doubles.AddProperty(pFlags); strings.AddProperty(pFlags); binary.AddProperty(pFlags); names.AddProperty(pFlags); parents.AddProperty(pFlags); /* * For each entry, check if its "used" propert was set -- if so, set * the "flags" property to MK4_INUSE. */ for (i = 0, l = markers.GetSize(); i < l; i++) { if ((int) pUsed(markers[i]) == 1) { pFlags(markers[i]) = (int) MK4_INUSE; } } for (i = 0, l = nodes.GetSize(); i < l; i++) { if ((int) pUsed(nodes[i]) == 1) { pFlags(nodes[i]) = (int) MK4_INUSE; } } for (i = 0, l = vertices.GetSize(); i < l; i++) { if ((int) pUsed(vertices[i]) == 1) { pFlags(vertices[i]) = (int) MK4_INUSE; } } for (i = 0, l = doubles.GetSize(); i < l; i++) { if ((int) pUsed(doubles[i]) == 1) { pFlags(doubles[i]) = (int) MK4_INUSE; } } for (i = 0, l = strings.GetSize(); i < l; i++) { if ((int) pUsed(strings[i]) == 1) { pFlags(strings[i]) = (int) MK4_INUSE; } } for (i = 0, l = binary.GetSize(); i < l; i++) { if ((int) pUsed(binary[i]) == 1) { pFlags(binary[i]) = (int) MK4_INUSE; } } for (i = 0, l = names.GetSize(); i < l; i++) { if ((int) pUsed(names[i]) == 1) { pFlags(names[i]) = (int) MK4_INUSE; } } for (i = 0, l = parents.GetSize(); i < l; i++) { if ((int) pUsed(parents[i]) == 1) { pFlags(parents[i]) = (int) MK4_INUSE; } } /* * Now discard the old "used" property by getting the views with * the new format: */ markers = storage->GetAs(MK4_GRAPHMARKERS1_1); nodes = storage->GetAs(MK4_GRAPHNODES1_1); vertices = storage->GetAs(MK4_GRAPHVERTICES1_1); doubles = storage->GetAs(MK4_GRAPHDOUBLES1_1); strings = storage->GetAs(MK4_GRAPHSTRINGS1_1); binary = storage->GetAs(MK4_GRAPHBINARY1_1); names = storage->GetAs(MK4_GRAPHNAMES1_1); parents = storage->GetAs(MK4_GRAPHNAMES1_1); pFirst(unused[MK4_GRAPHSTORAGEMINORVER]) = E4_MKSTORAGE_MINORVER; storage->Commit(); } /* * The destructor: */ e4_MetakitStorageImpl::~e4_MetakitStorageImpl() { /* * If the Metakit storage is still open, close it. */ if (storage != NULL) { delete storage; } /* * Clean up the deletion stacks if they're present. */ if (idStack1 != NULL) { delete idStack1; } if (idStack2 != NULL) { delete idStack2; } } /* * Commit changes to this storage */ bool e4_MetakitStorageImpl::DRV_Commit() { if (!IsUnstable()) { return true; } DRV_DoGC(E4_GCBEFORECOMMIT); if (storage != NULL) { storage->Commit(); } MarkStable(); return true; } /* * Is this instance valid? */ bool e4_MetakitStorageImpl::DRV_IsValid() const { return ((storage != NULL) && (storage->Strategy().IsValid())); } /* * Helper functions to initialize and manage the free lists. */ void e4_MetakitStorageImpl::PopulateNameHash() { int i, lim; for (i = 0, lim = names.GetSize(); i < lim; i++) { if (((int) pFlags(names[i]) & MK4_INUSE) == MK4_INUSE) { AddNameToNameHash(pNameVal(names[i]), i); } } } void e4_MetakitStorageImpl::MakeParentSpace() { int next = parents.GetSize(); int newsize = next + MK4_GRAPHINCREMENT; parents.SetSize(newsize); pFirst(unused[MK4_GRAPHFIRSTUNUSEDPARENT]) = next; for (; next < newsize; next++) { pNext(parents[next]) = next + 1; pFlags(parents[next]) = 0; } pNext(parents[newsize - 1]) = E4_NEXTNONE; pFlags(parents[newsize - 1]) = 0; } void e4_MetakitStorageImpl::MakeNodeSpace() { int next = nodes.GetSize(); int newsize = next + MK4_GRAPHINCREMENT; nodes.SetSize(newsize); pFirst(unused[MK4_GRAPHFIRSTUNUSEDNODE]) = next; for (; next < newsize; next++) { pNext(nodes[next]) = next + 1; pFlags(nodes[next]) = 0; } pNext(nodes[newsize - 1]) = E4_NEXTNONE; pFlags(nodes[newsize - 1]) = 0; statistics[(int) E4_SPNODE][(int) E4_SSAVAIL] = newsize; } void e4_MetakitStorageImpl::MakeVertexSpace() { int next = vertices.GetSize(); int newsize = next + MK4_GRAPHINCREMENT; vertices.SetSize(newsize); pFirst(unused[MK4_GRAPHFIRSTUNUSEDVERTEX]) = next; for (; next < newsize; next++) { pNext(vertices[next]) = next + 1; pFlags(vertices[next]) = 0; } pNext(vertices[newsize - 1]) = E4_NEXTNONE; pFlags(vertices[newsize - 1]) = 0; statistics[(int) E4_SPVERTEX][(int) E4_SSAVAIL] = newsize; } void e4_MetakitStorageImpl::MakeDoubleSpace() { int next = doubles.GetSize(); int newsize = next + MK4_GRAPHINCREMENT; doubles.SetSize(newsize); pFirst(unused[MK4_GRAPHFIRSTUNUSEDDOUBLE]) = next; for (; next < newsize; next++) { pNext(doubles[next]) = next + 1; pFlags(doubles[next]) = 0; } pNext(doubles[newsize - 1]) = E4_NEXTNONE; pFlags(doubles[newsize - 1]) = 0; statistics[(int) E4_SPDOUBLE][(int) E4_SSAVAIL] = newsize; } void e4_MetakitStorageImpl::MakeStringSpace() { int next = strings.GetSize(); int newsize = next + MK4_GRAPHINCREMENT; strings.SetSize(newsize); pFirst(unused[MK4_GRAPHFIRSTUNUSEDSTRING]) = next; for (; next < newsize; next++) { pNext(strings[next]) = next + 1; pFlags(strings[next]) = 0; } pNext(strings[newsize - 1]) = E4_NEXTNONE; pFlags(strings[newsize - 1]) = 0; statistics[(int) E4_SPSTRING][(int) E4_SSAVAIL] = newsize; } void e4_MetakitStorageImpl::MakeBinarySpace() { int next = binary.GetSize(); int newsize = next + MK4_GRAPHINCREMENT; binary.SetSize(newsize); pFirst(unused[MK4_GRAPHFIRSTUNUSEDBINARY]) = next; for (; next < newsize; next++) { pNext(binary[next]) = next + 1; pFlags(binary[next]) = 0; } pNext(binary[newsize - 1]) = E4_NEXTNONE; pFlags(binary[newsize - 1]) = 0; statistics[(int) E4_SPBINARY][(int) E4_SSAVAIL] = newsize; } void e4_MetakitStorageImpl::MakeNameSpace() { int next = names.GetSize(); int newsize = next + MK4_GRAPHINCREMENT; names.SetSize(newsize); pFirst(unused[MK4_GRAPHFIRSTUNUSEDNAME]) = next; for (; next < newsize; next++) { pNext(names[next]) = next + 1; pFlags(names[next]) = 0; } pNext(names[newsize - 1]) = E4_NEXTNONE; pFlags(names[newsize - 1]) = 0; statistics[(int) E4_SPNAME][(int) E4_SSAVAIL] = newsize; } /* * Reclaim the storage occuppied by a vertex: */ void e4_MetakitStorageImpl::DRV_FreeVertex(int id) { int n; switch ((int) pVertexType(vertices[id])) { case E4_VTNODE: n = (int) pRowID(vertices[id]); /* * Clean up the association between the node value and this vertex * if we are not recycling the node value now (its not known to be * unreachable). If we are recycling the node value then it will be * cleaned up when the node is recycled. */ if (!IsUnreachableNodeID(n)) { RemoveNodeVertexAssoc(n, id); } break; case E4_VTINT: /* * Nothing to do, because the integer is allocated inline inside * the pRowID property. */ break; case E4_VTDOUBLE: FreeDouble((int) pRowID(vertices[id])); break; case E4_VTSTRING: FreeString((int) pRowID(vertices[id])); break; case E4_VTBINARY: FreeBinary((int) pRowID(vertices[id])); break; } UnusedVertex(id); } /* * Reclaim the storage occuppied by a node: */ void e4_MetakitStorageImpl::DRV_FreeNode(int id) { int p, pn; /* * Recycle all the overhead structures associated with this node. * No need to recycle vertices, they've been recycled already. */ for (p = (int) pParentID(nodes[id]); p != E4_NEXTNONE; p = pn) { pn = (int) pNext(parents[p]); UnusedParent(p); } UnusedNode(id); } /* * Mark a node as having had a node detach notify callback delivered: */ void e4_MetakitStorageImpl::DRV_MarkDetachNotifiedNodeID(int id) { int flags; /* * If index is out of bounds, return. */ if ((id < 0) || (id >= nodes.GetSize())) { return; } /* * If not MK4_INUSE return. */ flags = (int) pFlags(nodes[id]); if ((flags & MK4_INUSE) == 0) { return; } /* * If not detached, return. */ if ((flags & MK4_DETACHED) == 0) { return; } flags |= MK4_DETACHNOTIFY; pFlags(nodes[id]) = flags; } /* * Mark a vertex as having had a detach notify callback delivered. */ void e4_MetakitStorageImpl::DRV_MarkDetachNotifiedVertexID(int id) { int flags; /* * If index is out of bounds, return. */ if ((id < 0) || (id >= vertices.GetSize())) { return; } /* * If not MK4_INUSE return. */ flags = (int) pFlags(vertices[id]); if ((flags & MK4_INUSE) == 0) { return; } /* * If not detached, return. */ if ((flags & MK4_DETACHED) == 0) { return; } flags |= MK4_DETACHNOTIFY; pFlags(vertices[id]) = flags; } /* * Has a detach callback not yet been delivered for this node? * False means the callback has already been delivered or the * node is not detached. */ bool e4_MetakitStorageImpl::DRV_IsNewlyDetachedNodeID(int id) { int flags; /* * If index is out of bounds, return false. */ if ((id < 0) || (id >= nodes.GetSize())) { return false; } /* * If not MK4_INUSE return false. */ flags = (int) pFlags(nodes[id]); if ((flags & MK4_INUSE) == 0) { return false; } /* * If not detached, return false. */ if ((flags & MK4_DETACHED) == 0) { return false; } /* * Check if the MK4_DETACHNOTIFY is set. If yes, then return false. */ if ((flags & MK4_DETACHNOTIFY) == MK4_DETACHNOTIFY) { return false; } return true; } /* * Has a detach callback not yet been delivered for this vertex? * False means the callback has already been delivered or the * node is not detached. */ bool e4_MetakitStorageImpl::DRV_IsNewlyDetachedVertexID(int id) { int flags; /* * If index is out of bounds, return false. */ if ((id < 0) || (id >= vertices.GetSize())) { return false; } /* * If not MK4_INUSE return false. */ flags = (int) pFlags(vertices[id]); if ((flags & MK4_INUSE) == 0) { return false; } /* * If not detached, return false. */ if ((flags & MK4_DETACHED) == 0) { return false; } /* * Check if the MK4_DETACHNOTIFY is set. If yes, then return false. */ if ((flags & MK4_DETACHNOTIFY) == MK4_DETACHNOTIFY) { return false; } return true; } /* * If parentID denotes a node that is a parent of the node denoted by * childID, return true, else return false. */ bool e4_MetakitStorageImpl::DRV_IsParentID(int parentID, int childID) const { int pid; for (pid = (int) pParentID(nodes[childID]); pid != E4_NEXTNONE; pid = (int) pNext(parents[pid])) { if (parentID == (int) pNodeID(parents[pid])) { return true; } } return false; } /* * Compute the rank of a child node in the vertex list of a node. */ int e4_MetakitStorageImpl::DRV_GetRankOfChildNode(int parentID, int childID, int ith) const { int f, rank, count; if ((parentID < 0) || (parentID >= nodes.GetSize()) || (((int) pFlags(nodes[parentID]) & MK4_INUSE) == 0) || (childID < 0) || (childID >= nodes.GetSize()) || (((int) pFlags(nodes[childID]) & MK4_INUSE) == 0)) { return E4_VERTEXNOTFOUND; } for (count = 1, rank = 1, f = (int) pFirstVertex(nodes[parentID]); f != E4_NEXTNONE; f = (int) pNext(vertices[f]), rank++) { if (((e4_VertexType) (int) pVertexType(vertices[f]) == E4_VTNODE) && ((int) pRowID(vertices[f]) == childID)) { if (count == ith) { return rank; } count++; } } return E4_VERTEXNOTFOUND; } /* * Helper function to set a vertex value: */ bool e4_MetakitStorageImpl::DRV_SetVertex(int index, int nameID, int vertexType, int itemID) { pVertexType(vertices[index]) = vertexType; pNameID(vertices[index]) = nameID; pRowID(vertices[index]) = itemID; /* * Special handling for E4_VTNODE: */ if (vertexType == E4_VTNODE) { AddParent(itemID, (int) pNodeID(vertices[index]), index); } /* * Do not change the "next" and "used" property. */ return true; } /* * Reserve a vertex for a detached vertex: */ int e4_MetakitStorageImpl::DRV_ReserveVertexID(int nameID) { int i; /* * First of all grab a free row in the "vertices" view. */ if ((int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDVERTEX]) == E4_NEXTNONE) { MakeVertexSpace(); } i = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDVERTEX]); pFirst(unused[MK4_GRAPHFIRSTUNUSEDVERTEX]) = (int) pNext(vertices[i]); pNodeID(vertices[i]) = E4_NEXTNONE; pVertexType(vertices[i]) = E4_VTINT; pRowID(vertices[i]) = 0; /* * The vertex starts out detached. Since we do not want to receive * a detach callback on this vertex (if it stays detached) we mark * it as already having had its callback. */ pFlags(vertices[i]) = (MK4_INUSE | MK4_DETACHED | MK4_DETACHNOTIFY); pNameID(vertices[i]) = nameID; return i; } /* * Insert a new vertex in the node identified by nodeID at the position * indicated by "io" and "rank". The ID of the new vertex is returned. */ int e4_MetakitStorageImpl::DRV_AddVertex(int nodeID, e4_InsertOrder io, int &rank) { int i, j, k, flags; /* * See if we can reserve a vertex: */ i = DRV_ReserveVertexID(0); if (i < 0) { return E4_VERTEXNOTFOUND; } /* * Update the count of used vertices. */ statistics[(int) E4_SPVERTEX][(int) E4_SSUSED]++; statistics[(int) E4_SPVERTEX][(int) E4_SSALLOC]++; /* * Initialize the values in the newly allocated vertex. */ pNameID(vertices[i]) = -1; pNodeID(vertices[i]) = nodeID; pRowID(vertices[i]) = -1; pUserData(vertices[i]) = 0; /* * The vertex is no longer detached. */ flags = (int) pFlags(vertices[i]); flags &= ~(MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(vertices[i]) = flags; /* * Now use the row we grabbed as the vertex indicated by the "io" and * "rank" arguments. */ switch (io) { case E4_IOFIRST: pNext(vertices[i]) = (int) pFirstVertex(nodes[nodeID]); pPrev(vertices[i]) = E4_NEXTNONE; if ((int) pFirstVertex(nodes[nodeID]) != E4_NEXTNONE) { pPrev(vertices[pFirstVertex(nodes[nodeID])]) = i; } pFirstVertex(nodes[nodeID]) = i; if ((int) pLastVertex(nodes[nodeID]) == E4_NEXTNONE) { pLastVertex(nodes[nodeID]) = i; } rank = 1; break; case E4_IOLAST: pNext(vertices[i]) = E4_NEXTNONE; if ((int) pFirstVertex(nodes[nodeID]) == E4_NEXTNONE) { pFirstVertex(nodes[nodeID]) = i; } if ((int) pLastVertex(nodes[nodeID]) != E4_NEXTNONE) { pPrev(vertices[i]) = (int) pLastVertex(nodes[nodeID]); pNext(vertices[pLastVertex(nodes[nodeID])]) = i; } else { pPrev(vertices[i]) = E4_NEXTNONE; } pLastVertex(nodes[nodeID]) = i; rank = (int) pVertexCount(nodes[nodeID]) + 1; break; case E4_IOAT: case E4_IOBEFORE: if (rank == 1) { pNext(vertices[i]) = (int) pFirstVertex(nodes[nodeID]); pPrev(vertices[i]) = E4_NEXTNONE; if ((int) pLastVertex(nodes[nodeID]) == E4_NEXTNONE) { pLastVertex(nodes[nodeID]) = i; } if ((int) pFirstVertex(nodes[nodeID]) != E4_NEXTNONE) { pPrev(vertices[pFirstVertex(nodes[nodeID])]) = i; } pFirstVertex(nodes[nodeID]) = i; rank = 1; } else { j = DRV_VertexIDFromRank(nodeID, rank - 1); if (j == E4_VERTEXNOTFOUND) { goto error; } k = (int) pNext(vertices[j]); if (k != E4_VERTEXNOTFOUND) { pPrev(vertices[k]) = i; } pNext(vertices[j]) = i; pNext(vertices[i]) = k; pPrev(vertices[i]) = j; if ((int) pLastVertex(nodes[nodeID]) == j) { pLastVertex(nodes[nodeID]) = i; } rank = i; } break; case E4_IOAFTER: j = DRV_VertexIDFromRank(nodeID, rank); if (j == E4_VERTEXNOTFOUND) { goto error; } pNext(vertices[i]) = (int) pNext(vertices[j]); pPrev(vertices[i]) = j; if ((int) pNext(vertices[i]) != E4_NEXTNONE) { pPrev(vertices[pNext(vertices[i])]) = i; } pNext(vertices[j]) = i; if ((int) pLastVertex(nodes[nodeID]) == j) { pLastVertex(nodes[nodeID]) = i; } rank = j + 1; break; } /* * Update the vertex count for this node. */ pVertexCount(nodes[nodeID]) = (int) pVertexCount(nodes[nodeID]) + 1; return i; error: /* * Some kind of error occurred, after we allocated the new row. * Free up the allocated row so that it can be used in a future * operation. */ UnusedVertex(i); return E4_VERTEXNOTCREATED; } /* * Free a row occupied by a 64-bit floating point value. */ bool e4_MetakitStorageImpl::FreeDouble(int doubleID) { if ((doubleID < 0) || (doubleID >= doubles.GetSize()) || (((int) pFlags(doubles[doubleID]) & MK4_INUSE) == 0)) { return false; } UnusedDouble(doubleID); return true; } /* * Free a row occupied by a string value. Release the storage occupied by * the actual string value also. */ bool e4_MetakitStorageImpl::FreeString(int stringID) { if ((stringID < 0) || (stringID >= strings.GetSize()) || (((int) pFlags(strings[stringID]) & MK4_INUSE) == 0)) { return false; } UnusedString(stringID); pStringVal(strings[stringID]) = ""; return true; } /* * Free a row occupied by a binary value. Release the storage occupied by * the actual value also. */ bool e4_MetakitStorageImpl::FreeBinary(int binaryID) { if ((binaryID < 0) || (binaryID >= binary.GetSize()) || (((int) pFlags(binary[binaryID]) & MK4_INUSE) == 0)) { return false; } UnusedBinary(binaryID); c4_Bytes bytes(NULL, 0); pBinaryVal(binary[binaryID]) = bytes; return true; } /* * Return a node from a designated row. */ bool e4_MetakitStorageImpl::DRV_GetNode(int index, e4_NodeImpl *&value) const { if ((index < 0) || (index >= nodes.GetSize()) || (((int) pFlags(nodes[index]) & MK4_INUSE) == 0)) { return false; } value = FindOrCreateNode(index); return true; } /* * Specialized internal version to return a node from a designated row. */ bool e4_MetakitStorageImpl::DRV_GetNode(int index, e4_NodeImpl *&value, bool *isNew) const { if ((index < 0) || (index >= nodes.GetSize()) || (((int) pFlags(nodes[index]) & MK4_INUSE) == 0)) { return false; } value = FindOrCreateNode(index, isNew); return true; } /* * Return an integer value from a designated row. */ bool e4_MetakitStorageImpl::DRV_GetInt(int index, int &value) const { /* * Integers are represented directly in the vertex, so the index * *is* the vertex value. */ value = index; return true; } /* * Return a 64-bit floating point value from a designated row. */ bool e4_MetakitStorageImpl::DRV_GetDouble(int index, double &value) const { if ((index < 0) || (index >= doubles.GetSize()) || (((int) pFlags(doubles[index]) & MK4_INUSE) == 0)) { return false; } value = (double) pDoubleVal(doubles[index]); return true; } /* * Return a string value from a designated row. */ bool e4_MetakitStorageImpl::DRV_GetString(int index, char *&value) const { if ((index < 0) || (index >= strings.GetSize()) || (((int) pFlags(strings[index]) & MK4_INUSE) == 0)) { return false; } value = (char *) (const char *) pStringVal(strings[index]); return true; } /* * Return a binary value from a designated row. */ bool e4_MetakitStorageImpl::DRV_GetBinary(int index, void *&value, int &nbytes) const { if ((index < 0) || (index >= binary.GetSize()) || (((int) pFlags(binary[index]) & MK4_INUSE) == 0)) { return false; } c4_Bytes bytes = pBinaryVal(binary[index]); value = (void *) (const void *) bytes.Contents(); nbytes = bytes.Size(); return true; } /* * Retrieve a vertex name by the name ID. */ bool e4_MetakitStorageImpl::DRV_GetVertexName(int index, const char *&nm) const { if ((index < 0) || (index >= names.GetSize()) || (((int) pFlags(names[index]) & MK4_INUSE) == 0)) { return false; } nm = pNameVal(names[index]); return true; } /* * Retrieve the raw value ID (for use by GC only). */ bool e4_MetakitStorageImpl::DRV_GetRawValue(int index, int &value) const { if ((index < 0) || (index >= vertices.GetSize()) || (((int) pFlags(vertices[index]) & MK4_INUSE) == 0)) { return false; } value = (int) pRowID(vertices[index]); return true; } /* * Retrieve the node ID that is the value of a vertex. */ bool e4_MetakitStorageImpl::DRV_GetNodeID(int index, int &id) const { if ((index < 0) || (index >= vertices.GetSize()) || (((int) pFlags(vertices[index]) & MK4_INUSE) == 0) || ((e4_VertexType) (int) pVertexType(vertices[index]) != E4_VTNODE)) { return false; } id = (int) pRowID(vertices[index]); return true; } /* * Returns true if the given ID is that of the root node. */ bool e4_MetakitStorageImpl::DRV_IsRootNodeID(int nodeID) { if ((int) pFirst(unused[MK4_GRAPHROOTNODE]) == nodeID) { return true; } return false; } /* * Get the ID of the root node. */ int e4_MetakitStorageImpl::DRV_GetRootNodeID() { return (int) pFirst(unused[MK4_GRAPHROOTNODE]); } /* * Set the root node to another node. */ bool e4_MetakitStorageImpl::DRV_SetRootNodeID(int newRootID) { /* * Sanity checks. */ if ((newRootID < 0) || (newRootID >= nodes.GetSize()) || (((int) pFlags(nodes[newRootID]) & MK4_INUSE) != MK4_INUSE)) { return false; } /* * Set the new root ID: */ pFirst(unused[MK4_GRAPHROOTNODE]) = newRootID; return true; } /* * Add a row for a new node. */ int e4_MetakitStorageImpl::DRV_ReserveNodeID() { int idx; if (pFirst(unused[MK4_GRAPHFIRSTUNUSEDNODE]) == E4_NEXTNONE) { MakeNodeSpace(); } idx = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDNODE]); pFirst(unused[MK4_GRAPHFIRSTUNUSEDNODE]) = (int) pNext(nodes[idx]); statistics[(int) E4_SPNODE][(int) E4_SSUSED]++; statistics[(int) E4_SPNODE][(int) E4_SSALLOC]++; /* * The node starts out as detached. We don't want to receive a detach * callback on this node (if it stays detached) so we mark it as having * already had a callback. */ pFlags(nodes[idx]) = (MK4_INUSE | MK4_DETACHED | MK4_DETACHNOTIFY); pUserData(nodes[idx]) = 0; pNext(nodes[idx]) = E4_NEXTNONE; pVertexCount(nodes[idx]) = 0; pFirstVertex(nodes[idx]) = E4_NEXTNONE; pLastVertex(nodes[idx]) = E4_NEXTNONE; pParentID(nodes[idx]) = E4_NEXTNONE; pRefCount(nodes[idx]) = 0; pDetachedVertices(nodes[idx]) = E4_NEXTNONE; return idx; } /* * Add an integer to the storage -- nothing to do because the * integer is represented directly in the vertex. */ int e4_MetakitStorageImpl::DRV_AddInt(int value) { return value; } /* * Add a row for a new 64-bit floating point value. */ int e4_MetakitStorageImpl::DRV_AddDouble(double value) { int idx; if ((int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDDOUBLE]) == E4_NEXTNONE) { MakeDoubleSpace(); } idx = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDDOUBLE]); pFirst(unused[MK4_GRAPHFIRSTUNUSEDDOUBLE]) = (int) pNext(doubles[idx]); statistics[(int) E4_SPDOUBLE][(int) E4_SSUSED]++; statistics[(int) E4_SPDOUBLE][(int) E4_SSALLOC]++; pFlags(doubles[idx]) = MK4_INUSE; pDoubleVal(doubles[idx]) = value; return idx; } /* * Add a row for a new string value. */ int e4_MetakitStorageImpl::DRV_AddString(const char *value) { int idx; if ((int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDSTRING]) == E4_NEXTNONE) { MakeStringSpace(); } idx = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDSTRING]); pFirst(unused[MK4_GRAPHFIRSTUNUSEDSTRING]) = (int) pNext(strings[idx]); statistics[(int) E4_SPSTRING][(int) E4_SSUSED]++; statistics[(int) E4_SPSTRING][(int) E4_SSALLOC]++; pFlags(strings[idx]) = MK4_INUSE; pStringVal(strings[idx]) = value; return idx; } /* * Add a row for a new binary value. */ int e4_MetakitStorageImpl::DRV_AddBinary(const void *value, int nbytes) { c4_Bytes bytes(value, nbytes); int idx; if ((int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDBINARY]) == E4_NEXTNONE) { MakeBinarySpace(); } idx = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDBINARY]); pFirst(unused[MK4_GRAPHFIRSTUNUSEDBINARY]) = (int) pNext(binary[idx]); statistics[(int) E4_SPBINARY][(int) E4_SSUSED]++; statistics[(int) E4_SPBINARY][(int) E4_SSALLOC]++; pFlags(binary[idx]) = MK4_INUSE; pBinaryVal(binary[idx]) = bytes; return idx; } /* * Add a row for a new vertex, node or marker name. */ int e4_MetakitStorageImpl::DRV_AddName(const char *nm) { int idx; if ((int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDNAME]) == E4_NEXTNONE) { MakeNameSpace(); } idx = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDNAME]); pFirst(unused[MK4_GRAPHFIRSTUNUSEDNAME]) = (int) pNext(names[idx]); statistics[(int) E4_SPNAME][(int) E4_SSUSED]++; statistics[(int) E4_SPNAME][(int) E4_SSALLOC]++; pFlags(names[idx]) = MK4_INUSE; pNameVal(names[idx]) = nm; return idx; } int e4_MetakitStorageImpl::DRV_VertexIDFromNthVertex(int nodeID, int nameID, int nth, int &rank) const { int i, r, cnt; /* * Its not cached, so we must search for it the slow way. Note * that it's also not known whether there is an nth vertex with * name nameID in this node. */ for (r = 1, i = (int) pFirstVertex(nodes[nodeID]), cnt = 0; i != E4_NEXTNONE; i = (int) pNext(vertices[i]), r++) { if ((int) pNameID(vertices[i]) == nameID) { cnt++; if (cnt == nth) { break; } } } if ((cnt != nth) || (i == E4_NEXTNONE) || ((int) pNameID(vertices[i]) != nameID)) { return E4_VERTEXNOTFOUND; } rank = r; return i; } int e4_MetakitStorageImpl::DRV_VertexIDFromRank(int nodeID, int rank) const { int i, r; /* * Quick check to see if the node has at least that many * vertices. If not, we do not need to search. */ if ((rank < 1) || ((int) pVertexCount(nodes[nodeID]) < rank)) { return E4_VERTEXNOTFOUND; } /* * The data we were looking for is not cached, so we * must search for it the slow way. But we know at this * point that the search will be successful. */ for (i = (int) pFirstVertex(nodes[nodeID]), r = 1; r < rank; i = (int) pNext(vertices[i]), r++) { } return i; } int e4_MetakitStorageImpl::DRV_RankFromVertexID(int nodeID, int index) const { int i, r; for (i = (int) pFirstVertex(nodes[nodeID]), r = 1; (i != E4_NEXTNONE) && (i != index); i = (int) pNext(vertices[i]), r++) { } if (i != index) { r = E4_VERTEXNOTFOUND; } return r; } int e4_MetakitStorageImpl::DRV_GetVertexIDInParent(int parentID, int childID, int ith) const { int i, count; /* * Sanity checks. */ if ((parentID < 0) || (parentID >= nodes.GetSize()) || (((int) pFlags(nodes[parentID]) & MK4_INUSE) == 0) || (childID < 0) || (childID >= nodes.GetSize()) || (((int) pFlags(nodes[childID]) & MK4_INUSE) == 0)) { return E4_VERTEXNOTFOUND; } /* * Look for ith vertex in parent that contains * the child node as its value. We cannot use the * nextInParent chain because that's not guaranteed * to be in rank order. */ for (count = 1, i = (int) pFirstVertex(nodes[parentID]); i != E4_NEXTNONE; i = (int) pNext(vertices[i])) { if (((e4_VertexType) (int) pVertexType(vertices[i]) == E4_VTNODE) && ((int) pRowID(vertices[i]) == childID)) { if (count == ith) { return i; } count++; } } return E4_VERTEXNOTFOUND; } /* * Free the storage occupied by an old value of a vertex: */ void e4_MetakitStorageImpl::FreeVertexValue(int vertexID) { int x = 0; switch (pVertexType(vertices[vertexID])) { case E4_VTNODE: RemoveParent((int) pRowID(vertices[vertexID]), (int) pNodeID(vertices[vertexID]), vertexID, true); break; case E4_VTINT: /* * Nothing to do because the value is represented directly * in the vertex. */ break; case E4_VTDOUBLE: FreeDouble((int) pRowID(vertices[vertexID])); break; case E4_VTSTRING: FreeString((int) pRowID(vertices[vertexID])); break; case E4_VTBINARY: FreeBinary((int) pRowID(vertices[vertexID])); break; default: /* * Should abort here. */ break; } } /* * Get the value of a vertex given its index. */ bool e4_MetakitStorageImpl::DRV_GetVertexByIndex(int i, e4_ValueImpl *&v) const { e4_ValueImpl *vp; e4_NodeImpl *n; double d; char *s; void *bytes; int nbytes; vp = new e4_ValueImpl; vp->vertexType = (e4_VertexType) (int) pVertexType(vertices[i]); switch(vp->vertexType) { case E4_VTUNKNOWN: return false; case E4_VTNODE: if (DRV_GetNode((int) pRowID(vertices[i]), n) != true) { return false; } vp->u.n = n; break; case E4_VTINT: /* * Integers are represented directly in a vertex. */ vp->u.i = (int) pRowID(vertices[i]); break; case E4_VTDOUBLE: if (DRV_GetDouble((int) pRowID(vertices[i]), d) != true) { return false; } vp->u.d = d; break; case E4_VTSTRING: if (DRV_GetString((int) pRowID(vertices[i]), s) != true) { return false; } vp->u.s = s; break; case E4_VTBINARY: if (DRV_GetBinary((int) pRowID(vertices[i]), bytes, nbytes) != true) { return false; } vp->u.b.bytes = bytes; vp->u.b.nbytes = nbytes; break; default: return false; } v = vp; return true; } bool e4_MetakitStorageImpl::DRV_GetVertexByIndex(int i, e4_NodeImpl *&n) const { if ((int) pVertexType(vertices[i]) != E4_VTNODE) { return false; } return DRV_GetNode((int) pRowID(vertices[i]), n); } bool e4_MetakitStorageImpl::DRV_GetVertexByIndex(int i, int &value) const { if ((int) pVertexType(vertices[i]) != E4_VTINT) { return false; } /* * Integers are represented directly in the vertex. */ value = (int) pRowID(vertices[i]); return true; } bool e4_MetakitStorageImpl::DRV_GetVertexByIndex(int i, double &value) const { if ((int) pVertexType(vertices[i]) != E4_VTDOUBLE) { return false; } return DRV_GetDouble((int) pRowID(vertices[i]), value); } bool e4_MetakitStorageImpl::DRV_GetVertexByIndex(int i, const char *&value) const { char *lvalue; if ((int) pVertexType(vertices[i]) != E4_VTSTRING) { return false; } if (DRV_GetString((int) pRowID(vertices[i]), lvalue)) { value = lvalue; return true; } return false; } bool e4_MetakitStorageImpl::DRV_GetVertexByIndex(int i, const void *&bytes, int &nbytes) const { void *lbytes; if ((int) pVertexType(vertices[i]) != E4_VTBINARY) { return false; } if (DRV_GetBinary((int) pRowID(vertices[i]), lbytes, nbytes)) { bytes = lbytes; return true; } return false; } /* * Set a vertex whose index is given: */ bool e4_MetakitStorageImpl::DRV_SetVertexByIndex(int i, int value) { if (pVertexType(vertices[i]) != E4_VTINT) { FreeVertexValue(i); } DRV_SetVertex(i, pNameID(vertices[i]), E4_VTINT, value); return true; } bool e4_MetakitStorageImpl::DRV_SetVertexByIndex(int i, double value) { int j; if ((int) pVertexType(vertices[i]) != E4_VTDOUBLE) { FreeVertexValue(i); j = DRV_AddDouble(value); DRV_SetVertex(i, (int) pNameID(vertices[i]), E4_VTDOUBLE, j); } else { pDoubleVal(doubles[pRowID(vertices[i])]) = value; } return true; } bool e4_MetakitStorageImpl::DRV_SetVertexByIndex(int i, const char *value) { int j; if ((int) pVertexType(vertices[i]) != E4_VTSTRING) { FreeVertexValue(i); j = DRV_AddString(value); DRV_SetVertex(i, (int) pNameID(vertices[i]), E4_VTSTRING, j); } else { /* * NOTE: This assumes that string values are not * shared. */ pStringVal(strings[pRowID(vertices[i])]) = value; } return true; } bool e4_MetakitStorageImpl::DRV_SetVertexByIndex(int i, const void *bs, int nbs) { int j; if ((int) pVertexType(vertices[i]) != E4_VTBINARY) { FreeVertexValue(i); j = DRV_AddBinary(bs, nbs); DRV_SetVertex(i, pNameID(vertices[i]), E4_VTBINARY, j); } else { c4_Bytes bytes(bs, nbs); pBinaryVal(binary[pRowID(vertices[i])]) = bytes; } return true; } bool e4_MetakitStorageImpl::DRV_SetVertexByIndexToNode(int i, int childID) { FreeVertexValue(i); DRV_SetVertex(i, pNameID(vertices[i]), E4_VTNODE, childID); return true; } bool e4_MetakitStorageImpl::DRV_SetNodeUserData(int nodeID, int userData) { if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return false; } if ((int) pUserData(nodes[nodeID]) != userData) { pUserData(nodes[nodeID]) = userData; } return true; } bool e4_MetakitStorageImpl::DRV_SetVertexUserData(int vertexID, int userData) { if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return false; } if ((int) pUserData(vertices[vertexID]) != userData) { pUserData(vertices[vertexID]) = userData; } return true; } bool e4_MetakitStorageImpl::DRV_GetNodeUserData(int nodeID, int &userData) const { if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return false; } userData = (int) pUserData(nodes[nodeID]); return true; } bool e4_MetakitStorageImpl::DRV_GetVertexUserData(int vertexID, int &userData) const { if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return false; } userData = (int) pUserData(vertices[vertexID]); return true; } /* * Given a node ID, retrieve the parent node or its ID. */ e4_NodeImpl * e4_MetakitStorageImpl::DRV_GetParentNode(int childID, int nth) const { e4_NodeImpl *n; int parentID; if ((childID < 0) || (childID >= nodes.GetSize()) || (((int) pFlags(nodes[childID]) & MK4_INUSE) == 0)) { return NULL; } parentID = DRV_GetParentNodeID(childID, nth); if (parentID == E4_NODENOTFOUND) { return NULL; } if (DRV_GetNode(parentID, n) == false) { return NULL; } return n; } int e4_MetakitStorageImpl::DRV_GetParentNodeID(int childID, int nth) const { int i, pid; /* * If this node has no parents then return an indication * that we could not find an ID for its parent. */ if ((int) pParentID(nodes[childID]) == E4_NEXTNONE) { return E4_NODENOTFOUND; } /* * If nth is less than one, we want the last parent, whatever its rank. */ if (nth < 1) { for (pid = (int) pParentID(nodes[childID]); (int) pNext(parents[pid]) != E4_NEXTNONE; pid = (int) pNext(parents[pid])); return (int) pNodeID(parents[pid]); } /* * Get the nth parent in the list of parents. */ for (pid = (int) pParentID(nodes[childID]), i = 1; (i < nth) && ((int) pNext(parents[pid]) != E4_NEXTNONE); i++, pid = (int) pNext(parents[pid])); /* * If this node does not have an nth parent, return failure. */ if (i < nth) { return E4_NODENOTFOUND; } /* * We found the nth parent. */ return (int) pNodeID(parents[pid]); } /* * Get the vertex after one identified by vertexID. */ e4_VertexImpl * e4_MetakitStorageImpl::DRV_NextVertex(int num, int vertexID) const { int nvID; int i; if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return NULL; } if (num < 1) { return NULL; } for (nvID = vertexID, i = 0; i < num; i++) { nvID = (int) pNext(vertices[nvID]); if ((nvID == E4_NEXTNONE) || (((int) pFlags(vertices[nvID]) & MK4_INUSE) == 0)) { return NULL; } } return GetVertex(nvID); } /* * Get the vertex before one identified by vertexID. */ e4_VertexImpl * e4_MetakitStorageImpl::DRV_PrevVertex(int num, int vertexID) const { int nvID; int i; if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return NULL; } if (num < 1) { return NULL; } for (nvID = vertexID, i = 0; i < num; i++) { nvID = (int) pPrev(vertices[nvID]); if ((nvID == E4_NEXTNONE) || (((int) pFlags(vertices[nvID]) & MK4_INUSE) == 0)) { return NULL; } } return GetVertex(nvID); } /* * Get the vertexID of the next vertex. */ int e4_MetakitStorageImpl::DRV_NextVertexID(int vertexID) const { int nvid; if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return E4_VERTEXNOTFOUND; } nvid = (int) pNext(vertices[vertexID]); if (nvid == E4_NEXTNONE) { return E4_VERTEXNOTFOUND; } return nvid; } /* * Get the vertexID of the preceding vertex. */ int e4_MetakitStorageImpl::DRV_PrevVertexID(int vertexID) const { int pvid; if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return E4_VERTEXNOTFOUND; } pvid = (int) pPrev(vertices[vertexID]); if (pvid == E4_NEXTNONE) { return E4_VERTEXNOTFOUND; } return pvid; } /* * Is the node identified by index valid? */ bool e4_MetakitStorageImpl::DRV_IsLegalNodeID(int index) const { int flags; /* * If index is out of bounds, return false. */ if ((index < 0) || (index >= nodes.GetSize())) { return false; } /* * If not MK4_INUSE, return false. */ flags = (int) pFlags(nodes[index]); if ((flags & MK4_INUSE) == 0) { return false; } /* * If not detached, return true. */ if ((flags & MK4_DETACHED) == 0) { return true; } /* * If we get here, the node is detached. * * The node must either be the root node or referenced by the * user program, to be legal. */ if (!((((e4_MetakitStorageImpl *) this)->DRV_IsRootNodeID(index)) || IsReferencedNode(index))) { return false; } return true; } /* * Retrieve the ID of the first and last vertex in a node. */ int e4_MetakitStorageImpl::DRV_GetFirstVertexID(int nodeID) const { return (int) pFirstVertex(nodes[nodeID]); } int e4_MetakitStorageImpl::DRV_GetLastVertexID(int nodeID) const { return (int) pLastVertex(nodes[nodeID]); } /* * Retrieve an e4_VertexImpl instance for the vertex following the one * identified by the given ID in its node. */ e4_VertexImpl * e4_MetakitStorageImpl::DRV_FindNextVertex(int vertexID, e4_VisitMethod vm, int vf, int nameID, int nodeID, int parentID, e4_VertexType typeID, e4_DetachChoice dc) const { switch (vm) { case E4_VMSTORAGE: return FindNextVertexStorage(vertexID, vf, nameID, typeID); case E4_VMNODE: return FindNextVertexNode(vertexID, vf, nameID, typeID, nodeID); case E4_VMNODERANDOM: return FindNextVertexNodeRandom(vertexID, vf, nameID, typeID, nodeID); case E4_VMPARENT: return FindNextVertexParent(vertexID, nameID, nodeID, parentID, dc); case E4_VMUNKNOWN: case E4_VMLASTMETHOD: default: return NULL; } } /* * Helper method to visit all vertices of a storage according to some given * constraints. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexStorage(int vertexID, int vf, int nameID, e4_VertexType typeID) const { if (vertexID == E4_VERTEXNOTFOUND) { vertexID = -1; } switch (vf) { case E4_VFNONE: return FindNextVertexStorageNone(vertexID); case E4_VFNAME: return FindNextVertexStorageName(vertexID, nameID); case E4_VFTYPE: return FindNextVertexStorageType(vertexID, typeID); case (E4_VFNAME | E4_VFTYPE): return FindNextVertexStorageBoth(vertexID, nameID, typeID); default: return NULL; } } /* * Helper method to visit all vertices of a storage. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexStorageNone(int vertexID) const { int i, l; for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if (((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices of a storage with a given name. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexStorageName(int vertexID, int nameID) const { int i, l; for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if ((((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) && ((int) pNameID(vertices[i]) == nameID)) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices of a storage with a given type. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexStorageType(int vertexID, e4_VertexType vt) const { int i, l; for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if ((((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) && ((e4_VertexType) (int) pVertexType(vertices[i]) == vt)) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices of a storage with a given name and type. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexStorageBoth(int vertexID, int nameID, e4_VertexType vt) const { int i, l; for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if ((((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) && ((int) pNameID(vertices[i]) == nameID) && ((e4_VertexType) (int) pVertexType(vertices[i]) == vt)) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices that point at this node. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexParent(int vertexID, int nameID, int nodeID, int parentID, e4_DetachChoice dc) const { /* * Sanity checks: the nodeID value must be a valid nodeID. */ if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return NULL; } /* * If the vertexID != E4_VERTEXNOTFOUND then the vertex must be valid * and its value must be the node identified by nodeID. */ if (vertexID != E4_VERTEXNOTFOUND) { if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return NULL; } if (((e4_VertexType) (int) pVertexType(vertices[vertexID]) != E4_VTNODE) || ((int) pRowID(vertices[vertexID]) != nodeID)) { return NULL; } } /* * Dispatch to the right method: */ if (parentID != E4_NODENOTFOUND) { return FindNextVertexParentSpecific(vertexID, nameID, nodeID, parentID); } if (dc == E4_DCDETACHED) { return FindNextVertexParentDetached(vertexID, nameID, nodeID); } if (dc == E4_DCBOTH) { return FindNextVertexParentBoth(vertexID, nameID, nodeID); } if (dc == E4_DCATTACHED) { return FindNextVertexParentAttached(vertexID, nameID, nodeID); } return NULL; } /* * Helper method to visit the next detached vertex with the given name that * has the given node as its value. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexParentDetached(int vertexID, int nameID, int nodeID) const { /* * Set up for searching: */ if (vertexID == E4_VERTEXNOTFOUND) { vertexID = (int) pDetachedVertices(nodes[nodeID]); } else { vertexID = (int) pNextInParent(vertices[vertexID]); } /* * Look for the next vertex that satisfies the name constraint. */ for (; vertexID != E4_NEXTNONE; vertexID = (int) pNextInParent(vertices[vertexID])) { if ((nameID == E4_INVALIDUNIQUEID) || (nameID == (int) pNameID(vertices[vertexID]))) { return GetVertex(vertexID); } } /* * There are no more vertices to visit, so return NULL. */ return NULL; } /* * Helper method to visit the next vertex with the given name and * a specific parent that has the given node as its value. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexParentSpecific(int vertexID, int nameID, int nodeID, int parentID) const { int pid; /* * Set up for searching: */ if (vertexID == E4_VERTEXNOTFOUND) { for (pid = (int) pParentID(nodes[nodeID]); pid != E4_NEXTNONE; pid = (int) pNext(parents[pid])) { if (parentID == (int) pNodeID(parents[pid])) { break; } } if (pid == E4_NEXTNONE) { return NULL; } vertexID = (int) pVertexChain(parents[pid]); } else { vertexID = (int) pNextInParent(vertices[vertexID]); } /* * Look for the next vertex that satisfies the name constraint. */ for (; vertexID != E4_NEXTNONE; vertexID = (int) pNextInParent(vertices[vertexID])) { if ((nameID == E4_INVALIDUNIQUEID) || (nameID == (int) pNameID(vertices[vertexID]))) { return GetVertex(vertexID); } } /* * There are no more vertices to visit, so return NULL. */ return NULL; } /* * Helper method to visit the next attached vertex with the given name * that has the given node as its value. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexParentAttached(int vertexID, int nameID, int nodeID) const { int pid, parentID; /* * Set up for searching: * * - If no vertex ID is given, set vertexID to the first attached * vertex that has this node as its value. * - Otherwise set vertexID to the next vertex in the same parent that * has this node as its value. * * In either case set pid to the ID for the parent record of the current * parent. */ if (vertexID == E4_VERTEXNOTFOUND) { pid = (int) pParentID(nodes[nodeID]); if (pid == E4_NEXTNONE) { return NULL; } vertexID = (int) pVertexChain(parents[pid]); } else { for (pid = (int) pParentID(nodes[nodeID]), parentID = (int) pNodeID(vertices[vertexID]); pid != E4_NEXTNONE; pid = (int) pNext(parents[pid])) { if (parentID == (int) pNodeID(parents[pid])) { break; } } if (pid == E4_NEXTNONE) { return NULL; } vertexID = pNextInParent(vertices[vertexID]); } /* * Search for the next vertex that satisfies the name constraint in any * (remaining) parent of this node. */ while ((pid != E4_NEXTNONE) || (vertexID != E4_NEXTNONE)) { if (vertexID == E4_NEXTNONE) { pid = (int) pNext(parents[pid]); if (pid != E4_NEXTNONE) { vertexID = (int) pVertexChain(parents[pid]); } } if (vertexID != E4_NEXTNONE) { if ((nameID == E4_INVALIDUNIQUEID) || (nameID == (int) pNameID(vertices[vertexID]))) { return GetVertex(vertexID); } vertexID = (int) pNextInParent(vertices[vertexID]); } } /* * No more vertices to visit; return NULL. */ return NULL; } /* * Helper method to visit the next vertex (both attached and detached) that * has the given node as its value and the given name. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexParentBoth(int vertexID, int nameID, int nodeID) const { e4_VertexImpl *res = NULL; /* * If vertexID == E4_VERTEXNOTFOUND look first in the detached vertices. * Then look in the attached vertices for this node. */ if (vertexID == E4_VERTEXNOTFOUND) { res = FindNextVertexParentDetached(vertexID, nameID, nodeID); if (res != NULL) { return res; } return FindNextVertexParentAttached(vertexID, nameID, nodeID); } /* * If the current vertex is detached, continue looking in the detached * vertices and if found return that; otherwise reset vertexID to * E4_VERTEXNOTFOUND. Then fall through to looking in the attached * vertices that have this node as their value. */ if (((int) pFlags(vertices[vertexID]) & MK4_DETACHED) == MK4_DETACHED) { res = FindNextVertexParentDetached(vertexID, nameID, nodeID); if (res != NULL) { return res; } vertexID = E4_VERTEXNOTFOUND; } /* * Try to find an attached vertex. */ return FindNextVertexParentAttached(vertexID, nameID, nodeID); } /* * Helper method to visit all vertices in a node. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNode(int vertexID, int vf, int nameID, e4_VertexType vt, int nodeID) const { switch (vf) { case E4_VFNONE: return FindNextVertexNodeNone(vertexID, nodeID); case E4_VFNAME: return FindNextVertexNodeName(vertexID, nameID, nodeID); case E4_VFTYPE: return FindNextVertexNodeType(vertexID, vt, nodeID); case (E4_VFNAME | E4_VFTYPE): return FindNextVertexNodeBoth(vertexID, nameID, vt, nodeID); default: return NULL; } } /* * Helper method to visit all vertices in a node without constraints. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNodeNone(int vertexID, int nodeID) const { vertexID = FindNextVertexIndexInNode(vertexID, nodeID); if (vertexID == E4_NEXTNONE) { return NULL; } return GetVertex(vertexID); } /* * Helper method to visit all vertices in a node with a given name. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNodeName(int vertexID, int nameID, int nodeID) const { int i; for (i = FindNextVertexIndexInNode(vertexID, nodeID); i != E4_NEXTNONE; i = (int) pNext(vertices[i])) { if ((int) pNameID(vertices[i]) == nameID) { return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices in a node with a given type. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNodeType(int vertexID, e4_VertexType vt, int nodeID) const { int i; for (i = FindNextVertexIndexInNode(vertexID, nodeID); i != E4_NEXTNONE; i = (int) pNext(vertices[i])) { if ((e4_VertexType) (int) pVertexType(vertices[i]) == vt) { return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices in a node with a given type and name. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNodeBoth(int vertexID, int nameID, e4_VertexType vt, int nodeID) const { int i; for (i = FindNextVertexIndexInNode(vertexID, nodeID); i != E4_NEXTNONE; i = (int) pNext(vertices[i])) { if (((int) pNameID(vertices[i]) == nameID) && ((e4_VertexType) (int) pVertexType(vertices[i]) == vt)) { return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices in a node in some random order. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNodeRandom(int vertexID, int vf, int nameID, e4_VertexType vt, int nodeID) const { switch (vf) { case E4_VFNONE: return FindNextVertexNRNone(vertexID, nodeID); case E4_VFNAME: return FindNextVertexNRName(vertexID, nameID, nodeID); case E4_VFTYPE: return FindNextVertexNRType(vertexID, vt, nodeID); case (E4_VFNAME | E4_VFTYPE): return FindNextVertexNRBoth(vertexID, nameID, vt, nodeID); default: return NULL; } } /* * Helper method to visit all vertices in a node in some random order, * with no constraints. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNRNone(int vertexID, int nodeID) const { int i, l; if (vertexID == E4_VERTEXNOTFOUND) { vertexID = -1; } for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if ((((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) && ((int) pNodeID(vertices[i]) == nodeID)) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices with a given name in a supplied node * in some random order. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNRName(int vertexID, int nameID, int nodeID) const { int i, l; if (vertexID == E4_VERTEXNOTFOUND) { vertexID = -1; } for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if ((((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) && ((int) pNodeID(vertices[i]) == nodeID) && ((int) pNameID(vertices[i]) == nameID)) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices with a given type in a supplied node * in some random order. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNRType(int vertexID, e4_VertexType vt, int nodeID) const { int i, l; if (vertexID == E4_VERTEXNOTFOUND) { vertexID = -1; } for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if ((((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) && ((int) pNodeID(vertices[i]) == nodeID) && ((e4_VertexType) (int) pVertexType(vertices[i]) == vt)) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to visit all vertices with a given name and type in a supplied * node in some random order. */ e4_VertexImpl * e4_MetakitStorageImpl::FindNextVertexNRBoth(int vertexID, int nameID, e4_VertexType vt, int nodeID) const { int i, l; if (vertexID == E4_VERTEXNOTFOUND) { vertexID = -1; } for (i = vertexID + 1, l = vertices.GetSize(); i < l; i++) { if ((((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) && ((int) pNodeID(vertices[i]) == nodeID) && ((int) pNameID(vertices[i]) == nameID) && ((e4_VertexType) (int) pVertexType(vertices[i]) == vt)) { if ((((int) pFlags(vertices[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedVertex(i)) { continue; } return GetVertex(i); } } return NULL; } /* * Helper method to find the vertexID with the next rank after a given * vertexID in a node identified by a supplied nodeID. */ int e4_MetakitStorageImpl::FindNextVertexIndexInNode(int vertexID, int nodeID) const { if (vertexID == E4_VERTEXNOTFOUND) { if (nodeID == E4_NODENOTFOUND) { return E4_NEXTNONE; } return pFirstVertex(nodes[nodeID]); } if (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0) { return E4_NEXTNONE; } if ((int) pNodeID(vertices[vertexID]) != nodeID) { return E4_NEXTNONE; } return (int) pNext(vertices[vertexID]); } /* * Given a node ID, retrieve the instance of the next node after * the given one in this storage. */ e4_NodeImpl * e4_MetakitStorageImpl::DRV_FindNextNode(int nodeID) const { int i, l; e4_NodeImpl *n; if (nodeID == E4_NODENOTFOUND) { nodeID = -1; } for (l = nodes.GetSize(), i = nodeID + 1; i < l; i++) { if (((int) pFlags(nodes[i]) & MK4_INUSE) == MK4_INUSE) { /* * If the node is detached and not referenced by the program, * and it's not the root node, then skip this node. */ if ((((int) pFlags(nodes[i]) & MK4_DETACHED) == MK4_DETACHED) && !IsReferencedNode(i) && (i != (int) pFirst(unused[MK4_GRAPHROOTNODE]))) { continue; } (void) DRV_GetNode(i, n); return n; } } return NULL; } /* * Given a node ID, retrieve the number of vertices in that node. */ int e4_MetakitStorageImpl::DRV_VertexCountFromNodeID(int nodeID) const { return (int) pVertexCount(nodes[nodeID]); } /* * Given a node ID, retrieve the number of vertices in that node that * have the given name. */ int e4_MetakitStorageImpl::DRV_VertexCountWithNameIDFromNodeID(int nodeID, int vertexID, int nameID) const { int i, count; for (i = (int) pFirstVertex(nodes[nodeID]), count = 0; (i != E4_NEXTNONE) && (i != vertexID); i = (int) pNext(vertices[i])) { if ((int) pNameID(vertices[i]) == nameID) { count++; } } if ((i == vertexID) && (i != E4_NEXTNONE)) { count++; } return count; } /* * Given a node ID, retrieve the number of vertices in that node with the * given type. */ int e4_MetakitStorageImpl::DRV_VertexCountWithTypeFromNodeID(int nodeID, int vertexID, e4_VertexType tp) const { int i, count; for (i = (int) pFirstVertex(nodes[nodeID]), count = 0; (i != E4_NEXTNONE) && (i != vertexID); i = (int) pNext(vertices[i])) { if ((int) pVertexType(vertices[i]) == tp) { count++; } } if ((i == vertexID) && (i != E4_NEXTNONE)) { count++; } return count; } /* * Given a node ID, retrieve the number of vertices in that node with the * same value. */ int e4_MetakitStorageImpl::DRV_VertexCountWithValueFromNodeID(int nodeID, int vertexID, const e4_Value &v) const { int i, count; switch (v.vertexType) { case E4_VTNODE: { int vn = GetNodeID(v.n); for (i = (int) pFirstVertex(nodes[nodeID]), count = 0; (i != E4_NEXTNONE) && (i != vertexID); i = (int) pNext(vertices[i])) { if (((int) pVertexType(vertices[i]) == E4_VTNODE) && ((int) pRowID(vertices[i]) == vn)) { count++; } } break; } case E4_VTINT: { int vi = v.u.i; for (i = (int) pFirstVertex(nodes[nodeID]), count = 0; (i != E4_NEXTNONE) && (i != vertexID); i = (int) pNext(vertices[i])) { if (((int) pVertexType(vertices[i]) == E4_VTINT) && ((int) pRowID(vertices[i]) == vi)) { count++; } } break; } case E4_VTDOUBLE: { double vd = v.u.d; for (i = (int) pFirstVertex(nodes[nodeID]), count = 0; (i != E4_NEXTNONE) && (i != vertexID); i = (int) pNext(vertices[i])) { if (((int) pVertexType(vertices[i]) == E4_VTDOUBLE) && (pDoubleVal(doubles[(int) pRowID(vertices[i])]) == vd)) { count++; } } break; } case E4_VTSTRING: { const char *vs = v.u.s; for (i = (int) pFirstVertex(nodes[nodeID]), count = 0; (i != E4_NEXTNONE) && (i != vertexID); i = (int) pNext(vertices[i])) { if (((int) pVertexType(vertices[i]) == E4_VTSTRING) && (strcmp(pStringVal(strings[(int) pRowID(vertices[i])]), vs) == 0)) { count++; } } break; } case E4_VTBINARY: { const char *vb = (const char *) v.u.b.bytes; const char *sb; int nb = v.u.b.nbytes; int j; for (i = (int) pFirstVertex(nodes[nodeID]), count = 0; (i != E4_NEXTNONE) && (i != vertexID); i = (int) pNext(vertices[i])) { if ((int) pVertexType(vertices[i]) == E4_VTBINARY) { c4_Bytes bytes = pBinaryVal(binary[(int)pRowID(vertices[i])]); if (bytes.Size() != nb) { continue; } sb = (const char *) (const void *) bytes.Contents(); for (j = 0; j < nb; j++) { if (sb[j] != vb[j]) { break; } } if (j == nb) { count++; } } } break; } default: count = 0; } if ((i == vertexID) && (i != E4_NEXTNONE)) { count++; } return count; } /* * Given a vertex ID retrieve the node containing that vertex. */ e4_NodeImpl * e4_MetakitStorageImpl::DRV_ContainingNodeFromVertexID(int vertexID) const { e4_NodeImpl *n; if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return NULL; } if (DRV_GetNode(pNodeID(vertices[vertexID]), n) == false) { return NULL; } return n; } /* * Given a vertex ID retrieve the node ID for the node containing that vertex. */ int e4_MetakitStorageImpl::DRV_ContainingNodeIDFromVertexID(int vertexID) const { if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return E4_NODENOTFOUND; } return (int) pNodeID(vertices[vertexID]); } /* * Check whether a vertex ID is legal. */ bool e4_MetakitStorageImpl::DRV_IsLegalVertexID(int index) const { int flags; /* * If index is out of bounds, return false. */ if ((index < 0) || (index >= vertices.GetSize())) { return false; } /* * If not MK4_INUSE, return false. */ flags = (int) pFlags(vertices[index]); if ((flags & MK4_INUSE) == 0) { return false; } /* * If not detached, return true. */ if ((flags & MK4_DETACHED) == 0) { return true; } /* * If detached, must be referenced by user program to be legal. */ if (!IsReferencedVertex(index)) { return false; } return true; } /* * Retrieve the vertex type, the ID of the containing node or the name * of the vertex, given a vertex ID. */ e4_VertexType e4_MetakitStorageImpl::DRV_VertexTypeFromVertexID(int index) const { return (e4_VertexType) (int) pVertexType(vertices[index]); } int e4_MetakitStorageImpl::DRV_NodeIDFromVertexID(int index) const { return (int) pNodeID(vertices[index]); } const char * e4_MetakitStorageImpl::DRV_VertexNameFromVertexID(int index) const { const char *nm; if (DRV_GetVertexName(pNameID(vertices[index]), nm) != true) { return NULL; } return nm; } /* * Find the name ID of a vertex with a given vertex ID. */ int e4_MetakitStorageImpl::DRV_NameIDFromVertexID(int vertexID) const { return (int) pNameID(vertices[vertexID]); } /* * Rename a vertex given a vertex ID. */ bool e4_MetakitStorageImpl::DRV_RenameVertexByVertexID(int vertexID, int nameID) { pNameID(vertices[vertexID]) = nameID; return true; } /* * Add the node identified by "parentID" to the list of nodes that * contain the node identified by "childID". Add the vertex identified * by "vertexID" to the list of vertices referenced by the parent * record for "parentID". * * NOTE: A parent node can contain a child node multiple times, hence we * maintain a reference count to efficiently represent this multiple * containment. */ void e4_MetakitStorageImpl::AddParent(int childID, int parentID, int vertexID) { int i, back, pid, flags; /* * If the new parentID is E4_NEXTNONE, it means that we're adding * a detached vertex to the list of detached vertices whose value * is the child node. */ if (parentID == E4_NEXTNONE) { pNextInParent(vertices[vertexID]) = (int) pDetachedVertices(nodes[childID]); pDetachedVertices(nodes[childID]) = vertexID; return; } /* * The child node is no longer detached. */ flags = (int) pFlags(nodes[childID]); flags &= (~(MK4_DETACHED | MK4_DETACHNOTIFY)); pFlags(nodes[childID]) = flags; /* * Increment the reference count for the child node because * it gets a new parent. */ pRefCount(nodes[childID]) = (int) pRefCount(nodes[childID]) + 1; /* * See if the parentID is already present in the list * of parents for the node denoted by childID. In that case * increment the number of times the node is a child of this * parent, and return. */ for (i = (int) pParentID(nodes[childID]); i != E4_NEXTNONE; i = (int) pNext(parents[i])) { if ((int) pNodeID(parents[i]) == parentID) { pCount(parents[i]) = (int) pCount(parents[i]) + 1; /* * Add this vertex to the chain of vertices referenced * by this parent record. */ pNextInParent(vertices[vertexID]) = (int) pVertexChain(parents[i]); pVertexChain(parents[i]) = vertexID; return; } } /* * Did not find the "parentID" in the current list, so * add a new row in the "parents" view for this node. */ if ((int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDPARENT]) == E4_NEXTNONE) { MakeParentSpace(); } i = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDPARENT]); pFirst(unused[MK4_GRAPHFIRSTUNUSEDPARENT]) = (int) pNext(parents[i]); /* * Must add the new parent as the last one in the list * of parents for the child node. */ pFlags(parents[i]) = MK4_INUSE; pNodeID(parents[i]) = parentID; pCount(parents[i]) = 1; pNext(parents[i]) = E4_NEXTNONE; pVertexChain(parents[i]) = vertexID; /* * Mark this vertex as the last one in the parent that has as its * value this child node. */ pNextInParent(vertices[vertexID]) = E4_NEXTNONE; /* * After the following loop, back will contain the last parent * in the chain of parents for the child node. */ for (back = E4_NEXTNONE, pid = (int) pParentID(nodes[childID]); pid != E4_NEXTNONE; pid = (int) pNext(parents[pid])) { back = pid; } /* * If back == E4_NEXTNONE it means that the child node does * not yet have any parents, hence make this entry the first * one. Otherwise, modify the chain pointer of back to point * to the new entry. */ if (back == E4_NEXTNONE) { pParentID(nodes[childID]) = i; } else { pNext(parents[back]) = i; } } /* * Helper method used by DRV_MoveVertex only, to remove a parent reference * to parentID through vertexID from the list of parents of childID. The node * identified by childID node may temporarily unreachable, and since it's * temporary, no notifications are sent and no GC is performed. */ void e4_MetakitStorageImpl::RemoveParent(int childID, int parentID, int vertexID) { int cur, prev, vv, pv, flags; /* * Sanity checks: */ if ((childID < 0) || (childID >= nodes.GetSize()) || (((int) pFlags(nodes[childID]) & MK4_INUSE) == 0) || (parentID >= nodes.GetSize())) { return; } /* * If the parentID == E4_NEXTNONE then the vertex is a detached one. * In that case, splice it out of the list of detached vertices that * point at this node. */ if (parentID == E4_NEXTNONE) { /* * The child node loses a detached vertex pointing at it. */ for (prev = E4_NEXTNONE, cur = (int) pDetachedVertices(nodes[childID]); cur != E4_NEXTNONE; cur = (int) pNextInParent(vertices[cur])) { if (cur == vertexID) { if (prev == E4_NEXTNONE) { pDetachedVertices(nodes[childID]) = (int) pNextInParent(vertices[cur]); } else { pNextInParent(vertices[prev]) = (int) pNextInParent(vertices[cur]); } break; } prev = cur; } } else { /* * Decrement the reference count for the child node * because it loses a parent. */ pRefCount(nodes[childID]) = (int) pRefCount(nodes[childID]) - 1; if ((int) pRefCount(nodes[childID]) < 0) { pRefCount(nodes[childID]) = 0; } /* * If the parent ID is present in the list of parents of the * child, retrieve the parent record. Otherwise, bail out. */ for (cur = (int) pParentID(nodes[childID]), prev = E4_NEXTNONE; cur != E4_NEXTNONE; cur = (int) pNext(parents[cur])) { if ((int) pNodeID(parents[cur]) == parentID) { break; } prev = cur; } if (cur == E4_NEXTNONE) { return; } /* * If the number of times the child node appears in the parent * node is greater than one, decrement the count, and remove the * first vertex in the parent that has the child as its value. */ if ((int) pCount(parents[cur]) > 1) { pCount(parents[cur]) = (int) pCount(parents[cur]) - 1; /* * Splice the vertex out of the list of vertices in the parent * whose value is this child node. */ for (pv = E4_NEXTNONE, vv = (int) pVertexChain(parents[cur]); vv != E4_NEXTNONE; vv = pNextInParent(vertices[vv])) { /* * When we find the vertex splice it out of the list * and break. */ if (vv == vertexID) { if (pv == E4_NEXTNONE) { pVertexChain(parents[cur]) = (int) pNextInParent(vertices[vv]); } else { pNextInParent(vertices[pv]) = (int) pNextInParent(vertices[vv]); } break; } pv = vv; } if (vv == E4_NEXTNONE) { return; } } else { /* * No, this parent had only one reference to this child, so we must * splice out the record from the list of parents. If this is the * first record, then update the pParentID vertex in the child * node to the next record, otherwise splice it out of the list. In * either case, return the record to the freelist of * parent records. * * NOTE: We dont bother to splice out the vertex from the list of * vertices in the parent record, because the parent record is * recycled anyway. But we must check that indeed the child is * referenced from the parent through the given vertex. */ if (prev == E4_NEXTNONE) { pParentID(nodes[childID]) = (int) pNext(parents[cur]); } else { pNext(parents[prev]) = (int) pNext(parents[cur]); } UnusedParent(cur); } } /* * See if the child node is newly detached (wasn't detached and * became detached as a result of this operation). */ if (((int) pParentID(nodes[childID]) == E4_NEXTNONE) && (((int) pFlags(nodes[childID]) & MK4_DETACHED) == 0)) { flags = (int) pFlags(nodes[childID]); flags |= MK4_DETACHED; flags &= ~(MK4_DETACHNOTIFY); pFlags(nodes[childID]) = flags; } } /* * Remove a parent from the list of parents of a child, and if requested, * decrement the reference count for the child. */ void e4_MetakitStorageImpl::RemoveParent(int childID, int parentID, int vertexID, bool GCOrDetach) { int cur, prev, vv, pv, flags; e4_NodeImpl *np; /* * Sanity checks: */ if ((childID < 0) || (childID >= nodes.GetSize()) || (((int) pFlags(nodes[childID]) & MK4_INUSE) == 0) || (parentID >= nodes.GetSize())) { return; } /* * If the parentID == E4_NEXTNONE then the vertex is a detached one. * In that case, splice it out of the list of detached vertices that * point at this node. */ if (parentID == E4_NEXTNONE) { /* * The child node loses a detached vertex pointing at it. */ for (prev = E4_NEXTNONE, cur = (int) pDetachedVertices(nodes[childID]); cur != E4_NEXTNONE; cur = (int) pNextInParent(vertices[cur])) { if (cur == vertexID) { if (prev == E4_NEXTNONE) { pDetachedVertices(nodes[childID]) = (int) pNextInParent(vertices[cur]); } else { pNextInParent(vertices[prev]) = (int) pNextInParent(vertices[cur]); } break; } prev = cur; } /* * See if we found the vertex among the detached ones that * point at this node. */ if (cur == E4_NEXTNONE) { return; } } else { /* * Decrement the reference count for the child node * because it loses a parent. */ pRefCount(nodes[childID]) = (int) pRefCount(nodes[childID]) - 1; if ((int) pRefCount(nodes[childID]) < 0) { pRefCount(nodes[childID]) = 0; } /* * If the parent ID is present in the list of parents of the * child, retrieve the parent record. Otherwise, bail out. */ for (cur = (int) pParentID(nodes[childID]), prev = E4_NEXTNONE; cur != E4_NEXTNONE; cur = (int) pNext(parents[cur])) { if ((int) pNodeID(parents[cur]) == parentID) { break; } prev = cur; } if (cur == E4_NEXTNONE) { return; } /* * If the number of times the child node appears in the parent * node is greater than one, decrement the count, and remove the * first vertex in the parent that has the child as its value. */ if ((int) pCount(parents[cur]) > 1) { pCount(parents[cur]) = (int) pCount(parents[cur]) - 1; /* * Splice the vertex out of the list of vertices in the parent * whose value is this child node. */ for (pv = E4_NEXTNONE, vv = (int) pVertexChain(parents[cur]); vv != E4_NEXTNONE; vv = pNextInParent(vertices[vv])) { /* * When we find the vertex splice it out of the list * and break. */ if (vv == vertexID) { if (pv == E4_NEXTNONE) { pVertexChain(parents[cur]) = (int) pNextInParent(vertices[vv]); } else { pNextInParent(vertices[pv]) = (int) pNextInParent(vertices[vv]); } break; } pv = vv; } if (vv == E4_NEXTNONE) { return; } } else { /* * No, this parent had only one reference to this child, so we must * splice out the record from the list of parents. If this is the * first record, then update the pParentID vertex in the child * node to the next record, otherwise splice it out of the list. In * either case, return the record to the freelist of * parent records. * * NOTE: We dont bother to splice out the vertex from the list of * vertices in the parent record, because the parent record is * recycled anyway. But we must check that indeed the child is * referenced from the parent through the given vertex. */ if (prev == E4_NEXTNONE) { pParentID(nodes[childID]) = (int) pNext(parents[cur]); } else { pNext(parents[prev]) = (int) pNext(parents[cur]); } UnusedParent(cur); } } /* * See if the child node is newly detached (wasn't detached and * became detached as a result of this operation). */ if (((int) pParentID(nodes[childID]) == E4_NEXTNONE) && (((int) pFlags(nodes[childID]) & MK4_DETACHED) == 0)) { flags = (int) pFlags(nodes[childID]); flags |= MK4_DETACHED; flags &= ~(MK4_DETACHNOTIFY); pFlags(nodes[childID]) = flags; /* * See if the node is recycle-able. */ if (((int) pDetachedVertices(nodes[childID]) == E4_NEXTNONE) && !IsReferencedNode(childID)) { /* * The node is unreachable. Recycle it. */ if (GCOrDetach) { DRV_DoGC(E4_AUTOGC); } else { needsGC = true; } } else if (GCOrDetach) { /* * The node is referenced by the program or by some detached * vertices. Cause a detach event. */ flags = (int) pFlags(nodes[childID]); flags |= MK4_DETACHNOTIFY; pFlags(nodes[childID]) = flags; if (HasCallbacks(E4_ECDETNODE)) { np = FindReferencedNode(childID); if ((np != NULL) && (!np->HasFlags(E4_CBDETACHDELIVERED))) { CauseEventInternal(E4_ECDETNODE, np, NULL); np->SetFlags(E4_CBDETACHDELIVERED); } } } } } /* * Clean up the association between a vertex and its node value. Used by * the new GC when the vertex is being recycled but its node value is not * known to be unreachable. */ void e4_MetakitStorageImpl::RemoveNodeVertexAssoc(int nid, int vid) { int i, p, nv; /* * If the vertex is detached, remove it from the list of detached * vertices that have this node as their value. * * Otherwise, locate the parent record for the node that used to be * a parent through this vertex. Remove the vertex from the list of * vertices which associate the parent node and this node, and if the * occurrence count is now zero, remove the parent record also. */ nv = (int) pNextInParent(vertices[vid]); if (((int) pFlags(vertices[vid]) & MK4_DETACHED) == MK4_DETACHED) { /* * This vertex is detached, so remove it from the list of detached * vertices whose value is this node. */ if ((int) pDetachedVertices(nodes[nid]) == vid) { pDetachedVertices(nodes[nid]) = nv; } else { for (i = (int) pDetachedVertices(nodes[nid]); (i != E4_NEXTNONE) && ((int) pNextInParent(vertices[i]) != vid); i = pNextInParent(vertices[i])) { } if (i != E4_NEXTNONE) { pNextInParent(vertices[i]) = nv; } } } else { /* * This vertex is not detached. */ p = (int) pNodeID(vertices[vid]); for (i = (int) pParentID(nodes[nid]); (i != E4_NEXTNONE) && ((int) pNodeID(parents[i]) != p); i = (int) pNext(parents[i])) { } if (i != E4_NEXTNONE) { pCount(parents[i]) = (int) pCount(parents[i]) - 1; /* * If there are other occurrences of this parent, remove the * vertex from the vertex chain for this child node. Otherwise * remove the whole parent record. */ if ((int) pCount(parents[i]) > 0) { if ((int) pVertexChain(parents[i]) == vid) { pVertexChain(parents[i]) = (int) pNextInParent(vertices[vid]); } else { for (i = pVertexChain(parents[i]); (int) pNextInParent(vertices[i]) != vid; i = (int) pNextInParent(vertices[i])) { } pNextInParent(vertices[i]) = (int) pNextInParent(vertices[vid]); } } else { p = i; if ((int) pParentID(nodes[nid]) == i) { pParentID(nodes[nid]) = (int) pNext(parents[i]); } else { for (i = (int) pParentID(nodes[nid]); (int) pNext(parents[i]) != p; i = pNext(parents[i])) { } pNext(parents[i]) = (int) pNext(parents[p]); } UnusedParent(p); } } } } /* * Add entities to their respective free lists. */ void e4_MetakitStorageImpl::UnusedParent(int i) { pNext(parents[i]) = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDPARENT]); pFlags(parents[i]) = 0; pCount(parents[i]) = 0; pFirst(unused[MK4_GRAPHFIRSTUNUSEDPARENT]) = i; } void e4_MetakitStorageImpl::UnusedNode(int i) { bool reallyFreed = false; if (((int) pFlags(nodes[i]) & MK4_INUSE) == MK4_INUSE) { reallyFreed = true; } pNext(nodes[i]) = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDNODE]); pFlags(nodes[i]) = 0; pFirstVertex(nodes[i]) = E4_NEXTNONE; pParentID(nodes[i]) = E4_NEXTNONE; pFirst(unused[MK4_GRAPHFIRSTUNUSEDNODE]) = i; if (reallyFreed) { statistics[(int) E4_SPNODE][(int) E4_SSUSED]--; statistics[(int) E4_SPNODE][(int) E4_SSFREED]++; } } void e4_MetakitStorageImpl::UnusedVertex(int i) { bool reallyFreed = false; if (((int) pFlags(vertices[i]) & MK4_INUSE) == MK4_INUSE) { reallyFreed = true; } pNext(vertices[i]) = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDVERTEX]); pFlags(vertices[i]) = 0; pFirst(unused[MK4_GRAPHFIRSTUNUSEDVERTEX]) = i; if (reallyFreed) { statistics[(int) E4_SPVERTEX][(int) E4_SSUSED]--; statistics[(int) E4_SPVERTEX][(int) E4_SSFREED]++; } } void e4_MetakitStorageImpl::UnusedInt(int i) { /* * Nothing to do here. */ } void e4_MetakitStorageImpl::UnusedDouble(int i) { pNext(doubles[i]) = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDDOUBLE]); pFlags(doubles[i]) = 0; pFirst(unused[MK4_GRAPHFIRSTUNUSEDDOUBLE]) = i; statistics[(int) E4_SPDOUBLE][(int) E4_SSUSED]--; statistics[(int) E4_SPDOUBLE][(int) E4_SSFREED]++; } void e4_MetakitStorageImpl::UnusedString(int i) { pNext(strings[i]) = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDSTRING]); pFlags(strings[i]) = 0; pFirst(unused[MK4_GRAPHFIRSTUNUSEDSTRING]) = i; statistics[(int) E4_SPSTRING][(int) E4_SSUSED]--; statistics[(int) E4_SPSTRING][(int) E4_SSFREED]++; } void e4_MetakitStorageImpl::UnusedName(int i) { pNext(names[i]) = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDNAME]); pFlags(names[i]) = 0; pFirst(unused[MK4_GRAPHFIRSTUNUSEDNAME]) = i; statistics[(int) E4_SPNAME][(int) E4_SSUSED]--; statistics[(int) E4_SPNAME][(int) E4_SSFREED]++; } void e4_MetakitStorageImpl::UnusedBinary(int i) { pNext(binary[i]) = (int) pFirst(unused[MK4_GRAPHFIRSTUNUSEDBINARY]); pFlags(binary[i]) = 0; pFirst(unused[MK4_GRAPHFIRSTUNUSEDBINARY]) = i; statistics[(int) E4_SPBINARY][(int) E4_SSUSED]--; statistics[(int) E4_SPBINARY][(int) E4_SSFREED]++; } /* * Move the vertex identified by vertexID into the node identified by * nodeID as the first vertex. */ bool e4_MetakitStorageImpl::DRV_MoveVertexToFirst(int vertexID, int nodeID) { /* * Sanity checks: */ if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return false; } /* * Step 1: Splice the vertex out of any node it is in now. */ SpliceOut(vertexID, nodeID); /* * Step 2: Splice the vertex into its new location. */ SpliceIn(vertexID, nodeID, E4_NEXTNONE); return true; } /* * Move the vertex identified by vertexID into the node identified by * nodeID as the last vertex. */ bool e4_MetakitStorageImpl::DRV_MoveVertexToLast(int vertexID, int nodeID) { /* * Sanity checks: */ if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return false; } /* * Step 1: Splice the vertex out of any node it is in now. */ SpliceOut(vertexID, nodeID); /* * Step 2: Splice the vertex into its new location. */ SpliceIn(vertexID, nodeID, (int) pLastVertex(nodes[nodeID])); return true; } /* * Move the vertex identified by vertexID into the node identified by * nodeID as the last vertex. */ bool e4_MetakitStorageImpl::DRV_MoveVertexAfter(int vertexID, int afterVertexID, int rank) { int nodeID; /* * Sanity checks: */ if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (afterVertexID < 0) || (afterVertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0) || (((int) pFlags(vertices[afterVertexID]) & MK4_INUSE) == 0) || (((int) pFlags(vertices[afterVertexID]) & MK4_DETACHED) == MK4_DETACHED)) { return false; } nodeID = pNodeID(vertices[afterVertexID]); /* * Step 1: Splice the vertex out of any node it is in now. */ SpliceOut(vertexID, nodeID); /* * Step 2: Splice the vertex into its new location. */ SpliceIn(vertexID, nodeID, afterVertexID); return true; } /* * Helper function for splicing a vertex out of a node. */ void e4_MetakitStorageImpl::SpliceOut(int vertexID, int newParentID) { int nodeID, nextID, prevID, childID; /* * Splice the vertex out of its containing node. */ nodeID = (int) pNodeID(vertices[vertexID]); nextID = (int) pNext(vertices[vertexID]); prevID = (int) pPrev(vertices[vertexID]); if (nodeID != E4_NEXTNONE) { if ((int) pFirstVertex(nodes[nodeID]) == vertexID) { pFirstVertex(nodes[nodeID]) = nextID; } if ((int) pLastVertex(nodes[nodeID]) == vertexID) { pLastVertex(nodes[nodeID]) = prevID; } /* * Decrement the vertex count for the node out of which we spliced * the vertex. */ pVertexCount(nodes[nodeID]) = (int) pVertexCount(nodes[nodeID]) - 1; } if (nextID != E4_NEXTNONE) { pPrev(vertices[nextID]) = prevID; } if (prevID != E4_NEXTNONE) { pNext(vertices[prevID]) = nextID; } /* * If the vertex has a node value, and the old and new nodes containing * the vertex are different, then remove the old parent node. */ if ((e4_VertexType) (int) pVertexType(vertices[vertexID]) == E4_VTNODE) { childID = (int) pRowID(vertices[vertexID]); if (nodeID != newParentID) { RemoveParent(childID, nodeID, vertexID); } } /* * This vertex now is not part of any node. */ pNodeID(vertices[vertexID]) = E4_NEXTNONE; pNextInParent(vertices[vertexID]) = E4_NEXTNONE; pPrev(vertices[vertexID]) = E4_NEXTNONE; pNext(vertices[vertexID]) = E4_NEXTNONE; } /* * Helper method for splicing in a vertex being moved in a new location. * For use only by DRV_MoveVertex. */ void e4_MetakitStorageImpl::SpliceIn(int vertexID, int nodeID, int vertexAfterID) { int pn, flags; /* * The node gains a new vertex. */ pVertexCount(nodes[nodeID]) = (int) pVertexCount(nodes[nodeID]) + 1; /* * And the vertex has a new node it is in. */ pNodeID(vertices[vertexID]) = nodeID; /* * Now add the new vertex at the appropriate place. */ pPrev(vertices[vertexID]) = vertexAfterID; if (vertexAfterID == E4_NEXTNONE) { /* * Insert the new vertex as the first vertex in this node. */ pn = (int) pFirstVertex(nodes[nodeID]); pNext(vertices[vertexID]) = pn; pFirstVertex(nodes[nodeID]) = vertexID; } else { /* * Insert the new vertex somewhere else in the node. */ pn = (int) pNext(vertices[vertexAfterID]); pNext(vertices[vertexID]) = pn; pNext(vertices[vertexAfterID]) = vertexID; } /* * Finish fixing up the chain of vertices in this node. */ if (pn != E4_NEXTNONE) { pPrev(vertices[pn]) = vertexID; } else { pLastVertex(nodes[nodeID]) = vertexID; } /* * If the vertex has a node value, that node gained a parent. */ if ((e4_VertexType) (int) pVertexType(vertices[vertexID]) == E4_VTNODE) { AddParent((int) pRowID(vertices[vertexID]), nodeID, vertexID); } /* * The moved vertex is no longer detached. */ flags = (int) pFlags(vertices[vertexID]); flags = ~(MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(vertices[vertexID]) = flags; } /* * Copy all e4Graph data from this storage to another storage. */ bool e4_MetakitStorageImpl::DRV_CopyTo(e4_StorageImpl *osp) { e4_MetakitStorageImpl *omsp; int i, l; /* * Check the other storage is using the Metakit storage driver. If * not, bail out. */ if (strcmp(GetDriver(), E4_METAKIT) != 0) { return false; } omsp = (e4_MetakitStorageImpl *) osp; /* * Empty out the cache of the other storage. */ omsp->CleanUp(); /* * Copy all tables from this storage to the other storage. */ omsp->nodes.SetSize(nodes.GetSize()); omsp->vertices.SetSize(vertices.GetSize()); omsp->doubles.SetSize(doubles.GetSize()); omsp->strings.SetSize(strings.GetSize()); omsp->binary.SetSize(binary.GetSize()); omsp->names.SetSize(names.GetSize()); omsp->unused.SetSize(unused.GetSize()); omsp->parents.SetSize(parents.GetSize()); for (i = 0, l = nodes.GetSize(); i < l; i++) { omsp->nodes[i] = nodes[i]; } for (i = 0, l = vertices.GetSize(); i < l; i++) { omsp->vertices[i] = vertices[i]; } for (i = 0, l = doubles.GetSize(); i < l; i++) { omsp->doubles[i] = doubles[i]; } for (i = 0, l = strings.GetSize(); i < l; i++) { omsp->strings[i] = strings[i]; } for (i = 0, l = binary.GetSize(); i < l; i++) { omsp->binary[i] = binary[i]; } for (i = 0, l = names.GetSize(); i < l; i++) { omsp->names[i] = names[i]; } for (i = 0, l = unused.GetSize(); i < l; i++) { omsp->unused[i] = unused[i]; } for (i = 0, l = parents.GetSize(); i < l; i++) { omsp->parents[i] = parents[i]; } /* * Finally initialize the new data in the other storage and set * the state bits the same as this storage. */ omsp->Initialize(GetState(), ((GetPermissions() & E4_SPINITIALIZE) == E4_SPINITIALIZE), ((GetPermissions() & E4_SPUPDATEFORMAT) == E4_SPUPDATEFORMAT)); return true; } /* * Destroy the physical storage and make this instance invalid. */ void e4_MetakitStorageImpl::DRV_Destroy() { /* * First of all, clean up the state associated with this storage. */ CleanUp(); /* * Destroying a Metakit storage is a two step process. First * we have to discard the last reference to the storage, to * give Metakit a chance to commit the storage. Then, we unlink * the file containing the storage so that it will no longer * be present on the disk. The order of these operations is * important: if you reverse the order the effect of unlinking * the file will be undone when Metakit commits the file and * makes it appear again! */ if (storage != NULL) { delete storage; storage = NULL; } if (name != NULL) { unlink(name); } } /* * Retrieve the nth vertex in the parent node identified by parentID * whose value is the node identified by nodeID. */ e4_VertexImpl * e4_MetakitStorageImpl::DRV_GetVertexRefFromParent(int parentID, int nodeID, int nth) const { bool found; int pid, vid, count; if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return NULL; } if ((parentID < 0) || (parentID >= nodes.GetSize()) || (((int) pFlags(nodes[parentID]) & MK4_INUSE) == 0)) { return NULL; } /* * Ensure that the node identified by parentID is indeed a parent * node of the node identified by nodeID. */ for (found = false, pid = (int) pParentID(nodes[nodeID]); (!found) && (pid != E4_NEXTNONE); pid = (int) pNext(parents[pid])) { if (parentID == (int) pNodeID(parents[pid])) { found = true; } } if (!found) { return NULL; } /* * Scan down the chain of vertices in the parent node and find the nth * one whose value is the node identified by nodeID. */ for (vid = (int) pFirstVertex(nodes[parentID]), count = 0; vid != E4_NEXTNONE; vid = (int) pNext(vertices[vid])) { if (((int) pVertexType(vertices[vid]) == E4_VTNODE) && ((int) pRowID(vertices[vid]) == parentID)) { count++; if (count == nth) { break; } } } if (vid == E4_NEXTNONE) { return NULL; } return GetVertex(vid); } /* * Retrieve the nth vertex in the ith parent of the node identified by * nodeID whose value is the node identified by nodeID. */ e4_VertexImpl * e4_MetakitStorageImpl::DRV_GetVertexRefFromIthParent(int i, int nodeID, int nth) const { int parentID, pid, vid, count; if ((i < 1) || (nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return NULL; } for (count = 0, pid = (int) pParentID(nodes[nodeID]); (count < i) && (pid != E4_NEXTNONE); count++, pid = (int) pNext(parents[pid])) { } if (pid == E4_NEXTNONE) { return NULL; } parentID = (int) pNodeID(parents[pid]); if ((parentID < 0) || (parentID >= nodes.GetSize()) || (((int) pFlags(nodes[parentID]) & MK4_INUSE) == 0)) { return NULL; } /* * Scan down the chain of vertices in the parent node and find the nth * one whose value is the node identified by nodeID. */ for (vid = (int) pFirstVertex(nodes[parentID]), count = 0; vid != E4_NEXTNONE; vid = (int) pNext(vertices[vid])) { if (((int) pVertexType(vertices[vid]) == E4_VTNODE) && ((int) pRowID(vertices[vid]) == parentID)) { count++; if (count == nth) { break; } } } if (vid == E4_NEXTNONE) { return NULL; } return GetVertex(vid); } /* * How many parents does the node with the given ID have? */ int e4_MetakitStorageImpl::DRV_ParentCount(int nodeID) const { int count, pid; if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return E4_NODENOTFOUND; } /* * Count the number of different nodes that are parents of * the node with the given node ID. */ for (count = 0, pid = (int) pParentID(nodes[nodeID]); pid != E4_NEXTNONE; count++, pid = (int) pNext(parents[pid])); return count; } /* * How many vertices contain the node with the given nodeID as their value? */ int e4_MetakitStorageImpl::DRV_OccurrenceCount(int nodeID) const { if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return E4_NODENOTFOUND; } return (int) pRefCount(nodes[nodeID]); } /* * How many vertices in the node identified by the given parent ID contain * as their value the node denoted by the child ID? */ int e4_MetakitStorageImpl::DRV_OccurrenceCount(int nodeID, int parentID) const { int pid; if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0) || (parentID < 0) || (parentID >= nodes.GetSize()) || (((int) pFlags(nodes[parentID]) & MK4_INUSE) == 0)) { return E4_NODENOTFOUND; } /* * Search for the parent record for the child node that contains * the parent node information: */ for (pid = (int) pParentID(nodes[nodeID]); pid != E4_NEXTNONE; pid = (int) pNext(parents[pid])) { if ((int) pNodeID(parents[pid]) == parentID) { return (int) pCount(parents[pid]); } } /* * Didn't find the parent in the list of parents for this child. So * the child occurs zero times in that parent. */ return 0; } /* * What is the rank of the parent node with the given parent ID for the * child node with the given child ID? */ int e4_MetakitStorageImpl::DRV_ParentRank(int nodeID, int parentID) const { int pid, rank; if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0) || (parentID < 0) || (parentID >= nodes.GetSize()) || (((int) pFlags(nodes[parentID]) & MK4_INUSE) == 0)) { return E4_NODENOTFOUND; } /* * Search for the parent record for the child node that contains * the parent node information: */ for (pid = (int) pParentID(nodes[nodeID]), rank = 1; pid != E4_NEXTNONE; pid = (int) pNext(parents[pid]), rank++) { if ((int) pNodeID(parents[pid]) == parentID) { return rank; } } return E4_NODENOTFOUND; } /* * Return the hash code for this storage. */ int e4_MetakitStorageImpl::DRV_HashCode() const { return (int) pFirst(unused[MK4_GRAPHHASHCODE]); } /* * Get a value for a statistic being collected for this storage. */ bool e4_MetakitStorageImpl::DRV_GetStatistic(e4_Space sp, e4_SpaceStat st, int &v) { /* * Select the statistic to retrieve. */ if (((int) sp < 0) || ((int) sp >= (int) E4_SPLAST) || ((int) st < 0) || ((int) st >= (int) E4_SSLAST)) { return false; } v = statistics[(int) sp][(int) st]; return true; } /* * Compute the number of slots available in a specific space in the storage. */ void e4_MetakitStorageImpl::UpdateAvailable(e4_Space sp) { /* TODO: Implement! */ } /* * Compute the number of slots used in a specific space in the storage. */ void e4_MetakitStorageImpl::UpdateUsed(e4_Space sp) { /* TODO: Implement! */ } /* * DETACHMENT MECHANISM: * ===================== */ /* * Detach the node identified by the given nodeID, by detaching * all vertices that have this node as their value from their containing * nodes. */ bool e4_MetakitStorageImpl::DRV_DetachNodeByID(int nodeID) { int nstate, pid, nextParentID, vertexID, nextVertexID; int parentID, next, prev, flags; /* * Sanity checks. */ if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return false; } /* * If already detached, punt. */ if (((int) pFlags(nodes[nodeID]) & MK4_DETACHED) == MK4_DETACHED) { return true; } /* * Iterate over all parents and detach all vertices that have the * child node as their value. */ for (pid = (int) pParentID(nodes[nodeID]); pid != E4_NEXTNONE; pid = nextParentID) { /* * Iterate over the vertices and set each of them to {E4_VTINT, 0}. */ parentID = (int) pNodeID(parents[pid]); /* * Update the vertex count of the parent node. */ pVertexCount(nodes[parentID]) = (int) pVertexCount(nodes[parentID]) - (int) pCount(parents[pid]); /* * Now detach each vertex in parentID that has this node as its * value. */ for (vertexID = (int) pVertexChain(parents[pid]); vertexID != E4_NEXTNONE; vertexID = nextVertexID) { /* * This vertex no longer denotes the nodeID. */ nextVertexID = (int) pNextInParent(vertices[vertexID]); pNextInParent(vertices[vertexID]) = E4_NEXTNONE; /* * Splice it out of its containing node. */ next = (int) pNext(vertices[vertexID]); prev = (int) pPrev(vertices[vertexID]); if (prev == E4_NEXTNONE) { pFirstVertex(nodes[parentID]) = next; } else { pNext(vertices[prev]) = next; } if (next == E4_NEXTNONE) { pLastVertex(nodes[parentID]) = prev; } else { pPrev(vertices[next]) = prev; } flags = (int) pFlags(vertices[vertexID]); flags |= MK4_DETACHED; pFlags(vertices[vertexID]) = flags; pNodeID(vertices[vertexID]) = pNextInParent(vertices[vertexID]) = pPrev(vertices[vertexID]) = pNext(vertices[vertexID]) = E4_NEXTNONE; /* * If the vertex is referenced then move it into the list of * detached vertices pointing at this node. Otherwise mark * the storage as needing GC. */ if (IsReferencedVertex(vertexID)) { pNextInParent(vertices[vertexID]) = (int) pDetachedVertices(nodes[nodeID]); pDetachedVertices(nodes[nodeID]) = (int) vertexID; } else { needsGC = true; } } /* * Recycle this parent record. */ nextParentID = (int) pNext(parents[pid]); UnusedParent(pid); } /* * This node now has no parents. */ pRefCount(nodes[nodeID]) = 0; pParentID(nodes[nodeID]) = E4_NEXTNONE; /* * Mark the node as detached. */ nstate = (int) pFlags(nodes[nodeID]); nstate |= (MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(nodes[nodeID]) = nstate; /* * If this node is not referenced by the user program, it might mean * that it became unreachable, so mark the storage as needing a GC. */ if (!IsReferencedNode(nodeID)) { needsGC = true; } /* * If a GC is needed and it's not deferred, do it now. */ DRV_DoGC(E4_AUTOGC); return true; } /* * Detach this vertex from its containing node. */ bool e4_MetakitStorageImpl::DRV_DetachVertexByID(int vertexID) { int nodeID, vstate; /* * Sanity checks. */ if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return false; } /* * If the vertex is already detached, punt. */ if (((int) pFlags(vertices[vertexID]) & MK4_DETACHED) == MK4_DETACHED) { return true; } /* * NOTE: If we got here the vertex MUST be in some node, because * MK4_DETACHED was not set. If this is not true, punt and fail. */ nodeID = (int) pNodeID(vertices[vertexID]); if (nodeID == E4_NEXTNONE) { return false; } /* * Splice the vertex out of its old parent. Note that this also * takes care of the case where the vertex point at a node, updating * the parent bookkeeping for the child node and moving the vertex * to the list of detached vertices pointing at the node. */ SpliceOut(vertexID, E4_NODENOTFOUND); /* * Mark the vertex as detached. */ vstate = (int) pFlags(vertices[vertexID]); vstate |= (MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(vertices[vertexID]) = vstate; /* * If the vertex is not referenced, mark the storage as needing GC. */ if (!IsReferencedVertex(vertexID)) { needsGC = true; } /* * If a GC is needed and GC is not being deferred, then clean up * right away. * * NOTE: In the new scheme GC would be deferred here and instead we * would record the vertexID as known unreachable. */ DRV_DoGC(E4_AUTOGC); return true; } /* * Is the node identified by the given ID detached? */ bool e4_MetakitStorageImpl::DRV_IsDetachedNodeID(int nodeID) const { if ((nodeID < 0) || (nodeID >= nodes.GetSize()) || (((int) pFlags(nodes[nodeID]) & MK4_INUSE) == 0)) { return false; } if (((int) pFlags(nodes[nodeID]) & MK4_DETACHED) == MK4_DETACHED) { return true; } return false; } /* * Is the vertex identified by the given ID detached? */ bool e4_MetakitStorageImpl::DRV_IsDetachedVertexID(int vertexID) const { if ((vertexID < 0) || (vertexID >= vertices.GetSize()) || (((int) pFlags(vertices[vertexID]) & MK4_INUSE) == 0)) { return false; } if (((int) pFlags(vertices[vertexID]) & MK4_DETACHED) == MK4_DETACHED) { return true; } return false; } /* * Get the vertex ID of the first or subsequent detached vertex after the given * vertex ID, whose value is the given node ID. */ int e4_MetakitStorageImpl::DRV_GetFirstDetachedVertexIDWithNodeID(int nodeID) const { return (int) pDetachedVertices(nodes[nodeID]); } int e4_MetakitStorageImpl::DRV_GetNextDetachedVertexIDAfter(int vertexID) const { return (int) pNextInParent(vertices[vertexID]); } /* * GC MECHANISM: * ============= */ /* * Do a GC. */ void e4_MetakitStorageImpl::DRV_DoGC(int reqstate) { int oldState, tmpState; /* * Always honor explicit GC requests. Otherwise, if the * requested GC state is not set, do not enter GC. */ if (!((reqstate == E4_REQUESTEDGC) || ((GetState() & reqstate) == reqstate))) { return; } /* * Only do GC if the storage is not NULL. */ if (storage == NULL) { return; } /* * If the requested GC state is E4_AUTOGC only do the GC if needsGC * is set. */ if ((reqstate == E4_AUTOGC) && (needsGC == false)) { return; } /* * Defer GC until we're done, and keep looping until needsGC * is false. */ oldState = GetState(); tmpState = (oldState & (~(E4_AUTOGC))); SetState(tmpState); do { InitGC(); SpanReachableNodes(); CollectUnreachableEntities(); FireEventsForNewlyDetached(); } while (needsGC); SetState(oldState); } /* * Helper method to reinitialize the GC counters. */ void e4_MetakitStorageImpl::InitGC() { needsGC = false; } /* * Is GC needed? */ bool e4_MetakitStorageImpl::DRV_NeedsGC() const { return needsGC; } /* * Set the flag indicating whether GC is needed. */ void e4_MetakitStorageImpl::DRV_SetNeedsGC(bool needs) { needsGC = needs; } /* * Span all reachable nodes. At the end of this procedure all reachable * entities have MK4_REACHABLE in their flags. */ void e4_MetakitStorageImpl::SpanReachableNodes() { /* * Seed the set of reachable nodes from the exported nodes. This * may add some nodes that are exported but detached. */ SeedReachableNodesFromReferencedNodes(); /* * Seed the set of reachable nodes from the exported vertices. This * may add some nodes that are reachable only from referenced vertices. */ SeedReachableNodesFromReferencedVertices(); /* * Now span the initial set to mark the complete set of all * reachable nodes. As a side effect also mark all reachable vertices. */ SpanSeededNodes(); } /* * Seed the set of reachable nodes from the set of referenced nodes and * from the distinguished root node. */ void e4_MetakitStorageImpl::SeedReachableNodesFromReferencedNodes() { int i, l, nstate; for (i = 0, l = nodes.GetSize(); i < l; i++) { nstate = (int) pFlags(nodes[i]); /* * Look for IN_USE nodes. */ if ((nstate & MK4_INUSE) == MK4_INUSE) { /* * If this node is referenced by the user program it is * considered to be reachable. */ if (IsReferencedNode(i)) { idStack1->Push(i); } } } /* * Last, seed from the root node. */ idStack1->Push((int) pFirst(unused[MK4_GRAPHROOTNODE])); } /* * Seed the set of reachable nodes from the set of referenced vertices. * Some of these vertices may hold the only reference to a node. */ void e4_MetakitStorageImpl::SeedReachableNodesFromReferencedVertices() { int i, l, vstate, nodeID; for (i = 0, l = vertices.GetSize(); i < l; i++) { vstate = (int) pFlags(vertices[i]); /* * Look for IN_USE vertices. */ if ((vstate & MK4_INUSE) == MK4_INUSE) { /* * If the vertex is referenced from the user program, it is * considered reachable. Check if the value is a node. If so, * that node is also considered reachable. Do *NOT* mark the * node as reachable here so that the spanning phase knows to * span through it to all reachable nodes from this node. */ if (IsReferencedVertex(i)) { vstate |= MK4_REACHABLE; pFlags(vertices[i]) = vstate; /* * If the value is a node, that node is also considered * to be reachable. */ if ((e4_VertexType) (int) pVertexType(vertices[i]) == E4_VTNODE) { nodeID = (int) pRowID(vertices[i]); idStack1->Push(nodeID); } } } } } /* * Span the set of nodes collected in the seeding phase, marking each one * as reachable, and also marking any vertices that are contained in * reachable nodes as reachable. */ void e4_MetakitStorageImpl::SpanSeededNodes() { int nodeID, childID, vertexID, nstate, cstate, vstate; bool changed; e4_IntStack *tmpstk; /* * Iterate until changed == false. If a node is found that is not * marked as reachable, then: * - this node is marked as reachable, * - changed is set to true, * - the child nodes of this node are added to the spanning set, * - the vertices in this node are marked as reachable and */ do { /* * No change so far. */ changed = false; /* * Iterate over all nodes currently known as seeds: */ while (idStack1->Pop(&nodeID)) { /* * Check if this node is not yet known to be reachable. */ nstate = (int) pFlags(nodes[nodeID]); if ((nstate & MK4_REACHABLE) == 0) { /* * Found a node that is not yet known to be reachable. * * Step 1: Mark this node as reachable. */ nstate |= MK4_REACHABLE; pFlags(nodes[nodeID]) = nstate; /* * Step 2: Record that something changed. */ changed = true; /* * Step 3 and 4: Add the child nodes to the set of seeds * to be examined next, and mark all vertices in this node * as reachable. */ for (vertexID = (int) pFirstVertex(nodes[nodeID]); vertexID != E4_NEXTNONE; vertexID = (int) pNext(vertices[vertexID])) { vstate = (int) pFlags(vertices[vertexID]); /* * Sanity check: Vertex cannot be detached. */ if ((vstate & MK4_DETACHED) == MK4_DETACHED) { fprintf(stderr, "Inconsistent state: detached vertex %d in node %d\n", vertexID, nodeID); } /* * Mark this vertex as reachable. */ vstate |= MK4_REACHABLE; pFlags(vertices[vertexID]) = vstate; /* * See if the value is a node. */ if ((e4_VertexType) (int) pVertexType(vertices[vertexID]) == E4_VTNODE) { /* * Found a node. */ childID = (int) pRowID(vertices[vertexID]); /* * Sanity checks: cannot be detached. */ cstate = (int) pFlags(nodes[childID]); if ((cstate & MK4_DETACHED) == MK4_DETACHED) { fprintf(stderr, "Inconsistent state: detached node %d in vertex %d\n", childID, vertexID); } /* * Add the node to the set of seeds to be examined * next round. */ idStack2->Push(childID); } } } } /* * Switch stacks. At this point idStack2 contains the newly * reachable nodes whose children may not yet have been * explored, and idStack1 is empty. */ tmpstk = idStack1; idStack1 = idStack2; idStack2 = tmpstk; } while (changed); } /* * Collect all unreachable entities. */ void e4_MetakitStorageImpl::CollectUnreachableEntities() { /* * Order is important: First we recycle the values of all unreachable * vertices, then we collect unreachable nodes. Finally we collect * unreachable vertices. This is the required order because recycling * unreachable vertex values may cause the vertex to be spliced out of * a node. If we attempted that after collecting unreachable nodes then * dangling pointers would result. */ RecycleUnreachableVertexValues(); CollectUnreachableNodes(); CollectUnreachableVertices(); } /* * Collect all unreachable nodes, add them to the nodes free list. */ void e4_MetakitStorageImpl::CollectUnreachableNodes() { int i, nstate, next, pstate; /* * Reset nodes free list. */ pFirst(unused[MK4_GRAPHFIRSTUNUSEDNODE]) = E4_NEXTNONE; /* * Add all nodes that aren't explicitly marked as reachable to * the nodes free list. Traverse in reverse order to that the * free list will be ordered in ascending order. All parent * records that are no longer used are marked as such. */ for (i = nodes.GetSize() - 1; i > -1; i--) { nstate = (int) pFlags(nodes[i]); /* * If the node is not marked as reachable, add it to the * nodes free list. Also mark any attached parent records * as no longer in use if the node was in use. */ if ((nstate & MK4_REACHABLE) == 0) { if ((nstate & MK4_INUSE) == MK4_INUSE) { for (next = (int) pParentID(nodes[i]); next != E4_NEXTNONE; next = (int) pNext(parents[next])) { pFlags(parents[next]) = 0; } for (next = (int) pFirstVertex(nodes[i]); next != E4_NEXTNONE; next = (int) pNext(vertices[next])) { pNodeID(vertices[next]) = E4_NEXTNONE; } } UnusedNode(i); } else { nstate &= ~(MK4_REACHABLE); pFlags(nodes[i]) = nstate; } } /* * Now rebuild the parents free list. */ pFirst(unused[MK4_GRAPHFIRSTUNUSEDPARENT]) = E4_NEXTNONE; for (i = parents.GetSize() - 1; i > -1; i--) { pstate = (int) pFlags(parents[i]); if ((pstate & MK4_INUSE) == 0) { UnusedParent(i); } } } /* * For unreachable vertices whose value is a node, if the node * is marked as reachable, splice the vertex out of its parent. If the * node value is not marked reachable, do not bother. * * For unreachable vertices with other values, recycle the storage * occuppied by the value. */ void e4_MetakitStorageImpl::RecycleUnreachableVertexValues() { int i, vstate, nodeID; for (i = vertices.GetSize() - 1; i > -1; i--) { vstate = (int) pFlags(vertices[i]); if ((vstate & MK4_REACHABLE) == 0) { /* * If the vertex was not in use, it was already unreachable. */ if ((vstate & MK4_INUSE) == MK4_INUSE) { /* * Check if the value is a node. If not, just recycle the * value. If it is a node, check if the node is marked * reachable. If it is, splice the vertex out of its * parents, otherwise don't bother. * * If we remove the old parent, do not recursively start * a new GC or callback event processing. Callbacks will * be processed en-masse when the GC is done. */ if ((e4_VertexType) (int) pVertexType(vertices[i]) == E4_VTNODE) { nodeID = (int) pRowID(vertices[i]); if (nodeID != E4_NEXTNONE) { if (((int) pFlags(nodes[nodeID]) & MK4_REACHABLE) == MK4_REACHABLE) { RemoveParent(nodeID, (int) pNodeID(vertices[i]), i, false); } } } else { FreeVertexValue(i); } } } } } /* * Collect unreachable vertices, add them to the vertices free list and * recycle the storage for the value. */ void e4_MetakitStorageImpl::CollectUnreachableVertices() { int i, vstate; /* * Reset vertices free list. */ pFirst(unused[MK4_GRAPHFIRSTUNUSEDVERTEX]) = E4_NEXTNONE; /* * Add all vertices that aren't explicitly marked reachable to the * free list. Traverse the list in descending order so that the free * list will be ordered in ascending order. */ for (i = vertices.GetSize() - 1; i > -1; i--) { vstate = (int) pFlags(vertices[i]); if ((vstate & MK4_REACHABLE) == 0) { UnusedVertex(i); } else { vstate &= ~(MK4_REACHABLE); pFlags(vertices[i]) = vstate; } } } /* * Fire detach events for entities that became newly detached * during this GC. */ void e4_MetakitStorageImpl::FireEventsForNewlyDetached() { FireEventsForNewlyDetachedNodes(); FireEventsForNewlyDetachedVertices(); } void e4_MetakitStorageImpl::FireEventsForNewlyDetachedNodes() { int i, l, flags; e4_NodeImpl *np; bool nodeDetCallbacks; nodeDetCallbacks = HasCallbacks(E4_ECDETNODE); /* * We must iterate over all nodes even when there are no * registered callbacks, to correctly set the MK4_DETACHED * flag for newly detached nodes. */ for (i = 0, l = nodes.GetSize(); i < l; i++) { flags = (int) pFlags(nodes[i]); if ((flags & MK4_INUSE) == 0) { continue; } /* * If this node already has been notified of * a detach, don't bother. */ if ((flags & MK4_DETACHNOTIFY) == MK4_DETACHNOTIFY) { continue; } /* * If we found a detached node, process it. */ if (((int) pParentID(nodes[i]) == E4_NEXTNONE) && ((int) pDetachedVertices(nodes[i]) == E4_NEXTNONE)) { flags |= (MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(nodes[i]) = flags; if (nodeDetCallbacks) { np = FindReferencedNode(i); if ((np != NULL) && (!np->HasFlags(E4_CBDETACHDELIVERED))) { CauseEventInternal(E4_ECDETNODE, np, NULL); np->SetFlags(E4_CBDETACHDELIVERED); } } } } } void e4_MetakitStorageImpl::FireEventsForNewlyDetachedVertices() { int i, l, flags; bool vertexDetCallbacks; e4_VertexImpl *vp; vertexDetCallbacks = HasCallbacks(E4_ECDETVERTEX); /* * We must iterate over all vertices even when there are no * callbacks registered, to set the MK4_DETACHED flags for * newly detached vertices. */ for (i = 0, l = vertices.GetSize(); i < l; i++) { flags = (int) pFlags(vertices[i]); if ((flags & MK4_INUSE) == 0) { continue; } /* * If this vertex already has been notified of * a detach, don't bother. */ if ((flags & MK4_DETACHNOTIFY) == MK4_DETACHNOTIFY) { continue; } /* * If we found a detached vertex, process it. */ if ((int) pNodeID(vertices[i]) == E4_NEXTNONE) { flags |= (MK4_DETACHED | MK4_DETACHNOTIFY); pFlags(vertices[i]) = flags; if (vertexDetCallbacks) { vp = FindReferencedVertex(i); if ((vp != NULL) && (!vp->HasFlags(E4_CBDETACHDELIVERED))) { CauseEventInternal(E4_ECDETVERTEX, vp, NULL); vp->SetFlags(E4_CBDETACHDELIVERED); } } } } }