node_file.cpp
Go to the documentation of this file.
00001 #include <megatree/node_file.h>
00002 #include <math.h>
00003 #include <algorithm>
00004 #include <string.h>
00005 
00006 namespace megatree
00007 {
00008 
00009 
00010 void NodeFile::deserialize()
00011 {
00012   is_modified = true;
00013 
00014   // signal conditions that are waiting for initialization
00015   SpinLock::ScopedLock lock(node_state_mutex);
00016   node_state = LOADED;
00017   node_state_condition.notify_all();
00018 }
00019 
00020 
00021 void NodeFile::deserialize(const ByteVec &buffer)
00022 {
00023   //use_count = 0; only set use_count to 0 in constructor
00024   is_modified = false;
00025   unsigned offset = 0;
00026 
00027   // Reads the byte indicating which child node files exist.
00028   memcpy(&child_files, (void*)&buffer[offset], 1);
00029   offset += 1;
00030 
00031   // Reads all the nodes
00032   while (offset < buffer.size())
00033   {
00034     ShortId short_id;
00035     Node* node = node_allocator ? node_allocator->allocate() : new Node;
00036     deserializeNode(node, short_id, buffer, offset);
00037 
00038     // add node to cache
00039     NodeCache::iterator it = node_cache.find(short_id);
00040     if (it == node_cache.end())
00041     {
00042       node_cache.insert(std::pair<ShortId, Node* >(short_id, node));
00043     }
00044     else
00045     {
00046       *(it->second) = *node;
00047       node_allocator ? node_allocator->deAllocate(node) : delete node;
00048     }
00049   }
00050 
00051   assert(buffer.size() == offset);
00052 
00053   // signal conditions that are waiting for initialization
00054   SpinLock::ScopedLock lock(node_state_mutex);
00055   node_state = LOADED;
00056   node_state_condition.notify_all();
00057 
00058   //printf("Deserialized buffer %s with num nodes %d\n", path.string().c_str(), (int)node_cache.size());
00059 }
00060 
00061 
00062 void NodeFile::serialize(ByteVec& buffer)
00063 {
00064   buffer.resize(1 + node_cache.size() * NODE_SIZE);
00065   unsigned offset = 0;
00066 
00067   // Writes the byte indicating which child node files exist.
00068   memcpy(&buffer[offset], (char*)(&child_files), 1);
00069   offset += 1;
00070 
00071   // write entire cache into buffer
00072   for (NodeCache::const_iterator it=node_cache.begin(); it!=node_cache.end(); it++)
00073     serializeNode(it->second, it->first, buffer, offset);
00074 
00075   //printf("Serialized to buffer %s with num nodes %d\n", path.string().c_str(), (int)node_cache.size());
00076 }
00077 
00078 void NodeFile::serializeBytesize(ByteVec& buffer)
00079 {
00080   const static size_t STRIDE = 3 + 3;
00081   buffer.resize(1 + node_cache.size() * STRIDE);
00082   buffer[0] = child_files;
00083   size_t offset = 1;
00084 
00085   for (NodeCache::const_iterator it = node_cache.begin(); it != node_cache.end(); ++it)
00086   {
00087     // Determines the node's position from the id
00088     //
00089     // ID:  0123456789abcdefgh  (0 is high bit)
00090     //  x:  0  3  6  9  c  f
00091     //  y:   1  4  7  a  d  g
00092     //  z:    2  5  8  b  e  h
00093     uint8_t x=0, y=0, z=0;
00094     for (int i = 7; i >=0; --i) {
00095       int which = (it->first >> (i*3)) & 07;
00096       x = (x << 1) | ((which & (1<<X_BIT)) ? 1 : 0);
00097       y = (y << 1) | ((which & (1<<Y_BIT)) ? 1 : 0);
00098       z = (z << 1) | ((which & (1<<Z_BIT)) ? 1 : 0);
00099     }
00100 
00101     // TODO: This assumes nodefiles with a width of 6, which is not true all the time.
00102     x = x << 2;
00103     y = y << 2;
00104     z = z << 2;
00105 
00106     buffer[offset + 0] = x;
00107     buffer[offset + 1] = y;
00108     buffer[offset + 2] = z;
00109 
00110     // Copies over the color
00111     buffer[offset + 3] = it->second->color[0];
00112     buffer[offset + 4] = it->second->color[1];
00113     buffer[offset + 5] = it->second->color[2];
00114 
00115     offset += STRIDE;
00116   }
00117 }
00118 
00119 
00120 // use condition variable to wait for initialization
00121 void NodeFile::waitUntilLoaded()
00122 {
00123   //TODO: Decide what to do with conditions here
00124   //boost::mutex dummy_mutex;
00125   //boost::mutex::scoped_lock dummy_lock(dummy_mutex);
00126   while (true)
00127   {
00128     {
00129       SpinLock::ScopedLock lock(node_state_mutex);
00130       if(node_state == LOADED)
00131         break;
00132       node_state_condition.wait(node_state_mutex);
00133     }
00134     //node_state_condition.wait(dummy_lock);
00135   }
00136 }
00137 
00138 void NodeFile::setNodeState(NodeState state)
00139 {
00140   SpinLock::ScopedLock lock(node_state_mutex);
00141   node_state = state;
00142   node_state_condition.notify_all();
00143 }
00144 
00145 NodeFile::~NodeFile()
00146 {
00147   // return nodes back to node_allocator
00148   if (node_allocator) {
00149     std::vector<Node*> allocated_nodes(node_cache.size());
00150     size_t i = 0;
00151     for (NodeCache::iterator it = node_cache.begin(); it != node_cache.end(); it++)
00152     {
00153       allocated_nodes[i++] = it->second;
00154     }
00155     assert(!allocated_nodes.empty());
00156     assert(allocated_nodes[0] != NULL);
00157     node_allocator->deallocateMany(allocated_nodes);
00158   }
00159   else {
00160     for (NodeCache::iterator it = node_cache.begin(); it != node_cache.end(); it++)
00161     {
00162       delete it->second;
00163     }
00164   }
00165 
00166   // checks
00167   if (is_modified)
00168     fprintf(stderr, "Destructing NodeFile %s that was not written to disk\n", path.string().c_str());
00169 
00170   if (users() != 0)
00171     fprintf(stderr, "NodeFile %s destructing while %d nodes are still in use!\n", path.string().c_str(), users());
00172 }
00173 
00174 
00175 
00176 
00177 // Reads an existing node from the cache.
00178 // When reading from disk, we don't know the id of the node, so the id is passed on.
00179 Node* NodeFile::readNode(const ShortId& short_id)
00180 {
00181   // get the node from the cache
00182   NodeCache::iterator it = node_cache.find(short_id);
00183   if (it == node_cache.end())
00184   {
00185     SpinLock::ScopedLock lock(node_state_mutex);
00186 
00187     assert(node_state != EVICTING);
00188 
00189     // allocate a Node object
00190     if (node_state == LOADING)
00191     {
00192       Node* node = node_allocator ? node_allocator->allocate() : new Node;
00193       node->reset();
00194       node_cache.insert(std::pair<ShortId, Node* >(short_id, node));
00195       use_count++;
00196 
00197       return node;
00198     }
00199 
00200     // bad situation
00201     fprintf(stderr, "Could not find node with short_id %o in %s with %d nodes\n",
00202             short_id, path.string().c_str(), (int)node_cache.size());
00203     /*
00204     for (NodeCache::iterator jt = node_cache.begin(); jt != node_cache.end(); ++jt)
00205     {
00206       fprintf(stderr, "  Node  %8u: \n", jt->first);
00207     }
00208     */
00209     //abort();
00210     return NULL;
00211   }
00212 
00213   use_count++;
00214 
00215   return it->second;
00216 }
00217 
00218 void NodeFile::initializeFromChildren(const boost::filesystem::path &_path,
00219                                       std::vector<boost::shared_ptr<NodeFile> >& children)
00220 {
00221   assert(children.size() == 8);
00222   node_cache.clear();
00223   child_files = 0;
00224   path = _path;
00225 
00226   // Here's how the ID's of the nodes change:
00227   //
00228   //          nodefile       short_id
00229   // child:   f171114232?    321567
00230   // parent:  f171114232    ?32156
00231 
00232   // Assigns child nodes to the parent node that they descend from.
00233   typedef std::map<ShortId, std::vector<Node*> > ParentGrouping;
00234   ParentGrouping parent_groupings;  // parent short id  ->  8 child nodes
00235   for (int i = 0; i < 8; ++i)
00236   {
00237     if (children[i])
00238     {
00239       child_files |= (1 << i);
00240 
00241       // Encodes the id element that came from the child nodefile's id and
00242       // should prefix the short id of the parent nodes.
00243       //
00244       // TODO: This assumes that the node width is 6, an unreasonable
00245       // assumption to make at this level.  This must be changed eventually.
00246       ShortId short_id_prefix = i << (5 * 3);
00247 
00248       for (NodeCache::iterator it = children[i]->node_cache.begin(); it != children[i]->node_cache.end(); ++it)
00249       {
00250         uint8_t which_child = it->first & 7;
00251 
00252         // Determines the parent node for this node
00253         ShortId parent_short_id = short_id_prefix + (it->first >> 3);
00254 
00255         // Puts the child into its parent's group.
00256         std::vector<Node*> &children = parent_groupings[parent_short_id];
00257         if (children.empty())
00258           children.resize(8, NULL);
00259         children[which_child] = it->second;
00260       }
00261     }
00262   }
00263 
00264   // Condenses the groups of child nodes into a parent node.
00265   for (ParentGrouping::iterator it = parent_groupings.begin(); it != parent_groupings.end(); ++it)
00266   {
00267     Node *parent_node = new Node;
00268     parent_node->copyFromChildNodes(&it->second[0]);
00269     node_cache.insert(std::make_pair(it->first, parent_node));
00270   }
00271 }
00272 
00273 // Special case: Initializes NodeFile f from f1
00274 void NodeFile::initializeRootNodeFile(const boost::filesystem::path &_path, NodeFile& child)
00275 {
00276   path = _path;  // A formality.  If pretty much has to be "f"
00277 
00278   node_cache.clear();
00279   path = _path;
00280   child_files = 0x02;
00281 
00282   NodeCache last_level = child.node_cache;
00283   bool condensing_f1 = true;
00284 
00285   while (true)
00286   {
00287     printf("Looping\n");
00288     //   1. Groups the nodes in the last level by parent.
00289 
00290     typedef std::map<ShortId, std::vector<Node*> > ParentGrouping;
00291     ParentGrouping parent_groupings;  // parent short id  ->  8 child nodes
00292 
00293     // The nodes from f1 need a "1" prefixed to their short_ids.
00294     //
00295     // TODO: This assumes that the node width is 6, an unreasonable
00296     // assumption to make at this level.  This must be changed eventually.
00297     ShortId short_id_prefix = 0;
00298     if (condensing_f1)
00299       short_id_prefix = 1 << (5 * 3);
00300 
00301     for (NodeCache::iterator it = last_level.begin(); it != last_level.end(); ++it)
00302     {
00303       uint8_t which_child = it->first & 7;
00304 
00305       // Determines the parent node for this node
00306       ShortId parent_short_id = short_id_prefix + (it->first >> 3);
00307 
00308       // Puts the child into its parent's group.
00309       std::vector<Node*> &children = parent_groupings[parent_short_id];
00310       if (children.empty())
00311         children.resize(8, NULL);
00312       children[which_child] = it->second;
00313 
00314       printf("child %o is %u of %o\n", it->first, which_child, parent_short_id);
00315     }
00316 
00317     //     2. Condenses the groups of child nodes into parent nodes.
00318 
00319     last_level.clear();
00320     for (ParentGrouping::iterator it = parent_groupings.begin(); it != parent_groupings.end(); ++it)
00321     {
00322       Node *parent_node = new Node;
00323       parent_node->copyFromChildNodes(&it->second[0]);
00324       last_level.insert(std::make_pair(it->first, parent_node));
00325     }
00326 
00327     //     3. Inserts the parent nodes into nodefile f
00328 
00329     node_cache.insert(last_level.begin(), last_level.end());
00330 
00331     condensing_f1 = false;
00332 
00333     // Checks if we've reached the root.
00334     if (last_level.size() == 1 && last_level.begin()->first == 1)
00335       break;
00336   }
00337 }
00338 
00339 
00340 // Create a new node.
00341 Node* NodeFile::createNode(const ShortId& short_id)
00342 {
00343   //printf("Create node with short_id %d in %s/%s \n", short_id, folder.string().c_str(), filename.c_str());
00344   //assert(node_cache.find(short_id) == node_cache.end());
00345 
00346   // Creates a new node object and adds it to the cache
00347   Node* node = node_allocator ? node_allocator->allocate() : new Node;
00348   node->reset();
00349   node_cache.insert(std::pair<ShortId, Node* >(short_id, node));
00350 
00351   use_count++;
00352   is_modified = true;
00353   return node;
00354 }
00355 
00356 
00357 void NodeFile::releaseNode(Node* node, const ShortId& short_id, bool modified)
00358 {
00359   assert(use_count > 0);  // Sanity check that we're not releasing more nodes than were created.
00360   //assert(node_cache.find(short_id) != node_cache.end());
00361 
00362   is_modified = is_modified || modified;
00363   use_count--;
00364 }
00365 
00366 
00367 
00368 // write node to buffer
00369 void NodeFile::serializeNode(const Node* node, const ShortId& short_id, ByteVec& buffer, unsigned& offset)
00370 {
00371   memcpy(&buffer[offset], (char *)node->point, POINT_SIZE);
00372   offset += POINT_SIZE;
00373   memcpy(&buffer[offset], (char*)node->color, COLOR_SIZE);
00374   offset += COLOR_SIZE;
00375   memcpy(&buffer[offset], (char *)&node->count, COUNT_SIZE);
00376   offset += COUNT_SIZE;
00377   memcpy(&buffer[offset], (char *)&node->children, CHILDREN_SIZE);
00378   offset += CHILDREN_SIZE;
00379   memcpy(&buffer[offset], (char *)&short_id, SHORT_ID_SIZE);
00380   offset += SHORT_ID_SIZE;
00381 }
00382 
00383 
00384 // read node from buffer
00385 void NodeFile::deserializeNode(Node* node, ShortId& short_id, const ByteVec& buffer, unsigned& offset)
00386 {
00387   memcpy((char *)node->point, (void*)&buffer[offset], POINT_SIZE);
00388   offset += POINT_SIZE;
00389   memcpy((char*)node->color, (void*)&buffer[offset], COLOR_SIZE);
00390   offset += COLOR_SIZE;
00391   memcpy((char *)&node->count, (void*)&buffer[offset], COUNT_SIZE);
00392   offset += COUNT_SIZE;
00393   memcpy((char *)&node->children, (void*)&buffer[offset], CHILDREN_SIZE);
00394   offset += CHILDREN_SIZE;
00395   memcpy((char *)&short_id, (void*)&buffer[offset], SHORT_ID_SIZE);
00396   offset += SHORT_ID_SIZE;
00397 }
00398 
00399 
00400 
00401 }


megatree_cpp
Author(s): Stuart Glaser
autogenerated on Thu Nov 28 2013 11:30:34