tools/rea.c

   1 /*
   2  * rea.c --
   3  *
   4  *      This file holds the reverse engineering algorithm common for
   5  *      dump-cm.c and dump-svg.c.
   6  *
   7  * Copyright (c) 2000 A. Mueller, Technical University of Braunschweig.
   8  * Copyright (c) 2005 K. Sperner, Technical University of Braunschweig.
   9  *
  10  * See the file "COPYING" for information on usage and redistribution
  11  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  12  *
  13  * @(#) $Id: rea.c 7823 2008-03-01 13:53:12Z schoenw $
  14  */
  15
  16
  17
  18 #include <config.h>
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <ctype.h>
  24 #ifdef HAVE_WIN_H
  25 #include "win.h"
  26 #endif
  27
  28 #include "smi.h"
  29 #include "smidump.h"
  30 #include "rea.h"
  31
  32
  33
  34 /*
  35  * Constants used by the reverse engineering algorithm.
  36  */
  37
  38 static char *pointer[] = {
  39     "Index", NULL
  40 };
  41
  42 static char *suffix[] = {
  43     "OrZero", NULL
  44 };
  45
  46 static char *supportObjs[] = {
  47     "RowStatus", "StorageType", NULL
  48 };
  49
  50 static char *baseTypes[] = {
  51     "Integer32", "OctetString", "Unsigned32", "Integer64",
  52     "Unsigned64", "Float32", "Float64", "Float128",
  53     "Enumeration", "Counter32", "Counter64","Bits",
  54     "Gauge", "Gauge32", "Integer", "TimeTicks",
  55     "IpAddress", "Opaque", "ObjectIdentifier",
  56     NULL
  57 };
  58
  59
  60
  61 /*
  62  * driver output control
  63  */
  64
  65 /*
  66  * variables for svg-output
  67  *
  68  * When you change CANVASHEIGHT, CANVASWIDTH values here, you should
  69  * also change them in initSvg() and the cgi-script.
  70  */
  71
  72 int       CANVASHEIGHT          = 700; /* height of the svg */
  73 int       CANVASWIDTH           = 1100; /* width of the svg */
  74 int       SHOW_DEPRECATED       = 0; /* false, show deprecated objects */
  75 int       SHOW_DEPR_OBSOLETE    = 0; /* false, show deprecated and
  76                                         obsolete objects */
  77 int       STATIC_OUTPUT         = 0; /* false, enable interactivity */
  78 /* variables for cm-driver */
  79 int       XPLAIN                = 0; /* false, generates ASCII output */
  80 int       XPLAIN_DEBUG          = 0; /* false, generates additional
  81                                                output in xplain-mode */
  82 int       SUPPRESS_DEPRECATED   = 1; /* true, suppresses deprecated
  83                                                objects */
  84 /* common variables */
  85 int       PRINT_DETAILED_ATTR   = 1; /* true, prints all column
  86                                                objects */
  87 int       IGNORE_IMPORTED_NODES = 1; /* true, ignores nodes which are
  88                                                imported from other MIBs*/
  89
  90 /*
  91  * global variables
  92  */
  93 Graph     *graph  = NULL;            /* the graph */
  94
  95
  96
  97
  98
  99 /* ------ Misc. -----------------                                            */
 100
 101
 102
 103
 104
 105 /*
 106  * cmpSmiNodes
 107  *
 108  * Compares two SmiNode and returns 1 if they are equal and 0 otherwise.
 109  */
 110 int cmpSmiNodes(SmiNode *node1, SmiNode *node2)
 111 {
 112     SmiModule *module1, *module2;
 113
 114     module1 = smiGetNodeModule(node1);
 115     module2 = smiGetNodeModule(node2);
 116
 117     if (!node1 || !node2 || !module1 || !module2) return 0;
 118
 119     return (strcmp(node1->name, node2->name) == 0 &&
 120             strcmp(module1->name, module2->name) == 0);
 121 }
 122
 123 /*
 124  * strpfxlen
 125  *
 126  * Returns the number of identical characters at the beginning of s1 and s2.
 127  */
 128 static int strpfxlen(const char *s1, const char *s2)
 129 {
 130     int i;
 131
 132     for (i = 0; s1[i] && s2[i]; i++) {
 133         if (s1[i] != s2[i]) {
 134             break;
 135         }
 136     }
 137
 138     return i;
 139 }
 140
 141
 142
 143
 144
 145 /* ------ Graph primitives ------                                            */
 146
 147
 148
 149
 150
 151 /*
 152  * graphInsertNode
 153  *
 154  *          Inserts a new node into an existing graph.
 155  *
 156  * Result : pointer to the new node
 157  */
 158 GraphNode *graphInsertNode(Graph *graph, SmiNode *smiNode)
 159 {
 160     GraphNode *newNode;
 161     GraphNode *tNode;
 162     GraphNode *lastNode;
 163
 164     newNode = xmalloc(sizeof(GraphNode));
 165     memset(newNode, 0, sizeof(GraphNode));
 166     newNode->smiNode = smiNode;
 167
 168     if (graph->nodes == NULL) {
 169         graph->nodes = newNode;
 170         return newNode;
 171     }
 172
 173     lastNode = NULL;
 174     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
 175         lastNode = tNode;
 176     }
 177
 178     lastNode->nextPtr = newNode;
 179
 180     return newNode;
 181 }
 182
 183 /*
 184  * graphInsertComponent
 185  *
 186  *          Inserts a new component into an existing graph.
 187  *
 188  * Result : pointer to the new component
 189  */
 190 GraphComponent *graphInsertComponent(Graph *graph)
 191 {
 192     GraphComponent *newComponent;
 193     GraphComponent *tComponent;
 194     GraphComponent *lastComponent;
 195
 196     newComponent = xmalloc(sizeof(GraphComponent));
 197     memset(newComponent, 0, sizeof(GraphComponent));
 198
 199     if (graph->components == NULL) {
 200         graph->components = newComponent;
 201         return newComponent;
 202     }
 203
 204     lastComponent = NULL;
 205     for (tComponent = graph->components; tComponent;
 206                                             tComponent = tComponent->nextPtr) {
 207         lastComponent = tComponent;
 208     }
 209
 210     lastComponent->nextPtr = newComponent;
 211
 212     return newComponent;
 213 }
 214
 215 /*
 216  * graphInsertEdge
 217  *
 218  *          Inserts a new edge into an existing list of edges.
 219  *
 220  * Input  : graph     = pointer to an edge structure
 221  *          startNode = pointer to the starting node of the edge
 222  *          endNode   = pointer to the ending node of the edge
 223  *          indexkind = type of relationship between the two nodes
 224  *
 225  * Result : pointer to the new edge
 226  */
 227 static GraphEdge *graphInsertEdge(Graph *graph, GraphNode *startNode,
 228                               GraphNode *endNode,
 229                               SmiIndexkind indexkind,
 230                               GraphEnhIndex enhancedindex)
 231 {
 232     GraphEdge *newEdge;
 233     GraphEdge *tEdge;
 234     GraphEdge *lastEdge;
 235
 236     newEdge = xmalloc(sizeof(GraphEdge));
 237     memset(newEdge, 0, sizeof(GraphEdge));
 238     newEdge->startNode = startNode;
 239     newEdge->endNode = endNode;
 240     newEdge->indexkind = indexkind;
 241     newEdge->connection = GRAPH_CON_ASSOCIATION;
 242     newEdge->enhancedindex = enhancedindex;
 243
 244     switch (newEdge->indexkind) {
 245     case SMI_INDEX_AUGMENT :
 246         newEdge->cardinality = GRAPH_CARD_ONE_TO_ONE;
 247         break;
 248     case SMI_INDEX_SPARSE  :
 249         newEdge->cardinality = GRAPH_CARD_ONE_TO_ZERO_OR_ONE;
 250         break;
 251     case SMI_INDEX_EXPAND  :
 252         newEdge->cardinality = GRAPH_CARD_UNKNOWN;
 253         break;
 254     case SMI_INDEX_REORDER :
 255         newEdge->cardinality = GRAPH_CARD_ONE_TO_ONE;
 256         break;
 257     case SMI_INDEX_INDEX   :
 258         newEdge->cardinality = GRAPH_CARD_UNKNOWN;
 259         break;
 260     case SMI_INDEX_UNKNOWN :
 261         newEdge->cardinality = GRAPH_CARD_UNKNOWN;
 262         break;
 263     }
 264
 265     if (graph->edges == NULL) {
 266         graph->edges = newEdge;
 267         return newEdge;
 268     }
 269
 270     lastEdge = NULL;
 271     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
 272         lastEdge = tEdge;
 273     }
 274
 275     lastEdge->nextPtr = newEdge;
 276
 277     return newEdge;
 278 }
 279
 280 /*
 281  * graphExit
 282  *
 283  * Frees all memory allocated by the graph.
 284  */
 285 void graphExit(Graph *graph)
 286 {
 287     GraphEdge *tEdge, *dummyEdge;
 288     GraphNode *tNode, *dummyNode;
 289     GraphComponent *tComponent, *dummyComponent;
 290
 291     if (graph) {
 292
 293         dummyNode = NULL;
 294         tNode = graph->nodes;
 295         while (tNode != NULL) {
 296             dummyNode = tNode;
 297             tNode = tNode->nextPtr;
 298
 299             xfree(dummyNode);
 300         }
 301
 302         dummyEdge = NULL;
 303         tEdge = graph->edges;
 304         while (tEdge != NULL) {
 305             dummyEdge = tEdge;
 306             tEdge = tEdge->nextPtr;
 307
 308             xfree(dummyEdge);
 309         }
 310
 311         dummyComponent = NULL;
 312         tComponent = graph->components;
 313         while (tComponent != NULL) {
 314             dummyComponent = tComponent;
 315             tComponent = tComponent->nextPtr;
 316
 317             xfree(dummyComponent);
 318         }
 319
 320         xfree(graph);
 321     }
 322 }
 323
 324 /*
 325  * graphGetFirstEdgeByNode
 326  *
 327  * Returns the first edge adjacent to the given node (as startNode or EndNode).
 328  */
 329 GraphEdge *graphGetFirstEdgeByNode(Graph *graph, GraphNode *node)
 330 {
 331     GraphEdge *tEdge;
 332
 333     if (!graph || !node) {
 334         return NULL;
 335     }
 336
 337     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
 338         /*if (tEdge->startNode->smiNode->name == node->smiNode->name ||
 339           tEdge->endNode->smiNode->name == node->smiNode->name) break;*/
 340         if (cmpSmiNodes(tEdge->startNode->smiNode, node->smiNode) ||
 341             cmpSmiNodes(tEdge->endNode->smiNode, node->smiNode)) break;
 342     }
 343
 344     return tEdge;
 345 }
 346
 347 /*
 348  * graphGetNextEdgeByNode
 349  *
 350  * Returns the next edge adjacent to the given node (as startNode or EndNode)
 351  * after the given edge.
 352  */
 353 GraphEdge *graphGetNextEdgeByNode(Graph *graph,
 354                                          GraphEdge *edge,
 355                                          GraphNode *node)
 356 {
 357     GraphEdge *tEdge;
 358
 359     if (!graph || !node) {
 360         return NULL;
 361     }
 362
 363     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
 364         /*if (tEdge->startNode->smiNode->name ==
 365             edge->startNode->smiNode->name &&
 366             tEdge->endNode->smiNode->name ==
 367             edge->endNode->smiNode->name) break;*/
 368         if (cmpSmiNodes(tEdge->startNode->smiNode,edge->startNode->smiNode) &&
 369             cmpSmiNodes(tEdge->endNode->smiNode,edge->endNode->smiNode))
 370             break;
 371     }
 372
 373     for (tEdge = tEdge->nextPtr; tEdge; tEdge = tEdge->nextPtr) {
 374         /*if (tEdge->startNode->smiNode->name == node->smiNode->name ||
 375           tEdge->endNode->smiNode->name == node->smiNode->name) break;*/
 376         if (cmpSmiNodes(tEdge->startNode->smiNode, node->smiNode) ||
 377             cmpSmiNodes(tEdge->endNode->smiNode, node->smiNode)) break;
 378     }
 379
 380     return tEdge;
 381 }
 382
 383 /*
 384  * graphCheckForRedundantEdge
 385  *
 386  * Finds redundant edges and returns 1 if one is found and 0 otherwise.
 387  */
 388 static int graphCheckForRedundantEdge(Graph *graph,
 389                                GraphNode *startNode,
 390                                GraphNode *endNode)
 391 {
 392     GraphEdge *tEdge;
 393
 394     if (!graph || !startNode || !endNode) {
 395         return 0;
 396     }
 397
 398     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
 399         /*if (tEdge->startNode->smiNode->name == startNode->smiNode->name &&
 400           tEdge->endNode->smiNode->name == endNode->smiNode->name) {*/
 401         if (cmpSmiNodes(tEdge->startNode->smiNode, startNode->smiNode) &&
 402             cmpSmiNodes(tEdge->endNode->smiNode, endNode->smiNode)) {
 403
 404             return 1;
 405         }
 406     }
 407
 408     return 0;
 409 }
 410
 411 /*
 412  * graphGetNode
 413  *
 414  * Returns the graph node containing smiNode.
 415  */
 416 static GraphNode *graphGetNode(Graph *graph, SmiNode *smiNode)
 417 {
 418     GraphNode *tNode;
 419
 420     if (!smiNode || !graph) {
 421         return NULL;
 422     }
 423
 424     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
 425         if (tNode->smiNode->name == smiNode->name) {
 426             break;
 427         }
 428     }
 429
 430     return tNode;
 431 }
 432
 433 /*
 434  * graphShowNodes
 435  *
 436  * Prints the nodes of the graph.
 437  */
 438 void graphShowNodes(Graph *graph)
 439 {
 440     GraphNode *tNode;
 441
 442     if (!graph->nodes) {
 443         printf("No nodes!\n");
 444         return;
 445     }
 446
 447     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
 448         if (tNode->smiNode->nodekind == SMI_NODEKIND_TABLE)
 449             printf(" [TABLE]");
 450         else printf("[SCALAR]");
 451         printf("%40s [%s]\n", tNode->smiNode->name,
 452                smiGetNodeModule(tNode->smiNode)->name);
 453     }
 454 }
 455
 456 /*
 457  * graphShowEdges
 458  *
 459  * Prints the edges with their attributes in the following order :
 460  *    - start node
 461  *    - reason for the link
 462  *    - connection type in UML
 463  *    - cardinality
 464  *    - index relationship derived from the row-objects of the tables
 465  *
 466  */
 467 static void graphShowEdges(Graph *graph)
 468 {
 469     GraphEdge  *tEdge;
 470
 471     if (!graph->edges) {
 472         printf("No edges!\n");
 473         return;
 474     }
 475
 476     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
 477
 478         if (XPLAIN_DEBUG) {
 479             switch (tEdge->enhancedindex) {
 480             case GRAPH_ENHINDEX_UNKNOWN :
 481                 printf("[UNKNOWN] ");
 482                 break;
 483             case GRAPH_ENHINDEX_NOTIFICATION :
 484                 break;
 485             case GRAPH_ENHINDEX_NAMES :
 486                 printf("  [NAMES] ");
 487                 break;
 488             case GRAPH_ENHINDEX_TYPES :
 489                 printf("  [TYPES] ");
 490                 break;
 491             case GRAPH_ENHINDEX_INDEX :
 492                 printf("  [INDEX] ");
 493                 break;
 494             case GRAPH_ENHINDEX_REROUTE :
 495                 printf("[REROUTE] ");
 496                 break;
 497             case GRAPH_ENHINDEX_POINTER :
 498                 printf("[POINTER] ");
 499                 break;
 500             }
 501         }
 502
 503         switch (tEdge->connection) {
 504         case GRAPH_CON_AGGREGATION:
 505             printf("AG.");
 506             break;
 507         case GRAPH_CON_DEPENDENCY:
 508             printf("D. ");
 509             break;
 510         case GRAPH_CON_ASSOCIATION:
 511             printf("A. ");
 512             break;
 513         case GRAPH_CON_UNKNOWN:
 514             break;
 515         }
 516
 517         switch (tEdge->cardinality) {
 518         case GRAPH_CARD_UNKNOWN      :
 519             printf("  (-:-)  ");
 520             break;
 521         case GRAPH_CARD_ONE_TO_ONE   :
 522             printf("  (1:1)  ");
 523             break;
 524         case GRAPH_CARD_ONE_TO_MANY  :
 525             printf("  (1:n)  ");
 526             break;
 527         case GRAPH_CARD_ZERO_TO_ONE  :
 528             printf("  (0:1)  ");
 529             break;
 530         case GRAPH_CARD_ZERO_TO_MANY :
 531             printf("  (0:n)  ");
 532             break;
 533         case GRAPH_CARD_ONE_TO_ZERO_OR_ONE :
 534             printf("(1:0..1) ");
 535             break;
 536         }
 537
 538         switch (tEdge->indexkind) {
 539         case SMI_INDEX_UNKNOWN  :
 540             printf("GENERIC ");
 541             break;
 542         case SMI_INDEX_INDEX    :
 543             printf("  INDEX ");
 544             break;
 545         case SMI_INDEX_AUGMENT  :
 546             printf("AUGMENT ");
 547             break;
 548         case SMI_INDEX_SPARSE   :
 549             printf(" SPARSE ");
 550             break;
 551         case SMI_INDEX_EXPAND   :
 552             printf(" EXPAND ");
 553             break;
 554         case SMI_INDEX_REORDER  :
 555             printf("REORDER ");
 556             break;
 557         }
 558         printf("%29s - ",tEdge->startNode->smiNode->name);
 559         printf("%s\n",tEdge->endNode->smiNode->name);
 560     }
 561 }
 562
 563
 564
 565
 566
 567 /* ------ algorithm primitives ------                                        */
 568
 569
 570
 571 /*
 572  * algCountIndexElements
 573  *
 574  * Returns the number of index elements in a given row entry.
 575  */
 576
 577 static int algCountIndexElements(SmiNode *smiNode)
 578 {
 579     int          count;
 580     SmiElement   *smiElement;
 581
 582     if (smiNode->nodekind != SMI_NODEKIND_ROW) {
 583         return 0;
 584     }
 585
 586     count = 0;
 587     for (smiElement = smiGetFirstElement(smiNode);
 588          smiElement;
 589          smiElement = smiGetNextElement(smiElement)) {
 590         count++;
 591     }
 592
 593     return count;
 594 }
 595
 596 /*
 597  * algInsertEdge
 598  *
 599  * Inserts an edge in a given graph. The edge is adjacent to snode
 600  * and enode.
 601  * The type of edge is given in indexkind and the enhanced index as
 602  * an additional information in enhancedindex.
 603  * Nodes which are not loaded yet into the node list of the graph
 604  * are added (nodes from imported MIBs).
 605  */
 606 static void algInsertEdge(SmiNode *snode, SmiNode *enode,
 607                           SmiIndexkind indexkind,
 608                           GraphEnhIndex enhancedindex)
 609 {
 610     GraphNode *startNode;
 611     GraphNode *endNode;
 612
 613     if (!graph) return;
 614
 615     startNode = graphGetNode(graph, snode);
 616     endNode   = graphGetNode(graph, enode);
 617
 618     /* insert imported nodes into graph if needed */
 619     if (startNode == NULL) {
 620         if (IGNORE_IMPORTED_NODES) return;
 621
 622         startNode = graphInsertNode(graph, snode);
 623     }
 624     if (endNode == NULL) {
 625         if (IGNORE_IMPORTED_NODES) return;
 626
 627         endNode = graphInsertNode(graph, enode);
 628     }
 629
 630     if (graphCheckForRedundantEdge(graph, startNode, endNode) == 0 &&
 631         graphCheckForRedundantEdge(graph, endNode, startNode) == 0) {
 632         graphInsertEdge(graph, startNode, endNode, indexkind, enhancedindex);
 633     }
 634 }
 635
 636 /*
 637  * algGetGroupByFatherNode
 638  *
 639  * Returns the group number associated with the father node of the
 640  * given node. If there is no group the result is 0 for no
 641  * grouping.
 642  */
 643 static int algGetGroupByFatherNode(SmiNode *smiNode)
 644 {
 645     GraphNode *tNode;
 646
 647     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
 648         if (tNode->smiNode->nodekind == SMI_NODEKIND_SCALAR &&
 649             !graphGetFirstEdgeByNode(graph, tNode)) {
 650             if (cmpSmiNodes(smiGetParentNode(smiNode),
 651                             smiGetParentNode(tNode->smiNode))) {
 652                 return tNode->group;
 653             }
 654         }
 655     }
 656
 657     return 0;
 658 }
 659
 660 /*
 661  * algGetNumberOfGroups
 662  *
 663  * Returns the number of groups.
 664  */
 665 int algGetNumberOfGroups()
 666 {
 667     GraphNode *tNode;
 668     int       maxGroup;
 669
 670     maxGroup = 0;
 671
 672     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
 673         maxGroup = max(maxGroup, tNode->group);
 674     }
 675
 676     return maxGroup;
 677 }
 678
 679 /*
 680  * algPrintGroup
 681  *
 682  * Prints the group with the number group.
 683  */
 684 static void algPrintGroup(int group)
 685 {
 686     GraphNode *tNode;
 687
 688     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
 689         if (tNode->group == group) {
 690             printf("%2d - %35s\n", group, tNode->smiNode->name);
 691         }
 692     }
 693 }
 694
 695 /*
 696  * algGetTypeDescription
 697  *
 698  * Returns the description of the data type used in smiNode.
 699  */
 700 char *algGetTypeDescription(SmiNode *smiNode)
 701 {
 702     SmiType *smiType, *parentType;
 703
 704     smiType = smiGetNodeType(smiNode);
 705
 706     if (!smiType || smiNode->nodekind == SMI_NODEKIND_TABLE)
 707         return NULL;
 708
 709     if (smiType->decl == SMI_DECL_IMPLICIT_TYPE) {
 710         parentType = smiGetParentType(smiType);
 711         smiType = parentType;
 712     }
 713
 714     return smiType->description;
 715 }
 716
 717 /*
 718  * algGetTypeName
 719  *
 720  * Returns the name of the data type used in smiNode.
 721  */
 722 char *algGetTypeName(SmiNode *smiNode)
 723 {
 724     SmiType *smiType, *parentType;
 725
 726     smiType = smiGetNodeType(smiNode);
 727
 728     if (!smiType || smiNode->nodekind == SMI_NODEKIND_TABLE)
 729         return NULL;
 730
 731     if (smiType->decl == SMI_DECL_IMPLICIT_TYPE) {
 732         parentType = smiGetParentType(smiType);
 733         smiType = parentType;
 734     }
 735
 736     return smiType->name;
 737 }
 738
 739 /*
 740  * algGetTypeModule
 741  *
 742  * Returns the module which defines the data type used in smiNode.
 743  */
 744 SmiModule *algGetTypeModule(SmiNode *smiNode)
 745 {
 746     SmiType *smiType, *parentType;
 747     SmiModule *smiModule;
 748
 749     smiType = smiGetNodeType(smiNode);
 750
 751     if (!smiType || smiNode->nodekind == SMI_NODEKIND_TABLE)
 752         return NULL;
 753
 754     if (smiType->decl == SMI_DECL_IMPLICIT_TYPE) {
 755         parentType = smiGetParentType(smiType);
 756         smiType = parentType;
 757     }
 758
 759     smiModule = smiGetTypeModule(smiType);
 760
 761     return smiModule;
 762 }
 763
 764 /*
 765  * algCountElementsFromOtherTables
 766  *
 767  * Returns the number of index objects derived from other tables than
 768  * the given one.
 769  */
 770 static int algCountElementsFromOtherTables(SmiNode *smiNode)
 771 {
 772     SmiElement *smiElement;
 773     SmiNode    *tNode;
 774     int        elems = 0;
 775
 776     for (smiElement = smiGetFirstElement(smiNode);
 777          smiElement;
 778          smiElement = smiGetNextElement(smiElement)) {
 779
 780         tNode = smiGetElementNode(smiElement);
 781
 782         if (cmpSmiNodes(smiGetParentNode(smiGetParentNode(tNode)),
 783                         smiGetParentNode(smiNode)) != 1) {
 784             elems++;
 785         }
 786     }
 787
 788     return elems;
 789 }
 790
 791 /*
 792  * algGetNumberOfRows
 793  *
 794  * Returns the number of rows =
 795  *   number of elements in smiNode - number of rows
 796  *   + RowStatus-Objects + StorageType-Objects
 797  *
 798  * If the number is > 0 it is only a supporting table (like entLPMappingTable)
 799  * and if the number is < 0 it is a "full" table (like ifTable).
 800  *
 801  * Subroutine for algCheckForDependency.
 802  */
 803 static int algGetNumberOfRows(SmiNode *smiNode)
 804 {
 805     SmiNode *tSmiNode;
 806     SmiNode *table;
 807     int     i, elemCount;
 808
 809     elemCount = 0;
 810     table = smiNode;
 811     tSmiNode = smiGetFirstChildNode(table);
 812
 813     elemCount = algCountIndexElements(tSmiNode) -
 814         algCountElementsFromOtherTables(tSmiNode);
 815
 816     for (tSmiNode = smiGetNextNode(tSmiNode, SMI_NODEKIND_COLUMN);
 817          tSmiNode;
 818          tSmiNode = smiGetNextNode(tSmiNode, SMI_NODEKIND_COLUMN)) {
 819
 820         if (cmpSmiNodes(table, smiGetParentNode(smiGetParentNode(tSmiNode)))
 821             != 1) {
 822             break;
 823         }
 824
 825         for (i = 0; supportObjs[i]; i++) {
 826             char *typeName = algGetTypeName(tSmiNode);
 827             if (typeName && (strcasecmp(typeName, supportObjs[i]) == 0)) {
 828                 break;
 829             }
 830         }
 831
 832         if (!supportObjs[i]) elemCount--;
 833     }
 834
 835     return elemCount;
 836 }
 837
 838 /*
 839  * isBaseType
 840  *
 841  * returns 1 if smiElement is a basetype used in SMIv2/SMIng. Otherwise
 842  * the result is 0.
 843  */
 844 int isBaseType(SmiNode *node)
 845 {
 846     int i;
 847
 848     for (i = 0; baseTypes[i]; i++) {
 849         if (strcasecmp(algGetTypeName(node), baseTypes[i]) == 0) {
 850             return 1;
 851         }
 852     }
 853
 854     return 0;
 855 }
 856
 857 /*
 858  * algFindEqualType
 859  *
 860  * Looks in all tables indices for an equal type to the type used in typeNode.
 861  * It returns the first table found which is different to startTable.
 862  *
 863  * Subroutine for algCheckForDependency.
 864  */
 865 static SmiNode *algFindEqualType(SmiNode *startTable, SmiNode *typeNode)
 866 {
 867     SmiElement *smiElement;
 868     SmiNode    *tSmiNode;
 869     char       *typeName;
 870     GraphNode  *tNode;
 871
 872     typeName = algGetTypeName(typeNode);
 873     /* if (isBaseType(typeNode)) return NULL; */
 874
 875     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
 876         if (tNode->smiNode->nodekind == SMI_NODEKIND_TABLE) {
 877
 878             tSmiNode = tNode->smiNode;
 879             if (cmpSmiNodes(tSmiNode, startTable) == 1) break;
 880
 881             for (smiElement = smiGetFirstElement(
 882                 smiGetFirstChildNode(tSmiNode));
 883                  smiElement;
 884                  smiElement = smiGetNextElement(smiElement)) {
 885                 /* found type matching ? */
 886                 if (strcmp(typeName,
 887                                algGetTypeName(smiGetElementNode
 888                                               (smiElement))) == 0) {
 889                     return tSmiNode;
 890                 }
 891             }
 892
 893         }
 894     }
 895
 896     return NULL;
 897 }
 898
 899 /*
 900  * 0 = totaly equal (order and objects)
 901  * 1 = equal objects but different order
 902  * 2 = inequal
 903  * 3 = error;
 904  */
 905  static int equalElements(SmiNode *firstRow, SmiNode *secondRow)
 906 {
 907     int i,j,number1, number2;
 908     SmiElement *elemFirst, *elemSecond;
 909
 910     if (!firstRow->nodekind == SMI_NODEKIND_ROW ||
 911         !secondRow->nodekind == SMI_NODEKIND_ROW) {
 912         /* printf("no row entries\n"); */
 913         return 3;
 914     }
 915
 916     if (cmpSmiNodes(firstRow, secondRow) == 1) {
 917         /* printf("same objects\n"); */
 918         return 3;
 919     }
 920
 921     number1 = algCountIndexElements(firstRow);
 922     number2 = algCountIndexElements(secondRow);
 923
 924     if (number1 != number2) {
 925         /* printf("Different number of elements\n"); */
 926         return 2;
 927     }
 928
 929     i = 0;
 930     for (elemFirst = smiGetFirstElement(firstRow);
 931          elemFirst;
 932          elemFirst = smiGetNextElement(elemFirst)) {
 933         i++;
 934
 935         j = 0;
 936         for (elemSecond = smiGetFirstElement(secondRow);
 937              elemSecond;
 938              elemSecond = smiGetNextElement(elemSecond)) {
 939             j++;
 940             if (i == j && cmpSmiNodes(smiGetElementNode(elemFirst),
 941                                       smiGetElementNode(elemSecond)) == 1) {
 942                 break;
 943             }
 944         }
 945
 946         /* maybe same elements but in different order */
 947         if (!elemSecond) break;
 948     }
 949     if (!elemFirst) {
 950         /* printf("totaly equal\n"); */
 951         return 0;
 952     }
 953
 954     for (elemFirst = smiGetFirstElement(firstRow);
 955          elemFirst;
 956          elemFirst = smiGetNextElement(elemFirst)) {
 957
 958         for (elemSecond = smiGetFirstElement(secondRow);
 959              elemSecond;
 960              elemSecond = smiGetNextElement(elemSecond)) {
 961
 962             if (cmpSmiNodes(smiGetElementNode(elemFirst),
 963                             smiGetElementNode(elemSecond)) == 1) {
 964                 break;
 965             }
 966         }
 967
 968         /* maybe same elements but in different order */
 969         if (!elemSecond) break;
 970     }
 971
 972     if (!elemFirst) {
 973         /* printf("Equal\n"); */
 974         return 1;
 975     }
 976     else {
 977         /* printf("inequal"); */
 978         return 2;
 979     }
 980 }
 981
 982 /*
 983  * algIsIndexElement
 984  *
 985  * Tests whether a given node is part of the index of a particular
 986  * table. Returns 1 if the node is an index node and 0 otherwise.
 987  */
 988
 989 int algIsIndexElement(SmiNode *table, SmiNode *node)
 990 {
 991     SmiElement *smiElement;
 992     SmiNode    *row;
 993
 994     if (node->nodekind != SMI_NODEKIND_TABLE) {
 995         return 0;
 996     }
 997
 998     row = smiGetFirstChildNode(table);
 999     if (!row || row->nodekind != SMI_NODEKIND_ROW) {
1000         return 0;
1001     }
1002
1003     for (smiElement = smiGetFirstElement(row);
1004          smiElement;
1005          smiElement = smiGetNextElement(smiElement)) {
1006         SmiNode *indexNode = smiGetElementNode(smiElement);
1007         if (cmpSmiNodes(indexNode, node)) {
1008             return 1;
1009         }
1010     }
1011
1012     return 0;
1013 }
1014
1015 /* -------------- main functions ------------------------------------------- */
1016
1017
1018
1019
1020 /*
1021  * algCheckForExpandRel
1022  *
1023  * Checks the given table for an expand relationship to an other table.
1024  *
1025  * 1. gets the expanded table (father node of smiNode)
1026  * 2. gets the base table by walking through the elements of the smiNode
1027  *    starting at the end. The first table found which is different from the
1028  *    expanded table is the first candidate for the base table.
1029  * 3. comparing the number of elements in both tables
1030  *    if the number in the expanded table is greater -> 5.
1031  *    if the number in the base table is greater     -> 4.
1032  * 4. getting a second base table candidate :
1033  *    It is possible that a table expands an other table which is expanded
1034  *    by this.
1035  *    Therefore it is hard to track the base table.
1036  *    - scanning all tables which are different from the expanded table
1037  *    - the base table must have :
1038  *         - least elements
1039  *         - the same elementes must occur as in the expanded table
1040  * 5. the elements in both tables are checked for equality
1041  */
1042 static void algCheckForExpandRel(SmiNode *smiNode)
1043 {
1044     SmiNode      *tNode;
1045     SmiNode      *baseTable;
1046     SmiNode      *expTable;
1047     SmiElement   *smiElement;
1048     SmiElement   *findElement;
1049     unsigned int refcounter;
1050     unsigned int basecounter;
1051
1052     if (!smiNode) return;
1053
1054     expTable = smiGetParentNode(smiNode);
1055
1056     /* count the elements in the given table <- father of smiNode */
1057     refcounter = algCountIndexElements(smiNode);
1058
1059     /* find the base table <- via the last element which does not refer to
1060        the expTable */
1061     baseTable = NULL;
1062     for (smiElement = smiGetFirstElement(smiNode);
1063          smiElement;
1064          smiElement = smiGetNextElement(smiElement)) {
1065         tNode = smiGetElementNode(smiElement);
1066         tNode = smiGetParentNode(tNode);
1067         tNode = smiGetParentNode(tNode);
1068
1069         if (cmpSmiNodes(tNode, expTable) == 1) break;
1070
1071         baseTable = tNode;
1072     }
1073
1074     if (!baseTable) return;
1075
1076     /* count the elements in the basetable */
1077     basecounter = algCountIndexElements(smiGetFirstChildNode(baseTable));
1078
1079     /* are baseTable and expTable identical ? */
1080     if (basecounter >= refcounter) {
1081
1082         /* searching for new base table candidate in order to handle multiple
1083            indices */
1084         for (baseTable = smiGetNextNode(baseTable, SMI_NODEKIND_TABLE);
1085              baseTable;
1086              baseTable = smiGetNextNode(baseTable, SMI_NODEKIND_TABLE)) {
1087
1088             basecounter = algCountIndexElements(smiGetFirstChildNode(baseTable));
1089
1090             if (basecounter < refcounter) {
1091
1092                 for (smiElement = smiGetFirstElement(
1093                     smiGetFirstChildNode(expTable));
1094                      smiElement;
1095                      smiElement = smiGetNextElement(smiElement)) {
1096                     tNode = smiGetElementNode(smiElement);
1097
1098                     /*if (smiGetParentNode(smiGetParentNode(tNode))->name ==
1099                       expTable->name) break; */
1100                     if (cmpSmiNodes(smiGetParentNode(smiGetParentNode(tNode)),
1101                                     expTable) == 1) break;
1102
1103                     for (findElement = smiGetFirstElement(
1104                         smiGetFirstChildNode(baseTable));
1105                          findElement;
1106                          findElement = smiGetNextElement(findElement)) {
1107                         if (cmpSmiNodes(tNode, smiGetElementNode(findElement))
1108                             == 1) break;
1109                     }
1110
1111                     if (!findElement) {
1112                         return;
1113                     }
1114                 }
1115                 break;
1116             }
1117         }
1118
1119         if (!baseTable) {
1120             return;
1121         }
1122     }
1123
1124     for (smiElement = smiGetFirstElement(smiGetFirstChildNode(baseTable));
1125          smiElement;
1126          smiElement = smiGetNextElement(smiElement)) {
1127         tNode = smiGetElementNode(smiElement);
1128
1129         for (findElement = smiGetFirstElement(smiGetFirstChildNode(expTable));
1130              findElement;
1131              findElement = smiGetNextElement(findElement)) {
1132             if (cmpSmiNodes(tNode, smiGetElementNode(findElement)) == 1)
1133                 break;
1134         }
1135
1136         if (!findElement) {
1137             return;
1138         }
1139     }
1140
1141     algInsertEdge(baseTable, expTable, SMI_INDEX_EXPAND,
1142                   GRAPH_ENHINDEX_INDEX);
1143 }
1144
1145 /*
1146  * algCheckForSparseRel
1147  *
1148  * Checks the given table for a sparse relationship to an other table.
1149  *
1150  * Criterias for a sparse relationship :
1151  *    - same number of index elements in both tables
1152  *    - the same order of this elements
1153  * 1. Getting the basetable via the last element in the index of smiNode.
1154  * 2. comparing the number of elements
1155  */
1156 static void algCheckForSparseRel(SmiNode *smiNode)
1157 {
1158     SmiNode      *tNode = NULL;
1159     SmiNode      *table;
1160     SmiElement   *smiElement;
1161     unsigned int basecounter;
1162
1163     if (!smiNode) return;
1164
1165     table = smiGetParentNode(smiNode);
1166
1167     basecounter = algCountIndexElements(smiNode);
1168
1169     /* getting the basetable via the father node of the last element
1170        to handle multiple instanceing */
1171     for (smiElement = smiGetFirstElement(smiNode);
1172          smiElement;
1173          smiElement = smiGetNextElement(smiElement)) {
1174         tNode = smiGetElementNode(smiElement);
1175     }
1176
1177     if (! tNode) {
1178         return;
1179     }
1180
1181     tNode = smiGetParentNode(tNode);
1182     if (equalElements(smiNode, tNode) == 0) {
1183         algInsertEdge(smiGetParentNode(tNode), smiGetParentNode(smiNode),
1184                       SMI_INDEX_SPARSE, GRAPH_ENHINDEX_INDEX);
1185     }
1186 }
1187
1188 /*
1189  * algCheckForReOrderRel
1190  *
1191  * Checks the given table for a reorder relationship to an other table.
1192  *
1193  * Criterias for reoder relationships :
1194  *    - same number of elements
1195  *    - same elements must occur in a different order
1196  */
1197 static void algCheckForReorderRel(SmiNode *smiNode)
1198 {
1199     SmiNode   *tNode;
1200     GraphNode *graphNode;
1201
1202     if (!smiNode) {
1203         return;
1204     }
1205
1206     for (graphNode = graph->nodes;
1207          graphNode;
1208          graphNode = graphNode->nextPtr) {
1209         tNode = graphNode->smiNode;
1210         if (tNode->nodekind == SMI_NODEKIND_TABLE) {
1211             if (equalElements(smiNode, smiGetFirstChildNode(tNode)) == 1) {
1212                 algInsertEdge(smiGetParentNode(smiNode), tNode,
1213                               SMI_INDEX_REORDER, GRAPH_ENHINDEX_INDEX);
1214                 break;
1215             }
1216         }
1217     }
1218 }
1219
1220 /*
1221  * algGetIndexkind
1222  *
1223  * Gets the indexkind of the given table. The row object of the table is
1224  * passed to this function.
1225  * Therefore three subfunctions are called to get the indexkind.
1226  *   - algChechForExpandRel
1227  *   - algCheckForSparseRel
1228  *   - algCheckForReOrderRel
1229  * Look there for further information.
1230  */
1231 static void algGetIndexkind(SmiNode *row)
1232 {
1233     algCheckForExpandRel(row);
1234     algCheckForSparseRel(row);
1235     algCheckForReorderRel(row);
1236 }
1237
1238 /*
1239  * algLinkTables
1240  *
1241  * Links the tables of the given module.
1242  *
1243  *  1. Getting the tables and the scalars from the given module.
1244  *  2. Linking the tables :
1245  *     - AUGMENT no work to do just adding the corresponding edge
1246  *     - for other relationships the subfunction algGetIndexkind is called
1247  *       look there for further information
1248  */
1249 void algLinkTables()
1250 {
1251     GraphNode  *tGraphNode;
1252     SmiNode    *node;
1253     SmiNode    *tSmiNode;
1254
1255     /* linking the tables */
1256     for (tGraphNode = graph->nodes;
1257          tGraphNode;
1258          tGraphNode = tGraphNode->nextPtr) {
1259         node = tGraphNode->smiNode;
1260
1261         if (node->nodekind == SMI_NODEKIND_TABLE) {
1262             node = smiGetFirstChildNode(node);
1263
1264             if (node->nodekind == SMI_NODEKIND_ROW) {
1265
1266                 /* get the relationship between the tables and insert
1267                    the edges */
1268                 if (node->indexkind == SMI_INDEX_INDEX) {
1269                     algGetIndexkind(node);
1270                 } else {
1271                     tSmiNode = node;
1272                     node = smiGetRelatedNode(node);
1273                     node = smiGetParentNode(node);
1274                     algInsertEdge(node,
1275                                   smiGetParentNode(tSmiNode),
1276                                   tSmiNode->indexkind,
1277                                   GRAPH_ENHINDEX_INDEX);
1278                 }
1279             }
1280         }
1281     }
1282
1283    if (XPLAIN) {
1284        printf("--- Second Phase - linking the tables\n\n");
1285        graphShowEdges(graph);
1286    }
1287 }
1288
1289 /*
1290  * algCheckLinksByName
1291  *
1292  * Reordering the connections by looking at the names.
1293  * Related objects are linked (if their names are related).
1294  * Every expand relationship is examined. Therefore number of
1295  * identical characters at the beginning of the both table names is
1296  * counted.
1297  * Then every sparse relationship (only the ending node) is checked if
1298  * there is better connection with more identical characters at the beginning.
1299  * The starting node must be same as in the expand relationship to make sure
1300  * that there are no unrelated tables are linked.
1301  * Only legal overlappings lead to a new edge. A illegal overlap is :
1302  * - when the next character in both strings is a lower case character
1303  *   because if something like this is detected the two strings are
1304  *   corresponding in the middle of their names and not at defined points
1305  *   like suffix or prefix (-> the next character must be upper case or NULL)
1306  */
1307 void algCheckLinksByName()
1308 {
1309     GraphEdge *tEdge, *tEdge2, *newEdge;
1310     char      *start, *end, *end2;
1311     int       overlap, longestOverlap, i;
1312
1313     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
1314
1315         if (tEdge->indexkind == SMI_INDEX_EXPAND) {
1316
1317             start = tEdge->startNode->smiNode->name;
1318             end = tEdge->endNode->smiNode->name;
1319
1320             overlap = strpfxlen(start,end);
1321
1322             /*
1323              * looking for better connection with longer overlap
1324              * maybe better to traverse the edges with graphGetNextEdgeByNode
1325              * using tEdge->startNode
1326              */
1327             newEdge = NULL;
1328             longestOverlap = overlap;
1329             for (tEdge2 = graphGetFirstEdgeByNode(graph,tEdge->startNode);
1330                  tEdge2;
1331                  tEdge2 = graphGetNextEdgeByNode(graph, tEdge2,
1332                                                  tEdge->startNode)) {
1333
1334                 /*
1335                  * must be a sparse relationship to get a correct new edge
1336                  */
1337                 if (tEdge2->indexkind == SMI_INDEX_SPARSE) {
1338                     end2 = tEdge2->endNode->smiNode->name;
1339
1340                     /*
1341                      * new overlap longer and different tables ?
1342                      */
1343                     i = strpfxlen(end,end2);
1344                     if (overlap < i &&
1345                         !cmpSmiNodes(tEdge->endNode->smiNode,
1346                                      tEdge2->endNode->smiNode)) {
1347                         /*
1348                          * legal overlap ?
1349                          */
1350                         if (islower((int)end[i]) && islower((int)end2[i])) {
1351                             break;
1352                         }
1353
1354                         longestOverlap=i;
1355                         newEdge = tEdge2;
1356                     }
1357                 }
1358             }
1359
1360             /* better connection found -> changing the edge */
1361             if (newEdge) {
1362                 tEdge->startNode = newEdge->endNode;
1363             }
1364         }
1365     }
1366
1367     if (XPLAIN) {
1368         printf("\n--- Third Phase - reordering the connections\n\n");
1369         graphShowEdges(graph);
1370     }
1371 }
1372
1373 /*
1374  * algLinkObjectsByNames
1375  *
1376  * Links Scalars to Tables using the prefix
1377  * Links Tables to Tables using the prefix
1378  */
1379 static void algLinkObjectsByNames()
1380 {
1381     GraphNode *tNode, *tNode2;
1382     int       overlap,minoverlap,new;
1383
1384     /* getting the minimum overlap for all nodes */
1385     minoverlap = 10000;
1386     tNode2 = graph->nodes;
1387     if (tNode2) {
1388         for (tNode = tNode2->nextPtr; tNode; tNode = tNode->nextPtr) {
1389             minoverlap = min(minoverlap, strpfxlen(tNode->smiNode->name,
1390                                                    tNode2->smiNode->name));
1391         }
1392     }
1393
1394     /*
1395      * prefix overlap of one is too short to create any usefull edges
1396      */
1397     if (minoverlap == 1) return;
1398
1399     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
1400         if (!graphGetFirstEdgeByNode(graph, tNode)) {
1401             overlap = minoverlap;
1402
1403             for (tNode2 = graph->nodes; tNode2; tNode2 = tNode2->nextPtr) {
1404                 if (cmpSmiNodes(tNode->smiNode, tNode2->smiNode)) continue;
1405
1406                 new = strpfxlen(tNode->smiNode->name, tNode2->smiNode->name);
1407
1408                 if (new >= overlap) {
1409
1410                     /*
1411                      * no scalar - scalar edges
1412                      */
1413                     if (tNode->smiNode->nodekind == SMI_NODEKIND_SCALAR &&
1414                         tNode2->smiNode->nodekind == SMI_NODEKIND_SCALAR) {
1415                         continue;
1416                     }
1417
1418                     /*
1419                      * is it a legal prefix
1420                      * (if the next char is NULL || uppercase)
1421                      */
1422                     if (tNode->smiNode->name[new] &&
1423                         tNode2->smiNode->name[new]) {
1424                         if (!isupper((int)tNode->smiNode->name[new]) ||
1425                             !isupper((int)tNode2->smiNode->name[new])) continue;
1426                     }
1427
1428                     overlap = new;
1429                 }
1430             }
1431
1432             if (overlap == minoverlap) continue;
1433
1434             new = 0;
1435             for (tNode2 = graph->nodes; tNode2; tNode2 = tNode2->nextPtr) {
1436                 if (cmpSmiNodes(tNode->smiNode, tNode2->smiNode)) continue;
1437
1438                 new = strpfxlen(tNode->smiNode->name, tNode2->smiNode->name);
1439
1440                 if (new == overlap && new > minoverlap) {
1441
1442                     /*
1443                      * a scalar should only be adjacent to one node
1444                      */
1445                     if (tNode2->smiNode->nodekind == SMI_NODEKIND_SCALAR &&
1446                         graphGetFirstEdgeByNode(graph,tNode2)) continue;
1447                     if (tNode->smiNode->nodekind == SMI_NODEKIND_SCALAR &&
1448                         graphGetFirstEdgeByNode(graph,tNode)) continue;
1449
1450                     /*
1451                      * adding only table -> scalar edges
1452                      */
1453                     if (tNode->smiNode->nodekind == SMI_NODEKIND_SCALAR &&
1454                         tNode2->smiNode->nodekind == SMI_NODEKIND_SCALAR) {
1455                         continue;
1456                     }
1457
1458                     if (tNode->smiNode->nodekind == SMI_NODEKIND_SCALAR) {
1459                         algInsertEdge(tNode2->smiNode, tNode->smiNode,
1460                                       SMI_INDEX_UNKNOWN,
1461                                       GRAPH_ENHINDEX_NAMES);
1462                     } else {
1463                         algInsertEdge(tNode->smiNode, tNode2->smiNode,
1464                                       SMI_INDEX_UNKNOWN,
1465                                       GRAPH_ENHINDEX_NAMES);
1466                     }
1467                 }
1468             }
1469         }
1470     }
1471 }
1472
1473
1474 /*
1475  * algGroupScalars
1476  *
1477  * Grouping the scalars using a common fathernode.
1478  */
1479 static void algGroupScalars()
1480 {
1481     GraphNode *tNode;
1482     int       actGroup, fGroup;
1483
1484     actGroup = 0;
1485     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
1486         if (!graphGetFirstEdgeByNode(graph, tNode) &&
1487             tNode->smiNode->nodekind == SMI_NODEKIND_SCALAR) {
1488             fGroup = algGetGroupByFatherNode(tNode->smiNode);
1489             if (fGroup == 0) {
1490                 tNode->group = ++actGroup;
1491             }
1492             else {
1493                 tNode->group = fGroup;
1494             }
1495         }
1496     }
1497
1498     if (XPLAIN) {
1499         printf("Scalar Groups : \n");
1500
1501         if (algGetNumberOfGroups() != 0) {
1502             for (actGroup = 1;
1503                  actGroup <= algGetNumberOfGroups();
1504                  actGroup++) {
1505                 algPrintGroup(actGroup);
1506                 printf("\n");
1507             }
1508         } else printf("No groups!\n");
1509         printf("\n");
1510     }
1511 }
1512
1513 /*
1514  * algLinkLonelyTables
1515  *
1516  * Links isolated tables with other tables via the types of the
1517  * index objects.
1518  * If no type is found the types are checked via the suffix if they differ
1519  * only in the range (-OrZero). Therefore the suffix-vector is checked.
1520  * Basetypes used in SMIv1/v2/ng are sorted out.
1521  */
1522 static void algLinkLonelyTables()
1523 {
1524     SmiElement *smiElement, *smiElement2 = NULL;
1525     GraphNode  *tNode, *tNode2;
1526     int        i;
1527
1528     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
1529         if (!graphGetFirstEdgeByNode(graph, tNode) &&
1530             tNode->smiNode->nodekind == SMI_NODEKIND_TABLE) {
1531
1532             for (smiElement = smiGetFirstElement(
1533                 smiGetFirstChildNode(tNode->smiNode));
1534                  smiElement;
1535                  smiElement = smiGetNextElement(smiElement)) {
1536
1537                 for (tNode2 = graph->nodes;
1538                      tNode2;
1539                      tNode2 = tNode2->nextPtr) {
1540                     if (tNode->smiNode->nodekind == SMI_NODEKIND_TABLE &&
1541                         tNode != tNode2) {
1542
1543                         for (smiElement2 = smiGetFirstElement(
1544                             smiGetFirstChildNode(tNode2->smiNode));
1545                              smiElement2;
1546                              smiElement2 = smiGetNextElement(smiElement2)) {
1547
1548                             if (strcasecmp(algGetTypeName(
1549                                            smiGetElementNode(smiElement2)),
1550                                        algGetTypeName(
1551                                            smiGetElementNode(smiElement)))
1552                                 == 0) {
1553
1554                                 if (isBaseType(smiGetElementNode(smiElement))
1555                                     == 1){
1556                                     continue;
1557                                 }
1558
1559                                 graphInsertEdge(graph,tNode2, tNode,
1560                                                 SMI_INDEX_UNKNOWN,
1561                                                 GRAPH_ENHINDEX_TYPES);
1562                                 break;
1563                             }
1564                             else {
1565                                 for (i = 0; suffix[i]; i++) {
1566                                     if (strstr(
1567                                         algGetTypeName(
1568                                             smiGetElementNode(smiElement)),
1569                                         suffix[i])) {
1570                                         graphInsertEdge(graph,tNode2,
1571                                                         tNode,
1572                                                         SMI_INDEX_UNKNOWN,
1573                                                         GRAPH_ENHINDEX_TYPES);
1574                                         break;
1575                                     }
1576                                 }
1577
1578                                 if (suffix[i]) break;
1579                             }
1580                         }
1581                     }
1582                     if (smiElement2) break;
1583                 }
1584                 if (tNode2) break;
1585             }
1586
1587         }
1588     }
1589 }
1590
1591 /*
1592  * algConnectLonelyNodes
1593  *
1594  * Connect the isolated nodes (scalars and tables)
1595  *
1596  * 1. Trying to link tables via the type of the index objects
1597  * 2. Trying to link scalars to tables using the names
1598  * 3. Trying to group scalars which have not been adjacent to any edge.
1599  */
1600 void algConnectLonelyNodes()
1601 {
1602     if (XPLAIN) {
1603         printf("\n--- Fourth Phase -  connecting isolated nodes\n\n");
1604     }
1605
1606     algLinkLonelyTables();
1607
1608     algLinkObjectsByNames();
1609
1610     algGroupScalars();
1611
1612     if (XPLAIN) {
1613         graphShowEdges(graph);
1614     }
1615 }
1616
1617 /*
1618  * Subfunction of algCheckForDependencies
1619  *
1620  * change UML-edges to dependecy if possible
1621  */
1622 static void createDependencies()
1623 {
1624     GraphEdge *tEdge;
1625     int       elemCount;
1626
1627     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
1628
1629         if (tEdge->indexkind == SMI_INDEX_UNKNOWN) {
1630
1631             if (tEdge->startNode->smiNode->nodekind == SMI_NODEKIND_TABLE &&
1632                 tEdge->endNode->smiNode->nodekind   == SMI_NODEKIND_TABLE) {
1633
1634                 elemCount = algGetNumberOfRows(tEdge->startNode->smiNode);
1635                 if (elemCount >= 0) tEdge->connection = GRAPH_CON_DEPENDENCY;
1636
1637                 elemCount = algGetNumberOfRows(tEdge->endNode->smiNode);
1638                 if (elemCount >= 0) tEdge->connection = GRAPH_CON_DEPENDENCY;
1639             }
1640         }
1641     }
1642 }
1643
1644 /*
1645  * returns 1 if a new rerouting edge creates a loop and 0 otherwise
1646  */
1647 static int isloop(GraphEdge *tEdge, SmiNode *depTable)
1648 {
1649     GraphEdge *loopEdge;
1650
1651     for (loopEdge = graphGetFirstEdgeByNode(graph, tEdge->endNode);
1652          loopEdge;
1653          loopEdge = graphGetNextEdgeByNode(graph,loopEdge,tEdge->endNode)) {
1654
1655         if ((cmpSmiNodes(loopEdge->startNode->smiNode, depTable)) ||
1656             (cmpSmiNodes(loopEdge->endNode->smiNode, depTable) &&
1657              (loopEdge != tEdge))) {
1658             return 1;
1659         }
1660     }
1661
1662     return 0;
1663 }
1664
1665 /*
1666  * subfunction of algCheckForDependency
1667  */
1668 static void rerouteDependencyEdge(GraphEdge *tEdge)
1669 {
1670     SmiNode    *startTable, *endTable, *depTable;
1671     SmiElement *smiElement;
1672
1673     startTable = tEdge->startNode->smiNode;
1674     endTable = tEdge->endNode->smiNode;
1675
1676     for (smiElement = smiGetFirstElement(
1677         smiGetFirstChildNode(endTable));
1678          smiElement;
1679          smiElement = smiGetNextElement(smiElement)) {
1680
1681         /* look only at expanded indices (only present in endTable) */
1682         if (cmpSmiNodes(endTable, smiGetParentNode(
1683             smiGetParentNode(smiGetElementNode(smiElement)))) == 1) {
1684             depTable = algFindEqualType(startTable,
1685                                         smiGetElementNode(smiElement));
1686
1687             /* depTable different to endTable? */
1688             if (depTable && !cmpSmiNodes(depTable, endTable)) {
1689
1690                 /* prevent loops */
1691                 if (isloop(tEdge, depTable)) continue;
1692
1693                 algInsertEdge(depTable,
1694                               startTable, SMI_INDEX_UNKNOWN,
1695                               GRAPH_ENHINDEX_REROUTE);
1696                 break;
1697             }
1698         }
1699     }
1700 }
1701
1702 /*
1703  * algCheckForDependency
1704  *
1705  * Tries to change connection types from association to dependency by
1706  * looking at the types.
1707  *
1708  * 1. Supporting tables are revealed. Supporting tables consist only
1709  *    index objects and RowStatus-Objects and/or Storage-Type/Objects.
1710  * 2. If a supporting table is found the connection type is changed to
1711  *    dependency.
1712  * 3. Now the types of the index objects are checked (only in the end-table).
1713  *    If the same type is found in an other table the start-table is going to
1714  *    be connected with it (inserting a new edge).
1715  *    The end-table is still connected to the start-table.
1716  */
1717 void algCheckForDependency()
1718 {
1719     GraphEdge  *tEdge;
1720
1721     createDependencies();
1722
1723     for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {
1724
1725         if (tEdge->connection == GRAPH_CON_DEPENDENCY) {
1726
1727             rerouteDependencyEdge(tEdge);
1728         }
1729     }
1730
1731     if (XPLAIN) {
1732         printf("\n--- Fifth Phase - checking for dependency relationships\n\n");
1733         graphShowEdges(graph);
1734     }
1735 }
1736
1737 /*
1738  *
1739  */
1740 static SmiNode *algFindTable(SmiNode *node)
1741 {
1742     GraphNode  *tNode;
1743     SmiNode    *smiNode;
1744     SmiElement *smiElement;
1745     char       *toFind;
1746
1747     if (!node) return NULL;
1748
1749     toFind = xstrdup(node->name
1750                      + strpfxlen(node->name, smiGetParentNode(node)->name));
1751
1752     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
1753         if (tNode->smiNode->nodekind == SMI_NODEKIND_TABLE) {
1754             if (cmpSmiNodes(node, tNode->smiNode)) continue;
1755             smiNode = smiGetFirstChildNode(tNode->smiNode);
1756
1757             for (smiElement = smiGetFirstElement(smiNode);
1758                  smiElement;
1759                  smiElement = smiGetNextElement(smiElement)) {
1760                 smiNode = smiGetElementNode(smiElement);
1761                 if (strstr(smiNode->name, toFind)) {
1762                     xfree(toFind);
1763                     return smiGetParentNode(smiGetParentNode(smiNode));
1764                 }
1765             }
1766         }
1767     }
1768
1769     xfree(toFind);
1770
1771     return NULL;
1772 }
1773
1774 /*
1775  * Creates edges based on column-objects pointing to other tables.
1776  * Column-objects with a substring "Index" are examined.
1777  */
1778 void algCheckForPointerRels()
1779 {
1780     GraphNode *tNode;
1781     SmiModule *module;
1782     SmiNode   *smiNode = NULL;
1783     SmiNode   *ppNode, *table;
1784     int       i;
1785
1786     for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {
1787         if (tNode->smiNode->nodekind == SMI_NODEKIND_TABLE) {
1788
1789             module  = smiGetNodeModule(tNode->smiNode);
1790
1791             for (smiNode = smiGetFirstNode(module, SMI_NODEKIND_COLUMN);
1792                  smiNode;
1793                  smiNode = smiGetNextNode(smiNode, SMI_NODEKIND_COLUMN)) {
1794                 ppNode = smiGetParentNode(smiNode);
1795                 ppNode = smiGetParentNode(ppNode);
1796
1797                 if (!algIsIndexElement(tNode->smiNode, smiNode) &&
1798                     cmpSmiNodes(tNode->smiNode, ppNode)) {
1799
1800                     for (i = 0; pointer[i]; i++) {
1801                         if (strstr(smiNode->name, pointer[i])) {
1802                             /* printf("%s \n",smiNode->name); */
1803                             table = algFindTable(smiNode);
1804                             if (table) {
1805                                 algInsertEdge(table, tNode->smiNode,
1806                                               SMI_INDEX_UNKNOWN,
1807                                               GRAPH_ENHINDEX_POINTER);
1808                             }
1809                         }
1810                     }
1811                 }
1812             }
1813         }
1814     }
1815
1816     if (XPLAIN) {
1817         printf("\n--- Sixth Phase - checking for pointer relationships\n\n");
1818         graphShowEdges(graph);
1819     }
1820 }