/* Sun-$Revision: 23.6 $ */ /* Copyright 1992-9 Sun Microsystems, Inc. and Stanford University. See the LICENSE file for license information. */ # pragma interface inline int32 addressHash(void* v, int32 m) { return lowerBits(int32(v) >> 5, m); } enum { tcCList = 4000 }; class Clist; struct CListEntry: ResourceObj { virtual bool EQ(CListEntry* e) { return this == e; } int32 identityHash(int32 m) { // use address as source of hash for identity hash tables return addressHash(this, m); } virtual CListEntry* realDeepCopy() { return this; } CListEntry* deepCopy() { return realDeepCopy(); } // memory operations - only here because it's now possible for ResourceObjs // to reside in the CHeap. virtual void scavenge_contents() { } virtual void gc_mark_contents() { } virtual void gc_unmark_contents() { } virtual void verify() { } virtual void switch_pointers(oop from, oop to) { Unused(from); Unused(to); } virtual void relocate() { } virtual void oops_do(oopsDoFn f) { Unused((void*)f); } }; struct HashTableKey: CListEntry { virtual int32 hash(int32 m) { return identityHash(m); } }; struct CListElem: ResourceObj { CListEntry* _data; CListElem* _next; CListElem(CListEntry* d, CListElem* n = NULL) { _data = d; _next = n; } ~CListElem() { delete _data; if (_next) { delete _next; } } CListEntry* data() { return _data; } void setData(CListEntry* d) { _data = d; } CListElem* next() { return _next; } void setNext(CListElem* n) { _next = n; } void insertAfter(CListEntry* d) { _next = new CListElem(d, _next); } }; struct CList: CListEntry { CListElem* _head; CListElem* _tail; CList(CListEntry* d, CList* l) { _head = _tail = new CListElem(d); appendList(l); } CList() { _head = _tail = NULL; } CList(CListEntry* d) { _head = _tail = new CListElem(d); } CList(CListEntry* d1, CListEntry* d2) { _tail = new CListElem(d2); _head = new CListElem(d1, _tail); } CList(CListEntry* d1, CListEntry* d2, CListEntry* d3) { _tail = new CListElem(d3); _head = new CListElem(d1, new CListElem(d2, _tail)); } CList(CListEntry* d1, CListEntry* d2, CListEntry* d3, CListEntry* d4) { _tail = new CListElem(d4); _head = new CListElem(d1, new CListElem(d2, new CListElem(d3, _tail))); } CList(CListEntry* d1, CListEntry* d2, CListEntry* d3, CListEntry* d4, CListEntry* d5) { _tail = new CListElem(d5); _head = new CListElem(d1, new CListElem(d2, new CListElem(d3, new CListElem(d4, _tail)))); } ~CList() { if (this) { delete _head; _head = _tail = NULL; } } CList* prepend(CListEntry* d) { if (this == EMPTY) { return new CList(d); } else { _head = new CListElem(d, _head); if (_tail == NULL) { _tail = _head; } return this; } } CList* prependList(CList* l); CList* append(CListEntry* d) { CListElem* e; if (this == EMPTY) { return new CList(d); } else { e = new CListElem(d); if (_tail == NULL) { _head = _tail = e; } else { _tail->_next = e; _tail = e; } return this; } } CList* appendList(CList* l); CListElem* head() { return this ? _head : NULL; } void setHead(CListElem* h) { _head = h; } CListElem* tail() { return this ? _tail : NULL; } void setTail(CListElem* t) { assert(t || !_head, "probably doesn't do what you want; use appendList"); _tail = t;} CList* copy(); CListEntry* realDeepCopy(); CList* deepCopy() { if (isEmpty()) { return EMPTY; } else { return (CList*)realDeepCopy(); } } CList* reverse(); // memory operations - needed for ResourceObjs that have been allocated in // the CHeap. void scavenge_contents(); void gc_mark_contents(); void gc_unmark_contents(); void verify(); void switch_pointers(oop from, oop to); void relocate(); void oops_do(oopsDoFn f); bool isEmpty() { return this == EMPTY || _head == NULL; } bool nonEmpty() { return ! isEmpty(); } bool isSingleton() { return this != EMPTY && _head != NULL && _head == _tail; } bool nonSingleton() { return !isSingleton(); } int32 length(); CListEntry* nth(fint i); void nthPut(fint i, CListEntry* d); CListEntry* first() { return head()->data(); } CListEntry* second() { return head()->next()->data(); } CListEntry* last() { return tail()->data(); } bool includes(CListEntry* d); bool includesList(CList* l); bool includesAny(CList* l); bool EQ(CListEntry* l) { return EQlist((CList*) l); } bool EQlist(CList* l); bool identityIncludes(CListEntry* d); bool identityIncludesList(CList* l); bool identityIncludesAny(CList* l); bool identityEQ(CList* l); bool identityNE(CList* l) { return !identityEQ(l); } CList* add(CListEntry* d) { return includes(d) ? this : append(d); } CList* addList(CList* l); CList* identityAdd(CListEntry* d) { return identityIncludes(d) ? this : append(d); } CList* identityAddList(CList* l); void remove(CListEntry* d); void removeList(CList* l); void identityRemove(CListEntry* d); void identityRemoveList(CList* l); # ifdef UNUSED CList* intersection(CList* l, bool makeCopy); # endif CList* identityIntersection(CList* l, bool makeCopy); CListElem* spliceOutNext(CListElem* e); CListEntry* removeHead() { assert(nonEmpty(), "removing from an empty list"); CListEntry* d = first(); spliceOutNext(NULL); return d; } CList* push(CListEntry* d) { return prepend(d); } CList* pushList(CList* l) { return prependList(l); } CListEntry* pop() { return removeHead(); } CList* pop(fint count); void print(); void print_short(); }; # define ListTemplate(name,dataType) \ struct CONC(name,ListElem): CListElem { \ CONC(name,ListElem)(dataType d, CONC(name,ListElem)* n = NULL) \ : CListElem((CListEntry*) d, (CListElem*) n) {} \ \ dataType data() { return (dataType) CListElem::data(); } \ void setData(dataType d) { CListElem::setData((CListEntry*) d); } \ \ CONC(name,ListElem)* next() { \ return (CONC(name,ListElem)*) CListElem::next(); } \ void setNext(CONC(name,ListElem)* n) { CListElem::setNext(n); } \ \ void insertAfter(dataType d) { CListElem::insertAfter((CListEntry*) d); } \ }; \ \ struct CONC(name,List): CList { \ CONC(name,List)(dataType d, CONC(name,List)* l) \ : CList((CListEntry*) d, (CList*) l) {} \ CONC(name,List)() {} \ CONC(name,List)(dataType d) : CList((CListEntry*) d) {} \ CONC(name,List)(dataType d1, dataType d2) \ : CList((CListEntry*) d1, (CListEntry*) d2) {} \ CONC(name,List)(dataType d1, dataType d2, dataType d3) \ : CList((CListEntry*) d1, (CListEntry*) d2, (CListEntry*) d3) {} \ CONC(name,List)(dataType d1, dataType d2, dataType d3, dataType d4) \ : CList((CListEntry*) d1, (CListEntry*) d2, (CListEntry*) d3, \ (CListEntry*) d4) {} \ CONC(name,List)(dataType d1, dataType d2, dataType d3, dataType d4, \ dataType d5) \ : CList((CListEntry*) d1, (CListEntry*) d2, (CListEntry*) d3, \ (CListEntry*) d4, (CListEntry*) d5) {} \ \ CONC(name,ListElem)* head() { \ return (CONC(name,ListElem)*) CList::head(); } \ void setHead(CONC(name,ListElem)* h) { \ CList::setHead((CONC(name,ListElem)*) h); } \ CONC(name,ListElem)* tail() { \ return (CONC(name,ListElem)*) CList::tail(); } \ void setTail(CONC(name,ListElem)* t) { \ CList::setTail((CONC(name,ListElem)*) t); } \ \ dataType first() { return (dataType) CList::first(); } \ dataType second() { return (dataType) CList::second(); } \ dataType last() { return (dataType) CList::last(); } \ \ CONC(name,List)* prepend(dataType d) { \ return (CONC(name,List)*) CList::prepend((CListEntry*) d); } \ CONC(name,List)* prepend(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::prependList((CList*) l); } \ CONC(name,List)* append(dataType d) { \ return (CONC(name,List)*) CList::append((CListEntry*) d); } \ CONC(name,List)* append(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::appendList((CList*) l); } \ \ CONC(name,List)* copy() { return (CONC(name,List)*) CList::copy(); } \ CONC(name,List)* deepCopy() { \ return (CONC(name,List)*) CList::deepCopy(); } \ CONC(name,List)* reverse() { \ return (CONC(name,List)*) CList::reverse(); } \ \ dataType nth(fint i) { return (dataType) CList::nth(i); } \ void nthPut(fint i, dataType d) { CList::nthPut(i, (CListEntry*) d); } \ \ bool includes(dataType d) { return CList::includes((CListEntry*) d); } \ bool includes(CONC(name,List)* l) { \ return CList::includesList((CList*) l); } \ bool includesAny(CONC(name,List)* l) { \ return CList::includesAny((CList*) l); } \ \ CONC(name,List)* add(dataType d) { \ return (CONC(name,List)*) CList::add((CListEntry*) d); } \ CONC(name,List)* add(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::addList((CList*) l); } \ \ CONC(name,ListElem)* spliceOutNext(CONC(name,ListElem)* e) { \ return (CONC(name,ListElem)*) CList::spliceOutNext((CListElem*) e); } \ void remove(dataType d) { CList::remove((CListEntry*) d); } \ void remove(CONC(name,List)* l) { CList::removeList((CList*) l); } \ \ dataType removeHead() { return (dataType) CList::removeHead(); } \ \ CONC(name,List)* push(dataType d) { \ return (CONC(name,List)*) CList::push((CListEntry*) d); } \ CONC(name,List)* push(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::pushList(l); } \ dataType pop() { return (dataType) CList::pop(); } \ CONC(name,List)* pop(fint count) { \ return (CONC(name,List)*) CList::pop(count); } \ }; // this was part of the interface #ifdef UNUSED CONC(name,List)* intersection(CONC(name,List)* l, bool makeCopy = true) { \ return (CONC(name,List)*) CList::intersection(l, makeCopy); } \ #endif # define IdentityListTemplate(name,dataType) \ struct CONC(name,ListElem): CListElem { \ CONC(name,ListElem)(dataType d, CONC(name,ListElem)* n = NULL) \ : CListElem((CListEntry*) d, (CListElem*) n) {} \ \ dataType data() { return (dataType) CListElem::data(); } \ void setData(dataType d) { CListElem::setData((CListEntry*) d); } \ \ CONC(name,ListElem)* next() { \ return (CONC(name,ListElem)*) CListElem::next(); } \ void setNext(CONC(name,ListElem)* n) { CListElem::setNext(n); } \ \ void insertAfter(dataType d) { CListElem::insertAfter((CListEntry*) d); } \ }; \ \ struct CONC(name,List): CList { \ CONC(name,List)(dataType d, CONC(name,List)* l) \ : CList((CListEntry*) d, (CList*) l) {} \ CONC(name,List)() {} \ CONC(name,List)(dataType d) \ : CList((CListEntry*) d) {} \ CONC(name,List)(dataType d1, dataType d2) \ : CList((CListEntry*) d1, (CListEntry*) d2) {} \ CONC(name,List)(dataType d1, dataType d2, dataType d3) \ : CList((CListEntry*) d1, (CListEntry*) d2, (CListEntry*) d3) {} \ CONC(name,List)(dataType d1, dataType d2, dataType d3, dataType d4) \ : CList((CListEntry*) d1, (CListEntry*) d2, (CListEntry*) d3, \ (CListEntry*) d4) {} \ CONC(name,List)(dataType d1, dataType d2, dataType d3, dataType d4, \ dataType d5) \ : CList((CListEntry*) d1, (CListEntry*) d2, (CListEntry*) d3, \ (CListEntry*) d4, (CListEntry*) d5) {} \ \ CONC(name,ListElem)* head() { \ return (CONC(name,ListElem)*) CList::head(); } \ void setHead(CONC(name,ListElem)* t) { \ CList::setHead((CONC(name,ListElem)*) t); } \ CONC(name,ListElem)* tail() { \ return (CONC(name,ListElem)*) CList::tail(); } \ void setTail(CONC(name,ListElem)* t) { \ CList::setTail((CONC(name,ListElem)*) t); } \ \ dataType first() { return (dataType) CList::first(); } \ dataType second() { return (dataType) CList::second(); } \ dataType last() { return (dataType) CList::last(); } \ \ CONC(name,List)* prepend(dataType d) { \ return (CONC(name,List)*) CList::prepend((CListEntry*) d); } \ CONC(name,List)* prepend(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::prependList((CList*) l); } \ CONC(name,List)* append(dataType d) { \ return (CONC(name,List)*) CList::append((CListEntry*) d); } \ CONC(name,List)* append(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::appendList((CList*) l); } \ \ CONC(name,List)* copy() { return (CONC(name,List)*) CList::copy(); } \ CONC(name,List)* reverse() { \ return (CONC(name,List)*) CList::reverse(); } \ \ dataType nth(fint i) { return (dataType) CList::nth(i); } \ void nthPut(fint i, dataType d) { CList::nthPut(i, (CListEntry*) d); } \ \ bool includes(dataType d) { \ return CList::identityIncludes((CListEntry*) d); } \ bool includes(CONC(name,List)* l) { \ return CList::identityIncludesList((CList*) l); } \ bool includesAny(CONC(name,List)* l) { \ return CList::identityIncludesAny((CList*) l); } \ \ bool EQ(CListEntry* l) { \ return CList::identityEQ((CList*) l); } \ \ CONC(name,List)* add(dataType d) { \ return (CONC(name,List)*) CList::identityAdd((CListEntry*) d); } \ CONC(name,List)* add(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::identityAddList((CList*) l); } \ \ CONC(name,ListElem)* spliceOutNext(CONC(name,ListElem)* e) { \ return (CONC(name,ListElem)*) CList::spliceOutNext((CListElem*) e); } \ void remove(dataType d) { CList::identityRemove((CListEntry*) d); } \ void remove(CONC(name,List)* l) { \ CList::identityRemoveList((CList*) l); } \ \ CONC(name,List)* intersection(CONC(name,List)* l, bool makeCopy = true) { \ return (CONC(name,List)*) CList::identityIntersection(l, makeCopy); } \ \ dataType removeHead() { return (dataType) CList::removeHead(); } \ \ CONC(name,List)* push(dataType d) { \ return (CONC(name,List)*) CList::push((CListEntry*) d); } \ CONC(name,List)* push(CONC(name,List)* l) { \ return (CONC(name,List)*) CList::pushList(l); } \ dataType pop() { return (dataType) CList::pop(); } \ CONC(name,List)* pop(fint count) { \ return (CONC(name,List)*) CList::pop(count); } \ }; \ \ \ struct CONC(name,ListStream): AnywhereObj { \ CONC(name,ListElem)* rest; \ dataType current; \ \ void init(CONC(name,List)* lst, dataType none) { \ if (lst->nonEmpty()) { rest=lst->head(); advance(); } \ else { rest= NULL; current= none; } \ } \ void advance() { if (rest) { current= rest->data(); rest= rest->next();} }\ void print_short() { lprintf("rest %#lx, current %#lx\n", \ (long unsigned)rest, (long unsigned)current); \ } \ }; struct lookupTarget; IdentityListTemplate(lookupTarget,lookupTarget*) struct abstractSlotRef; ListTemplate(abstractSlotRef,abstractSlotRef*) struct LookupMarker; IdentityListTemplate(LookupMarker,LookupMarker*) IdentityListTemplate(Int,int32) IdentityListTemplate(StringOop,stringOop) IdentityListTemplate(Oop, oop)