ooRexx  4.2.0-source
About: ooRexx (Open Object Rexx) is a free implementation of Object Rexx. Object Rexx is an enhancement of the classic Rexx interpreter; a full-featured programming language with a human-oriented syntax.
  Fossies Dox: ooRexx-4.2.0-source.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation)  

RexxCompoundTable.cpp
Go to the documentation of this file.
1 /*----------------------------------------------------------------------------*/
2 /* */
3 /* Copyright (c) 1995, 2004 IBM Corporation. All rights reserved. */
4 /* Copyright (c) 2005-2009 Rexx Language Association. All rights reserved. */
5 /* */
6 /* This program and the accompanying materials are made available under */
7 /* the terms of the Common Public License v1.0 which accompanies this */
8 /* distribution. A copy is also available at the following address: */
9 /* http://www.oorexx.org/license.html */
10 /* */
11 /* Redistribution and use in source and binary forms, with or */
12 /* without modification, are permitted provided that the following */
13 /* conditions are met: */
14 /* */
15 /* Redistributions of source code must retain the above copyright */
16 /* notice, this list of conditions and the following disclaimer. */
17 /* Redistributions in binary form must reproduce the above copyright */
18 /* notice, this list of conditions and the following disclaimer in */
19 /* the documentation and/or other materials provided with the distribution. */
20 /* */
21 /* Neither the name of Rexx Language Association nor the names */
22 /* of its contributors may be used to endorse or promote products */
23 /* derived from this software without specific prior written permission. */
24 /* */
25 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS */
26 /* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT */
27 /* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS */
28 /* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT */
29 /* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, */
30 /* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED */
31 /* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, */
32 /* OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY */
33 /* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING */
34 /* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */
35 /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
36 /* */
37 /*----------------------------------------------------------------------------*/
38 /****************************************************************************/
39 /* REXX Kernel RexxCompoundTable.c */
40 /* */
41 /* Stem object table of compound variables */
42 /* */
43 /****************************************************************************/
44 #include "RexxCore.h"
45 #include "RexxCompoundTable.hpp"
46 #include "RexxCompoundElement.hpp"
47 #include "RexxCompoundTail.hpp"
48 
50  RexxStem *parentStem) /* the parent object we're embedded in */
51 {
52  setParent(parentStem); /* make the parent hook up */
53  setRoot(OREF_NULL); /* no root member */
54 }
55 
63  RexxCompoundTable &other)
64 {
65  RexxCompoundElement *entry = other.first();/* grab the first element */
66  while (entry != NULL)
67  { /* while we have more entry to process */
68  /* insert an entry in our table */
69  RexxCompoundElement *newEntry = findEntry(entry->getName(), true);
70  /* copy over the value */
71  newEntry->setValue(entry->variableValue);
72  entry = other.next(entry);
73  }
74 }
75 
77 {
78  setRoot(OREF_NULL); /* clear the anchor */
79 }
80 
81 
83 {
84  /* process the tail and search */
85  RexxCompoundTail resolved_tail(tail);
86  return findEntry(&resolved_tail, create);
87 }
88 
89 
91  RexxCompoundTail *tail, /* our tail search target */
92  bool create) /* we're creating a variable */
93 {
94  int rc = 0; /* comparison result */
95  RexxCompoundElement *previous; /* pointer for tree traversal */
96  RexxCompoundElement *anchor; /* pointer to current block */
97 
98  anchor = root; /* get root block */
99  previous = anchor; /* save starting point */
100  /* loop through on left branch*/
101  while (anchor)
102  {
103  /* do the name comparison */
104  rc = tail->compare(anchor->getName());
105  if (rc > 0)
106  { /* left longer? */
107  previous = anchor; /* save the previous */
108  /* take the right branch */
109  anchor = anchor->right;
110  continue; /* loop */
111  }
112  else if (rc < 0)
113  { /* left shorter? */
114  previous = anchor; /* save the previous */
115  /* the the left branch */
116  anchor = anchor->left;
117  continue; /* loop */
118  }
119  else
120  { /* names match */
121  return anchor; /* return the anchor */
122  }
123  }
124  if (!create)
125  { /* not a SET operation, */
126  return OREF_NULL; /* return var not found */
127  }
128  /* create a new compound variable */
129  anchor = new_compoundElement(tail->makeString());
130 
131  if (!previous)
132  { /* if first insertion */
133  anchor->setParent(OREF_NULL); /* no parent */
134  setRoot(anchor); /* set the tree top */
135  }
136  else
137  { /* real insertion */
138 
139  anchor->setParent(previous); /* set our parent entry */
140  if (rc > 0) /* should this be left or */
141  {
142  /* right on parent tree */
143  previous->setRight(anchor); /* right */
144  }
145  else
146  {
147  previous->setLeft(anchor); /* left */
148  }
149  balance(anchor); /* Balance the tree from here */
150  /* up */
151  }
152  return anchor; /* return new block pointer */
153 }
154 
155 
157  RexxCompoundElement *node) /* starting point */
158 {
159  RexxCompoundElement *_parent; /* block parent pointer */
160  unsigned short depth; /* current depth */
161  unsigned short wd; /* working depth */
162 
163  if (node == root) /* this the root? */
164  {
165  return; /* nothing to Balance */
166  }
167 
168  _parent = node->parent; /* step up to block's parent */
169  depth = 1; /* initial depth is 1 */
170 
171  while (_parent != OREF_NULL)
172  { /* while still have a parent */
173 
174  if (_parent->right == node)
175  { /* if on right branch */
176  _parent->rightdepth = depth; /* set right depth */
177  /* deeper on left? */
178  if (depth > (wd = _parent->leftdepth + (unsigned short)1))
179  {
180  moveNode(&_parent, false); /* adjust right branch */
181  depth = _parent->rightdepth; /* readjust depth */
182  }
183  else
184  {
185  if (wd < depth) /* left shorter */
186  {
187  return ; /* done */
188  }
189  }
190  }
191  else
192  {
193  _parent->leftdepth = depth; /* set left depth */
194  /* if right shorter */
195  if (depth > (wd = _parent->rightdepth + (unsigned short)1))
196  {
197  moveNode(&_parent, true); /* adjust left branch */
198  depth = _parent->leftdepth; /* readjust depth */
199  }
200  else
201  {
202  if (wd < depth) /* right shorter */
203  {
204  return ; /* done */
205  }
206  }
207  }
208  depth++; /* increment the depth */
209  node = _parent; /* step up to current */
210  _parent = _parent->parent; /* and lift up one more */
211  }
212 }
213 
215  RexxCompoundElement **anchor, /* node to move */
216  bool toright) /* move direction */
217 {
218  RexxCompoundElement *temp; /* anchor save position */
219  RexxCompoundElement *work; /* working block pointer */
220  RexxCompoundElement *work1; /* working block pointer */
221  RexxCompoundElement *work2; /* working block pointer */
222 
223  temp = *anchor; /* save where we are */
224 
225  if (toright)
226  { /* move right? */
227  work = temp->left; /* get left branch pointer */
228  work1 = temp->left = work->right; /* move right to left */
229  temp->leftdepth = work->rightdepth;/* adjust left depth value */
230  if (work1) /* was a right moved */
231  {
232  work1->setParent(temp); /* set its parent correctly */
233  }
234  work->setRight(temp); /* set new right */
235  work->rightdepth++; /* adjust its depth */
236  }
237  else
238  {
239  work = temp->right; /* get right node */
240  work1 = temp->right = work->left; /* move rights left node */
241  temp->rightdepth = work->leftdepth;/* set correct depth on left */
242  if (work1) /* moved a node */
243  {
244  work1->setParent(temp); /* set its parent correctly */
245  }
246  work->setLeft(temp); /* set left node */
247  work->leftdepth++; /* adjust its depth */
248  }
249  work->setParent(temp->parent); /* move node's parent around */
250  work2 = temp->parent;
251  temp->setParent(work); /* so that top is correct */
252  if (work2 == OREF_NULL) /* is this new root? */
253  {
254  setRoot(work); /* yes, adjust the root */
255  }
256  else if (work2->left == temp) /* was it on left */
257  {
258  work2->setLeft(work); /* make it left */
259  }
260  else
261  {
262  work2->setRight(work); /* else make it right */
263  }
264  *anchor = work; /* return correct position */
265 }
266 
267 
269 {
270  if (root == OREF_NULL)
271  {
272  return OREF_NULL;
273  }
274  else
275  {
276  return findLeaf(root);
277  }
278 }
279 
280 
282  RexxCompoundElement *node) /* starting point we're drilling from */
283 {
284  for (;;)
285  {
286  while (node->left != OREF_NULL)
287  { /* go as far left as we can */
288  node = node->left;
289  }
290  if (node->right == OREF_NULL)
291  { /* if there is no right child, stop here */
292  return node;
293  }
294  node = node->right; /* go right one level and repeat */
295  }
296 }
297 
298 
300  RexxCompoundElement *node) /* starting point we're drilling from */
301 {
302  /* get the parent node */
303  RexxCompoundElement *_parent = node->parent;
304  if (_parent != OREF_NULL)
305  {
306  if (_parent->right == node)
307  { /* if coming back up from the right */
308  return _parent; /* this node's turn has come */
309  }
310  if (_parent->right != OREF_NULL)
311  { /* if no right child, do this one immediately */
312  return findLeaf(_parent->right);/* drill down the other branch */
313  }
314  return _parent;
315  }
316  return OREF_NULL; /* we've reached the top */
317 }
318 
319 
321  RexxStem *parentStem)
322 /******************************************************************************/
323 /* Function: Set the parent for a compound table. N.B., this cannot be an */
324 /* inline method because of circular header file dependencies between */
325 /* RexxCompoundTable and RexxStem. */
326 /******************************************************************************/
327 {
328  // NOTE: This seems a little weird, but we're doing the set using the parent
329  // object...which will actually set the value in our own object instance.
330  // This is done because the if we have checkSetOref turned on, the validity
331  // checker won't recognize our address as being a valid object because it's
332  // embedded within another Rexx object.
333  OrefSet(parentStem, parentStem->tails.parent, parentStem);
334 }
335 
336 
338  RexxCompoundElement *newRoot)
339 /******************************************************************************/
340 /* Function: Set the root node for a compound table. N.B., this cannot be an*/
341 /* inline method because of circular header file dependencies between */
342 /* RexxCompoundTable and RexxStem. */
343 /******************************************************************************/
344 {
345  // NOTE: This seems a little weird, but we're doing the set using the parent
346  // object...which will actually set the value in our own object instance.
347  // This is done because the if we have checkSetOref turned on, the validity
348  // checker won't recognize our address as being a valid object because it's
349  // embedded within another Rexx object.
350  OrefSet(parent, parent->tails.root, newRoot);
351 }
352 
353 
355 /******************************************************************************/
356 /* Function: Search for a compound entry. This version is optimized for */
357 /* "find-but-don't create" usage. */
358 /******************************************************************************/
359 {
360  int rc; /* comparison result */
361  RexxCompoundElement *anchor; /* pointer to current block */
362 
363  anchor = root; /* get root block */
364  /* loop through on left branch*/
365  while (anchor != NULL)
366  {
367  /* do the name comparison */
368  rc = tail->compare(anchor->getName());
369  if (rc > 0)
370  { /* left longer? */
371  /* take the right branch */
372  anchor = anchor->right;
373  continue; /* loop */
374  }
375  else if (rc < 0)
376  { /* left shorter? */
377  /* the the left branch */
378  anchor = anchor->left;
379  continue; /* loop */
380  }
381  else
382  { /* names match */
383  return anchor; /* return the anchor */
384  }
385  }
386  return OREF_NULL; /* return var not found */
387 }
RexxCompoundElement::right
RexxCompoundElement * right
Definition: RexxCompoundElement.hpp:76
RexxCompoundTable::parent
RexxStem * parent
Definition: RexxCompoundTable.hpp:87
RexxCompoundElement
Definition: RexxCompoundElement.hpp:50
RexxCompoundTable.hpp
RexxCompoundElement::left
RexxCompoundElement * left
Definition: RexxCompoundElement.hpp:75
OrefSet
#define OrefSet(o, r, v)
Definition: RexxCore.h:94
new_compoundElement
RexxCompoundElement * new_compoundElement(RexxString *s)
Definition: RexxCompoundElement.hpp:84
RexxCompoundElement::setParent
void setParent(RexxCompoundElement *parentElement)
Definition: RexxCompoundElement.hpp:64
RexxVariable::getName
RexxString * getName()
Definition: RexxVariable.hpp:74
RexxCompoundElement::parent
RexxCompoundElement * parent
Definition: RexxCompoundElement.hpp:77
work
char work[256]
Definition: rxqueue.cpp:82
RexxCompoundTable::findLeaf
RexxCompoundElement * findLeaf(RexxCompoundElement *node)
Definition: RexxCompoundTable.cpp:281
RexxCompoundTail.hpp
RexxStem
Definition: StemClass.hpp:70
RexxCompoundTable::setRoot
void setRoot(RexxCompoundElement *newRoot)
Definition: RexxCompoundTable.cpp:337
OREF_NULL
#define OREF_NULL
Definition: RexxCore.h:60
RexxCompoundTable::findEntry
RexxCompoundElement * findEntry(RexxCompoundTail *tail)
Definition: RexxCompoundTable.cpp:354
RexxCompoundElement::setRight
void setRight(RexxCompoundElement *rightChild)
Definition: RexxCompoundElement.hpp:66
RexxCompoundTable::init
void init(RexxStem *parent)
Definition: RexxCompoundTable.cpp:49
RexxCompoundTable::clear
void clear()
Definition: RexxCompoundTable.cpp:76
RexxStem::tails
RexxCompoundTable tails
Definition: StemClass.hpp:159
RexxCompoundTable::first
RexxCompoundElement * first()
Definition: RexxCompoundTable.cpp:268
RexxVariable::variableValue
RexxObject * variableValue
Definition: RexxVariable.hpp:98
RexxCompoundTail::makeString
RexxString * makeString()
Definition: RexxCompoundTail.cpp:343
RexxCompoundElement::rightdepth
unsigned short rightdepth
Definition: RexxCompoundElement.hpp:79
RexxCompoundTable::next
RexxCompoundElement * next(RexxCompoundElement *node)
Definition: RexxCompoundTable.cpp:299
RexxCompoundTable::moveNode
void moveNode(RexxCompoundElement **anchor, bool toright)
Definition: RexxCompoundTable.cpp:214
RexxCompoundElement.hpp
RexxCompoundTable
Definition: RexxCompoundTable.hpp:66
RexxCompoundTable::root
RexxCompoundElement * root
Definition: RexxCompoundTable.hpp:86
RexxCompoundTable::setParent
void setParent(RexxStem *parent)
Definition: RexxCompoundTable.cpp:320
RexxCompoundTable::copyFrom
void copyFrom(RexxCompoundTable &other)
Definition: RexxCompoundTable.cpp:62
RexxCore.h
RexxCompoundElement::setLeft
void setLeft(RexxCompoundElement *leftChild)
Definition: RexxCompoundElement.hpp:65
RexxCompoundTail
Definition: RexxCompoundTail.hpp:52
RexxCompoundTail::compare
int compare(RexxString *name)
Definition: RexxCompoundTail.hpp:154
RexxCompoundElement::leftdepth
unsigned short leftdepth
Definition: RexxCompoundElement.hpp:78
RexxCompoundElement::setValue
void setValue(RexxObject *value)
Definition: RexxCompoundElement.hpp:69
RexxString
Definition: StringClass.hpp:119
RexxCompoundTable::balance
void balance(RexxCompoundElement *node)
Definition: RexxCompoundTable.cpp:156