Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

list_node_pool.h

Go to the documentation of this file.
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

Generated on Sat Nov 27 15:02:49 2004 for static_container by doxygen 1.3.6