root/core/cache.hpp

/* [<][>][^][v][top][bottom][index][help] */

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. select
  2. id
  3. id
  4. process
  5. process
  6. statistics_
  7. internal_cache
  8. insert

   1 /******************************************************************************
   2 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/core/cache.hpp 2055 2017-05-13 19:35:47Z jmmcg $
   3 **
   4 ** Copyright © 2005 by J.M.McGuiness, coder@hussar.me.uk
   5 **
   6 ** This library is free software; you can redistribute it and/or
   7 ** modify it under the terms of the GNU Lesser General Public
   8 ** License as published by the Free Software Foundation; either
   9 ** version 2.1 of the License, or (at your option) any later version.
  10 **
  11 ** This library is distributed in the hope that it will be useful,
  12 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14 ** Lesser General Public License for more details.
  15 **
  16 ** You should have received a copy of the GNU Lesser General Public
  17 ** License along with this library; if not, write to the Free Software
  18 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  19 */
  20 
  21 #include "thread_pool_sequential.hpp"
  22 #include "thread_pool_master.hpp"
  23 #include "thread_pool_workers.hpp"
  24 
  25 #include <limits>
  26 #include <map>
  27 #include <time.h>
  28 
  29 /** \file
  30         This file declares the various object that comprise the cache namespace.
  31 */
  32 
  33 namespace jmmcg { namespace cache {
  34 
  35         namespace private_ {
  36                 template<typename Mdl> struct multi_or_sequential {
  37                         static constexpr enum ppd::pool_traits::size_mode_t infinite_size_type=ppd::pool_traits::size_mode_t::infinite; ///< We allow an arbitrarily large amount of work to be transferred.
  38                         static constexpr enum ppd::pool_traits::size_mode_t fixed_size_type=ppd::pool_traits::size_mode_t::fixed_size;  ///< Specifies that the thread pool is finite in size.
  39                 };
  40                 template<> struct multi_or_sequential<ppd::sequential_mode> {
  41                         static constexpr enum ppd::pool_traits::size_mode_t infinite_size_type=ppd::pool_traits::size_mode_t::sequential;
  42                         static constexpr enum ppd::pool_traits::size_mode_t fixed_size_type=ppd::pool_traits::size_mode_t::sequential;
  43                 };
  44         }
  45 
  46         /// Adaptors for the single & multi-threading traits.
  47         template<typename Key, typename Val, class Comp=std::less<Key>, class Alloc=std::allocator<Val> >
  48         struct threading {
  49                 /// The sequential trait.
  50                 template<ppd::generic_traits::api_type API>
  51                 struct single {
  52                         /// Use a standard map as the basic associative collection.
  53                         typedef std::map<Key, Val, Comp, Alloc> assoc_colln_t;
  54                         typedef typename assoc_colln_t::value_type::second_type mapped_type;
  55 
  56                         /// A sequential trait for executing work from which we do not need to get the results.
  57                         /**
  58                                 For compatibility with the multi-threaded version.
  59                         */
  60                         typedef ppd::thread_pool<
  61                                 ppd::pool_traits::work_distribution_mode_t::one_thread_distributes<>,   ///< The master thread distributes the work.
  62                                 ppd::pool_traits::size_mode_t::sequential,      ///< This parameter specifies that it is sequential.
  63                                 ppd::pool_aspects<
  64                                         ppd::generic_traits::return_data::joinable,     ///< This parameter specifies that we may be interested in any results.
  65                                         API,
  66                                         ppd::sequential_mode,   ///< This parameter specifies that it is sequential.
  67                                         ppd::pool_traits::normal_fifo
  68                                 >
  69                         > flusher_pool_t;
  70 
  71                         /// A sequential trait for executing work from which we want to get the results.
  72                         /**
  73                                 For compatibility with the multi-threaded version.
  74                         */
  75                         typedef ppd::thread_pool<
  76                                 ppd::pool_traits::work_distribution_mode_t::worker_threads_get_work<ppd::pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>,        ///< The underlying "thread pool" uses a work-stealing model.
  77                                 ppd::pool_traits::size_mode_t::sequential,      ///< This parameter specifies that it is sequential.
  78                                 ppd::pool_aspects<
  79                                         ppd::generic_traits::return_data::joinable,     ///< This parameter specifies that we may be interested in any results.
  80                                         API,
  81                                         ppd::sequential_mode,   ///< This parameter specifies that it is sequential.
  82                                         ppd::pool_traits::normal_fifo
  83                                 >
  84                         > populate_pool_t;
  85                 };
  86 
  87                 /// The multi-threaded trait.
  88                 template<ppd::generic_traits::api_type API, typename Mdl>
  89                 struct multi {
  90                         /// Use a standard map as the basic associative collection.
  91                         /**
  92                                 An associative collection that supported locking on its methods would avoid the gross locks required in the cache itself.
  93                         */
  94                         typedef std::map<Key,Val,Comp,Alloc> assoc_colln_t;
  95                         typedef typename assoc_colln_t::value_type::second_type mapped_type;
  96                         typedef private_::multi_or_sequential<Mdl> multi_or_sequential_chooser;
  97 
  98                         /// A multi-threaded trait for executing work from which we do not need to get the results.
  99                         typedef typename ppd::thread_pool<
 100                                 ppd::pool_traits::work_distribution_mode_t::one_thread_distributes<>,   ///< The master thread distributes the work.
 101                                 multi_or_sequential_chooser::infinite_size_type,
 102                                 ppd::pool_aspects<
 103                                         ppd::generic_traits::return_data::joinable,     ///< This parameter specifies that we may be interested in any results.
 104                                         API,
 105                                         Mdl,
 106                                         ppd::pool_traits::normal_fifo,
 107                                         std::less
 108                                 >
 109                         > flusher_pool_t;
 110 
 111                         /// A multi-threaded trait for executing work from which we want to get the results.
 112                         /**
 113                                 Note that this is a finite-sized thread pool.
 114                         */
 115                         typedef typename ppd::thread_pool<
 116                                 ppd::pool_traits::work_distribution_mode_t::worker_threads_get_work<ppd::pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>,        ///< The underlying thread pool uses a work-stealing model.
 117                                 multi_or_sequential_chooser::fixed_size_type,
 118                                 ppd::pool_aspects<
 119                                         ppd::generic_traits::return_data::joinable,     ///< This parameter specifies that we may be interested in any results.
 120                                         API,
 121                                         Mdl,
 122                                         ppd::pool_traits::normal_fifo
 123                                 >
 124                         > populate_pool_t;
 125                 };
 126         };
 127 
 128         /// A simple factory class that allows us to tell the cache how a value is made for a particular key.
 129         template<typename Key, typename Data>
 130         struct factory_base {
 131                 typedef Key key_type;
 132                 typedef Data value_type;
 133 
 134                 virtual value_type __fastcall make(const key_type &) const=0;
 135                 virtual ~factory_base() {}
 136         };
 137 
 138         /// An implementation of an Least Recently Used (LRU) algorithm for selecting victim entries in the cache for flushing.
 139         template<typename Val>
 140         class lru {
 141         public:
 142                 typedef Val value_type;
 143 
 144                 class criterion_t {
 145                 public:
 146                         explicit constexpr __stdcall criterion_t(const clock_t c) noexcept(true)
 147                         : oldest(c) {
 148                         }
 149 
 150                         void operator=(criterion_t const &)=delete;
 151 
 152                         template<class MapT_> bool __fastcall
 153                         operator()(const MapT_ &val) const noexcept(true) {
 154                                 return val.second.accessed()<=oldest;
 155                         }
 156 
 157                 private:
 158                         const clock_t oldest;
 159                 };
 160 
 161                 constexpr __stdcall lru(void);
 162                 explicit constexpr __stdcall lru(const value_type &);
 163                 __stdcall lru(const lru &);
 164                 __stdcall ~lru(void);
 165                 lru & __fastcall operator=(const lru &);
 166 
 167                 const value_type & __fastcall value(void) const noexcept(true);
 168                 value_type & __fastcall value(void) noexcept(true);
 169 
 170                 clock_t __fastcall accessed(void) const noexcept(true);
 171 
 172                 template<typename Iter> static const criterion_t __fastcall
 173                 select(Iter beg,const Iter &end) {
 174                         clock_t oldest=std::numeric_limits<clock_t>::max();
 175                         while (beg!=end) {
 176                                 oldest=std::min(oldest,beg++->second.accessed());
 177                         }
 178                         return criterion_t(oldest);
 179                 }
 180 
 181         private:
 182                 mutable clock_t age;
 183                 value_type range_value;
 184         };
 185 
 186         /// A trivial "no statistics" class.
 187         struct no_statistics {
 188                 typedef unsigned long accesses_type;
 189                 typedef unsigned long hits_type;
 190                 typedef unsigned long flushes_type;
 191                 typedef unsigned long creations_type;
 192 
 193                 static constexpr accesses_type __fastcall accesses() noexcept(true) {
 194                         return 0;
 195                 }
 196                 static constexpr hits_type __fastcall hits() noexcept(true) {
 197                         return 0;
 198                 }
 199                 static constexpr flushes_type __fastcall flushes() noexcept(true) {
 200                         return 0;
 201                 }
 202                 static constexpr creations_type __fastcall outstanding_fills() noexcept(true) {
 203                         return 0;
 204                 }
 205                 friend constexpr jmmcg::tostream &operator<<(jmmcg::tostream &os, const no_statistics &) noexcept(true) {
 206                         return os;
 207                 }
 208 
 209                 static void __fastcall accessed(void) noexcept(true) {}
 210                 static void __fastcall hit(void) noexcept(true) {}
 211                 static void __fastcall reset(void) noexcept(true) {}
 212                 static void __fastcall flushed(void) noexcept(true) {}
 213         };
 214 
 215         /// Some basic statistic gathering.
 216         class basic_statistics {
 217         public:
 218                 typedef unsigned long accesses_type;
 219                 typedef unsigned long hits_type;
 220                 typedef unsigned long flushes_type;
 221                 typedef unsigned long creations_type;
 222 
 223                 constexpr __stdcall basic_statistics(void) noexcept(true);
 224                 __stdcall basic_statistics(const basic_statistics &) noexcept(true);
 225                 virtual __stdcall ~basic_statistics(void) noexcept(true);
 226                 basic_statistics & __fastcall operator=(const basic_statistics &) noexcept(true);
 227 
 228                 /// Total number of accesses to the cache.
 229                 accesses_type __fastcall accesses(void) const noexcept(true);
 230                 /// Total number of hits into the cache.
 231                 hits_type __fastcall hits(void) const noexcept(true);
 232                 /// Total number of cache flushes.
 233                 flushes_type __fastcall flushes(void) const noexcept(true);
 234                 /// Total number of outstanding cache fills.
 235                 /**
 236                         More useful for the multi-threaded cache to help tune the cache high- and low-water marks
 237                         and pool size for creating range-data the cache.
 238                 */
 239                 creations_type __fastcall outstanding_fills(void) const noexcept(true);
 240 
 241                 /// Write all of the statistics to an output stream, in a formatted manner.
 242                 /**
 243                         \param os       The output stream, templated for narrow or wide char use, based upon the definition or not of the preprocessor constant JMMCG_WIDE_CHARS. Idf not defined, standard "char" traits are used, otherwise "wchar_t" traits.
 244                         \param stats    The basic_statistics object that should be written.
 245                         \return A reference to that "std::ostream" that was passed in.
 246                 */
 247                 friend jmmcg::tostream &operator<<(jmmcg::tostream &os, const basic_statistics &stats);
 248 
 249                 /// Increment the "accessed" counter by 1.
 250                 void __fastcall accessed(void) noexcept(true);
 251                 /// Increment the "total hits" counter by 1.
 252                 void __fastcall hit(void) noexcept(true);
 253                 /// Increment the "total flushes" counter by 1.
 254                 void __fastcall flushed(void) noexcept(true);
 255                 /// Reset all of the counters.
 256                 void __fastcall reset(void) noexcept(true);
 257 
 258         private:
 259                 accesses_type total_accesses_;
 260                 hits_type total_hits_;
 261                 flushes_type total_flushes_;
 262         };
 263 
 264         /// A base cache class, for deriving from to provide the real functionality.
 265         /**
 266                 This class provides a low-level interface for the various cache types that can be
 267                 declared to allow some sort of compatibility and flexibility between them.
 268                 It also contains the factory, that identifies the basic properties of a cache:
 269                 the key and value types. Flush policies, statistics and threading are all extra
 270                 sugar, to some extent.
 271         */
 272         template<
 273                 class Factory
 274         >
 275         class base {
 276         public:
 277                 typedef Factory factory_type;   ///< The factory that is used to create a range-data value for a particular key.
 278                 typedef typename factory_type::key_type key_type;       ///< The type of the key.
 279                 typedef typename factory_type::value_type value_type;   ///< The type of the range-data.
 280 
 281                 __stdcall base(const base &);
 282                 virtual __stdcall ~base(void) noexcept(true);
 283 
 284                 base & __fastcall operator=(const base &);
 285 
 286                 /// Returns "true" iff the internal, associative collection is empty.
 287                 virtual bool __fastcall empty() const noexcept(true)=0;
 288                 /// This function will reset any statistics upon clearing all contents from the internal, associative collection.
 289                 virtual void __fastcall clear()=0;
 290 
 291                 /// Flush the contents of the cache according to the flush policy.
 292                 /**
 293                         The flush policy must be specified by a deriving class. The direct call to "flush" is run on the same thread, not another thread wrt the caller.
 294                 */
 295                 virtual void __fastcall flush()=0;
 296 
 297         protected:
 298                 struct range_data {
 299                         typename factory_type::value_type data;
 300                 };
 301                 /// This class creates the data for a particular key, using the supplied factory.
 302                 class find_range_data : virtual protected non_assignable {
 303                 public:
 304                         typedef range_data result_type;
 305 
 306                         explicit __stdcall find_range_data(const factory_type &f,const key_type &i)
 307                         : data_factory_(f),id(i) {
 308                         }
 309                         __stdcall find_range_data(const find_range_data &gw) noexcept(true)
 310                         : data_factory_(gw.data_factory_),id(gw.id) {
 311                         }
 312                         ~find_range_data() {
 313                         }
 314 
 315                         void __fastcall process(range_data &res) {
 316                                 res.data=data_factory_.make(id);
 317                         }
 318 
 319                         constexpr bool __fastcall operator<(find_range_data const &) const noexcept(true) {
 320                                 return true;
 321                         }
 322 
 323                 private:
 324                         const factory_type &data_factory_;
 325                         const key_type id;
 326                 };
 327 
 328                 /// This class flushes the internal associative collection of the cache according to the flush policy.
 329                 class flush_cache : virtual protected non_assignable {
 330                 public:
 331                         typedef void result_type;
 332 
 333                         explicit __stdcall flush_cache(base<Factory> &r) noexcept(true)
 334                         : the_cache(r) {
 335                         }
 336                         __stdcall flush_cache(const flush_cache &r) noexcept(true)
 337                         : the_cache(r.the_cache) {
 338                         }
 339                         ~flush_cache() {
 340                         }
 341 
 342                         void __fastcall process() {
 343                                 the_cache.flush();
 344                         }
 345 
 346                         constexpr bool __fastcall operator<(flush_cache const &) const noexcept(true) {
 347                                 return true;
 348                         }
 349 
 350                 private:
 351                         base<Factory> &the_cache;
 352                 };
 353 
 354                 explicit __stdcall base(const factory_type &f)
 355                 : data_factory_(f) {
 356                 }
 357 
 358                 const factory_type & __fastcall data_factory() const noexcept(true);
 359 
 360         private:
 361                 factory_type data_factory_;
 362         };
 363 
 364         /// A read-only cache that returns a const reference to the range data.
 365         /**
 366                 The cache is a value-type, so you can have caches of caches.
 367         */
 368         template<
 369                 class Factory,
 370                 class FP=lru<typename Factory::value_type>,     ///< We default to an LRU flush policy.
 371                 class ThrT=typename threading<typename Factory::key_type,FP>::template single<ppd::platform_api>,       ///< We default to a sequential policy.
 372                 class Stats=no_statistics       ///< We default to not collecting any statistics.
 373         >
 374         class ro : public base<Factory> {
 375         public:
 376                 typedef base<Factory>base_t;
 377                 typedef typename base_t::factory_type factory_type;     ///< The actual factory type.
 378                 typedef typename base_t::key_type key_type;     ///< The type of the key.
 379                 typedef ThrT thread_traits;     ///< The type of threading in force.
 380                 typedef Stats statistics_type;  ///< The statistics that will be gathered.
 381                 typedef typename thread_traits::assoc_colln_t colln_t;  ///< The type of the internal associative collection.
 382                 typedef typename colln_t::size_type size_type;  ///< The size type of the internal associative collection.
 383                 typedef const typename thread_traits::mapped_type mapped_type;  ///< The range-data type of the key type.
 384                 typedef typename thread_traits::flusher_pool_t::exception_type exception_type;  ///< The base class from which the exceptions that will be thrown by this class are derived.
 385                 typedef typename thread_traits::flusher_pool_t::pool_traits_type::os_traits os_traits;
 386                 typedef typename os_traits::lock_traits lock_traits;
 387 
 388                 /// The "low water mark" of the cache.
 389                 /**
 390                         The flush policy will attempt to ensure that size()>=low_water_mark.
 391                         But this is not guaranteed, because there may be outstanding cache fills from another thread.
 392                         \see size()
 393                 */
 394                 const size_type low_water_mark;
 395                 /// The "high water mark" of the cache.
 396                 /**
 397                         The flush policy will attempt to ensure that size()<=high_water_mark.
 398                         But this is not guaranteed, because there may be outstanding cache fills from another thread.
 399                         \see size()
 400                 */
 401                 const size_type high_water_mark;
 402 
 403                 /// Create an empty read-only cache.
 404                 /**
 405                         \param low_water        This is the low_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()>=low_water_mark.
 406                         \param high_water       This is the high_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()<=high_water_mark.
 407                         \param num_threads      This is the number of threads in the thread pool used for creating range-data for satisfying data requests. This number is set to prevent any data source (e.g. a database) from becoming overwhelmed by requests.
 408                         \param f                The factory that is used to create a range-data item for a particular key.
 409                         \see size()
 410                 */
 411                 explicit constexpr __stdcall ro(const size_type low_water, const size_type high_water, const typename thread_traits::populate_pool_t::pool_type::size_type num_threads, const factory_type &f)
 412                 : base<Factory>(f), low_water_mark(low_water), high_water_mark(high_water), serialize(), flusher_pool(), populate_pool(num_threads), internal_cache(), statistics_() {
 413                 }
 414                 /// Create a read-only cache and populate it with some values.
 415                 /**
 416                         Note that a (possibly) asynchronous flush() may occur after the population to ensure that the
 417                         max_size of the cache is maintained.
 418                         \param low_water        This is the low_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()>=low_water_mark.
 419                         \param high_water       This is the high_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()<=high_water_mark.
 420                         \param num_threads      This is the number of threads in the thread pool used for creating range-data for satisfying data requests. This number is set to prevent any data source (e.g. a database) from becoming overwhelmed by requests.
 421                         \param f                The factory that is used to create a range-data item for a particular key.
 422                         \param beg      An iterator to the beginning of the source data.
 423                         \param end      An iterator to the end of the source data.
 424                         \see size()
 425                         \see insert()
 426                 */
 427                 template<typename Iter> constexpr __stdcall
 428                 ro(const size_type low_water, const size_type high_water, const typename thread_traits::populate_pool_t::pool_type::size_type num_threads, const factory_type &f, const Iter &beg, const Iter &end)
 429                 : base<Factory>(f), low_water_mark(low_water), high_water_mark(high_water), serialize(), flusher_pool(), populate_pool(num_threads), internal_cache(beg, end) {
 430                 }
 431                 __stdcall ro(const ro &);
 432                 virtual __stdcall ~ro(void) noexcept(true);
 433 
 434                 ro & __fastcall operator=(const ro &);
 435 
 436                 /// Indicate if the cache is empty.
 437                 /**
 438                         Note that this does not take into account any outstanding cache fills nor flush()s.
 439                         \return "true" iff size()==0.
 440                         \see size()
 441                         \see flush()
 442                 */
 443                 bool __fastcall empty(void) const noexcept(true);
 444                 /// Indicate the number of data items in the cache.
 445                 /**
 446                         Note that this does not take into account any outstanding cache fills nor flush()s.
 447                         \see flush()
 448                 */
 449                 const size_type __fastcall size(void) const noexcept(true);
 450                 /// Synchronously remove all data within the cache.
 451                 /**
 452                         Note that this does not take into account any outstanding cache fills nor flush()s.
 453                         Thus after this function it is not guaranteed that empty()==true.
 454                         This function will reset any statistics upon clearing all contents from the cache.
 455                         \see flush()
 456                         \see empty()
 457                 */
 458                 void __fastcall clear(void);
 459 
 460                 /// Synchronously insert a range of values into the cache.
 461                 /**
 462                         Note that a (possibly) asynchronous flush() may occur after the population to ensure that the
 463                         size()~<=high_water_mark of the cache is maintained.
 464                         \param beg      An iterator to the beginning of the source data.
 465                         \param end      An iterator to the end of the source data.
 466                         \see flush()
 467                 */
 468                 template<typename Iter> void __fastcall
 469                 insert(const Iter &beg, const Iter &end) {
 470                         internal_cache.insert(beg, end);
 471                         flusher_pool<<flush_nonjoinable()<<flush_cache(*this);
 472                 }
 473                 /// Lookup and return the range-data value associated with a key from the map.
 474                 /**
 475                         The creation of the range-data value may be asynchronous, as an implementation-defined optimization for multi-threaded caches.
 476                         A (possibly) asynchronous flush() is called to ensure that the high_water_mark is not exceeded before this function returns. Note that for asynchronous calls to flush(), they are only run once: overlapping calls to flush() will cause the later calls to be quashed, such that no buffering of flush()es occurs.
 477                         Note that it is guaranteed that empty()==false after this call.
 478                         \param key      The key to look up in the map and return the range-data value.
 479                         \return A const-qualified copy of the range data value associated with the key. This ensures that if an asynchronous flush() of the data item occurs, this will not leave a dangling reference in the client.
 480                         \see flush()
 481                         \see empty()
 482                 */
 483                 const mapped_type __fastcall operator[](const key_type &key);
 484                 /// A synchronous call to flush the cache according to the flush policy.
 485                 /**
 486                         Note that if two or more items within the cache satisfy the victimization criterion, and removing at least one of them would
 487                         ensure that the max_size criterion is satisfied, it is implementation defined regarding which of those items woulsd be flushed.
 488                 */
 489                 void __fastcall flush(void);
 490 
 491                 const statistics_type & __fastcall statistics(void) const noexcept(true);
 492 
 493         private:
 494                 typedef FP victimization_traits;
 495                 typedef typename lock_traits::critical_section_type atomic_t;
 496                 typedef typename atomic_t::write_unlockable_type lock_t;
 497                 typedef typename thread_traits::flusher_pool_t::nonjoinable flush_nonjoinable;
 498 
 499                 mutable atomic_t serialize;
 500                 mutable typename thread_traits::flusher_pool_t flusher_pool;
 501                 mutable typename thread_traits::populate_pool_t populate_pool;
 502                 mutable colln_t internal_cache;
 503                 mutable statistics_type statistics_;
 504         };
 505 
 506         /**
 507                 \todo Implement using the advice given in "Standard C++ IOStreams and Locales" by A.Langer & K.Kreft, page 170.
 508         */
 509         template<class F_,class P_,class TT_,class S_> jmmcg::tostream & __fastcall
 510         operator<<(jmmcg::tostream &os, const ro<F_,P_,TT_,S_> &r) {
 511                 os<<_T("Low water-mark=")<<r.low_water_mark
 512                         <<_T(", high water-mark=")<<r.high_water_mark
 513                         <<_T(", current number of elements=")<<r.size();
 514                 return os;
 515         }
 516 
 517 } }
 518 
 519 #include "cache_impl.hpp"

/* [<][>][^][v][top][bottom][index][help] */