1 // (C) Copyright Joel de Guzman 2003. 2 // Distributed under the Boost Software License, Version 1.0. (See 3 // accompanying file LICENSE_1_0.txt or copy at 4 // http://www.boost.org/LICENSE_1_0.txt) 5 6 #ifndef INDEXING_SUITE_DETAIL_JDG20036_HPP 7 # define INDEXING_SUITE_DETAIL_JDG20036_HPP 8 9 # include <boost/python/extract.hpp> 10 # include <boost/scoped_ptr.hpp> 11 # include <boost/get_pointer.hpp> 12 # include <boost/detail/binary_search.hpp> 13 # include <boost/numeric/conversion/cast.hpp> 14 # include <boost/python/detail/type_traits.hpp> 15 # include <vector> 16 # include <map> 17 #include <iostream> 18 19 namespace boost { namespace python { namespace detail { 20 21 #if defined(NDEBUG) 22 #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT 23 #else 24 #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT check_invariant() 25 #endif 26 27 template <class Proxy> 28 struct compare_proxy_index 29 { 30 // This functor compares a proxy and an index. 31 // This is used by proxy_group::first_proxy to 32 // get first proxy with index i. 33 34 template <class Index> operator ()boost::python::detail::compare_proxy_index35 bool operator()(PyObject* prox, Index i) const 36 { 37 typedef typename Proxy::policies_type policies_type; 38 Proxy& proxy = extract<Proxy&>(prox)(); 39 return policies_type:: 40 compare_index(proxy.get_container(), proxy.get_index(), i); 41 } 42 }; 43 44 // The proxy_group class holds a vector of container element 45 // proxies. First, what is a container element proxy? A container 46 // element proxy acts like a smart pointer holding a reference to 47 // a container and an index (see container_element, for details). 48 // 49 // The proxies are held in a vector always sorted by its index. 50 // Various functions manage the addition, removal and searching 51 // of proxies from the vector. 52 // 53 template <class Proxy> 54 class proxy_group 55 { 56 public: 57 58 typedef typename std::vector<PyObject*>::const_iterator const_iterator; 59 typedef typename std::vector<PyObject*>::iterator iterator; 60 typedef typename Proxy::index_type index_type; 61 typedef typename Proxy::policies_type policies_type; 62 63 iterator first_proxy(index_type i)64 first_proxy(index_type i) 65 { 66 // Return the first proxy with index <= i 67 return boost::detail::lower_bound( 68 proxies.begin(), proxies.end(), 69 i, compare_proxy_index<Proxy>()); 70 } 71 72 void remove(Proxy & proxy)73 remove(Proxy& proxy) 74 { 75 // Remove a proxy 76 for (iterator iter = first_proxy(proxy.get_index()); 77 iter != proxies.end(); ++iter) 78 { 79 if (&extract<Proxy&>(*iter)() == &proxy) 80 { 81 proxies.erase(iter); 82 break; 83 } 84 } 85 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 86 } 87 88 void add(PyObject * prox)89 add(PyObject* prox) 90 { 91 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 92 // Add a proxy 93 proxies.insert( 94 first_proxy(extract<Proxy&>(prox)().get_index()), prox); 95 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 96 } 97 98 void erase(index_type i,mpl::false_)99 erase(index_type i, mpl::false_) 100 { 101 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 102 // Erase the proxy with index i 103 replace(i, i+1, 0); 104 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 105 } 106 107 void erase(index_type i,mpl::true_)108 erase(index_type i, mpl::true_) 109 { 110 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 111 // Erase the proxy with index i 112 113 iterator iter = first_proxy(i); 114 extract<Proxy&> p(*iter); 115 116 if (iter != proxies.end() && p().get_index() == i) 117 { 118 extract<Proxy&> p(*iter); 119 p().detach(); 120 proxies.erase(iter); 121 } 122 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 123 } 124 125 void erase(index_type from,index_type to)126 erase(index_type from, index_type to) 127 { 128 // note: this cannot be called when container is not sliceable 129 130 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 131 // Erase all proxies with indexes from..to 132 replace(from, to, 0); 133 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 134 } 135 136 void replace(index_type from,index_type to,typename std::vector<PyObject * >::size_type len)137 replace( 138 index_type from, 139 index_type to, 140 typename std::vector<PyObject*>::size_type len) 141 { 142 // note: this cannot be called when container is not sliceable 143 144 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 145 // Erase all proxies with indexes from..to. 146 // Adjust the displaced indexes such that the 147 // final effect is that we have inserted *len* 148 // number of proxies in the vacated region. This 149 // procedure involves adjusting the indexes of 150 // the proxies. 151 152 iterator left = first_proxy(from); 153 iterator right = proxies.end(); // we'll adjust this later 154 155 for (iterator iter = left; iter != right; ++iter) 156 { 157 if (extract<Proxy&>(*iter)().get_index() > to) 158 { 159 right = iter; // adjust right 160 break; 161 } 162 extract<Proxy&> p(*iter); 163 p().detach(); 164 } 165 166 typename std::vector<PyObject*>::size_type 167 offset = left-proxies.begin(); 168 proxies.erase(left, right); 169 right = proxies.begin()+offset; 170 171 while (right != proxies.end()) 172 { 173 typedef typename Proxy::container_type::difference_type difference_type; 174 extract<Proxy&> p(*right); 175 p().set_index( 176 extract<Proxy&>(*right)().get_index() 177 - (difference_type(to) - from - len) 178 ); 179 180 ++right; 181 } 182 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 183 } 184 185 PyObject* find(index_type i)186 find(index_type i) 187 { 188 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 189 // Find the proxy with *exact* index i. 190 // Return 0 (null) if no proxy with the 191 // given index is found. 192 iterator iter = first_proxy(i); 193 if (iter != proxies.end() 194 && extract<Proxy&>(*iter)().get_index() == i) 195 { 196 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 197 return *iter; 198 } 199 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 200 return 0; 201 } 202 203 typename std::vector<PyObject*>::size_type size() const204 size() const 205 { 206 BOOST_PYTHON_INDEXING_CHECK_INVARIANT; 207 // How many proxies are there so far? 208 return proxies.size(); 209 } 210 211 private: 212 213 #if !defined(NDEBUG) 214 void check_invariant() const215 check_invariant() const 216 { 217 for (const_iterator i = proxies.begin(); i != proxies.end(); ++i) 218 { 219 if ((*i)->ob_refcnt <= 0) 220 { 221 PyErr_SetString(PyExc_RuntimeError, 222 "Invariant: Proxy vector in an inconsistent state"); 223 throw_error_already_set(); 224 } 225 226 if (i+1 != proxies.end()) 227 { 228 if (extract<Proxy&>(*(i+1))().get_index() == 229 extract<Proxy&>(*(i))().get_index()) 230 { 231 PyErr_SetString(PyExc_RuntimeError, 232 "Invariant: Proxy vector in an inconsistent state (duplicate proxy)"); 233 throw_error_already_set(); 234 } 235 } 236 } 237 } 238 #endif 239 240 std::vector<PyObject*> proxies; 241 }; 242 243 // proxy_links holds a map of Container pointers (keys) 244 // with proxy_group(s) (data). Various functions manage 245 // the addition, removal and searching of proxies from 246 // the map. 247 // 248 template <class Proxy, class Container> 249 class proxy_links 250 { 251 public: 252 253 typedef std::map<Container*, proxy_group<Proxy> > links_t; 254 typedef typename Proxy::index_type index_type; 255 256 void remove(Proxy & proxy)257 remove(Proxy& proxy) 258 { 259 // Remove a proxy. 260 typename links_t::iterator r = links.find(&proxy.get_container()); 261 if (r != links.end()) 262 { 263 r->second.remove(proxy); 264 if (r->second.size() == 0) 265 links.erase(r); 266 } 267 } 268 269 void add(PyObject * prox,Container & container)270 add(PyObject* prox, Container& container) 271 { 272 // Add a proxy 273 links[&container].add(prox); 274 } 275 276 template <class NoSlice> erase(Container & container,index_type i,NoSlice no_slice)277 void erase(Container& container, index_type i, NoSlice no_slice) 278 { 279 // Erase the proxy with index i 280 typename links_t::iterator r = links.find(&container); 281 if (r != links.end()) 282 { 283 r->second.erase(i, no_slice); 284 if (r->second.size() == 0) 285 links.erase(r); 286 } 287 } 288 289 void erase(Container & container,index_type from,index_type to)290 erase(Container& container, index_type from, index_type to) 291 { 292 // Erase all proxies with indexes from..to 293 typename links_t::iterator r = links.find(&container); 294 if (r != links.end()) 295 { 296 r->second.erase(from, to); 297 if (r->second.size() == 0) 298 links.erase(r); 299 } 300 } 301 302 void replace(Container & container,index_type from,index_type to,index_type len)303 replace( 304 Container& container, 305 index_type from, index_type to, index_type len) 306 { 307 // Erase all proxies with indexes from..to. 308 // Adjust the displaced indexes such that the 309 // final effect is that we have inserted *len* 310 // number of proxies in the vacated region. This 311 // procedure involves adjusting the indexes of 312 // the proxies. 313 314 typename links_t::iterator r = links.find(&container); 315 if (r != links.end()) 316 { 317 r->second.replace(from, to, len); 318 if (r->second.size() == 0) 319 links.erase(r); 320 } 321 } 322 323 PyObject* find(Container & container,index_type i)324 find(Container& container, index_type i) 325 { 326 // Find the proxy with *exact* index i. 327 // Return 0 (null) if no proxy with the given 328 // index is found. 329 typename links_t::iterator r = links.find(&container); 330 if (r != links.end()) 331 return r->second.find(i); 332 return 0; 333 } 334 335 private: 336 337 links_t links; 338 }; 339 340 // container_element is our container proxy class. 341 // This class acts like a smart pointer to a container 342 // element. The class holds an index and a reference to 343 // a container. Dereferencing the smart pointer will 344 // retrieve the nth (index) element from the container. 345 // 346 // A container_element can also be detached from the 347 // container. In such a detached state, the container_element 348 // holds a copy of the nth (index) element, which it 349 // returns when dereferenced. 350 // 351 template <class Container, class Index, class Policies> 352 class container_element 353 { 354 public: 355 356 typedef Index index_type; 357 typedef Container container_type; 358 typedef typename Policies::data_type element_type; 359 typedef Policies policies_type; 360 typedef container_element<Container, Index, Policies> self_t; 361 typedef proxy_group<self_t> links_type; 362 container_element(object container,Index index)363 container_element(object container, Index index) 364 : ptr() 365 , container(container) 366 , index(index) 367 { 368 } 369 container_element(container_element const & ce)370 container_element(container_element const& ce) 371 : ptr(ce.ptr.get() == 0 ? 0 : new element_type(*ce.ptr.get())) 372 , container(ce.container) 373 , index(ce.index) 374 { 375 } 376 ~container_element()377 ~container_element() 378 { 379 if (!is_detached()) 380 get_links().remove(*this); 381 } 382 operator *() const383 element_type& operator*() const 384 { 385 if (is_detached()) 386 return *get_pointer(ptr); 387 return Policies::get_item(get_container(), index); 388 } 389 get() const390 element_type* get() const 391 { 392 if (is_detached()) 393 return get_pointer(ptr); 394 return &Policies::get_item(get_container(), index); 395 } 396 397 void detach()398 detach() 399 { 400 if (!is_detached()) 401 { 402 ptr.reset( 403 new element_type( 404 Policies::get_item(get_container(), index))); 405 container = object(); // free container. reset it to None 406 } 407 } 408 409 bool is_detached() const410 is_detached() const 411 { 412 return get_pointer(ptr) != 0; 413 } 414 415 Container& get_container() const416 get_container() const 417 { 418 return extract<Container&>(container)(); 419 } 420 421 Index get_index() const422 get_index() const 423 { 424 return index; 425 } 426 427 void set_index(Index i)428 set_index(Index i) 429 { 430 index = i; 431 } 432 433 static proxy_links<self_t, Container>& get_links()434 get_links() 435 { 436 // All container_element(s) maintain links to 437 // its container in a global map (see proxy_links). 438 // This global "links" map is a singleton. 439 440 static proxy_links<self_t, Container> links; 441 return links; // singleton 442 } 443 444 private: 445 446 container_element& operator=(container_element const& ce); 447 448 scoped_ptr<element_type> ptr; 449 object container; 450 Index index; 451 }; 452 453 template < 454 class Container 455 , class DerivedPolicies 456 , class ContainerElement 457 , class Index 458 > 459 struct no_proxy_helper 460 { 461 static void register_container_elementboost::python::detail::no_proxy_helper462 register_container_element() 463 { 464 } 465 466 template <class DataType> 467 static object base_get_item_helperboost::python::detail::no_proxy_helper468 base_get_item_helper(DataType const& p, detail::true_) 469 { 470 return object(ptr(p)); 471 } 472 473 template <class DataType> 474 static object base_get_item_helperboost::python::detail::no_proxy_helper475 base_get_item_helper(DataType const& x, detail::false_) 476 { 477 return object(x); 478 } 479 480 static object base_get_item_boost::python::detail::no_proxy_helper481 base_get_item_(back_reference<Container&> const& container, PyObject* i) 482 { 483 return base_get_item_helper( 484 DerivedPolicies::get_item( 485 container.get(), DerivedPolicies:: 486 convert_index(container.get(), i)) 487 , is_pointer<BOOST_DEDUCED_TYPENAME Container::value_type>() 488 ); 489 } 490 491 static void base_replace_indexesboost::python::detail::no_proxy_helper492 base_replace_indexes( 493 Container& /*container*/, Index /*from*/, 494 Index /*to*/, Index /*n*/) 495 { 496 } 497 498 template <class NoSlice> 499 static void base_erase_indexboost::python::detail::no_proxy_helper500 base_erase_index( 501 Container& /*container*/, Index /*i*/, NoSlice /*no_slice*/) 502 { 503 } 504 505 static void base_erase_indexesboost::python::detail::no_proxy_helper506 base_erase_indexes(Container& /*container*/, Index /*from*/, Index /*to*/) 507 { 508 } 509 }; 510 511 template < 512 class Container 513 , class DerivedPolicies 514 , class ContainerElement 515 , class Index 516 > 517 struct proxy_helper 518 { 519 static void register_container_elementboost::python::detail::proxy_helper520 register_container_element() 521 { 522 register_ptr_to_python<ContainerElement>(); 523 } 524 525 static object base_get_item_boost::python::detail::proxy_helper526 base_get_item_(back_reference<Container&> const& container, PyObject* i) 527 { 528 // Proxy 529 Index idx = DerivedPolicies::convert_index(container.get(), i); 530 531 if (PyObject* shared = 532 ContainerElement::get_links().find(container.get(), idx)) 533 { 534 handle<> h(python::borrowed(shared)); 535 return object(h); 536 } 537 else 538 { 539 object prox(ContainerElement(container.source(), idx)); 540 ContainerElement:: 541 get_links().add(prox.ptr(), container.get()); 542 return prox; 543 } 544 } 545 546 static void base_replace_indexesboost::python::detail::proxy_helper547 base_replace_indexes( 548 Container& container, Index from, 549 Index to, Index n) 550 { 551 ContainerElement::get_links().replace(container, from, to, n); 552 } 553 554 template <class NoSlice> 555 static void base_erase_indexboost::python::detail::proxy_helper556 base_erase_index( 557 Container& container, Index i, NoSlice no_slice) 558 { 559 ContainerElement::get_links().erase(container, i, no_slice); 560 } 561 562 static void base_erase_indexesboost::python::detail::proxy_helper563 base_erase_indexes( 564 Container& container, Index from, Index to) 565 { 566 ContainerElement::get_links().erase(container, from, to); 567 } 568 }; 569 570 template < 571 class Container 572 , class DerivedPolicies 573 , class ProxyHandler 574 , class Data 575 , class Index 576 > 577 struct slice_helper 578 { 579 static object base_get_sliceboost::python::detail::slice_helper580 base_get_slice(Container& container, PySliceObject* slice) 581 { 582 Index from, to; 583 base_get_slice_data(container, slice, from, to); 584 return DerivedPolicies::get_slice(container, from, to); 585 } 586 587 static void base_get_slice_databoost::python::detail::slice_helper588 base_get_slice_data( 589 Container& container, PySliceObject* slice, Index& from_, Index& to_) 590 { 591 if (Py_None != slice->step) { 592 PyErr_SetString( PyExc_IndexError, "slice step size not supported."); 593 throw_error_already_set(); 594 } 595 596 Index min_index = DerivedPolicies::get_min_index(container); 597 Index max_index = DerivedPolicies::get_max_index(container); 598 599 if (Py_None == slice->start) { 600 from_ = min_index; 601 } 602 else { 603 long from = extract<long>( slice->start); 604 if (from < 0) // Negative slice index 605 from += max_index; 606 if (from < 0) // Clip lower bounds to zero 607 from = 0; 608 from_ = boost::numeric_cast<Index>(from); 609 if (from_ > max_index) // Clip upper bounds to max_index. 610 from_ = max_index; 611 } 612 613 if (Py_None == slice->stop) { 614 to_ = max_index; 615 } 616 else { 617 long to = extract<long>( slice->stop); 618 if (to < 0) 619 to += max_index; 620 if (to < 0) 621 to = 0; 622 to_ = boost::numeric_cast<Index>(to); 623 if (to_ > max_index) 624 to_ = max_index; 625 } 626 } 627 628 static void base_set_sliceboost::python::detail::slice_helper629 base_set_slice(Container& container, PySliceObject* slice, PyObject* v) 630 { 631 Index from, to; 632 base_get_slice_data(container, slice, from, to); 633 634 extract<Data&> elem(v); 635 // try if elem is an exact Data 636 if (elem.check()) 637 { 638 ProxyHandler::base_replace_indexes(container, from, to, 1); 639 DerivedPolicies::set_slice(container, from, to, elem()); 640 } 641 else 642 { 643 // try to convert elem to Data 644 extract<Data> elem(v); 645 if (elem.check()) 646 { 647 ProxyHandler::base_replace_indexes(container, from, to, 1); 648 DerivedPolicies::set_slice(container, from, to, elem()); 649 } 650 else 651 { 652 // Otherwise, it must be a list or some container 653 handle<> l_(python::borrowed(v)); 654 object l(l_); 655 656 std::vector<Data> temp; 657 for (int i = 0; i < l.attr("__len__")(); i++) 658 { 659 object elem(l[i]); 660 extract<Data const&> x(elem); 661 // try if elem is an exact Data type 662 if (x.check()) 663 { 664 temp.push_back(x()); 665 } 666 else 667 { 668 // try to convert elem to Data type 669 extract<Data> x(elem); 670 if (x.check()) 671 { 672 temp.push_back(x()); 673 } 674 else 675 { 676 PyErr_SetString(PyExc_TypeError, 677 "Invalid sequence element"); 678 throw_error_already_set(); 679 } 680 } 681 } 682 683 ProxyHandler::base_replace_indexes(container, from, to, 684 temp.end()-temp.begin()); 685 DerivedPolicies::set_slice(container, from, to, 686 temp.begin(), temp.end()); 687 } 688 } 689 } 690 691 static void base_delete_sliceboost::python::detail::slice_helper692 base_delete_slice(Container& container, PySliceObject* slice) 693 { 694 Index from, to; 695 base_get_slice_data(container, slice, from, to); 696 ProxyHandler::base_erase_indexes(container, from, to); 697 DerivedPolicies::delete_slice(container, from, to); 698 } 699 }; 700 701 template < 702 class Container 703 , class DerivedPolicies 704 , class ProxyHandler 705 , class Data 706 , class Index 707 > 708 struct no_slice_helper 709 { 710 static void slicing_not_suportedboost::python::detail::no_slice_helper711 slicing_not_suported() 712 { 713 PyErr_SetString(PyExc_RuntimeError, "Slicing not supported"); 714 throw_error_already_set(); 715 } 716 717 static object base_get_sliceboost::python::detail::no_slice_helper718 base_get_slice(Container& /*container*/, PySliceObject* /*slice*/) 719 { 720 slicing_not_suported(); 721 return object(); 722 } 723 724 static void base_set_sliceboost::python::detail::no_slice_helper725 base_set_slice(Container& /*container*/, PySliceObject* /*slice*/, PyObject* /*v*/) 726 { 727 slicing_not_suported(); 728 } 729 730 static void base_delete_sliceboost::python::detail::no_slice_helper731 base_delete_slice(Container& /*container*/, PySliceObject* /*slice*/) 732 { 733 slicing_not_suported(); 734 } 735 }; 736 737 #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP 738 }} // namespace python::detail 739 #endif 740 741 template <class Container, class Index, class Policies> 742 inline typename Policies::data_type* get_pointer(python::detail::container_element<Container,Index,Policies> const & p)743 get_pointer( 744 python::detail::container_element<Container, Index, Policies> const& p) 745 { 746 // Get the pointer of a container_element smart pointer 747 return p.get(); 748 } 749 750 #ifndef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP 751 // Don't hide these other get_pointer overloads 752 using boost::python::get_pointer; 753 using boost::get_pointer; 754 }} // namespace python::detail 755 #endif 756 757 } // namespace boost 758 759 #endif // INDEXING_SUITE_DETAIL_JDG20036_HPP 760