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