00001 // Filename: dataGraphTraverser.cxx 00002 // Created by: drose (11Mar02) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "dataGraphTraverser.h" 00016 #include "dataNode.h" 00017 #include "config_dgraph.h" 00018 #include "dcast.h" 00019 00020 00021 //////////////////////////////////////////////////////////////////// 00022 // Function: DataGraphTraverser::CollectedData::set_data 00023 // Access: Public 00024 // Description: Sets the data associated with the indicated parent of 00025 // this CollectedData object's node. 00026 //////////////////////////////////////////////////////////////////// 00027 void DataGraphTraverser::CollectedData:: 00028 set_data(int parent_index, const DataNodeTransmit &data) { 00029 if ((int)_data.size() <= parent_index) { 00030 _data.reserve(parent_index + 1); 00031 while ((int)_data.size() <= parent_index) { 00032 _data.push_back(DataNodeTransmit()); 00033 } 00034 } 00035 00036 nassertv(parent_index >= 0 && parent_index < (int)_data.size()); 00037 _data[parent_index] = data; 00038 } 00039 00040 //////////////////////////////////////////////////////////////////// 00041 // Function: DataGraphTraverser::Constructor 00042 // Access: Public 00043 // Description: 00044 //////////////////////////////////////////////////////////////////// 00045 DataGraphTraverser:: 00046 DataGraphTraverser(Thread *current_thread) : _current_thread(current_thread) { 00047 } 00048 00049 //////////////////////////////////////////////////////////////////// 00050 // Function: DataGraphTraverser::Destructor 00051 // Access: Public 00052 // Description: 00053 //////////////////////////////////////////////////////////////////// 00054 DataGraphTraverser:: 00055 ~DataGraphTraverser() { 00056 } 00057 00058 //////////////////////////////////////////////////////////////////// 00059 // Function: DataGraphTraverser::traverse 00060 // Access: Public 00061 // Description: Starts the traversal of the data graph at the 00062 // indicated root node. 00063 //////////////////////////////////////////////////////////////////// 00064 void DataGraphTraverser:: 00065 traverse(PandaNode *node) { 00066 if (node->is_of_type(DataNode::get_class_type())) { 00067 DataNode *data_node = DCAST(DataNode, node); 00068 // We must start the traversal at the root of the graph. 00069 nassertv(data_node->get_num_parents(_current_thread) == 0); 00070 00071 r_transmit(data_node, (DataNodeTransmit *)NULL); 00072 00073 } else { 00074 traverse_below(node, DataNodeTransmit()); 00075 } 00076 00077 collect_leftovers(); 00078 } 00079 00080 //////////////////////////////////////////////////////////////////// 00081 // Function: DataGraphTraverser::traverse_below 00082 // Access: Public 00083 // Description: Continues the traversal to all the children of the 00084 // indicated node, passing in the given data, without 00085 // actually calling transmit_data() on the given node. 00086 //////////////////////////////////////////////////////////////////// 00087 void DataGraphTraverser:: 00088 traverse_below(PandaNode *node, const DataNodeTransmit &output) { 00089 PandaNode::Children cr = node->get_children(_current_thread); 00090 int num_children = cr.get_num_children(); 00091 00092 for (int i = 0; i < num_children; i++) { 00093 PandaNode *child_node = cr.get_child(i); 00094 if (child_node->is_of_type(DataNode::get_class_type())) { 00095 DataNode *data_node = DCAST(DataNode, child_node); 00096 // If it's a DataNode-type child, we need to pass it the data. 00097 // Maybe it has only one parent, and can accept the data 00098 // immediately. 00099 int num_parents = data_node->get_num_parents(_current_thread); 00100 if (num_parents == 1) { 00101 // The easy, common case: only one parent. We make our output 00102 // into a one-element array of inputs by turning it into a 00103 // pointer. 00104 r_transmit(data_node, &output); 00105 } else { 00106 // A more difficult case: multiple parents. We must collect 00107 // instances together, meaning we must hold onto this node 00108 // until we have reached it through all paths. 00109 CollectedData &collected_data = _multipass_data[data_node]; 00110 int parent_index = data_node->find_parent(node, _current_thread); 00111 nassertv(parent_index != -1); 00112 00113 collected_data.set_data(parent_index, output); 00114 collected_data._num_parents++; 00115 nassertv(collected_data._num_parents <= num_parents); 00116 if (collected_data._num_parents == num_parents) { 00117 // Now we've got all the data; go into the child. 00118 r_transmit(data_node, &collected_data._data[0]); 00119 _multipass_data.erase(data_node); 00120 } 00121 } 00122 } else { 00123 // The child node is not a DataNode-type child. We continue the 00124 // traversal, but data does not pass through this node, and 00125 // instances are not collected together. (Although we appear to 00126 // be passing the data through here, it doesn't do any good 00127 // anyway, since the child nodes of this node will not know how 00128 // to interpret the data from a non-DataNode parent.) 00129 traverse_below(child_node, output); 00130 } 00131 } 00132 } 00133 00134 //////////////////////////////////////////////////////////////////// 00135 // Function: DataGraphTraverser::collect_leftovers 00136 // Access: Public 00137 // Description: Pick up any nodes that didn't get completely 00138 // traversed. These must be nodes that have multiple 00139 // parents, with at least one parent completely outside 00140 // of the data graph. 00141 //////////////////////////////////////////////////////////////////// 00142 void DataGraphTraverser:: 00143 collect_leftovers() { 00144 while (!_multipass_data.empty()) { 00145 MultipassData::iterator mi = _multipass_data.begin(); 00146 DataNode *data_node = (*mi).first; 00147 const CollectedData &collected_data = (*mi).second; 00148 00149 dgraph_cat.warning() 00150 << *data_node << " improperly parented partly outside of data graph.\n"; 00151 00152 r_transmit(data_node, &collected_data._data[0]); 00153 _multipass_data.erase(mi); 00154 } 00155 } 00156 00157 //////////////////////////////////////////////////////////////////// 00158 // Function: DataGraphTraverser::r_transmit 00159 // Access: Private 00160 // Description: Part of the recursive implementation of traverse(). 00161 // This transmits the given data into the indicated 00162 // DataNode, and then sends the output data to each of 00163 // the node's children. 00164 //////////////////////////////////////////////////////////////////// 00165 void DataGraphTraverser:: 00166 r_transmit(DataNode *data_node, const DataNodeTransmit inputs[]) { 00167 DataNodeTransmit output; 00168 output.reserve(data_node->get_num_outputs()); 00169 data_node->transmit_data(this, inputs, output); 00170 00171 traverse_below(data_node, output); 00172 }