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__
37 #include "base/cprintf.hh"
39 #define DEBUG_REMOVE 0
41 #define DEBUG_MEMORY 0
42 //#define DEBUG_MEMORY DEBUG
48 static long long allocated_elements;
49 static long long allocated_lists;
52 long long get_elements(void) {
53 return allocated_elements;
55 long long get_lists(void) {
56 return allocated_lists;
63 extern void what_the(void);
67 class res_list : public res_list_base
80 // always adds to the END of the list
81 res_element(res_element *_prev, bool allocate);
85 friend class res_list<T>;
86 friend class res_list<T>::iterator;
94 friend class res_list<T>;
98 iterator(res_element *q) : p(q) {}
99 iterator(void) { p=0; };
103 res_element *res_el_ptr(void) { return p;}
104 void point_to(T &d) { p->data = &d; }
106 iterator next(void) { return iterator(p->next); }
107 iterator prev(void) { return iterator(p->prev); }
108 bool operator== (iterator x) { return (x.p == this->p); }
109 bool operator != (iterator x) { return (x.p != this->p); }
110 T &operator * (void) { return *(p->data); }
111 T* operator -> (void) { return p->data; }
112 bool isnull(void) { return (p==0); }
113 bool notnull(void) { return (p!=0); }
117 iterator unused_elements;
121 unsigned base_elements;
122 unsigned extra_elements;
123 unsigned active_elements;
124 bool allocate_storage;
130 // Allocate new elements, and assign them to the unused_elements
133 unsigned allocate_elements(unsigned num, bool allocate_storage);
139 res_list(unsigned size, bool alloc_storage = false,
140 unsigned build_sz = 5);
147 iterator head(void) {return head_ptr;};
148 iterator tail(void) {return tail_ptr;};
150 unsigned num_free(void) { return size() - count(); }
151 unsigned size(void) { return base_elements + extra_elements; }
152 unsigned count(void) { return active_elements; }
153 bool empty(void) { return count() == 0; }
157 // Insert with data copy
159 iterator insert_after(iterator prev, T *d);
160 iterator insert_after(iterator prev, T &d);
161 iterator insert_before(iterator prev, T *d);
162 iterator insert_before(iterator prev, T &d);
165 // Insert new list element (no data copy)
167 iterator insert_after(iterator prev);
168 iterator insert_before(iterator prev);
170 iterator add_tail(T *d) { return insert_after(tail_ptr, d); }
171 iterator add_tail(T &d) { return insert_after(tail_ptr, d); }
172 iterator add_tail(void) { return insert_after(tail_ptr); }
173 iterator add_head(T *d) { return insert_before(head_ptr, d); }
174 iterator add_head(T &d) { return insert_before(head_ptr, d); }
175 iterator add_head(void) { return insert_before(head_ptr); }
177 iterator remove(iterator q);
178 iterator remove_head(void) {return remove(head_ptr);}
179 iterator remove_tail(void) {return remove(tail_ptr);}
181 bool in_list(iterator j);
182 void free_extras(void);
190 res_list<T>::res_element::res_element(res_element *_prev, bool allocate)
192 allocate_data = allocate;
205 ++allocated_elements;
211 res_list<T>::res_element::~res_element(void)
223 --allocated_elements;
229 res_list<T>::res_element::dump(void)
231 cprintf(" prev = %#x\n", prev);
232 cprintf(" next = %#x\n", next);
233 cprintf(" data = %#x\n", data);
238 res_list<T>::iterator::dump(void)
244 cprintf(" Null Pointer\n");
246 cprintf(" Null 'data' Pointer\n");
252 res_list<T>::iterator::data_ptr(void)
262 // Allocate new elements, and assign them to the unused_elements
267 res_list<T>::allocate_elements(unsigned num, bool allocate_storage)
269 res_element *pnew, *plast = 0, *pfirst=0;
271 for (int i=0; i<num; ++i) {
272 pnew = new res_element(plast, allocate_storage);
278 if (unused_elements.notnull()) {
279 // Add these new elements to the front of the list
280 plast->next = unused_elements.res_el_ptr();
281 unused_elements.res_el_ptr()->prev = plast;
284 unused_elements = iterator(pfirst);
291 res_list<T>::res_list(unsigned size, bool alloc_storage, unsigned build_sz)
298 build_size = build_sz;
299 allocate_storage = alloc_storage;
302 // Create the new elements
303 base_elements = allocate_elements(size, alloc_storage);
305 // The list of active elements
306 head_ptr = iterator(0);
307 tail_ptr = iterator(0);
315 res_list<T>::~res_list(void)
323 // put everything into the unused list
326 // rudely delete all the res_elements
327 for (iterator p = unused_elements;
333 // delete the res_element
334 // (it will take care of deleting the data)
335 delete p.res_el_ptr();
341 res_list<T>::full(void)
346 return unused_elements.isnull();
350 // Insert with data copy
353 inline typename res_list<T>::iterator
354 res_list<T>::insert_after(iterator prev, T *d)
358 if (!allocate_storage)
359 this->panic("Can't copy data... not allocating storage");
361 p = insert_after(prev);
370 inline typename res_list<T>::iterator
371 res_list<T>::insert_after(iterator prev, T &d)
375 p = insert_after(prev);
378 if (allocate_storage) {
379 // if we allocate storage, then copy the contents of the
380 // specified object to our object
384 // if we don't allocate storage, then we just want to
385 // point to the specified object
395 inline typename res_list<T>::iterator
396 res_list<T>::insert_after(iterator prev)
400 if (active_elements > 2*base_elements) {
405 // If we have no unused elements, make some more
406 if (unused_elements.isnull()) {
408 if (build_size == 0) {
409 return 0; // No space left, and can't allocate more....
412 extra_elements += allocate_elements(build_size, allocate_storage);
415 // grab the first unused element
416 res_element *p = unused_elements.res_el_ptr();
418 unused_elements = unused_elements.next();
422 // Insert the new element
423 if (head_ptr.isnull()) {
425 // Special case #1: Empty List
432 else if (prev.isnull()) {
434 // Special case #2: Insert at head
437 // our next ptr points to old head element
438 p->next = head_ptr.res_el_ptr();
440 // our element becomes the new head element
443 // no previous element for the head
446 // old head element points back to this element
449 else if (prev.next().isnull()) {
451 // Special case #3 Insert at tail
454 // our prev pointer points to old tail element
455 p->prev = tail_ptr.res_el_ptr();
457 // our element becomes the new tail
460 // no next element for the tail
463 // old tail element point to this element
468 // Normal insertion (after prev)
470 p->prev = prev.res_el_ptr();
471 p->next = prev.next().res_el_ptr();
473 prev.res_el_ptr()->next = p;
481 inline typename res_list<T>::iterator
482 res_list<T>::insert_before(iterator next, T &d)
486 p = insert_before(next);
489 if (allocate_storage) {
490 // if we allocate storage, then copy the contents of the
491 // specified object to our object
495 // if we don't allocate storage, then we just want to
496 // point to the specified object
506 inline typename res_list<T>::iterator
507 res_list<T>::insert_before(iterator next)
511 if (active_elements > 2*base_elements) {
516 // If we have no unused elements, make some more
517 if (unused_elements.isnull()) {
519 if (build_size == 0) {
520 return 0; // No space left, and can't allocate more....
523 extra_elements += allocate_elements(build_size, allocate_storage);
526 // grab the first unused element
527 res_element *p = unused_elements.res_el_ptr();
529 unused_elements = unused_elements.next();
533 // Insert the new element
534 if (head_ptr.isnull()) {
536 // Special case #1: Empty List
543 else if (next.isnull()) {
545 // Special case #2 Insert at tail
548 // our prev pointer points to old tail element
549 p->prev = tail_ptr.res_el_ptr();
551 // our element becomes the new tail
554 // no next element for the tail
557 // old tail element point to this element
560 else if (next.prev().isnull()) {
562 // Special case #3: Insert at head
565 // our next ptr points to old head element
566 p->next = head_ptr.res_el_ptr();
568 // our element becomes the new head element
571 // no previous element for the head
574 // old head element points back to this element
579 // Normal insertion (before next)
581 p->next = next.res_el_ptr();
582 p->prev = next.prev().res_el_ptr();
584 next.res_el_ptr()->prev = p;
593 inline typename res_list<T>::iterator
594 res_list<T>::remove(iterator q)
596 res_element *p = q.res_el_ptr();
599 // Handle the special cases
600 if (active_elements == 1) { // This is the only element
604 else if (q == head_ptr) { // This is the head element
606 head_ptr.res_el_ptr()->prev = 0;
610 else if (q == tail_ptr) { // This is the tail element
612 tail_ptr.res_el_ptr()->next = 0;
614 else { // This is between two elements
615 p->prev->next = p->next;
616 p->next->prev = p->prev;
618 // Get the "next" element for return
624 // Put this element back onto the unused list
625 p->next = unused_elements.res_el_ptr();
627 if (p->next) { // NULL if unused list is empty
631 if (!allocate_storage) {
637 // A little "garbage collection"
638 if (++remove_count > 10) {
644 unsigned unused_count = 0;
645 for (iterator i=unused_elements;
652 assert((active_elements+unused_count) == (base_elements+extra_elements));
661 res_list<T>::in_list(iterator j)
665 for (i=head(); i.notnull(); i=i.next()) {
666 if (j.res_el_ptr() == i.res_el_ptr()) {
676 res_list<T>::free_extras(void)
678 unsigned num_unused = base_elements + extra_elements - active_elements;
679 unsigned to_free = extra_elements;
683 if (extra_elements != 0) {
685 // Free min(extra_elements, # unused elements)
687 if (extra_elements > num_unused) {
688 to_free = num_unused;
691 p = unused_elements.res_el_ptr();
692 for (int i=0; i<to_free; ++i) {
693 res_element *q = p->next;
700 // update the unused element pointer to point to the first
701 // element that wasn't deleted.
702 unused_elements = iterator(p);
704 // Update the number of extra elements
705 extra_elements -= to_free;
714 res_list<T>::clear(void)
718 for (i=head_ptr; i.notnull(); i=n) {
728 res_list<T>::dump(void)
730 for (iterator i=head(); !i.isnull(); i=i.next())
736 res_list<T>::raw_dump(void)
740 for (iterator i=head(); !i.isnull(); i=i.next()) {
741 cprintf("Element %d:\n", j);
745 cprintf(" points to res_element @ %#x\n", p);
747 cprintf(" Data Element:\n");
751 cprintf(" NULL iterator!\n");
759 #endif // __RES_LIST_HH__