00001 #ifndef STATIC_CONTAINER_LIST_NODE_POOL_H 00002 00003 #define STATIC_CONTAINER_LIST_NODE_POOL_H 00004 00005 #include <boost/noncopyable.hpp> 00006 #include "static_container/list_node.h" 00007 #include "static_container/STATIC_CONTAINER_MEMBERTYPEDEF.h" 00008 00009 namespace static_container { 00011 00014 template < typename Value > 00015 class abstruct_list_node_pool : boost::noncopyable { 00016 public: 00017 typedef list_link link; 00018 typedef list_node< Value > node; 00019 STATIC_CONTAINER_MEMBERTYPEDEF( Value ) 00020 private: 00021 link free_; 00022 00023 protected: 00024 abstruct_list_node_pool() { 00025 } 00026 virtual node* getTop() = 0; 00027 00028 void init() { 00029 // すべての要素を free_ に追加 00030 node* top = getTop(); 00031 free_.next = top; 00032 free_.prev = top + size() - 1; 00033 top->prev = &free_; 00034 free_.prev->next = &free_; 00035 for ( size_type i = 1; i < size(); ++i ) { 00036 top[ i - 1 ].next = &top[ i ]; 00037 top[ i ].prev = &top[ i - 1 ]; 00038 } 00039 } 00040 public: 00041 virtual size_type size() const = 0; 00042 00044 node* allocate() { 00045 if ( free_.next != &free_ ) { 00046 node* result = static_cast< node* >( free_.next ); 00047 result->isolate(); 00048 return result; 00049 } else { 00050 return 0; 00051 } 00052 } 00053 00055 00058 void deallocate( link* first, link* last ) { 00059 if ( first == last ) { 00060 return; 00061 } 00062 00063 // 「first の直前」と「last」を接続 00064 first->prev->next = last; 00065 link* lastPrev = last->prev; 00066 last->prev = first->prev; 00067 00068 // [ first, lastPrev ] を free_ の終端に接続 00069 first->prev = free_.prev; 00070 free_.prev->next = first; 00071 free_.prev = lastPrev; 00072 lastPrev->next = &free_; 00073 } 00074 00076 00079 void deallocate( link* n ) { 00080 deallocate( n, n->next ); 00081 } 00082 00084 00088 bool full() const { 00089 return free_.next == &free_; 00090 } 00091 00093 size_type rest() const { 00094 link* n = free_.next; 00095 size_type result = 0; 00096 while ( &free_ != n ) { 00097 n = n->next; 00098 ++result; 00099 } 00100 return result; 00101 } 00102 }; 00103 00105 template < typename Value, uint_fast_t Size > 00106 class list_node_pool : public abstruct_list_node_pool< Value > { 00107 uintptr_t buffer_[ Size * sizeof( node ) / sizeof( uintptr_t ) ]; 00108 virtual node* getTop() { 00109 return reinterpret_cast< node* >( buffer_ ); 00110 } 00111 public: 00112 list_node_pool() { 00113 init(); 00114 } 00115 00116 virtual size_type size() const { 00117 return Size; 00118 } 00119 }; 00120 } 00121 00122 #endif