Hi,
here is a patch, which adds remove functionality to the patch cache
(hash-table) of the property tree.
What the patch does:
Every time a path is stored in a path-cache of a property node, the
referenced hash table adds a link to this path-cache. Therefore a node
knows all other nodes, which references him in their path-cache.
If a node is removed, it and all children tell all patch-caches, which
link to them, to delete this entries.
Therefore it is save now, to address a node by its name, even if a node
with the same name was deleted before (e.g. the AI/ tree is very dynamic).
The property tree is a very central part of flightgear. Therefore I
decided to comment out my debug outputs instead of deleting them (maybe
it's easier to check the functionality of the patch). Even the _value
member of SGPropertyNode::hash_table is only for the debug output.
If noone complains, I will post a patch without the debug stuff to be
committed to cvs soon.
(With this patch and the multiplayer patch (in cvs) aerotow should work
stable over the net).
Maik
Maik Justus schrieb am 22.01.2007 01:21:
Hi just to clarify:
if I wrote delete, I meant not delete as cpp defines delete. I thought
of removing a node.
Maik
Maik Justus schrieb am 22.01.2007 01:11:
Hi,
the patch-cache of the property tree is not designed for node-deleting.
But the multiplayer code deletes nodes deletes nodes very often. If you
access such nodes by name, which is necessary to acces multiplayer-nodes
(you can not store a pointer, tho node could be deleted meanwhile), you
often get a pointer to a already deleted node. As a result, aerotowing
often fails, if one player was removed from the multiplayer list for a
short time. As an ugly fix, you can switch off the path cache and
aerotow works as expected. As a solution I think of a vector of path
caches at every node, which stores all path caches, if they are pointing
to this node. If a node is removed, all linked path caches get this
information and the link can be deleted. This must be done for all
child-nodes, too. (one question: which member of SGPropertyNode is
called if a node is removed from the tree?)
Maik
Index: props.cxx
===================================================================
RCS file: /var/cvs/SimGear-0.3/source/simgear/props/props.cxx,v
retrieving revision 1.26
diff -u -p -r1.26 props.cxx
--- props.cxx 22 Oct 2006 13:08:09 -0000 1.26
+++ props.cxx 28 Jan 2007 20:18:53 -0000
@@ -909,6 +909,19 @@ SGPropertyNode::getChildren (const char
return children;
}
+void
+SGPropertyNode::removeTreeFromPathCaches()
+{
+ //if(_linkedNodes.size()) cout<<"removing tree from "<< _linkedNodes.size()
<<" path caches '"<<getPath()<<"'" << endl;
+ for(unsigned i=0; i<_linkedNodes.size(); i++)
+ {
+ _linkedNodes[i]->eraseNodeByPtr(this);
+ }
+ _linkedNodes.clear();
+ for (unsigned i = 0; i < _children.size(); ++i)
+ _children[i]->removeTreeFromPathCaches();
+}
+
/**
* Remove child by position.
@@ -931,6 +944,7 @@ SGPropertyNode::removeChild (int pos, bo
_path_cache->erase(node->getName()); // EMH - TODO: Take "index" into
account!
node->setAttribute(REMOVED, true);
node->clearValue();
+ node->removeTreeFromPathCaches();
fireChildRemoved(node);
return node;
}
@@ -967,6 +981,29 @@ SGPropertyNode::removeChildren (const ch
}
+ /**
+ * remove a linked node
+ */
+bool
+SGPropertyNode::removeLinkedNode (SGHashTable_ptr node)
+{
+ //cout<<"trying to remove a linked Node of '"<<getPath()<<"', linked by
'"<<node->_value->getPath()<<"':";
+ for(unsigned i=0; i<_linkedNodes.size(); i++)
+ {
+ if (_linkedNodes[i]==node)
+ {
+ vector<SGHashTable_ptr>::iterator it = _linkedNodes.begin();
+ it += i;
+ _linkedNodes.erase(it);
+ //cout <<"ok"<<endl;
+ return true;
+ }
+ }
+ //cout <<"error, not found!"<<endl;
+ return false;
+}
+
+
const char *
SGPropertyNode::getDisplayName (bool simplify) const
{
@@ -1741,8 +1778,7 @@ SGPropertyNode *
SGPropertyNode::getNode (const char * relative_path, bool create)
{
if (_path_cache == 0)
- _path_cache = new hash_table;
-
+ _path_cache = new hash_table(this);
SGPropertyNode * result = _path_cache->get(relative_path);
if (result == 0) {
vector<PathComponent> components;
@@ -2210,11 +2246,17 @@ SGPropertyNode::hash_table::bucket::eras
}
}
-
+/*
SGPropertyNode::hash_table::hash_table ()
: _data_length(0),
_data(0)
{
+}*/
+SGPropertyNode::hash_table::hash_table (SGPropertyNode * value)
+ : _data_length(0),
+ _data(0)
+{
+ _value=value;
}
SGPropertyNode::hash_table::~hash_table ()
@@ -2254,6 +2296,8 @@ SGPropertyNode::hash_table::put (const c
}
entry * e = _data[index]->get_entry(key, true);
e->set_value(value);
+ value->addLinkedNode(this);
+ //cout<<"adding linked Note '"<<_value->getPath() <<"' to
'"<<value->getPath()<<"'"<<endl;
}
void
@@ -2264,7 +2308,39 @@ SGPropertyNode::hash_table::erase (const
unsigned int index = hashcode(key) % _data_length;
if (_data[index] == 0)
return;
+ _data[index]->get_entry(key, true)->get_value()->removeLinkedNode(this);
_data[index]->erase(key);
+ _data[index]=0;
+}
+
+bool
+SGPropertyNode::hash_table::bucket::eraseNodeByPtr(SGPropertyNode * value)
+{
+ int i;
+ for (i = 0; i < _length; i++) {
+ if (_entries[i]->get_value()==value)
+ {
+ for (++i; i < _length; i++) {
+ _entries[i-1] = _entries[i];
+ }
+ _length--;
+ return true;
+ }
+ }
+ return false;
+}
+
+
+bool
+SGPropertyNode::hash_table::eraseNodeByPtr(SGPropertyNode * value)
+{
+ unsigned int d;
+ //cout<<"deleting '"<<value->getPath()<<"' at '"<<_value->getPath()<<"':";
+
+ for (d = 0; d < _data_length; d++)
+ if(_data[d]) if(_data[d]->eraseNodeByPtr(value)) {/*cout <<
"ok!"<<endl;*/return true;}
+ //cout<<"error!"<<endl;
+ return false;
}
unsigned int
Index: props.hxx
===================================================================
RCS file: /var/cvs/SimGear-0.3/source/simgear/props/props.hxx,v
retrieving revision 1.18
diff -u -p -r1.18 props.hxx
--- props.hxx 14 Mar 2006 15:55:24 -0000 1.18
+++ props.hxx 28 Jan 2007 20:18:56 -0000
@@ -457,7 +457,8 @@ private:
class SGPropertyNode;
typedef SGSharedPtr<SGPropertyNode> SGPropertyNode_ptr;
typedef SGSharedPtr<const SGPropertyNode> SGConstPropertyNode_ptr;
-
+//class hash_table;
+//typedef SGSharedPtr<hash_table> SGHashTable_ptr;
/**
* The property change listener interface.
@@ -489,6 +490,7 @@ private:
*/
class SGPropertyNode : public SGReferenced
{
+
public:
/**
@@ -781,7 +783,7 @@ public:
* Set a single mode attribute for the property node.
*/
void setAttribute (Attribute attr, bool state) {
- (state ? _attr |= attr : _attr &= ~attr);
+ (state ? _attr |= attr : _attr &= ~attr);//hier auch die Child
}
@@ -1134,6 +1136,13 @@ public:
void clearValue ();
+ /**
+ * tell all linked nodes (path cache entries) that
+ * this node and all childes are removed
+ */
+ void removeTreeFromPathCaches();
+
+
protected:
void fireValueChanged (SGPropertyNode * node);
@@ -1184,6 +1193,7 @@ private:
class hash_table;
+ typedef hash_table* SGHashTable_ptr;
int _index;
string _name;
@@ -1193,6 +1203,7 @@ private:
SGPropertyNode * _parent;
vector<SGPropertyNode_ptr> _children;
vector<SGPropertyNode_ptr> _removedChildren;
+ vector<SGHashTable_ptr> _linkedNodes;//by hash
mutable string _path;
mutable string _buffer;
hash_table * _path_cache;
@@ -1222,10 +1233,28 @@ private:
vector <SGPropertyChangeListener *> * _listeners;
+public:
+ //
+ // linked nodes (this nodes have references to this Node in their hash table)
+ //
+
+ /**
+ * add a linked node (a Hash Table o another Node which references this node)
+ */
+ void addLinkedNode (const SGHashTable_ptr node) {
_linkedNodes.push_back(node); }
+
+
+ /**
+ * remove a linked node (a Hash Table o another Node which references this
node)
+ */
+ bool removeLinkedNode (SGHashTable_ptr node);
+
+
+private:
/**
- * A very simple hash table with no remove functionality.
+ * A very simple hash table with remove functionality.
*/
class hash_table {
public:
@@ -1256,6 +1285,7 @@ private:
~bucket ();
entry * get_entry (const char * key, bool create = false);
void erase(const char * key);
+ bool eraseNodeByPtr(SGPropertyNode * value);
private:
int _length;
entry ** _entries;
@@ -1263,11 +1293,13 @@ private:
friend class bucket;
- hash_table ();
+ hash_table (SGPropertyNode * value);
+ SGPropertyNode * _value; //only for debug
~hash_table ();
SGPropertyNode * get (const char * key);
void put (const char * key, SGPropertyNode * value);
void erase(const char * key);
+ bool eraseNodeByPtr(SGPropertyNode * value);
private:
unsigned int hashcode (const char * key);
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Flightgear-devel mailing list
Flightgear-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/flightgear-devel
