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
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
00024 is_modified = false;
00025 unsigned offset = 0;
00026
00027
00028 memcpy(&child_files, (void*)&buffer[offset], 1);
00029 offset += 1;
00030
00031
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
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
00054 SpinLock::ScopedLock lock(node_state_mutex);
00055 node_state = LOADED;
00056 node_state_condition.notify_all();
00057
00058
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
00068 memcpy(&buffer[offset], (char*)(&child_files), 1);
00069 offset += 1;
00070
00071
00072 for (NodeCache::const_iterator it=node_cache.begin(); it!=node_cache.end(); it++)
00073 serializeNode(it->second, it->first, buffer, offset);
00074
00075
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
00088
00089
00090
00091
00092
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
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
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
00121 void NodeFile::waitUntilLoaded()
00122 {
00123
00124
00125
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
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
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
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
00178
00179 Node* NodeFile::readNode(const ShortId& short_id)
00180 {
00181
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
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
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
00205
00206
00207
00208
00209
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
00227
00228
00229
00230
00231
00232
00233 typedef std::map<ShortId, std::vector<Node*> > ParentGrouping;
00234 ParentGrouping parent_groupings;
00235 for (int i = 0; i < 8; ++i)
00236 {
00237 if (children[i])
00238 {
00239 child_files |= (1 << i);
00240
00241
00242
00243
00244
00245
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
00253 ShortId parent_short_id = short_id_prefix + (it->first >> 3);
00254
00255
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
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
00274 void NodeFile::initializeRootNodeFile(const boost::filesystem::path &_path, NodeFile& child)
00275 {
00276 path = _path;
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
00289
00290 typedef std::map<ShortId, std::vector<Node*> > ParentGrouping;
00291 ParentGrouping parent_groupings;
00292
00293
00294
00295
00296
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
00306 ShortId parent_short_id = short_id_prefix + (it->first >> 3);
00307
00308
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
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
00328
00329 node_cache.insert(last_level.begin(), last_level.end());
00330
00331 condensing_f1 = false;
00332
00333
00334 if (last_level.size() == 1 && last_level.begin()->first == 1)
00335 break;
00336 }
00337 }
00338
00339
00340
00341 Node* NodeFile::createNode(const ShortId& short_id)
00342 {
00343
00344
00345
00346
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);
00360
00361
00362 is_modified = is_modified || modified;
00363 use_count--;
00364 }
00365
00366
00367
00368
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
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 }