home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / SOURCE / TREES.C < prev    next >
C/C++ Source or Header  |  1996-06-04  |  10KB  |  463 lines
  1. /* Copyright 1991 Digital Equipment Corporation.
  2. ** All Rights Reserved.
  3. *****************************************************************/
  4. /*     $Id: trees.c,v 1.3 1995/07/27 21:22:21 duchier Exp $     */
  5.  
  6. #ifndef lint
  7. static char vcid[] = "$Id: trees.c,v 1.3 1995/07/27 21:22:21 duchier Exp $";
  8. #endif /* lint */
  9.  
  10. #include "extern.h"
  11. #include "print.h"
  12. #include "memory.h"
  13. #include "login.h"
  14.  
  15.   
  16.  
  17. /******** INTCMP(a,b)
  18.   Compares two integers, for use in FIND or INSERT.
  19. */
  20. long intcmp(a,b)
  21. long a;
  22. long b;
  23. {
  24.   return a-b;
  25. }
  26.  
  27.  
  28. /* Return TRUE iff the string s represents an integer. */
  29. /* Modify s to point to first non-zero digit. */
  30. /* Return number of significant digits in the integer and its sign. */
  31. long is_int(s, len, sgn)
  32. char **s;
  33. long *len;
  34. long *sgn;
  35. {
  36.   char *sint; /* Ptr to first non-zero digit */
  37.   char *stmp; /* Scratchpad for string ptr */
  38.  
  39.   /*
  40.   { register char *p= *s;
  41.     register char c= *p;
  42.     if(c>'0' && c<='9' && *(p+1)==0) return TRUE;
  43.   }
  44.   */
  45.   
  46.   stmp=(*s);
  47.   if (*sgn=(*stmp=='-')) {
  48.     stmp++;
  49.     if (!*stmp) return FALSE;
  50.   }
  51.   if (!*stmp) return FALSE; /* 6.10 */
  52.   while (*stmp=='0') stmp++;
  53.   sint=stmp;
  54.   while (*stmp) {
  55.     if (*stmp<'0' || *stmp>'9') return FALSE;
  56.     stmp++;
  57.   }
  58.   *len=stmp-sint;
  59.   *s=sint;
  60.   return TRUE;
  61. }
  62.  
  63.  
  64.  
  65.  
  66. /******** FEATCMP(s1,s2)
  67.   Compares two strings which represent features, for use
  68.   in FIND or INSERT.  This differs from strcmp for those strings
  69.   that represent integers.  These are compared as integers.
  70.   In addition, all integers are considered to be less than
  71.   all strings that do not represent integers.
  72. */
  73. long featcmp(str1,str2)
  74. char *str1, *str2;
  75. {
  76.   long len1,len2,sgn1,sgn2;
  77.   char *s1,*s2;
  78.  
  79.   if(str1==str2)
  80.     return 0;
  81.   
  82.   /* if (*str1==0 && *str2==0) return 0; "" bug is unaffected -- PVR 23.2.94 */
  83.  
  84.   if(*(str1+1)==0 && *(str2+1)==0)
  85.     return *str1 - *str2;
  86.   
  87.   
  88.   s1=str1; /* Local copies of the pointers */
  89.   s2=str2;
  90.  
  91.   if (is_int(&s1,&len1,&sgn1)) {
  92.     if (is_int(&s2,&len2,&sgn2)) {
  93.       if (sgn1!=sgn2) return (sgn2-sgn1); /* Check signs first */
  94.       if (len1!=len2) return (len1-len2); /* Then check lengths */
  95.       return strcmp(s1,s2); /* Use strcmp only if same sign and length */
  96.     }
  97.     else
  98.       return -1;
  99.   }
  100.   else {
  101.     if (is_int(&s2,&len2,&sgn2))
  102.       return 1;
  103.     else
  104.       return strcmp(s1,s2);
  105.   }
  106. }
  107.  
  108.  
  109. /******** HEAP_NCOPY_STRING(string,length)
  110.   Make a copy of the string in the heap, and return a pointer to that.
  111.   Exceptions: "1" and "2" are unique (and in the heap).
  112. */
  113. char *heap_ncopy_string(s,n)
  114. char *s;
  115. int n;
  116. {
  117.   char *p;
  118.   
  119.   if (s==one || s==two) return s;
  120.  
  121.   p=(char *)heap_alloc(n+1);
  122.   strncpy(p,s,n);
  123.   p[n]='\0';
  124.   
  125.   return p;
  126. }
  127.  
  128. /******** HEAP_COPY_STRING(string)
  129.   Make a copy of the string in the heap, and return a pointer to that.
  130.   Exceptions: "1" and "2" are unique (and in the heap).
  131. */
  132. char *heap_copy_string(s)
  133. char *s;
  134. { return heap_ncopy_string(s,strlen(s)); }
  135.  
  136.  
  137.  
  138. /******** STACK_COPY_STRING(string)
  139.   Make a copy of the string in the stack, and return a pointer to that.
  140.   Exceptions: "1" and "2" are unique (and in the heap).
  141. */
  142. char *stack_copy_string(s)
  143. char *s;
  144. {
  145.   char *p;
  146.   
  147.   if (s==one || s==two) return s;
  148.  
  149.   p=(char *)stack_alloc(strlen(s)+1);
  150.   strcpy(p,s);
  151.   
  152.   return p;
  153. }
  154.  
  155.  
  156.  
  157. /******** GENERAL_INSERT(comp,keystr,tree,info,heapflag,copystr,bkflag)
  158.   General tree insertion routine.
  159.   comp     = comparison routine for insertion.
  160.   keystr   = the insertion key.
  161.   tree     = the tree to insert in.
  162.   info     = the information to insert.
  163.   heapflag = HEAP or STACK for heap or stack allocation of insertion node.
  164.   copystr  = TRUE iff copy the keystr to the heap on insertion.
  165.   bkflag   = 1 iff the insertion is backtrackable (trailed with trail check).
  166.              2 iff the insertion must always be trailed.
  167.   Returns a pointer to the node containing the pair (keystr,info).
  168.  
  169.   Here KEYSTR can be either a pointer to a string, an integer, or a feature.
  170.   COMP is the function to call to compare 2 keys so it has three
  171.   possible values: COMP==strcmp(), COMP==intcmp(), or COMP==featcmp().
  172.   COMP(a,b) should return n where: n=0 if a=b; n>0 if a>b; n<0 if a<b.
  173. */
  174. ptr_node general_insert(comp,keystr,tree,info,heapflag,copystr,bkflag)
  175. long (*comp)();
  176. char *keystr;
  177. ptr_node *tree;
  178. GENERIC info;
  179. long heapflag, copystr, bkflag;
  180. {
  181.   long cmp;
  182.   ptr_node result;
  183.   long to_do=TRUE;
  184.  
  185.   
  186.   do {
  187.     if (*tree==NULL) {
  188.       if (bkflag==1) push_ptr_value(int_ptr,tree);
  189.       else if (bkflag==2) push_ptr_value_global(int_ptr,tree);
  190.       *tree = (heapflag==HEAP) ? HEAP_ALLOC(node): STACK_ALLOC(node);
  191.       result= *tree;
  192.       (*tree)->key = copystr ? heap_copy_string(keystr) : keystr;
  193.       (*tree)->left=NULL;
  194.       (*tree)->right=NULL;
  195.       (*tree)->data=info;
  196.       to_do=FALSE;
  197.     }
  198.     else {
  199.       cmp=(*comp)(keystr,(*tree)->key);
  200.       if (cmp<0)
  201.     tree=(&((*tree)->left));
  202.       else
  203.     if (cmp==0) {
  204.           if (bkflag)
  205.             Errorline("attempt to overwrite an existing feature; ignored.\n");
  206.           else
  207.         (*tree)->data=info;
  208.       result= *tree;
  209.       to_do=FALSE;
  210.     }
  211.     else
  212.       tree=(&((*tree)->right));
  213.     }
  214.   } while (to_do);
  215.   
  216.   return result;
  217. }
  218.  
  219.  
  220.  
  221. /******** HEAP_INSERT_COPYSTR(keystr,tree,info)
  222.   Insert the pointer INFO under the reference string KEYSTR (which is
  223.   a feature name) in the binary tree TREE.  KEYSTR is copied to the heap.
  224.   A potential additional node allocated to TREE is put on the heap.
  225. */
  226. void heap_insert_copystr(keystr,tree,info)
  227. char *keystr;
  228. ptr_node *tree;
  229. GENERIC info;
  230. {
  231.   general_insert(featcmp,keystr,tree,info,HEAP,TRUE,0);
  232. }
  233.  
  234.  
  235.  
  236. /******** STACK_INSERT_COPYSTR(keystr,tree,info)
  237.   Insert the pointer INFO under the reference string KEYSTR (which is
  238.   a feature name) in the binary tree TREE.  KEYSTR is copied to the heap.
  239.   A potential additional node allocated to TREE is put on the stack.
  240. */
  241. void stack_insert_copystr(keystr,tree,info)
  242. char *keystr;
  243. ptr_node *tree;
  244. GENERIC info;
  245. {
  246.   general_insert(featcmp,keystr,tree,info,STACK,TRUE,0);
  247. }
  248.  
  249.  
  250.  
  251. /******** HEAP_INSERT(comp,keystr,tree,info)
  252.   Insert the pointer INFO under the reference KEYSTR in the
  253.   binary tree TREE stored in the heap.
  254.   Return the pointer to the node of KEYSTR.
  255. */
  256. ptr_node heap_insert(comp,keystr,tree,info)
  257. long (*comp)();
  258. char *keystr;
  259. ptr_node *tree;
  260. GENERIC info;
  261. {
  262.   return general_insert(comp,keystr,tree,info,HEAP,FALSE,0);
  263. }
  264.  
  265.  
  266.  
  267. /******** STACK_INSERT(comp,keystr,tree,info)
  268.   Exactly the same as heap_insert, only the new node is in the stack.
  269. */
  270. ptr_node stack_insert(comp,keystr,tree,info)
  271. long (*comp)();
  272. char *keystr;
  273. ptr_node *tree;
  274. GENERIC info;
  275. {
  276.   return general_insert(comp,keystr,tree,info,STACK,FALSE,0);
  277. }
  278.  
  279.  
  280.  
  281. /******** BK_STACK_INSERT(comp,keystr,tree,info)
  282.   Insert the pointer INFO under the reference string KEYSTR of
  283.   length len in the binary tree TREE. Return the pointer to the permanent
  284.   storage place of KEY. This is used by C_APPLY_LABEL
  285.   Trail the change with a trail check.
  286. */
  287. ptr_node bk_stack_insert(comp,keystr,tree,info)
  288. long (*comp)();
  289. char *keystr;
  290. ptr_node *tree;
  291. GENERIC info;
  292. {
  293.   return general_insert(comp,keystr,tree,info,STACK,FALSE,1);
  294. }
  295.  
  296.  
  297.  
  298. /******** BK2_STACK_INSERT(comp,keystr,tree,info)
  299.   Insert the pointer INFO under the reference string KEYSTR of
  300.   length len in the binary tree TREE. Return the pointer to the permanent
  301.   storage place of KEY. This is used by C_APPLY_LABEL
  302.   Always trail the change.
  303. */
  304. ptr_node bk2_stack_insert(comp,keystr,tree,info)
  305. long (*comp)();
  306. char *keystr;
  307. ptr_node *tree;
  308. GENERIC info;
  309. {
  310.   return general_insert(comp,keystr,tree,info,STACK,FALSE,2);
  311. }
  312.  
  313.  
  314.  
  315. /******** FIND(comp,keystr,tree)
  316.   Return the NODE address corresponding to key KEYSTR in TREE using function
  317.   COMP to compare keys.
  318. */
  319. ptr_node find(comp,keystr,tree)
  320. long (*comp)();
  321. char *keystr;
  322. ptr_node tree;
  323. {
  324.   ptr_node result;
  325.   long cmp;
  326.   long to_do=TRUE;
  327.  
  328.   /*
  329.     if(comp==strcmp)
  330.     printf("%s ",keystr);
  331.     */
  332.     
  333.   do {
  334.     if (tree==NULL) {
  335.       result=NULL;
  336.       to_do=FALSE;
  337.     }
  338.     else {
  339.       cmp=(*comp)(keystr,tree->key);
  340.       if (cmp<0)
  341.     tree=tree->left;
  342.       else
  343.     if (cmp==0) {
  344.       result=tree;
  345.       to_do=FALSE;
  346.     }
  347.       else
  348.     tree=tree->right;
  349.     }
  350.   } while (to_do);
  351.  
  352.  
  353.   /* RM: Jan 27 1993 
  354.     if(comp==strcmp)
  355.     printf("Find: '%s' -> %x\n",keystr,result);
  356.     */
  357.   
  358.   return result;
  359. }
  360.  
  361.  
  362.  
  363. /******** FIND_DATA(p,t)
  364.   Return the node containing the data P in tree T. This is a linear search and
  365.   can be used to find the key to some data if it is unkown.
  366.   Return NULL if no key corresponds to data P.
  367. */
  368. ptr_node find_data(p,t)
  369. GENERIC p;
  370. ptr_node t;
  371. {
  372.   ptr_node r=NULL;
  373.  
  374.   if(t) 
  375.     if(t->data==p)
  376.       r=t;
  377.     else {
  378.       r=find_data(p,t->left);
  379.       if(r==NULL)
  380.     r=find_data(p,t->right);
  381.     }
  382.   
  383.   return r;
  384. }
  385.  
  386.  
  387.  
  388. /******** UPDATE_SYMBOL(s)
  389.   S is a string of characters encountered during parsing.
  390.   If it is an existing symbol then simply return its definition,
  391.   otherwise create a definition for it, and return that.
  392. */
  393. /*  Commented out by RM: Jan  7 1993
  394.     New routine is in modules.c
  395.     
  396. ptr_definition update_symbol(s)
  397. char *s;
  398. {
  399.   ptr_node n;
  400.   ptr_definition result;
  401.  
  402.   n=find(strcmp,s,symbol_table);
  403.   if(n)
  404.     result=(ptr_definition )n->data;
  405.   else {
  406.     s=heap_copy_string(s);
  407.       
  408.     result=HEAP_ALLOC(definition);
  409.     result->keyword->symbol=s;
  410.     result->rule=NULL;
  411.     result->properties=NULL;
  412.     result->date=0;
  413.     result->type=undef;
  414.     result->always_check=TRUE;
  415.     result->protected=TRUE;
  416.     result->evaluate_args=TRUE;
  417.     result->already_loaded=FALSE;
  418.     result->children=NULL;
  419.     result->parents=NULL;
  420.     result->code=NOT_CODED;
  421.     result->op_data=NULL;
  422.     
  423.     heap_insert(strcmp,s,&symbol_table,result);
  424.   }
  425.  
  426.   return result;
  427. }
  428. */
  429.  
  430.  
  431.  
  432. /******** DELETE_ATTR(key,tree)
  433.   Remove the node addressed by KEY from TREE.
  434. */
  435. void delete_attr(s,n)
  436. char *s;
  437. ptr_node *n;
  438. {
  439.   long cmp;
  440.   ptr_node new,r;
  441.  
  442.   if (*n) {
  443.     cmp=featcmp(s,(*n)->key);
  444.     if (cmp<0)
  445.       delete_attr(s,&((*n)->left));
  446.     else if (cmp>0)
  447.     delete_attr(s,&((*n)->right));
  448.     else if ((*n)->left) {
  449.       if ((*n)->right) {
  450.         r=(*n)->right;
  451.         new=heap_insert(featcmp,r->key,&((*n)->left),r->data);
  452.         new->left=r->left;
  453.         new->right=r->right;
  454.         *n = (*n) -> left;
  455.       }
  456.       else
  457.         *n = (*n)->left;
  458.     }
  459.     else
  460.       *n = (*n)->right;
  461.   }
  462. }
  463.