[patch] Patch from Tom Lane, improving linked list implementation

pg.patch (text/plain), 10.25 KB, created by David Blewett on 2006-12-19 17:01:39 UTC

diff -cr openjade-1.3.2.orig/style/ELObj.cxx openjade-1.3.2/style/ELObj.cxx
*** openjade-1.3.2.orig/style/ELObj.cxx	Fri Jan 11 10:48:38 2002
--- openjade-1.3.2/style/ELObj.cxx	Sat Dec  9 21:58:36 2006
***************
*** 1044,1049 ****
--- 1044,1054 ----
    return new (interp) ReverseNodeListObj(this);
  }
  
+ NodeListObj *NodeListObj::nodeListAppend(NodeListObj *newTail, Interpreter &interp)
+ {
+   return new (interp) HeadNodeListObj(this, newTail, interp);
+ }
+ 
  long NodeListObj::nodeListLength(EvalContext &context, Interpreter &interp)
  {
    NodeListObj *nl = this;
***************
*** 1217,1236 ****
  
  NodeListObj *PairNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
  {
!   if (!head_ || !head_->nodeListFirst(context, interp))
      return tail_->nodeListRest(context, interp);
    NodeListObj *tem = head_->nodeListRest(context, interp);
    ELObjDynamicRoot protect(interp, tem);
!   return new (interp) PairNodeListObj(tem, tail_);
  }
  
  NodeListObj *PairNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
  {
!   if (!head_ || !head_->nodeListFirst(context, interp))
      return tail_->nodeListChunkRest(context, interp, chunk);
    NodeListObj *tem = head_->nodeListChunkRest(context, interp, chunk);
    ELObjDynamicRoot protect(interp, tem);
!   return new (interp) PairNodeListObj(tem, tail_);
  }
  
  void PairNodeListObj::traceSubObjects(Collector &c) const
--- 1222,1260 ----
  
  NodeListObj *PairNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
  {
!   if (!head_)
!     return tail_->nodeListRest(context, interp);
!   if (!head_->nodeListFirst(context, interp)) {
!     head_ = 0;
      return tail_->nodeListRest(context, interp);
+   }
    NodeListObj *tem = head_->nodeListRest(context, interp);
    ELObjDynamicRoot protect(interp, tem);
!   if (!tem || !tem->nodeListFirst(context, interp))
!     return tail_;
!   return tem->nodeListAppend(tail_, interp);
  }
  
  NodeListObj *PairNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
  {
!   if (!head_)
!     return tail_->nodeListChunkRest(context, interp, chunk);
!   if (!head_->nodeListFirst(context, interp)) {
!     head_ = 0;
      return tail_->nodeListChunkRest(context, interp, chunk);
+   }
    NodeListObj *tem = head_->nodeListChunkRest(context, interp, chunk);
    ELObjDynamicRoot protect(interp, tem);
!   if (!tem || !tem->nodeListFirst(context, interp))
!     return tail_;
!   return tem->nodeListAppend(tail_, interp);
! }
! 
! NodeListObj *PairNodeListObj::nodeListAppend(NodeListObj *newTail, Interpreter &interp)
! {
!   NodeListObj *tem = new (interp) PairNodeListObj(tail_, newTail);
!   ELObjDynamicRoot protect(interp, tem);
!   return new (interp) PairNodeListObj(head_, tem);
  }
  
  void PairNodeListObj::traceSubObjects(Collector &c) const
***************
*** 1239,1244 ****
--- 1263,1384 ----
    c.trace(tail_);
  }
  
+ CellNodeListObj::CellNodeListObj(NodeListObj *head)
+ : head_(head), next_(0)
+ {
+   hasSubObjects_ = 1;
+ }
+ 
+ NodePtr CellNodeListObj::nodeListFirst(EvalContext &context, Interpreter &interp)
+ {
+   if (head_) {
+     NodePtr nd(head_->nodeListFirst(context, interp));
+     if (nd)
+       return nd;
+     head_ = 0;
+   }
+   if (next_)
+     return next_->nodeListFirst(context, interp);
+   return NodePtr();
+ }
+ 
+ NodeListObj *CellNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
+ {
+   if (!head_) {
+     if (next_)
+       return next_->nodeListRest(context, interp);
+     return interp.makeEmptyNodeList();
+   }
+   if (!head_->nodeListFirst(context, interp)) {
+     head_ = 0;
+     if (next_)
+       return next_->nodeListRest(context, interp);
+     return interp.makeEmptyNodeList();
+   }
+   NodeListObj *tem = head_->nodeListRest(context, interp);
+   ELObjDynamicRoot protect(interp, tem);
+   if (!tem || !tem->nodeListFirst(context, interp)) {
+     if (next_)
+       return next_;
+     return interp.makeEmptyNodeList();
+   }
+   if (next_)
+     return tem->nodeListAppend(next_, interp);
+   return tem;
+ }
+ 
+ NodeListObj *CellNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
+ {
+   if (!head_) {
+     if (next_)
+       return next_->nodeListChunkRest(context, interp, chunk);
+     chunk = 0;
+     return interp.makeEmptyNodeList();
+   }
+   if (!head_->nodeListFirst(context, interp)) {
+     head_ = 0;
+     if (next_)
+       return next_->nodeListChunkRest(context, interp, chunk);
+     chunk = 0;
+     return interp.makeEmptyNodeList();
+   }
+   NodeListObj *tem = head_->nodeListChunkRest(context, interp, chunk);
+   ELObjDynamicRoot protect(interp, tem);
+   if (!tem || !tem->nodeListFirst(context, interp)) {
+     if (next_)
+       return next_;
+     return interp.makeEmptyNodeList();
+   }
+   if (next_)
+     return tem->nodeListAppend(next_, interp);
+   return tem;
+ }
+ 
+ void CellNodeListObj::traceSubObjects(Collector &c) const
+ {
+   c.trace(head_);
+   c.trace(next_);
+ }
+ 
+ HeadNodeListObj::HeadNodeListObj(NodeListObj *first, NodeListObj *second, Interpreter &interp)
+ : first_(0), last_(0)
+ {
+   hasSubObjects_ = 1;
+   ELObjDynamicRoot protect(interp, this);
+   first_ = new (interp) CellNodeListObj(first);
+   last_ = new (interp) CellNodeListObj(second);
+   first_->next_ = last_;
+ }
+ 
+ NodePtr HeadNodeListObj::nodeListFirst(EvalContext &context, Interpreter &interp)
+ {
+   return first_->nodeListFirst(context, interp);
+ }
+ 
+ NodeListObj *HeadNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
+ {
+   return first_->nodeListRest(context, interp);
+ }
+ 
+ NodeListObj *HeadNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
+ {
+   return first_->nodeListChunkRest(context, interp, chunk);
+ }
+ 
+ NodeListObj *HeadNodeListObj::nodeListAppend(NodeListObj *newTail, Interpreter &interp)
+ {
+   CellNodeListObj *tem = new (interp) CellNodeListObj(newTail);
+   last_->next_ = tem;
+   last_ = tem;
+   return this;
+ }
+ 
+ void HeadNodeListObj::traceSubObjects(Collector &c) const
+ {
+   c.trace(first_);
+   // first_ will recurse to the rest
+ }
+ 
  ReverseNodeListObj::ReverseNodeListObj(NodeListObj *nl)
  : nl_(nl), reversed_(0)
  {
diff -cr openjade-1.3.2.orig/style/ELObj.h openjade-1.3.2/style/ELObj.h
*** openjade-1.3.2.orig/style/ELObj.h	Fri Jan 11 10:48:38 2002
--- openjade-1.3.2/style/ELObj.h	Sat Dec  9 20:14:23 2006
***************
*** 426,431 ****
--- 426,432 ----
    virtual NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &chunk);
    virtual NodePtr nodeListRef(long, EvalContext &, Interpreter &);
    virtual NodeListObj *nodeListReverse(EvalContext &, Interpreter &);
+   virtual NodeListObj *nodeListAppend(NodeListObj *, Interpreter &);
    virtual long nodeListLength(EvalContext &, Interpreter &);
    virtual bool suppressError();
  };
***************
*** 493,504 ****
--- 494,533 ----
    NodePtr nodeListFirst(EvalContext &, Interpreter &);
    NodeListObj *nodeListRest(EvalContext &, Interpreter &);
    NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &);
+   NodeListObj *nodeListAppend(NodeListObj *, Interpreter &);
    void traceSubObjects(Collector &) const;
  private:
    NodeListObj *head_; // may be null
    NodeListObj *tail_;
  };
  
+ class CellNodeListObj : public NodeListObj {
+ public:
+   CellNodeListObj(NodeListObj *);
+   NodePtr nodeListFirst(EvalContext &, Interpreter &);
+   NodeListObj *nodeListRest(EvalContext &, Interpreter &);
+   NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &);
+   void traceSubObjects(Collector &) const;
+ private:
+   NodeListObj *head_; // may be null
+   CellNodeListObj *next_; // may be null
+   friend class HeadNodeListObj; // needs access to next_ link
+ };
+ 
+ class HeadNodeListObj : public NodeListObj {
+ public:
+   HeadNodeListObj(NodeListObj *, NodeListObj *, Interpreter &);
+   NodePtr nodeListFirst(EvalContext &, Interpreter &);
+   NodeListObj *nodeListRest(EvalContext &, Interpreter &);
+   NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &);
+   NodeListObj *nodeListAppend(NodeListObj *, Interpreter &);
+   void traceSubObjects(Collector &) const;
+ private:
+   // there are always at least two cells in the list, hence first_ != last_
+   CellNodeListObj *first_;
+   CellNodeListObj *last_;
+ };
+ 
  inline
  bool ELObj::equal(ELObj &obj1, ELObj &obj2)
  {
diff -cr openjade-1.3.2.orig/style/primitive.cxx openjade-1.3.2/style/primitive.cxx
*** openjade-1.3.2.orig/style/primitive.cxx	Wed Mar 13 07:21:22 2002
--- openjade-1.3.2/style/primitive.cxx	Sat Dec  9 21:48:01 2006
***************
*** 3846,3870 ****
  
  DEFPRIMITIVE(NodeList, argc, argv, context, interp, loc)
  {
!   if (argc == 0)
      return interp.makeEmptyNodeList();
!   int i = argc - 1;
!   NodeListObj *nl = argv[i]->asNodeList();
    if (!nl)
      return argError(interp, loc,
! 		    InterpreterMessages::notANodeList, i, argv[i]);
!   if (i > 0) {
!     ELObjDynamicRoot protect(interp, nl);
!     for (;;) {
!       i--;
        NodeListObj *tem = argv[i]->asNodeList();
        if (!tem)
!         return argError(interp, loc,
! 	                InterpreterMessages::notANodeList, i, argv[i]);
!       nl = new (interp) PairNodeListObj(tem, nl);
!       if (i == 0)
! 	break;
!       protect = nl;
      }
    }
    return nl;
--- 3846,3868 ----
  
  DEFPRIMITIVE(NodeList, argc, argv, context, interp, loc)
  {
!   if (argc <= 0)
      return interp.makeEmptyNodeList();
!   NodeListObj *nl = argv[0]->asNodeList();
    if (!nl)
      return argError(interp, loc,
! 		    InterpreterMessages::notANodeList, 0, argv[0]);
!   if (argc > 1) {
!     ELObjDynamicRoot protect(interp);
!     ELObjDynamicRoot protect2(interp);
!     for (int i = 1; i < argc; i++) {
!       protect = nl;
        NodeListObj *tem = argv[i]->asNodeList();
        if (!tem)
! 	return argError(interp, loc,
! 			InterpreterMessages::notANodeList, i, argv[i]);
!       protect2 = tem;
!       nl = nl->nodeListAppend(tem, interp);
      }
    }
    return nl;