sc_list.cpp revision 12027
1/***************************************************************************** 2 3 Licensed to Accellera Systems Initiative Inc. (Accellera) under one or 4 more contributor license agreements. See the NOTICE file distributed 5 with this work for additional information regarding copyright ownership. 6 Accellera licenses this file to you under the Apache License, Version 2.0 7 (the "License"); you may not use this file except in compliance with the 8 License. You may obtain a copy of the License at 9 10 http://www.apache.org/licenses/LICENSE-2.0 11 12 Unless required by applicable law or agreed to in writing, software 13 distributed under the License is distributed on an "AS IS" BASIS, 14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 15 implied. See the License for the specific language governing 16 permissions and limitations under the License. 17 18 *****************************************************************************/ 19 20/***************************************************************************** 21 22 sc_list.cpp -- Simple implementation of a doubly linked list. 23 24 Original Author: Stan Y. Liao, Synopsys, Inc. 25 26 CHANGE LOG AT END OF FILE 27 *****************************************************************************/ 28 29 30#include <assert.h> 31#include <cstddef> 32 33#include "sysc/kernel/sc_cmnhdr.h" 34#include "sysc/utils/sc_iostream.h" 35#include "sysc/utils/sc_list.h" 36#include "sysc/utils/sc_mempool.h" 37#include "sysc/utils/sc_report.h" 38#include "sysc/utils/sc_utils_ids.h" 39 40namespace sc_core { 41 42class sc_plist_elem { 43 friend class sc_plist_base_iter; 44 friend class sc_plist_base; 45 46private: 47 sc_plist_elem() : data(0), prev(0), next(0) 48 {} 49 sc_plist_elem( void* d, sc_plist_elem* p, sc_plist_elem* n ) : 50 data(d), prev(p), next(n) 51 {} 52 ~sc_plist_elem() 53 {} 54 55 static void* operator new(std::size_t sz) { return sc_mempool::allocate(sz); } 56 static void operator delete(void* p, std::size_t sz) { sc_mempool::release(p, sz); } 57 58 void* data; 59 sc_plist_elem* prev; 60 sc_plist_elem* next; 61}; 62 63sc_plist_base::sc_plist_base() : head(0), tail(0) {} 64 65sc_plist_base::~sc_plist_base() 66{ 67 handle_t p; 68 for( handle_t h = head; h != 0; h = p ) { 69 p = h->next; 70 delete h; 71 } 72} 73 74void 75sc_plist_base::erase_all() 76{ 77 handle_t p; 78 for( handle_t h = head; h != 0; h = p ) { 79 p = h->next; 80 delete h; 81 } 82 head = 0; 83 tail = 0; 84} 85 86int 87sc_plist_base::size() const 88{ 89 int n = 0; 90 for( handle_t h = head; h != 0; h = h->next ) { 91 n++; 92 } 93 return n; 94} 95 96sc_plist_base::handle_t 97sc_plist_base::push_back( void* d ) 98{ 99 handle_t q = new sc_plist_elem( d, tail, 0 ); 100 if (tail) { 101 tail->next = q; 102 tail = q; 103 } 104 else { 105 head = tail = q; 106 } 107 return q; 108} 109 110sc_plist_base::handle_t 111sc_plist_base::push_front( void* d ) 112{ 113 handle_t q = new sc_plist_elem( d, (sc_plist_elem*) 0, head ); 114 if (head) { 115 head->prev = q; 116 head = q; 117 } 118 else { 119 head = tail = q; 120 } 121 return q; 122} 123 124void* 125sc_plist_base::pop_back() 126{ 127 handle_t q = tail; 128 void* d = q->data; 129 tail = tail->prev; 130 delete q; 131 if (tail != 0) { 132 tail->next = 0; 133 } 134 else { 135 head = 0; 136 } 137 return d; 138} 139 140void* 141sc_plist_base::pop_front() 142{ 143 handle_t q = head; 144 void* d = q->data; 145 head = head->next; 146 delete q; 147 if (head != 0) { 148 head->prev = 0; 149 } 150 else { 151 tail = 0; 152 } 153 return d; 154} 155 156sc_plist_base::handle_t 157sc_plist_base::insert_before( handle_t h, void* d ) 158{ 159 if (h == 0) { 160 return push_back(d); 161 } 162 else { 163 handle_t q = new sc_plist_elem( d, h->prev, h ); 164 h->prev->next = q; 165 h->prev = q; 166 return q; 167 } 168} 169 170sc_plist_base::handle_t 171sc_plist_base::insert_after( handle_t h, void* d ) 172{ 173 if (h == 0) { 174 return push_front(d); 175 } 176 else { 177 handle_t q = new sc_plist_elem( d, h, h->next ); 178 h->next->prev = q; 179 h->next = q; 180 return q; 181 } 182} 183 184void* 185sc_plist_base::remove( handle_t h ) 186{ 187 if (h == head) 188 return pop_front(); 189 else if (h == tail) 190 return pop_back(); 191 else { 192 void* d = h->data; 193 h->prev->next = h->next; 194 h->next->prev = h->prev; 195 delete h; 196 return d; 197 } 198} 199 200void* 201sc_plist_base::get( handle_t h ) const 202{ 203 return h->data; 204} 205 206void 207sc_plist_base::set( handle_t h, void* d ) 208{ 209 h->data = d; 210} 211 212void 213sc_plist_base::mapcar( sc_plist_map_fn f, void* arg ) 214{ 215 for (handle_t h = head; h != 0; h = h->next) { 216 f( h->data, arg ); 217 } 218} 219 220void* 221sc_plist_base::front() const 222{ 223 224 if (head) { 225 return head->data; 226 } 227 else { 228 SC_REPORT_ERROR( SC_ID_FRONT_ON_EMPTY_LIST_ , 0 ); 229 // never reached 230 return 0; 231 } 232} 233 234void* 235sc_plist_base::back() const 236{ 237 if (tail) { 238 return tail->data; 239 } 240 else { 241 SC_REPORT_ERROR( SC_ID_BACK_ON_EMPTY_LIST_, 0 ); 242 // never reached 243 return 0; 244 } 245} 246 247 248 249sc_plist_base_iter::sc_plist_base_iter( sc_plist_base* l, bool from_tail ) : 250 lst(l), ptr( from_tail ? l->tail : l->head ) 251{ 252} 253 254void 255sc_plist_base_iter::reset( sc_plist_base* l, bool from_tail ) 256{ 257 lst = l; 258 if (from_tail) { 259 ptr = l->tail; 260 } 261 else { 262 ptr = l->head; 263 } 264} 265 266sc_plist_base_iter::~sc_plist_base_iter() 267{ 268 269} 270 271bool 272sc_plist_base_iter::empty() const 273{ 274 return ptr == 0; 275} 276 277void 278sc_plist_base_iter::operator++(int) 279{ 280 ptr = ptr->next; 281} 282 283void 284sc_plist_base_iter::operator--(int) 285{ 286 ptr = ptr->prev; 287} 288 289void* 290sc_plist_base_iter::get() const 291{ 292 return ptr->data; 293} 294 295void 296sc_plist_base_iter::set( void* d ) 297{ 298 ptr->data = d; 299} 300 301void 302sc_plist_base_iter::remove() 303{ 304 sc_plist_base::handle_t nptr = ptr->next; 305 lst->remove(ptr); 306 ptr = nptr; 307} 308 309void 310sc_plist_base_iter::remove(int direction) 311{ 312 sc_plist_base::handle_t nptr = (direction == 1) ? ptr->next : ptr->prev; 313 lst->remove(ptr); 314 ptr = nptr; 315} 316 317void 318sc_plist_base_iter::set_handle( sc_plist_elem* h ) 319{ 320 ptr = h; 321} 322 323} // namespace sc_core 324 325// $Log: sc_list.cpp,v $ 326// Revision 1.4 2011/08/26 20:46:18 acg 327// Andy Goodrich: moved the modification log to the end of the file to 328// eliminate source line number skew when check-ins are done. 329// 330// Revision 1.3 2011/08/24 22:05:56 acg 331// Torsten Maehne: initialization changes to remove warnings. 332// 333// Revision 1.2 2011/02/18 20:38:43 acg 334// Andy Goodrich: Updated Copyright notice. 335// 336// Revision 1.1.1.1 2006/12/15 20:20:06 acg 337// SystemC 2.3 338// 339// Revision 1.3 2006/01/13 18:53:10 acg 340// Andy Goodrich: Added $Log command so that CVS comments are reproduced in 341// the source. 342 343// taf 344