home *** CD-ROM | disk | FTP | other *** search
/ Jason Aller Floppy Collection / 125.img / PRO-C4.ZIP / BENCH1.ZIP / BENCH / TREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-28  |  6.9 KB  |  394 lines
  1. /* ===( tree.c )=== */
  2.  
  3. /*
  4.  * Contains all tree initialization, manipulation, etc. functions
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <bench.h>
  9. #include <tree.h>
  10. #include <dllist.h>
  11.  
  12. #ifdef ANSI
  13. static void t_entinit(TREE *, struct tree_entry *, char *);
  14. int t_idxcmp(struct tree_entry *, struct tree_entry *);
  15. static void t_subbuild(TREE *, struct tree_entry *);
  16. static char *t_token(char *, char *, char *);
  17. #else
  18. static void t_entinit();
  19. int t_idxcmp();
  20. static void t_subbuild();
  21. static char *t_token();
  22. #endif
  23.  
  24. static int t_row;
  25. static int t_col;
  26.  
  27. struct tree_entry *t_add(tp, name)
  28. TREE *tp;
  29. char *name;
  30. {
  31.     struct tree_entry t_ent;
  32.     struct tree_entry *t_new = NULL;
  33.  
  34.     t_entinit(tp, &t_ent, name);
  35.  
  36.     if (dll_add(tp->listhd, &t_ent, ADD_NOSORT) != -1)
  37.         t_new = (struct tree_entry *)dll_curr(tp->listhd);
  38.  
  39.     return(t_new);
  40. }
  41.  
  42. int t_build(tp)
  43. TREE *tp;
  44. {
  45.     struct tree_entry *t_ent;
  46.     t_row = 0;
  47.     t_col = 1;
  48.  
  49.     if ((t_ent = (struct tree_entry *)dll_seek(tp->listhd, 0, SEEK_SET)) != NULL)
  50.         t_subbuild(tp, t_ent);
  51.  
  52.     return(t_row);
  53. }
  54.  
  55. struct tree_entry *t_childadd(tp, name, parent)
  56. TREE *tp;
  57. char *name;
  58. char *parent;
  59. {
  60.     struct tree_entry *t_new = NULL;
  61.     struct tree_entry *t_old;
  62.  
  63.     t_old = t_namefind(tp, parent);
  64.     if (t_old != NULL)
  65.     {
  66.         t_new = t_add(tp, name);
  67.         if (t_new != NULL)
  68.         {
  69.             t_new->t_parent = t_old->t_idx;
  70.             if (t_old->t_child == -1)
  71.                 t_old->t_child = t_new->t_idx;
  72.             else
  73.             {
  74.                 for(t_old = t_idxfind(tp, t_old->t_child); t_old->t_next != -1; t_old = t_idxfind(tp, t_old->t_next))
  75.                     ;
  76.                 t_new->t_prev = t_old->t_idx;
  77.                 t_old->t_next = t_new->t_idx;
  78.             }
  79.         }
  80.     }
  81.  
  82.     return(t_new);
  83. }
  84.  
  85. int t_close(tp)
  86. TREE *tp;
  87. {
  88.     int listhd;
  89.  
  90.     listhd = tp->listhd;
  91.     free(tp);
  92.  
  93.     return(dll_close(listhd));
  94. }
  95.  
  96. static void t_entinit(tp, t_ent, name)
  97. TREE *tp;
  98. struct tree_entry *t_ent;
  99. char *name;
  100. {
  101.     strcpy(t_ent->t_name, name);
  102.     t_ent->t_idx = tp->num_members++;
  103.     t_ent->t_parent = -1;
  104.     t_ent->t_child = -1;
  105.     t_ent->t_prev = -1;
  106.     t_ent->t_next = -1;
  107.     t_ent->t_from = -1;
  108.     t_ent->t_to = -1;
  109.     t_ent->t_row = 1;
  110.     t_ent->t_col = 1;
  111.     
  112.     return;
  113. }
  114.  
  115. int t_idxcmp(te1, te2)
  116. register struct tree_entry *te1, *te2;
  117. {
  118.     return(te2->t_idx - te1->t_idx);
  119. }
  120.  
  121. struct tree_entry *t_idxfind(tp, t_idx)
  122. TREE *tp;
  123. int t_idx;
  124. {
  125.     struct tree_entry t_ent;
  126.  
  127.     t_ent.t_idx = t_idx;
  128.     return((struct tree_entry *)dll_find(tp->listhd, &t_ent));
  129. }
  130.  
  131. struct tree_entry *t_namefind(tp, name)
  132. TREE *tp;
  133. char *name;
  134. {
  135.     struct tree_entry *t_find;
  136.  
  137.     if (tp->uniq == UNIQUE)
  138.     {
  139.         t_find = (struct tree_entry *)dll_seek(tp->listhd, 0, SEEK_SET);
  140.         for (; t_find != NULL; t_find = (struct tree_entry *)dll_next(tp->listhd))
  141.             if (strcmp(t_find->t_name, name) == 0)
  142.                 break;
  143.     }
  144.     else
  145.     {
  146.         char *partial;
  147.         char sep;
  148.  
  149.         t_find = t_rowfind(tp, 1);
  150.         if (t_find != NULL)
  151.         {
  152.             if (strncmp(t_find->t_name, name, strlen(t_find->t_name)) == 0)
  153.             {
  154.                 name += strlen(t_find->t_name);
  155.                 for(partial = t_token(name, ">\\/", &sep); partial != NULL; partial = t_token(NULL, ">\\/", &sep))
  156.                 {
  157.                     t_find = t_idxfind(tp, t_find->t_child);
  158.                     while (t_find != NULL)
  159.                     {
  160.                         if (strcmp(t_find->t_name, partial) == 0)
  161.                             break;
  162.                         if (t_find->t_next == -1)
  163.                             t_find = NULL;
  164.                         else
  165.                             t_find = t_idxfind(tp, t_find->t_next);
  166.                     }
  167.                     if (t_find == NULL)
  168.                         break;
  169.                 }
  170.             }
  171.             else
  172.                 t_find = NULL;
  173.         }
  174.     }
  175.  
  176.     return(t_find);
  177. }
  178.  
  179. TREE *t_open(name, uniq)
  180. char *name;
  181. int uniq;
  182. {
  183.     TREE *tp;
  184.     struct tree_entry t_ent;
  185.  
  186.     tp = (TREE *)alloc(sizeof(TREE));
  187.  
  188.     if (tp != NULL)
  189.     {
  190.         tp->num_members = 0;
  191.         tp->uniq = uniq;
  192.  
  193.         if ((tp->listhd = dll_open(t_idxcmp, sizeof(struct tree_entry))) == -1)
  194.         {
  195.             free(tp);
  196.             tp = NULL;
  197.         }
  198.         else
  199.         {
  200.             t_entinit(tp, &t_ent, name);
  201.  
  202.             if (dll_add(tp->listhd, &t_ent, ADD_NOSORT) == -1)
  203.             {
  204.                 dll_close(tp->listhd);
  205.                 free(tp);
  206.                 tp = NULL;
  207.             }
  208.         }
  209.     }
  210.  
  211.     return(tp);
  212. }
  213.  
  214. struct tree_entry *t_rowfind(tp, t_row)
  215. TREE *tp;
  216. int t_row;
  217. {
  218.     struct tree_entry *t_find;
  219.  
  220.     t_find = (struct tree_entry *)dll_seek(tp->listhd, 0, SEEK_SET);
  221.     for ( ; t_find != NULL; t_find = (struct tree_entry *)dll_next(tp->listhd))
  222.         if (t_row == t_find->t_row)
  223.             break;
  224.  
  225.     return(t_find);
  226. }
  227.  
  228. static void t_subbuild(tp, t_ent)
  229. TREE *tp;
  230. struct tree_entry *t_ent;
  231. {
  232.     static struct tree_entry *t_find;
  233.  
  234.     t_ent->t_row = ++t_row;
  235.     t_ent->t_col = t_col;
  236.  
  237.     if (t_ent->t_child != -1)
  238.         if ((t_find = t_idxfind(tp, t_ent->t_child)) != NULL)
  239.         {
  240.             t_col += 2;
  241.             t_subbuild(tp, t_find);
  242.             t_col -= 2;
  243.         }
  244.  
  245.     if (t_ent->t_to != -1)
  246.         if ((t_find = t_idxfind(tp, t_ent->t_to)) != NULL)
  247.         {
  248.             t_col += 2;
  249.             t_subbuild(tp, t_find);
  250.             t_col -= 2;
  251.         }
  252.  
  253.     if (t_ent->t_next != -1)
  254.         if ((t_find = t_idxfind(tp, t_ent->t_next)) != NULL)
  255.             t_subbuild(tp, t_find);
  256.  
  257.     return;
  258. }
  259.  
  260. struct tree_entry *t_toadd(tp, name, from)
  261. TREE *tp;
  262. char *name;
  263. char *from;
  264. {
  265.     struct tree_entry *t_new = NULL;
  266.     struct tree_entry *t_old;
  267.  
  268.     t_old = t_namefind(tp, from);
  269.     if (t_old != NULL)
  270.     {
  271.         t_new = t_add(tp, name);
  272.         if (t_new != NULL)
  273.         {
  274.             t_old->t_to = t_new->t_idx;
  275.             t_new->t_from = t_old->t_idx;
  276.         }
  277.     }
  278.     return(t_new);
  279. }
  280.  
  281. static char *t_token(string, delim, end)
  282. char *string, *delim, *end;
  283. {
  284.     static char *ptr;
  285.     static char *ds;
  286.     char *rptr;
  287.     char *p;
  288.     char *d;
  289.     
  290.     if (string != NULL)
  291.         ptr = string;
  292.  
  293.     ds = delim;
  294.  
  295.     do
  296.     {
  297.         for(p = ptr; *p; p++)
  298.         {
  299.             for(d = ds; *d; d++)
  300.             {
  301.                 if (*d == *p)
  302.                 {
  303.                     *end = *d;
  304.                     rptr = ptr;
  305.                     ptr = p + 1;
  306.                     break;
  307.                 }
  308.             }
  309.             if (*d)
  310.                 break;
  311.         }
  312.         if (*p)
  313.             *p = 0;
  314.         else
  315.         {
  316.             if (*ptr == 0)
  317.                 rptr = NULL;
  318.             else
  319.             {
  320.                 rptr = ptr;
  321.                 ptr = p;
  322.                 *end = *p;
  323.             }
  324.         }
  325.         if (rptr == NULL)
  326.             break;
  327.     }
  328.     while(*rptr == 0);
  329.  
  330.     return(rptr);
  331. }
  332.  
  333. int t_write(tp, tfp)
  334. TREE *tp;
  335. FILE *tfp;
  336. {
  337.     struct tree_entry *t_ent;
  338.  
  339.     if (fwrite(tp, sizeof(TREE), 1, tfp) != 1)
  340.         return(-1);
  341.  
  342.     t_ent = (struct tree_entry *)dll_seek(tp->listhd, 0, SEEK_SET);
  343.     for ( ; t_ent != NULL; t_ent = (struct tree_entry *)dll_next(tp->listhd))
  344.         if (fwrite(t_ent, sizeof(struct tree_entry), 1, tfp) != 1)
  345.             return(-1);
  346. }
  347.  
  348. TREE *t_read(tfp)
  349. FILE *tfp;
  350. {
  351.     struct tree_entry t_ent;
  352.     TREE *tp;
  353.     int i;
  354.     
  355.     tp = (TREE *)alloc(sizeof(TREE));
  356.     if (tp != NULL)
  357.     {
  358.         i = fread(tp, sizeof(TREE), 1, tfp);
  359.         if (i != 1 || tp->num_members <= 0)
  360.         {
  361.             free(tp);
  362.             tp = NULL;
  363.         }
  364.         else
  365.         {
  366.             tp->listhd = dll_open(t_idxcmp, sizeof(struct tree_entry));
  367.             if (tp->listhd == -1)
  368.             {
  369.                 free(tp);
  370.                 tp = NULL;
  371.             }
  372.             else
  373.             {
  374.                 for(i = 0; i < tp->num_members; i++)
  375.                 {
  376.                     if (fread(&t_ent, sizeof(struct tree_entry), 1, tfp) != 1)
  377.                         break;
  378.                     if (t_ent.t_idx != i)
  379.                         break;
  380.                     if (dll_add(tp->listhd, &t_ent, ADD_NOSORT) == -1)
  381.                         break;
  382.                 }
  383.                 if (i < tp->num_members)
  384.                 {
  385.                     dll_close(tp->listhd);
  386.                     free(tp);
  387.                     tp = NULL;
  388.                 }
  389.             }
  390.         }
  391.     }
  392.     return(tp);
  393. }
  394.