1 /* ------------------------------------------------------------------ 2 * Copyright (C) 1998-2009 PacketVideo 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 13 * express or implied. 14 * See the License for the specific language governing permissions 15 * and limitations under the License. 16 * ------------------------------------------------------------------- 17 */ 18 // -*- c++ -*- 19 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 20 21 // O S C L _ T A G T R E E 22 23 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 24 25 /*! \addtogroup osclbase OSCL Base 26 * 27 * @{ 28 */ 29 30 31 /*! \file oscl_tagtree.h 32 \brief The file oscl_tagtree.h ... 33 */ 34 35 #ifndef OSCL_TAGTREE_H_INCLUDED 36 #define OSCL_TAGTREE_H_INCLUDED 37 38 #ifndef OSCL_BASE_H_INCLUDED 39 #include "oscl_base.h" 40 #endif 41 42 #ifndef OSCL_MAP_H_INCLUDED 43 #include "oscl_map.h" 44 #endif 45 46 #ifndef OSCL_VECTOR_H_INCLUDED 47 #include "oscl_vector.h" 48 #endif 49 50 #ifndef OSCL_STDSTRING_H_INCLUDED 51 #include "oscl_stdstring.h" 52 #endif 53 54 #define OSCL_DISABLE_WARNING_TRUNCATE_DEBUG_MESSAGE 55 #include "osclconfig_compiler_warnings.h" 56 57 58 struct Oscl_Tag_Base 59 { 60 typedef char tag_base_unit; 61 typedef tag_base_unit* tag_base_type; 62 typedef uint32 size_type; 63 64 bool operator()(const tag_base_type& x, const tag_base_type& y) const 65 { 66 return tag_cmp(x, y) < 0; 67 } 68 size_type tag_len(const tag_base_type& t) const 69 { 70 return (size_type)oscl_strlen(t); 71 } 72 tag_base_type tag_copy(tag_base_type& dest, const tag_base_type& src) const 73 { 74 return oscl_strncpy(dest, src, oscl_strlen(src) + 1); 75 } 76 int32 tag_cmp(const tag_base_type& x, const tag_base_type& y) const 77 { 78 return oscl_strncmp(x, y, oscl_strlen(x) + 1); 79 } 80 OSCL_IMPORT_REF tag_base_type tag_ancestor(tag_base_type& dest, const tag_base_type& src) const; 81 OSCL_IMPORT_REF size_type tag_depth(const tag_base_type& t) const; 82 }; 83 84 template <class Alloc> 85 struct Oscl_Tag : public Oscl_Tag_Base 86 { 87 88 Oscl_Tag(const Oscl_Tag<Alloc>& t) 89 { 90 tag = tagAllocator.ALLOCATE(tag_len(t.tag) + 1); 91 tag_copy(tag, t.tag); 92 } 93 94 Oscl_Tag(const tag_base_type& t) 95 { 96 tag = tagAllocator.ALLOCATE(tag_len(t) + 1); 97 tag_copy(tag, t); 98 } 99 100 ~Oscl_Tag() 101 { 102 tagAllocator.deallocate(tag); 103 } 104 105 bool operator<(const Oscl_Tag<Alloc>& x) const 106 { 107 return (tag_cmp(tag, x.tag) < 0); 108 } 109 110 Oscl_TAlloc<tag_base_unit, Alloc> tagAllocator; 111 tag_base_type tag; 112 }; 113 114 /** 115 * Oscl_TagTree Class. 116 */ 117 template <class T, class Alloc> 118 class Oscl_TagTree 119 { 120 121 public: 122 typedef Oscl_Tag<Alloc> tag_type; 123 typedef typename tag_type::tag_base_type tag_base_type; 124 125 126 struct Node 127 { 128 typedef Oscl_Vector<Node*, Alloc> children_type; 129 Node() {} 130 131 tag_type tag; 132 T value; 133 Node* parent; 134 children_type children; 135 136 void sort_children() 137 { 138 bool tryagain; 139 if (children.empty()) return; 140 do 141 { 142 tryagain = 0; 143 for (typename children_type::iterator it = children.begin(); it != (children.end() - 1); it++) 144 { 145 typename children_type::iterator it2 = it + 1; 146 if ((*it2)->tag < (*it)->tag) 147 { 148 // swap em 149 Node* tmp = *it; 150 *it = *it2; 151 *it2 = tmp; 152 tryagain = 1; 153 } 154 } 155 } 156 while (tryagain); 157 } 158 159 typename tag_type::size_type depth() 160 { 161 return tag.tag_depth(tag.tag); 162 } 163 }; 164 165 typedef Oscl_Vector<Node*, Alloc> children_type; 166 167 typedef Node node_type; 168 typedef node_type* node_ptr; 169 typedef Oscl_Map<const tag_base_type, node_ptr, Alloc , Oscl_Tag_Base> map_type; 170 typedef typename map_type::size_type size_type; 171 typedef typename map_type::value_type value_type; 172 173 struct iterator 174 { 175 typedef node_type& reference; 176 typedef node_type* pointer; 177 typedef typename map_type::iterator mapiter; 178 typedef iterator self; 179 180 iterator() {} 181 iterator(mapiter x) 182 { 183 mapit = x; 184 } 185 iterator(const iterator& it) 186 { 187 mapit = it.mapit; 188 } 189 190 reference operator*() const 191 { 192 return *((*mapit).second); 193 } 194 pointer operator->() const 195 { 196 return &(operator*()); 197 } 198 199 bool operator==(const self& x) 200 { 201 return mapit == x.mapit; 202 } 203 204 bool operator!=(const self& x) 205 { 206 return mapit != x.mapit; 207 } 208 209 self& operator++() 210 { 211 mapit++; 212 return *this; 213 } 214 215 self operator++(int) 216 { 217 self tmp = *this; 218 ++*this; 219 return tmp; 220 } 221 222 self& operator--() 223 { 224 mapit--; 225 return *this; 226 } 227 228 self operator--(int) 229 { 230 self tmp = *this; 231 --*this; 232 return tmp; 233 } 234 235 mapiter mapit; 236 }; 237 238 struct const_iterator 239 { 240 typedef const node_type& reference; 241 typedef const node_type* pointer; 242 typedef typename map_type::const_iterator mapiter; 243 typedef const_iterator self; 244 245 const_iterator() {} 246 const_iterator(mapiter x) 247 { 248 mapit = x; 249 } 250 const_iterator(const const_iterator& it) 251 { 252 mapit = it.mapit; 253 } 254 255 reference operator*() const 256 { 257 return *((*mapit).second); 258 } 259 pointer operator->() const 260 { 261 return &(operator*()); 262 } 263 264 bool operator==(const self& x) 265 { 266 return mapit == x.mapit; 267 } 268 269 bool operator!=(const self& x) 270 { 271 return mapit != x.mapit; 272 } 273 274 self& operator++() 275 { 276 mapit++; 277 return *this; 278 } 279 280 self operator++(int) 281 { 282 self tmp = *this; 283 ++*this; 284 return tmp; 285 } 286 287 self& operator--() 288 { 289 mapit--; 290 return *this; 291 } 292 293 self operator--(int) 294 { 295 self tmp = *this; 296 --*this; 297 return tmp; 298 } 299 300 mapiter mapit; 301 }; 302 303 public: 304 305 /** 306 * Creates a tag tree with only a root node with tag "" 307 */ 308 Oscl_TagTree(size_type max_depth = 0) : maxDepth(max_depth) 309 { 310 // insert the root node 311 node_ptr node = create_node((char*)"", T()); 312 node->parent = NULL; 313 typename map_type::value_type pair(node->tag.tag, node); 314 nodeMap.insert(pair); 315 } 316 /** 317 * Copy constructor 318 */ 319 Oscl_TagTree(const Oscl_TagTree<T, Alloc>& x) : maxDepth(x.maxDepth) 320 { 321 for (const_iterator it = x.begin(); it != x.end(); it++) 322 { 323 insert(it->tag.tag, it->value); 324 } 325 } 326 /** 327 * Assignment operator 328 */ 329 Oscl_TagTree<T, Alloc>& operator=(const Oscl_TagTree<T, Alloc>& x) 330 { 331 maxDepth = x.maxDepth; 332 // clear the current tree 333 clear(); 334 // insert nodes from assigned tree 335 for (const_iterator it = x.begin(); it != x.end(); it++) 336 { 337 insert(it->tag.tag, it->value); 338 } 339 return *this; 340 } 341 /** 342 * Destructor 343 */ 344 ~Oscl_TagTree() 345 { 346 // destroy all nodes stored in the map 347 for (iterator it = begin(); it != end(); it++) 348 { 349 destroy_node(&(*it)); 350 } 351 } 352 /** 353 * Returns an iterator pointing to the first node in the tree. 354 */ 355 iterator begin() 356 { 357 return iterator(nodeMap.begin()); 358 } 359 /** 360 * Returns an iterator pointing to the first node in the tree. 361 */ 362 const_iterator begin() const 363 { 364 return const_iterator(nodeMap.begin()); 365 } 366 /** 367 * Returns an iterator pointing to the end of the tree. 368 */ 369 iterator end() 370 { 371 return iterator(nodeMap.end()); 372 } 373 /** 374 * Returns a const iterator pointing to the end of the tree. 375 */ 376 const_iterator end() const 377 { 378 return const_iterator(nodeMap.end()); 379 } 380 /** 381 * Returns true if tree size is 0 382 */ 383 bool empty() const 384 { 385 return nodeMap.empty(); 386 } 387 /** 388 * Returns the number of nodes stored in the tree 389 */ 390 size_type size() const 391 { 392 return nodeMap.size(); 393 } 394 /** 395 * Returns a reference to the object that is associated with a particular tag. 396 * If the map does not already contain such an object, operator[] inserts the default object T(). 397 */ 398 T& operator[](const tag_base_type& t) 399 { 400 return (*((insert(t, T())).first)).value; 401 } 402 403 typedef Oscl_Pair<iterator, bool> pair_iterator_bool; 404 /** 405 * Inserts x into the tree and associates it with tag t. If the tag already exists 406 * x will not be inserted, and an iterator pointing to the existing node with tag t 407 * is returned. 408 * 409 * @param t tag to use 410 * @param x element to insert 411 * 412 * @return Returns a pair of parameters, iterator and bool. The 413 * iterator points to the inserted node containing x. If 414 * the tag t already existed, then the iterator points to 415 * the node associated with tag t. The bool is true if x 416 * was inserted and false if it was not inserted due to an 417 * existing node with tag t. 418 */ 419 pair_iterator_bool insert(const tag_base_type& t, const T& x) 420 { 421 422 tag_type currenttag(t); 423 pair_iterator_bool result(end(), false); 424 node_ptr child = NULL; 425 size_type ii; 426 size_type maxloops; 427 428 // if it exceeds the max depth, then truncate it to the max depth size 429 if (maxDepth > 0 && currenttag.tag_depth(currenttag.tag) > maxDepth) 430 { 431 maxloops = currenttag.tag_depth(currenttag.tag) - maxDepth; 432 for (ii = 0; ii < maxloops; ii++) 433 { 434 currenttag.tag_ancestor(currenttag.tag, currenttag.tag); 435 } 436 } 437 438 maxloops = currenttag.tag_depth(currenttag.tag) + 1; 439 for (ii = 0; ii < maxloops; ii++) 440 { 441 // check if tag already exists; if so then no need to continue creating nodes 442 typename map_type::iterator mit = nodeMap.find(currenttag.tag); 443 if (mit != nodeMap.end()) 444 { 445 // set child parent relationship 446 if (child) 447 { 448 child->parent = (*mit).second; 449 child->parent->children.push_back(child); 450 } 451 // if this is the first pass node, then set it for the return value 452 if (result.first == end()) result.first = iterator(mit); 453 break; 454 } 455 // otherwise create a new node, insert it into map, and set parent/child relationship 456 else 457 { 458 // insert the new node 459 // first pass sets the node to the given value, all others are default value 460 node_ptr node; 461 if (result.first == end()) 462 { 463 node = create_node(currenttag.tag, x); 464 } 465 else 466 { 467 node = create_node(currenttag.tag, T()); 468 } 469 470 typename map_type::value_type pair(node->tag.tag, node); 471 typename map_type::pair_iterator_bool mapresult = (nodeMap.insert(pair)); 472 473 // if this is the first pass node to insert, save it for the return value 474 if (result.first == end()) 475 { 476 result.first = iterator(mapresult.first); 477 result.second = mapresult.second; 478 } 479 // set child/parent relationship 480 if (child) 481 { 482 child->parent = (*(mapresult.first)).second; 483 child->parent->children.push_back(child); 484 } 485 child = node; 486 } 487 488 currenttag.tag_ancestor(currenttag.tag, currenttag.tag); 489 } 490 491 return result; 492 } 493 /** 494 * Erases the element pointed to by the iterator. If the 495 * node has children, then the node will not be erased from 496 * the tree. It will be replaced with the default node 497 * value. 498 * 499 * @param position Iterator pointing to the node to be erased 500 */ 501 void erase(iterator position) 502 { 503 // if node has children, then replace it with default node value 504 if (!(position->children.empty())) 505 { 506 position->value = T(); 507 return; 508 } 509 510 // destroy the node since only the pointer is stored 511 destroy_node(&(*position)); 512 nodeMap.erase(position.mapit); 513 } 514 /** 515 * Erases the node with tag x. If the node has children, 516 * then the node will not be erased from the tree. It will 517 * be replaced with the default node value 518 * 519 * @param x Tag of node to erase 520 * 521 * @return Returns the number of nodes erased. Since one-to-one 522 * mapping between nodes and tags, this will be either 0 or 1 523 */ 524 size_type erase(const tag_base_type& x) 525 { 526 iterator it = find(x); 527 if (it != end()) 528 { 529 erase(it); 530 return 1; 531 } 532 return 0; 533 } 534 /** 535 * Erases the entire tag tree. 536 */ 537 void clear() 538 { 539 // destroy all nodes stored in the map 540 for (iterator it = begin(); it != end(); it++) 541 { 542 destroy_node(&(*it)); 543 } 544 // clear the map 545 nodeMap.clear(); 546 } 547 /** 548 * Finds an element whose key is x 549 * 550 * @return returns an iterator to the element with key x. If no element is found, returns end() 551 */ 552 iterator find(const tag_base_type& x) 553 { 554 return iterator(nodeMap.find(x)); 555 } 556 /** 557 * Finds an element whose key is x 558 */ 559 //Removed this version due to ADS 1.2 compile problem 560 // const_iterator find(const tag_base_type& x) const { return const_iterator(nodeMap.find(x)); } 561 /** 562 * Returns the number of elements with key x. This can only be 0 or 1.. 563 */ 564 size_type count(const tag_base_type& x) const 565 { 566 return nodeMap.count(x); 567 } 568 569 private: 570 node_ptr create_node(const tag_base_type& t, const T& x) 571 { 572 node_ptr n = nodeAllocator.ALLOCATE(1); 573 new(&n->tag) tag_type(t); 574 new(&n->value) T(x); 575 new(&n->children) Oscl_Vector<Node*, Alloc>(); 576 return n; 577 } 578 579 void destroy_node(node_ptr x) 580 { 581 x->tag.OSCL_TEMPLATED_DESTRUCTOR_CALL(tag_type, Oscl_Tag); 582 x->value.T::~T(); 583 x->children.OSCL_TEMPLATED_DESTRUCTOR_CALL(children_type, Oscl_Vector); 584 nodeAllocator.deallocate(x); 585 } 586 587 map_type nodeMap; 588 Oscl_TAlloc<node_type, Alloc> nodeAllocator; 589 size_type maxDepth; 590 }; 591 592 /*! @} */ 593 594 595 #endif 596 597