2 * Copyright (c) 2001-2005 The Regents of The University of Michigan
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 * Authors: Steve Raasch
32 #ifndef __RES_LIST_HH__
33 #define __RES_LIST_HH__
35 #include "base/cprintf.hh"
38 #define DEBUG_REMOVE 0
40 #define DEBUG_MEMORY 0
41 //#define DEBUG_MEMORY DEBUG
47 static long long allocated_elements;
48 static long long allocated_lists;
51 long long get_elements(void) {
52 return allocated_elements;
54 long long get_lists(void) {
55 return allocated_lists;
62 extern void what_the(void);
66 class res_list : public res_list_base
79 // always adds to the END of the list
80 res_element(res_element *_prev, bool allocate);
84 friend class res_list<T>;
85 friend class res_list<T>::iterator;
93 friend class res_list<T>;
97 iterator(res_element *q) : p(q) {}
98 iterator(void) { p=0; };
102 res_element *res_el_ptr(void) { return p;}
103 void point_to(T &d) { p->data = &d; }
105 iterator next(void) { return iterator(p->next); }
106 iterator prev(void) { return iterator(p->prev); }
107 bool operator== (iterator x) { return (x.p == this->p); }
108 bool operator != (iterator x) { return (x.p != this->p); }
109 T &operator * (void) { return *(p->data); }
110 T* operator -> (void) { return p->data; }
111 bool isnull(void) { return (p==0); }
112 bool notnull(void) { return (p!=0); }
116 iterator unused_elements;
120 unsigned base_elements;
121 unsigned extra_elements;
122 unsigned active_elements;
123 bool allocate_storage;
129 // Allocate new elements, and assign them to the unused_elements
132 unsigned allocate_elements(unsigned num, bool allocate_storage);
138 res_list(unsigned size, bool alloc_storage = false,
139 unsigned build_sz = 5);
146 iterator head(void) {return head_ptr;};
147 iterator tail(void) {return tail_ptr;};
149 unsigned num_free(void) { return size() - count(); }
150 unsigned size(void) { return base_elements + extra_elements; }
151 unsigned count(void) { return active_elements; }
152 bool empty(void) { return count() == 0; }
156 // Insert with data copy
158 iterator insert_after(iterator prev, T *d);
159 iterator insert_after(iterator prev, T &d);
160 iterator insert_before(iterator prev, T *d);
161 iterator insert_before(iterator prev, T &d);
164 // Insert new list element (no data copy)
166 iterator insert_after(iterator prev);
167 iterator insert_before(iterator prev);
169 iterator add_tail(T *d) { return insert_after(tail_ptr, d); }
170 iterator add_tail(T &d) { return insert_after(tail_ptr, d); }
171 iterator add_tail(void) { return insert_after(tail_ptr); }
172 iterator add_head(T *d) { return insert_before(head_ptr, d); }
173 iterator add_head(T &d) { return insert_before(head_ptr, d); }
174 iterator add_head(void) { return insert_before(head_ptr); }
176 iterator remove(iterator q);
177 iterator remove_head(void) {return remove(head_ptr);}
178 iterator remove_tail(void) {return remove(tail_ptr);}
180 bool in_list(iterator j);
181 void free_extras(void);
189 res_list<T>::res_element::res_element(res_element *_prev, bool allocate)
191 allocate_data = allocate;
204 ++allocated_elements;
210 res_list<T>::res_element::~res_element(void)
222 --allocated_elements;
228 res_list<T>::res_element::dump(void)
230 cprintf(" prev = %#x\n", prev);
231 cprintf(" next = %#x\n", next);
232 cprintf(" data = %#x\n", data);
237 res_list<T>::iterator::dump(void)
243 cprintf(" Null Pointer\n");
245 cprintf(" Null 'data' Pointer\n");
251 res_list<T>::iterator::data_ptr(void)
261 // Allocate new elements, and assign them to the unused_elements
266 res_list<T>::allocate_elements(unsigned num, bool allocate_storage)
268 res_element *pnew, *plast = 0, *pfirst=0;
270 for (int i=0; i<num; ++i) {
271 pnew = new res_element(plast, allocate_storage);
277 if (unused_elements.notnull()) {
278 // Add these new elements to the front of the list
279 plast->next = unused_elements.res_el_ptr();
280 unused_elements.res_el_ptr()->prev = plast;
283 unused_elements = iterator(pfirst);
290 res_list<T>::res_list(unsigned size, bool alloc_storage, unsigned build_sz)
297 build_size = build_sz;
298 allocate_storage = alloc_storage;
301 // Create the new elements
302 base_elements = allocate_elements(size, alloc_storage);
304 // The list of active elements
305 head_ptr = iterator(0);
306 tail_ptr = iterator(0);
314 res_list<T>::~res_list(void)
322 // put everything into the unused list
325 // rudely delete all the res_elements
326 for (iterator p = unused_elements;
332 // delete the res_element
333 // (it will take care of deleting the data)
334 delete p.res_el_ptr();
340 res_list<T>::full(void)
345 return unused_elements.isnull();
349 // Insert with data copy
352 inline typename res_list<T>::iterator
353 res_list<T>::insert_after(iterator prev, T *d)
357 if (!allocate_storage)
358 this->panic("Can't copy data... not allocating storage");
360 p = insert_after(prev);
369 inline typename res_list<T>::iterator
370 res_list<T>::insert_after(iterator prev, T &d)
374 p = insert_after(prev);
377 if (allocate_storage) {
378 // if we allocate storage, then copy the contents of the
379 // specified object to our object
383 // if we don't allocate storage, then we just want to
384 // point to the specified object
394 inline typename res_list<T>::iterator
395 res_list<T>::insert_after(iterator prev)
399 if (active_elements > 2*base_elements) {
404 // If we have no unused elements, make some more
405 if (unused_elements.isnull()) {
407 if (build_size == 0) {
408 return 0; // No space left, and can't allocate more....
411 extra_elements += allocate_elements(build_size, allocate_storage);
414 // grab the first unused element
415 res_element *p = unused_elements.res_el_ptr();
417 unused_elements = unused_elements.next();
421 // Insert the new element
422 if (head_ptr.isnull()) {
424 // Special case #1: Empty List
431 else if (prev.isnull()) {
433 // Special case #2: Insert at head
436 // our next ptr points to old head element
437 p->next = head_ptr.res_el_ptr();
439 // our element becomes the new head element
442 // no previous element for the head
445 // old head element points back to this element
448 else if (prev.next().isnull()) {
450 // Special case #3 Insert at tail
453 // our prev pointer points to old tail element
454 p->prev = tail_ptr.res_el_ptr();
456 // our element becomes the new tail
459 // no next element for the tail
462 // old tail element point to this element
467 // Normal insertion (after prev)
469 p->prev = prev.res_el_ptr();
470 p->next = prev.next().res_el_ptr();
472 prev.res_el_ptr()->next = p;
480 inline typename res_list<T>::iterator
481 res_list<T>::insert_before(iterator next, T &d)
485 p = insert_before(next);
488 if (allocate_storage) {
489 // if we allocate storage, then copy the contents of the
490 // specified object to our object
494 // if we don't allocate storage, then we just want to
495 // point to the specified object
505 inline typename res_list<T>::iterator
506 res_list<T>::insert_before(iterator next)
510 if (active_elements > 2*base_elements) {
515 // If we have no unused elements, make some more
516 if (unused_elements.isnull()) {
518 if (build_size == 0) {
519 return 0; // No space left, and can't allocate more....
522 extra_elements += allocate_elements(build_size, allocate_storage);
525 // grab the first unused element
526 res_element *p = unused_elements.res_el_ptr();
528 unused_elements = unused_elements.next();
532 // Insert the new element
533 if (head_ptr.isnull()) {
535 // Special case #1: Empty List
542 else if (next.isnull()) {
544 // Special case #2 Insert at tail
547 // our prev pointer points to old tail element
548 p->prev = tail_ptr.res_el_ptr();
550 // our element becomes the new tail
553 // no next element for the tail
556 // old tail element point to this element
559 else if (next.prev().isnull()) {
561 // Special case #3: Insert at head
564 // our next ptr points to old head element
565 p->next = head_ptr.res_el_ptr();
567 // our element becomes the new head element
570 // no previous element for the head
573 // old head element points back to this element
578 // Normal insertion (before next)
580 p->next = next.res_el_ptr();
581 p->prev = next.prev().res_el_ptr();
583 next.res_el_ptr()->prev = p;
592 inline typename res_list<T>::iterator
593 res_list<T>::remove(iterator q)
595 res_element *p = q.res_el_ptr();
598 // Handle the special cases
599 if (active_elements == 1) { // This is the only element
603 else if (q == head_ptr) { // This is the head element
605 head_ptr.res_el_ptr()->prev = 0;
609 else if (q == tail_ptr) { // This is the tail element
611 tail_ptr.res_el_ptr()->next = 0;
613 else { // This is between two elements
614 p->prev->next = p->next;
615 p->next->prev = p->prev;
617 // Get the "next" element for return
623 // Put this element back onto the unused list
624 p->next = unused_elements.res_el_ptr();
626 if (p->next) { // NULL if unused list is empty
630 if (!allocate_storage) {
636 // A little "garbage collection"
637 if (++remove_count > 10) {
643 unsigned unused_count = 0;
644 for (iterator i=unused_elements;
651 assert((active_elements+unused_count) == (base_elements+extra_elements));
660 res_list<T>::in_list(iterator j)
664 for (i=head(); i.notnull(); i=i.next()) {
665 if (j.res_el_ptr() == i.res_el_ptr()) {
675 res_list<T>::free_extras(void)
677 unsigned num_unused = base_elements + extra_elements - active_elements;
678 unsigned to_free = extra_elements;
682 if (extra_elements != 0) {
684 // Free min(extra_elements, # unused elements)
686 if (extra_elements > num_unused) {
687 to_free = num_unused;
690 p = unused_elements.res_el_ptr();
691 for (int i=0; i<to_free; ++i) {
692 res_element *q = p->next;
699 // update the unused element pointer to point to the first
700 // element that wasn't deleted.
701 unused_elements = iterator(p);
703 // Update the number of extra elements
704 extra_elements -= to_free;
713 res_list<T>::clear(void)
717 for (i=head_ptr; i.notnull(); i=n) {
727 res_list<T>::dump(void)
729 for (iterator i=head(); !i.isnull(); i=i.next())
735 res_list<T>::raw_dump(void)
739 for (iterator i=head(); !i.isnull(); i=i.next()) {
740 cprintf("Element %d:\n", j);
744 cprintf(" points to res_element @ %#x\n", p);
746 cprintf(" Data Element:\n");
750 cprintf(" NULL iterator!\n");
758 #endif // __RES_LIST_HH__