00001 #ifndef STATIC_CONTAINER_LIST_NODE_POOL_H 00002 00003 #define STATIC_CONTAINER_LIST_NODE_POOL_H 00004 00005 /* 00006 zlib/libpng license 00007 ------------------- 00008 00009 Copyright (C) 2004 &o 00010 00011 This software is provided 'as-is', without any express or implied warranty. In n 00012 o event will the authors be held liable for any damages arising from the use of 00013 this software. 00014 00015 Permission is granted to anyone to use this software for any purpose, including 00016 commercial applications, and to alter it and redistribute it freely, subject to 00017 the following restrictions: 00018 00019 The origin of this software must not be misrepresented; you must not claim that 00020 you wrote the original software. If you use this software in a product, an ackno 00021 wledgment in the product documentation would be appreciated but is not required. 00022 00023 Altered source versions must be plainly marked as such, and must not be misrepre 00024 sented as being the original software. 00025 This notice may not be removed or altered from any source distribution. 00026 00027 project site : https://sourceforge.jp/projects/gslib/ 00028 my site : http://www.game-syokunin.com/ 00029 -------------------------------------------------------------------------------- 00030 00031 法的には、上記の原文のほうが有効なので、より厳密には日本語訳よりも原文を参考にし 00032 てください。日本語訳は、http://opensource.jp/licenses/zlib-license.html から頂い 00033 てきました。 00034 00035 zlib/libpngライセンス ( 日本語訳 ) 00036 00037 Copyright (C) 2004 &o 00038 00039 本ソフトウェアは「現状のまま」で、明示であるか暗黙であるかを問わず、何らの保証も 00040 なく提供されます。本ソフトウェアの使用によって生じるいかなる損害についても、作者 00041 は一切の責任を負わないものとします。 以下の制限に従う限り、商用アプリケーション 00042 を含めて、本ソフトウェアを任意の目的に使用し、自由に改変して再頒布することをすべ 00043 ての人に許可します。 00044 00045 本ソフトウェアの出自について虚偽の表示をしてはなりません。あなたがオリジナルのソ 00046 フトウェアを作成したと主張してはなりません。あなたが本ソフトウェアを製品内で使用 00047 する場合、製品の文書に謝辞をれていただければ幸いですが、必須ではありません。 00048 ソースを変更した場合は、そのことを明示しなければなりません。オリジナルのソフトウ 00049 ェアであるという虚偽の表示をしてはなりません。 00050 ソースの頒布物から、この表示を削除したり、表示の内容を変更したりしてはなりません 00051 。 00052 00053 project site : https://sourceforge.jp/projects/gslib/ 00054 my site : http://www.game-syokunin.com/ 00055 */ 00056 00057 #include <boost/noncopyable.hpp> 00058 #include <gslib/static_container/list_node.h> 00059 #include <gslib/static_container/STATIC_CONTAINER_MEMBERTYPEDEF.h> 00060 #include <gslib/numeric.h> 00061 00062 namespace gslib { 00063 namespace static_container { 00065 00068 template < typename Value > 00069 class abstruct_list_node_pool : boost::noncopyable { 00070 public: 00071 typedef list_link link; 00072 typedef list_node< Value > node; 00073 STATIC_CONTAINER_MEMBERTYPEDEF( Value ) 00074 private: 00075 link free_; 00076 00077 protected: 00078 abstruct_list_node_pool() { 00079 } 00080 virtual node* getTop() = 0; 00081 00082 void init() { 00083 // すべての要素を free_ に追加 00084 node* top = getTop(); 00085 free_.next = top; 00086 free_.prev = top + size() - 1; 00087 top->prev = &free_; 00088 free_.prev->next = &free_; 00089 for ( size_type i = 1; i < size(); ++i ) { 00090 top[ i - 1 ].next = &top[ i ]; 00091 top[ i ].prev = &top[ i - 1 ]; 00092 } 00093 } 00094 public: 00095 virtual size_type size() const = 0; 00096 00098 node* allocate() { 00099 if ( free_.next != &free_ ) { 00100 node* result = static_cast< node* >( free_.next ); 00101 result->isolate(); 00102 return result; 00103 } else { 00104 return 0; 00105 } 00106 } 00107 00109 00112 void deallocate( link* first, link* last ) { 00113 if ( first == last ) { 00114 return; 00115 } 00116 00117 // 「first の直前」と「last」を接続 00118 first->prev->next = last; 00119 link* lastPrev = last->prev; 00120 last->prev = first->prev; 00121 00122 // [ first, lastPrev ] を free_ の終端に接続 00123 first->prev = free_.prev; 00124 free_.prev->next = first; 00125 free_.prev = lastPrev; 00126 lastPrev->next = &free_; 00127 } 00128 00130 00133 void deallocate( link* n ) { 00134 deallocate( n, n->next ); 00135 } 00136 00138 00142 bool full() const { 00143 return free_.next == &free_; 00144 } 00145 00147 size_type rest() const { 00148 link* n = free_.next; 00149 size_type result = 0; 00150 while ( &free_ != n ) { 00151 n = n->next; 00152 ++result; 00153 } 00154 return result; 00155 } 00156 }; 00157 00159 template < typename Value, uint_fast_t Size > 00160 class list_node_pool : public abstruct_list_node_pool< Value > { 00161 uintptr_t buffer_[ Size * sizeof( node ) / sizeof( uintptr_t ) ]; 00162 virtual node* getTop() { 00163 return reinterpret_cast< node* >( buffer_ ); 00164 } 00165 public: 00166 list_node_pool() { 00167 init(); 00168 } 00169 00170 virtual size_type size() const { 00171 return Size; 00172 } 00173 }; 00174 } 00175 } 00176 00177 #endif