1// Safe iterator implementation -*- C++ -*- 2 3// Copyright (C) 2003, 2004, 2005 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 2, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// You should have received a copy of the GNU General Public License along 18// with this library; see the file COPYING. If not, write to the Free 19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20// USA. 21 22// As a special exception, you may use this file as part of a free software 23// library without restriction. Specifically, if other files instantiate 24// templates or use macros or inline functions from this file, or you compile 25// this file and link it with other files to produce an executable, this 26// file does not by itself cause the resulting executable to be covered by 27// the GNU General Public License. This exception does not however 28// invalidate any other reasons why the executable file might be covered by 29// the GNU General Public License. 30 31#ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H 32#define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1 33 34#include <debug/debug.h> 35#include <debug/macros.h> 36#include <debug/functions.h> 37#include <debug/formatter.h> 38#include <debug/safe_base.h> 39#include <bits/stl_pair.h> 40#include <bits/cpp_type_traits.h> 41 42namespace __gnu_debug 43{ 44 using std::iterator_traits; 45 using std::pair; 46 47 /** Iterators that derive from _Safe_iterator_base but that aren't 48 * _Safe_iterators can be determined singular or non-singular via 49 * _Safe_iterator_base. 50 */ 51 inline bool 52 __check_singular_aux(const _Safe_iterator_base* __x) 53 { return __x->_M_singular(); } 54 55 /** \brief Safe iterator wrapper. 56 * 57 * The class template %_Safe_iterator is a wrapper around an 58 * iterator that tracks the iterator's movement among sequences and 59 * checks that operations performed on the "safe" iterator are 60 * legal. In additional to the basic iterator operations (which are 61 * validated, and then passed to the underlying iterator), 62 * %_Safe_iterator has member functions for iterator invalidation, 63 * attaching/detaching the iterator from sequences, and querying 64 * the iterator's state. 65 */ 66 template<typename _Iterator, typename _Sequence> 67 class _Safe_iterator : public _Safe_iterator_base 68 { 69 typedef _Safe_iterator _Self; 70 71 /** The precision to which we can calculate the distance between 72 * two iterators. 73 */ 74 enum _Distance_precision 75 { 76 __dp_equality, //< Can compare iterator equality, only 77 __dp_sign, //< Can determine equality and ordering 78 __dp_exact //< Can determine distance precisely 79 }; 80 81 /// The underlying iterator 82 _Iterator _M_current; 83 84 /// Determine if this is a constant iterator. 85 bool 86 _M_constant() const 87 { 88 typedef typename _Sequence::const_iterator const_iterator; 89 return __is_same<const_iterator, _Safe_iterator>::value; 90 } 91 92 typedef iterator_traits<_Iterator> _Traits; 93 94 public: 95 typedef _Iterator _Base_iterator; 96 typedef typename _Traits::iterator_category iterator_category; 97 typedef typename _Traits::value_type value_type; 98 typedef typename _Traits::difference_type difference_type; 99 typedef typename _Traits::reference reference; 100 typedef typename _Traits::pointer pointer; 101 102 /// @post the iterator is singular and unattached 103 _Safe_iterator() : _M_current() { } 104 105 /** 106 * @brief Safe iterator construction from an unsafe iterator and 107 * its sequence. 108 * 109 * @pre @p seq is not NULL 110 * @post this is not singular 111 */ 112 _Safe_iterator(const _Iterator& __i, const _Sequence* __seq) 113 : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i) 114 { 115 _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(), 116 _M_message(__msg_init_singular) 117 ._M_iterator(*this, "this")); 118 } 119 120 /** 121 * @brief Copy construction. 122 * @pre @p x is not singular 123 */ 124 _Safe_iterator(const _Safe_iterator& __x) 125 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current) 126 { 127 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(), 128 _M_message(__msg_init_copy_singular) 129 ._M_iterator(*this, "this") 130 ._M_iterator(__x, "other")); 131 } 132 133 /** 134 * @brief Converting constructor from a mutable iterator to a 135 * constant iterator. 136 * 137 * @pre @p x is not singular 138 */ 139 template<typename _MutableIterator> 140 _Safe_iterator( 141 const _Safe_iterator<_MutableIterator, 142 typename std::__enable_if< 143 _Sequence, 144 (std::__are_same<_MutableIterator, 145 typename _Sequence::iterator::_Base_iterator>::__value) 146 >::__type>& __x) 147 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base()) 148 { 149 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(), 150 _M_message(__msg_init_const_singular) 151 ._M_iterator(*this, "this") 152 ._M_iterator(__x, "other")); 153 } 154 155 /** 156 * @brief Copy assignment. 157 * @pre @p x is not singular 158 */ 159 _Safe_iterator& 160 operator=(const _Safe_iterator& __x) 161 { 162 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(), 163 _M_message(__msg_copy_singular) 164 ._M_iterator(*this, "this") 165 ._M_iterator(__x, "other")); 166 _M_current = __x._M_current; 167 this->_M_attach(static_cast<_Sequence*>(__x._M_sequence)); 168 return *this; 169 } 170 171 /** 172 * @brief Iterator dereference. 173 * @pre iterator is dereferenceable 174 */ 175 reference 176 operator*() const 177 { 178 179 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 180 _M_message(__msg_bad_deref) 181 ._M_iterator(*this, "this")); 182 return *_M_current; 183 } 184 185 /** 186 * @brief Iterator dereference. 187 * @pre iterator is dereferenceable 188 * @todo Make this correct w.r.t. iterators that return proxies 189 * @todo Use addressof() instead of & operator 190 */ 191 pointer 192 operator->() const 193 { 194 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 195 _M_message(__msg_bad_deref) 196 ._M_iterator(*this, "this")); 197 return &*_M_current; 198 } 199 200 // ------ Input iterator requirements ------ 201 /** 202 * @brief Iterator preincrement 203 * @pre iterator is incrementable 204 */ 205 _Safe_iterator& 206 operator++() 207 { 208 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 209 _M_message(__msg_bad_inc) 210 ._M_iterator(*this, "this")); 211 ++_M_current; 212 return *this; 213 } 214 215 /** 216 * @brief Iterator postincrement 217 * @pre iterator is incrementable 218 */ 219 _Safe_iterator 220 operator++(int) 221 { 222 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 223 _M_message(__msg_bad_inc) 224 ._M_iterator(*this, "this")); 225 _Safe_iterator __tmp(*this); 226 ++_M_current; 227 return __tmp; 228 } 229 230 // ------ Bidirectional iterator requirements ------ 231 /** 232 * @brief Iterator predecrement 233 * @pre iterator is decrementable 234 */ 235 _Safe_iterator& 236 operator--() 237 { 238 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 239 _M_message(__msg_bad_dec) 240 ._M_iterator(*this, "this")); 241 --_M_current; 242 return *this; 243 } 244 245 /** 246 * @brief Iterator postdecrement 247 * @pre iterator is decrementable 248 */ 249 _Safe_iterator 250 operator--(int) 251 { 252 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 253 _M_message(__msg_bad_dec) 254 ._M_iterator(*this, "this")); 255 _Safe_iterator __tmp(*this); 256 --_M_current; 257 return __tmp; 258 } 259 260 // ------ Random access iterator requirements ------ 261 reference 262 operator[](const difference_type& __n) const 263 { 264 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n) 265 && this->_M_can_advance(__n+1), 266 _M_message(__msg_iter_subscript_oob) 267 ._M_iterator(*this)._M_integer(__n)); 268 269 return _M_current[__n]; 270 } 271 272 _Safe_iterator& 273 operator+=(const difference_type& __n) 274 { 275 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n), 276 _M_message(__msg_advance_oob) 277 ._M_iterator(*this)._M_integer(__n)); 278 _M_current += __n; 279 return *this; 280 } 281 282 _Safe_iterator 283 operator+(const difference_type& __n) const 284 { 285 _Safe_iterator __tmp(*this); 286 __tmp += __n; 287 return __tmp; 288 } 289 290 _Safe_iterator& 291 operator-=(const difference_type& __n) 292 { 293 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n), 294 _M_message(__msg_retreat_oob) 295 ._M_iterator(*this)._M_integer(__n)); 296 _M_current += -__n; 297 return *this; 298 } 299 300 _Safe_iterator 301 operator-(const difference_type& __n) const 302 { 303 _Safe_iterator __tmp(*this); 304 __tmp -= __n; 305 return __tmp; 306 } 307 308 // ------ Utilities ------ 309 /** 310 * @brief Return the underlying iterator 311 */ 312 _Iterator 313 base() const { return _M_current; } 314 315 /** 316 * @brief Conversion to underlying non-debug iterator to allow 317 * better interaction with non-debug containers. 318 */ 319 operator _Iterator() const { return _M_current; } 320 321 /** Attach iterator to the given sequence. */ 322 void 323 _M_attach(const _Sequence* __seq) 324 { 325 _Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq), 326 _M_constant()); 327 } 328 329 /** Invalidate the iterator, making it singular. */ 330 void 331 _M_invalidate(); 332 333 /// Is the iterator dereferenceable? 334 bool 335 _M_dereferenceable() const 336 { return !this->_M_singular() && !_M_is_end(); } 337 338 /// Is the iterator incrementable? 339 bool 340 _M_incrementable() const { return this->_M_dereferenceable(); } 341 342 // Is the iterator decrementable? 343 bool 344 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); } 345 346 // Can we advance the iterator @p __n steps (@p __n may be negative) 347 bool 348 _M_can_advance(const difference_type& __n) const; 349 350 // Is the iterator range [*this, __rhs) valid? 351 template<typename _Other> 352 bool 353 _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const; 354 355 // The sequence this iterator references. 356 const _Sequence* 357 _M_get_sequence() const 358 { return static_cast<const _Sequence*>(_M_sequence); } 359 360 /** Determine the distance between two iterators with some known 361 * precision. 362 */ 363 template<typename _Iterator1, typename _Iterator2> 364 static pair<difference_type, _Distance_precision> 365 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs) 366 { 367 typedef typename iterator_traits<_Iterator1>::iterator_category 368 _Category; 369 return _M_get_distance(__lhs, __rhs, _Category()); 370 } 371 372 template<typename _Iterator1, typename _Iterator2> 373 static pair<difference_type, _Distance_precision> 374 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, 375 std::random_access_iterator_tag) 376 { 377 return std::make_pair(__rhs.base() - __lhs.base(), __dp_exact); 378 } 379 380 template<typename _Iterator1, typename _Iterator2> 381 static pair<difference_type, _Distance_precision> 382 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, 383 std::forward_iterator_tag) 384 { 385 return std::make_pair(__lhs.base() == __rhs.base()? 0 : 1, 386 __dp_equality); 387 } 388 389 /// Is this iterator equal to the sequence's begin() iterator? 390 bool _M_is_begin() const 391 { return *this == static_cast<const _Sequence*>(_M_sequence)->begin(); } 392 393 /// Is this iterator equal to the sequence's end() iterator? 394 bool _M_is_end() const 395 { return *this == static_cast<const _Sequence*>(_M_sequence)->end(); } 396 }; 397 398 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 399 inline bool 400 operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 401 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 402 { 403 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 404 _M_message(__msg_iter_compare_bad) 405 ._M_iterator(__lhs, "lhs") 406 ._M_iterator(__rhs, "rhs")); 407 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 408 _M_message(__msg_compare_different) 409 ._M_iterator(__lhs, "lhs") 410 ._M_iterator(__rhs, "rhs")); 411 return __lhs.base() == __rhs.base(); 412 } 413 414 template<typename _Iterator, typename _Sequence> 415 inline bool 416 operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 417 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 418 { 419 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 420 _M_message(__msg_iter_compare_bad) 421 ._M_iterator(__lhs, "lhs") 422 ._M_iterator(__rhs, "rhs")); 423 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 424 _M_message(__msg_compare_different) 425 ._M_iterator(__lhs, "lhs") 426 ._M_iterator(__rhs, "rhs")); 427 return __lhs.base() == __rhs.base(); 428 } 429 430 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 431 inline bool 432 operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 433 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 434 { 435 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 436 _M_message(__msg_iter_compare_bad) 437 ._M_iterator(__lhs, "lhs") 438 ._M_iterator(__rhs, "rhs")); 439 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 440 _M_message(__msg_compare_different) 441 ._M_iterator(__lhs, "lhs") 442 ._M_iterator(__rhs, "rhs")); 443 return __lhs.base() != __rhs.base(); 444 } 445 446 template<typename _Iterator, typename _Sequence> 447 inline bool 448 operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 449 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 450 { 451 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 452 _M_message(__msg_iter_compare_bad) 453 ._M_iterator(__lhs, "lhs") 454 ._M_iterator(__rhs, "rhs")); 455 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 456 _M_message(__msg_compare_different) 457 ._M_iterator(__lhs, "lhs") 458 ._M_iterator(__rhs, "rhs")); 459 return __lhs.base() != __rhs.base(); 460 } 461 462 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 463 inline bool 464 operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 465 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 466 { 467 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 468 _M_message(__msg_iter_order_bad) 469 ._M_iterator(__lhs, "lhs") 470 ._M_iterator(__rhs, "rhs")); 471 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 472 _M_message(__msg_order_different) 473 ._M_iterator(__lhs, "lhs") 474 ._M_iterator(__rhs, "rhs")); 475 return __lhs.base() < __rhs.base(); 476 } 477 478 template<typename _Iterator, typename _Sequence> 479 inline bool 480 operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 481 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 482 { 483 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 484 _M_message(__msg_iter_order_bad) 485 ._M_iterator(__lhs, "lhs") 486 ._M_iterator(__rhs, "rhs")); 487 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 488 _M_message(__msg_order_different) 489 ._M_iterator(__lhs, "lhs") 490 ._M_iterator(__rhs, "rhs")); 491 return __lhs.base() < __rhs.base(); 492 } 493 494 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 495 inline bool 496 operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 497 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 498 { 499 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 500 _M_message(__msg_iter_order_bad) 501 ._M_iterator(__lhs, "lhs") 502 ._M_iterator(__rhs, "rhs")); 503 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 504 _M_message(__msg_order_different) 505 ._M_iterator(__lhs, "lhs") 506 ._M_iterator(__rhs, "rhs")); 507 return __lhs.base() <= __rhs.base(); 508 } 509 510 template<typename _Iterator, typename _Sequence> 511 inline bool 512 operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 513 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 514 { 515 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 516 _M_message(__msg_iter_order_bad) 517 ._M_iterator(__lhs, "lhs") 518 ._M_iterator(__rhs, "rhs")); 519 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 520 _M_message(__msg_order_different) 521 ._M_iterator(__lhs, "lhs") 522 ._M_iterator(__rhs, "rhs")); 523 return __lhs.base() <= __rhs.base(); 524 } 525 526 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 527 inline bool 528 operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 529 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 530 { 531 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 532 _M_message(__msg_iter_order_bad) 533 ._M_iterator(__lhs, "lhs") 534 ._M_iterator(__rhs, "rhs")); 535 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 536 _M_message(__msg_order_different) 537 ._M_iterator(__lhs, "lhs") 538 ._M_iterator(__rhs, "rhs")); 539 return __lhs.base() > __rhs.base(); 540 } 541 542 template<typename _Iterator, typename _Sequence> 543 inline bool 544 operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 545 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 546 { 547 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 548 _M_message(__msg_iter_order_bad) 549 ._M_iterator(__lhs, "lhs") 550 ._M_iterator(__rhs, "rhs")); 551 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 552 _M_message(__msg_order_different) 553 ._M_iterator(__lhs, "lhs") 554 ._M_iterator(__rhs, "rhs")); 555 return __lhs.base() > __rhs.base(); 556 } 557 558 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 559 inline bool 560 operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 561 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 562 { 563 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 564 _M_message(__msg_iter_order_bad) 565 ._M_iterator(__lhs, "lhs") 566 ._M_iterator(__rhs, "rhs")); 567 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 568 _M_message(__msg_order_different) 569 ._M_iterator(__lhs, "lhs") 570 ._M_iterator(__rhs, "rhs")); 571 return __lhs.base() >= __rhs.base(); 572 } 573 574 template<typename _Iterator, typename _Sequence> 575 inline bool 576 operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 577 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 578 { 579 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 580 _M_message(__msg_iter_order_bad) 581 ._M_iterator(__lhs, "lhs") 582 ._M_iterator(__rhs, "rhs")); 583 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 584 _M_message(__msg_order_different) 585 ._M_iterator(__lhs, "lhs") 586 ._M_iterator(__rhs, "rhs")); 587 return __lhs.base() >= __rhs.base(); 588 } 589 590 // _GLIBCXX_RESOLVE_LIB_DEFECTS 591 // According to the resolution of DR179 not only the various comparison 592 // operators but also operator- must accept mixed iterator/const_iterator 593 // parameters. 594 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 595 inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type 596 operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 597 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 598 { 599 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 600 _M_message(__msg_distance_bad) 601 ._M_iterator(__lhs, "lhs") 602 ._M_iterator(__rhs, "rhs")); 603 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 604 _M_message(__msg_distance_different) 605 ._M_iterator(__lhs, "lhs") 606 ._M_iterator(__rhs, "rhs")); 607 return __lhs.base() - __rhs.base(); 608 } 609 610 template<typename _Iterator, typename _Sequence> 611 inline _Safe_iterator<_Iterator, _Sequence> 612 operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n, 613 const _Safe_iterator<_Iterator, _Sequence>& __i) 614 { return __i + __n; } 615} // namespace __gnu_debug 616 617#ifndef _GLIBCXX_EXPORT_TEMPLATE 618# include <debug/safe_iterator.tcc> 619#endif 620 621#endif 622