2 * Copyright (c) 2001-2004 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.
29 #ifndef __RES_LIST_HH__
30 #define __RES_LIST_HH__
32 #include "base/cprintf.hh"
35 #define DEBUG_REMOVE 0
37 #define DEBUG_MEMORY 0
38 //#define DEBUG_MEMORY DEBUG
44 static long long allocated_elements;
45 static long long allocated_lists;
48 long long get_elements(void) {
49 return allocated_elements;
51 long long get_lists(void) {
52 return allocated_lists;
59 extern void what_the(void);
63 class res_list : public res_list_base
76 // always adds to the END of the list
77 res_element(res_element *_prev, bool allocate);
81 friend class res_list<T>;
82 friend class res_list<T>::iterator;
90 friend class res_list<T>;
94 iterator(res_element *q) : p(q) {}
95 iterator(void) { p=0; };
99 res_element *res_el_ptr(void) { return p;}
100 void point_to(T &d) { p->data = &d; }
102 iterator next(void) { return iterator(p->next); }
103 iterator prev(void) { return iterator(p->prev); }
104 bool operator== (iterator x) { return (x.p == this->p); }
105 bool operator != (iterator x) { return (x.p != this->p); }
106 T &operator * (void) { return *(p->data); }
107 T* operator -> (void) { return p->data; }
108 bool isnull(void) { return (p==0); }
109 bool notnull(void) { return (p!=0); }
113 iterator unused_elements;
117 unsigned base_elements;
118 unsigned extra_elements;
119 unsigned active_elements;
120 bool allocate_storage;
126 // Allocate new elements, and assign them to the unused_elements
129 unsigned allocate_elements(unsigned num, bool allocate_storage);
135 res_list(unsigned size, bool alloc_storage = false,
136 unsigned build_sz = 5);
143 iterator head(void) {return head_ptr;};
144 iterator tail(void) {return tail_ptr;};
146 unsigned num_free(void) { return size() - count(); }
147 unsigned size(void) { return base_elements + extra_elements; }
148 unsigned count(void) { return active_elements; }
149 bool empty(void) { return count() == 0; }
153 // Insert with data copy
155 iterator insert_after(iterator prev, T *d);
156 iterator insert_after(iterator prev, T &d);
157 iterator insert_before(iterator prev, T *d);
158 iterator insert_before(iterator prev, T &d);
161 // Insert new list element (no data copy)
163 iterator insert_after(iterator prev);
164 iterator insert_before(iterator prev);
166 iterator add_tail(T *d) { return insert_after(tail_ptr, d); }
167 iterator add_tail(T &d) { return insert_after(tail_ptr, d); }
168 iterator add_tail(void) { return insert_after(tail_ptr); }
169 iterator add_head(T *d) { return insert_before(head_ptr, d); }
170 iterator add_head(T &d) { return insert_before(head_ptr, d); }
171 iterator add_head(void) { return insert_before(head_ptr); }
173 iterator remove(iterator q);
174 iterator remove_head(void) {return remove(head_ptr);}
175 iterator remove_tail(void) {return remove(tail_ptr);}
177 bool in_list(iterator j);
178 void free_extras(void);
186 res_list<T>::res_element::res_element(res_element *_prev, bool allocate)
188 allocate_data = allocate;
201 ++allocated_elements;
207 res_list<T>::res_element::~res_element(void)
219 --allocated_elements;
225 res_list<T>::res_element::dump(void)
227 cprintf(" prev = %#x\n", prev);
228 cprintf(" next = %#x\n", next);
229 cprintf(" data = %#x\n", data);
234 res_list<T>::iterator::dump(void)
240 cprintf(" Null Pointer\n");
242 cprintf(" Null 'data' Pointer\n");
248 res_list<T>::iterator::data_ptr(void)
258 // Allocate new elements, and assign them to the unused_elements
263 res_list<T>::allocate_elements(unsigned num, bool allocate_storage)
265 res_element *pnew, *plast = 0, *pfirst=0;
267 for (int i=0; i<num; ++i) {
268 pnew = new res_element(plast, allocate_storage);
274 if (unused_elements.notnull()) {
275 // Add these new elements to the front of the list
276 plast->next = unused_elements.res_el_ptr();
277 unused_elements.res_el_ptr()->prev = plast;
280 unused_elements = iterator(pfirst);
287 res_list<T>::res_list(unsigned size, bool alloc_storage, unsigned build_sz)
294 build_size = build_sz;
295 allocate_storage = alloc_storage;
298 // Create the new elements
299 base_elements = allocate_elements(size, alloc_storage);
301 // The list of active elements
302 head_ptr = iterator(0);
303 tail_ptr = iterator(0);
311 res_list<T>::~res_list(void)
319 // put everything into the unused list
322 // rudely delete all the res_elements
323 for (iterator p = unused_elements;
329 // delete the res_element
330 // (it will take care of deleting the data)
331 delete p.res_el_ptr();
337 res_list<T>::full(void)
342 return unused_elements.isnull();
346 // Insert with data copy
349 inline typename res_list<T>::iterator
350 res_list<T>::insert_after(iterator prev, T *d)
354 if (!allocate_storage)
355 panic("Can't copy data... not allocating storage");
357 p = insert_after(prev);
366 inline typename res_list<T>::iterator
367 res_list<T>::insert_after(iterator prev, T &d)
371 p = insert_after(prev);
374 if (allocate_storage) {
375 // if we allocate storage, then copy the contents of the
376 // specified object to our object
380 // if we don't allocate storage, then we just want to
381 // point to the specified object
391 inline typename res_list<T>::iterator
392 res_list<T>::insert_after(iterator prev)
396 if (active_elements > 2*base_elements) {
401 // If we have no unused elements, make some more
402 if (unused_elements.isnull()) {
404 if (build_size == 0) {
405 return 0; // No space left, and can't allocate more....
408 extra_elements += allocate_elements(build_size, allocate_storage);
411 // grab the first unused element
412 res_element *p = unused_elements.res_el_ptr();
414 unused_elements = unused_elements.next();
418 // Insert the new element
419 if (head_ptr.isnull()) {
421 // Special case #1: Empty List
428 else if (prev.isnull()) {
430 // Special case #2: Insert at head
433 // our next ptr points to old head element
434 p->next = head_ptr.res_el_ptr();
436 // our element becomes the new head element
439 // no previous element for the head
442 // old head element points back to this element
445 else if (prev.next().isnull()) {
447 // Special case #3 Insert at tail
450 // our prev pointer points to old tail element
451 p->prev = tail_ptr.res_el_ptr();
453 // our element becomes the new tail
456 // no next element for the tail
459 // old tail element point to this element
464 // Normal insertion (after prev)
466 p->prev = prev.res_el_ptr();
467 p->next = prev.next().res_el_ptr();
469 prev.res_el_ptr()->next = p;
477 inline typename res_list<T>::iterator
478 res_list<T>::insert_before(iterator next, T &d)
482 p = insert_before(next);
485 if (allocate_storage) {
486 // if we allocate storage, then copy the contents of the
487 // specified object to our object
491 // if we don't allocate storage, then we just want to
492 // point to the specified object
502 inline typename res_list<T>::iterator
503 res_list<T>::insert_before(iterator next)
507 if (active_elements > 2*base_elements) {
512 // If we have no unused elements, make some more
513 if (unused_elements.isnull()) {
515 if (build_size == 0) {
516 return 0; // No space left, and can't allocate more....
519 extra_elements += allocate_elements(build_size, allocate_storage);
522 // grab the first unused element
523 res_element *p = unused_elements.res_el_ptr();
525 unused_elements = unused_elements.next();
529 // Insert the new element
530 if (head_ptr.isnull()) {
532 // Special case #1: Empty List
539 else if (next.isnull()) {
541 // Special case #2 Insert at tail
544 // our prev pointer points to old tail element
545 p->prev = tail_ptr.res_el_ptr();
547 // our element becomes the new tail
550 // no next element for the tail
553 // old tail element point to this element
556 else if (next.prev().isnull()) {
558 // Special case #3: Insert at head
561 // our next ptr points to old head element
562 p->next = head_ptr.res_el_ptr();
564 // our element becomes the new head element
567 // no previous element for the head
570 // old head element points back to this element
575 // Normal insertion (before next)
577 p->next = next.res_el_ptr();
578 p->prev = next.prev().res_el_ptr();
580 next.res_el_ptr()->prev = p;
589 inline typename res_list<T>::iterator
590 res_list<T>::remove(iterator q)
592 res_element *p = q.res_el_ptr();
595 // Handle the special cases
596 if (active_elements == 1) { // This is the only element
600 else if (q == head_ptr) { // This is the head element
602 head_ptr.res_el_ptr()->prev = 0;
606 else if (q == tail_ptr) { // This is the tail element
608 tail_ptr.res_el_ptr()->next = 0;
610 else { // This is between two elements
611 p->prev->next = p->next;
612 p->next->prev = p->prev;
614 // Get the "next" element for return
620 // Put this element back onto the unused list
621 p->next = unused_elements.res_el_ptr();
623 if (p->next) { // NULL if unused list is empty
627 if (!allocate_storage) {
633 // A little "garbage collection"
634 if (++remove_count > 10) {
640 unsigned unused_count = 0;
641 for (iterator i=unused_elements;
648 assert((active_elements+unused_count) == (base_elements+extra_elements));
657 res_list<T>::in_list(iterator j)
661 for (i=head(); i.notnull(); i=i.next()) {
662 if (j.res_el_ptr() == i.res_el_ptr()) {
672 res_list<T>::free_extras(void)
674 unsigned num_unused = base_elements + extra_elements - active_elements;
675 unsigned to_free = extra_elements;
679 if (extra_elements != 0) {
681 // Free min(extra_elements, # unused elements)
683 if (extra_elements > num_unused) {
684 to_free = num_unused;
687 p = unused_elements.res_el_ptr();
688 for (int i=0; i<to_free; ++i) {
689 res_element *q = p->next;
696 // update the unused element pointer to point to the first
697 // element that wasn't deleted.
698 unused_elements = iterator(p);
700 // Update the number of extra elements
701 extra_elements -= to_free;
710 res_list<T>::clear(void)
714 for (i=head_ptr; i.notnull(); i=n) {
724 res_list<T>::dump(void)
726 for (iterator i=head(); !i.isnull(); i=i.next())
732 res_list<T>::raw_dump(void)
736 for (iterator i=head(); !i.isnull(); i=i.next()) {
737 cprintf("Element %d:\n", j);
741 cprintf(" points to res_element @ %#x\n", p);
743 cprintf(" Data Element:\n");
747 cprintf(" NULL iterator!\n");
755 #endif // __RES_LIST_HH__