cde/programs/dtappbuilder/src/libABobj/trav.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23
  24 /*
  25  *      $XConsortium: trav.c /main/3 1995/11/06 18:41:30 rswiston $
  26  *
  27  * @(#)trav.c   3.41 14 Feb 1994        cde_app_builder/src/libABobj
  28  *
  29  *      RESTRICTED CONFIDENTIAL INFORMATION:
  30  *
  31  *      The information in this document is subject to special
  32  *      restrictions in a confidential disclosure agreement between
  33  *      HP, IBM, Sun, USL, SCO and Univel.  Do not distribute this
  34  *      document outside HP, IBM, Sun, USL, SCO, or Univel without
  35  *      Sun's specific written approval.  This document and all copies
  36  *      and derivative works thereof must be returned or destroyed at
  37  *      Sun's request.
  38  *
  39  *      Copyright 1993 Sun Microsystems, Inc.  All rights reserved.
  40  *
  41  */
  42
  43
  44 /*
  45  *  traversal.c - traversals of object trees
  46  */
  47
  48 #include <stdio.h>
  49 #include <stdlib.h>
  50 #include "objP.h"
  51 #include "travP.h"
  52
  53 static int      travP_find_first(ABTraversal trav);
  54 static int      travP_find_next(ABTraversal trav);
  55 static int      travP_find_next_parents_first(ABTraversal trav);
  56 static int      travP_find_first_for_parents(ABTraversal trav);
  57 static int      travP_find_next_for_parents(ABTraversal trav);
  58 static BOOL     travP_qualifies(ABTraversal trav);
  59 static int      travP_verify_type(ABTraversal travType, BOOL warn);
  60 static ABObj    find_first_item(ABObj obj);
  61 static ABObj    find_first_child_of_type(ABObj obj,
  62                                 ABTraversal trav, AB_OBJECT_TYPE type);
  63 static ABObj    find_first_action(ABObj, ABTraversal);
  64 static ABObj    find_first_sibling_child(ABObj obj, ABTraversal trav);
  65 static ABObj    find_next_sibling_child(ABObj obj, ABTraversal trav);
  66 static ABObj    find_first_ancestor_sibling_child(ABObj obj, ABTraversal trav);
  67
  68
  69 int
  70 travP_open(
  71                         ABTraversal trav, ABObj root, unsigned travType,
  72                         ABObjTestFunc   testFunc)
  73 {
  74         travP_clean(trav);
  75         trav->travType= travType;
  76         trav->rootObj= root;
  77         trav->testFunc= testFunc;
  78         travP_reset(trav);
  79         travP_verify_type(trav, TRUE);
  80         return 0;
  81 }
  82
  83
  84 int
  85 travP_close(ABTraversal trav)
  86 {
  87     trav->rootObj= NULL;
  88     trav->travType= AB_TRAV_UNDEF;
  89     return 0;
  90 }
  91
  92 /*
  93  * Restarts the traversal from the beginning.  With a safe traversal,
  94  * the list of objects is not recalculated.
  95  */
  96 int
  97 travP_reset(ABTraversal trav)
  98 {
  99         trav->curObj= NULL;
 100         trav->done= FALSE;
 101         return 0;
 102 }
 103
 104
 105 /*
 106  * Hint: travP_goto(trav, -1) is equivalent to travP_reset(trav).
 107  */
 108 ABObj
 109 travP_goto(ABTraversal trav, int node_num)
 110 {
 111         int     i;
 112
 113         travP_reset(trav);
 114         for (i= 0; i <= node_num; ++i)
 115         {
 116                 travP_next(trav);
 117         }
 118
 119         return trav->curObj;
 120 }
 121
 122
 123 /*
 124  * Effects: gets the next object in the traversal
 125  * Modifies: checks/sets done flag
 126  */
 127 ABObj
 128 travP_next(ABTraversal trav)
 129 {
 130         BOOL    found_next= FALSE;
 131
 132         if (trav->done)
 133         {
 134             return NULL;
 135         }
 136         else if (trav->curObj == NULL)
 137         {
 138             /* starting a new traversal */
 139             travP_find_first(trav);
 140             found_next= ((trav->curObj == NULL) || travP_qualifies(trav));
 141         }
 142
 143         while (!found_next)
 144         {
 145                 travP_find_next(trav);
 146                 if (   (trav->curObj == NULL)
 147                     || (travP_qualifies(trav)) )
 148                 {
 149                         found_next= TRUE;
 150                 }
 151         } /* while !found_next */
 152
 153         if (trav->curObj == NULL)
 154         {
 155             trav->done= TRUE;
 156         }
 157
 158         return trav->curObj;
 159 } /* travP_next */
 160
 161
 162 /*
 163  * ASSUMES: rootObj is not NULL
 164  *              - done is FALSE
 165  */
 166 static int
 167 travP_find_first(ABTraversal trav)
 168 {
 169 #define rootObj (trav->rootObj)
 170 #define curObj (trav->curObj)
 171     curObj = NULL;
 172
 173     switch (travP_get_qualifier(trav))
 174     {
 175         case AB_TRAV_ACTIONS_FOR_OBJ:
 176             curObj= find_first_action(rootObj, trav);
 177         break;
 178
 179         case AB_TRAV_CHILDREN:
 180         case AB_TRAV_SALIENT_CHILDREN:
 181         case AB_TRAV_SALIENT_UI_CHILDREN:
 182             curObj= travP_obj_first_child(rootObj, trav);
 183         break;
 184
 185         case AB_TRAV_COMP_SUBOBJS:
 186             if (obj_is_root(rootObj))
 187             {
 188                 curObj = rootObj;
 189             }
 190         break;
 191
 192         case AB_TRAV_ITEMS_FOR_OBJ:
 193             curObj= find_first_item(rootObj);
 194         break;
 195
 196         case AB_TRAV_MODULES:
 197             curObj= obj_is_module(rootObj)?
 198                         rootObj
 199                     :
 200                         find_first_child_of_type(rootObj, trav, AB_TYPE_MODULE);
 201         break;
 202
 203         case AB_TRAV_PARENTS:
 204             travP_find_first_for_parents(trav);
 205         break;
 206
 207         case AB_TRAV_SIBLINGS:
 208         {
 209             ABObj       prevSibling= NULL;
 210             curObj= rootObj;
 211             while ((prevSibling= travP_obj_prev_sibling(curObj, trav)) != NULL)
 212             {
 213                 curObj= prevSibling;
 214             }
 215         }
 216         break;
 217
 218         default:
 219             curObj= rootObj;
 220         break;
 221     }
 222
 223     return 0;
 224 #undef rootObj
 225 #undef curObj
 226 }
 227
 228
 229 /*
 230  * Assumes:     - traversal is not "done"
 231  *              - curObj is not NULL
 232  */
 233 static int
 234 travP_find_next(ABTraversal trav)
 235 {
 236 #define curObj (trav->curObj)
 237     switch (travP_get_qualifier(trav))
 238    {
 239         /*
 240          * Types that return only a set of siblings
 241          */
 242         case AB_TRAV_ACTIONS_FOR_OBJ:
 243         case AB_TRAV_CHILDREN:
 244         case AB_TRAV_ITEMS_FOR_OBJ:
 245         case AB_TRAV_MODULES:
 246         case AB_TRAV_SALIENT_CHILDREN:
 247         case AB_TRAV_SALIENT_UI_CHILDREN:
 248         case AB_TRAV_SIBLINGS:
 249             curObj= travP_obj_next_sibling(curObj, trav);
 250         break;
 251
 252         /*
 253          * Types that return parents
 254          */
 255         case AB_TRAV_PARENTS:
 256             travP_find_next_for_parents(trav);
 257         break;
 258
 259         /*
 260          * Traversals that return an entire tree
 261          */
 262         default:
 263             travP_find_next_parents_first(trav);
 264         break;
 265     }
 266
 267     return 0;
 268 #undef curObj
 269 } /* travP_find_next */
 270
 271
 272 static int
 273 travP_find_first_for_parents(ABTraversal trav)
 274 {
 275 #define curObj (trav->curObj)
 276     ABObj       parent= NULL;
 277
 278     if (travP_is_parents_first(trav))
 279     {
 280         curObj= travP_obj_parent(trav->rootObj, trav);
 281         if (curObj != NULL)
 282         {
 283             while ((parent= travP_obj_parent(curObj, trav)) != NULL)
 284             {
 285                 curObj= parent;
 286             }
 287         }
 288     }
 289     else
 290     {
 291         curObj= travP_obj_parent(trav->rootObj, trav);
 292     }
 293
 294     return 0;
 295 #undef curObj
 296 }
 297
 298
 299 static int
 300 travP_find_next_for_parents(ABTraversal trav)
 301 {
 302 #define curObj (trav->curObj)
 303
 304     if (travP_is_parents_first(trav))
 305     {
 306         curObj= travP_obj_first_child(curObj, trav);
 307         if (curObj == trav->rootObj)
 308         {
 309             curObj= NULL;
 310         }
 311     }
 312     else
 313     {
 314         curObj= travP_obj_parent(curObj, trav);
 315     }
 316
 317     return 0;
 318 #undef curObj
 319 }
 320
 321 /*****************************************************************
 322 **                                                              **
 323 **      PARENTS_FIRST TRAVERSAL                                 **
 324 **                                                              **
 325 ******************************************************************/
 326
 327
 328 /*
 329  * Assumes: traversal is open and not done
 330  */
 331 static int
 332 travP_find_next_parents_first(ABTraversal trav)
 333 {
 334     ABObj       curObj= trav->curObj;
 335     ABObj       tmpObj= NULL;
 336
 337     if (curObj == trav->rootObj)
 338     {
 339         curObj= travP_obj_first_child(curObj, trav);
 340     }
 341     else
 342     {
 343         if ((tmpObj= travP_obj_next_sibling(curObj, trav)) != NULL)
 344         {
 345             curObj= tmpObj;
 346         }
 347         else
 348         {
 349             tmpObj= find_first_sibling_child(curObj, trav);
 350             if (tmpObj == NULL)
 351             {
 352                 tmpObj= find_first_ancestor_sibling_child(curObj, trav);
 353             }
 354             curObj= tmpObj;
 355         }
 356     }
 357
 358     trav->curObj= curObj;
 359     return 0;
 360 }
 361
 362
 363 static ABObj
 364 find_first_item(ABObj obj)
 365 {
 366     ABObj       compRoot= obj_get_root(obj);
 367     ABObj       child= NULL;
 368     ABObj       item= NULL;
 369
 370     for (child= obj->first_child; child != NULL; child= child->next_sibling)
 371     {
 372         if (obj_get_root(child) == compRoot)
 373         {
 374            /* it's a subobj - look at its children */
 375            item= find_first_item(child);
 376            if (item != NULL)
 377            {
 378                break;
 379            }
 380         }
 381         else
 382         {
 383             if (obj_is_item(child))
 384             {
 385                 item= child;
 386                 break;
 387             }
 388         }
 389     }
 390
 391     return item;
 392 }
 393
 394
 395 /*
 396  * Finds the first sibling (from "left" to "right") of the object
 397  * that has a child.  Returns the first child of that sibling.
 398  */
 399 static ABObj
 400 find_first_sibling_child(ABObj obj, ABTraversal trav)
 401 {
 402     ABObj       sibling= obj;
 403     ABObj       child= NULL;
 404     ABObj       prevSibling= NULL;
 405     ABObj       firstChild= NULL;
 406
 407     while ((prevSibling= travP_obj_prev_sibling(sibling, trav)) != NULL)
 408     {
 409         sibling= prevSibling;
 410     }
 411
 412     if ((firstChild= travP_obj_first_child(sibling, trav)) != NULL)
 413     {
 414         child= firstChild;
 415     }
 416     else
 417     {
 418         child= find_next_sibling_child(sibling, trav);
 419     }
 420     return child;
 421 }
 422
 423
 424 /*
 425  * Finds the next sibling of the object that has a child.
 426  * Returns the first child of that sibling.
 427  */
 428 static ABObj
 429 find_next_sibling_child(ABObj obj, ABTraversal trav)
 430 {
 431     ABObj       sibling= travP_obj_next_sibling(obj, trav);
 432     ABObj       child= NULL;
 433     ABObj       firstChild= NULL;
 434
 435     while (   (sibling != NULL)
 436            && ((firstChild= travP_obj_first_child(sibling, trav)) == NULL) )
 437     {
 438         sibling= travP_obj_next_sibling(sibling, trav);
 439     }
 440
 441     if (sibling != NULL)
 442     {
 443         child= firstChild;
 444     }
 445     return child;
 446 }
 447
 448
 449 /*
 450  * Finds the first ancestor that has a sibling to its "right"
 451  * that has a child.  Returns the child.
 452  */
 453 static ABObj
 454 find_first_ancestor_sibling_child(ABObj obj, ABTraversal trav)
 455 {
 456     ABObj       ancestor= travP_obj_parent(obj, trav);
 457     ABObj       child= NULL;
 458
 459     for (; ((ancestor != NULL) && (ancestor != trav->rootObj));
 460           ancestor= travP_obj_parent(ancestor, trav))
 461     {
 462         child= find_next_sibling_child(ancestor, trav);
 463         if (child != NULL)
 464         {
 465             break;
 466         }
 467     }
 468
 469     return child;
 470 }
 471
 472
 473 /*
 474  *  Check the new current object to see if it qualifies for the traversal.
 475  *
 476  *  Assumes: trav->curObj is not null
 477  */
 478 static BOOL
 479 travP_qualifies(ABTraversal trav)
 480 {
 481         register ABObj  curObj = trav->curObj;
 482         register BOOL   qualifies= TRUE;
 483
 484         if (obj_has_impl_flags(curObj, ObjFlagDestroyed))
 485         {
 486             qualifies= FALSE;
 487             goto epilogue;
 488         }
 489
 490         switch (travP_get_qualifier(trav))
 491         {
 492                 case AB_TRAV_ACTIONS:
 493                 case AB_TRAV_ACTIONS_FOR_OBJ:
 494                         qualifies= obj_is_action(curObj);
 495                         break;
 496
 497                 case AB_TRAV_COMP_SUBOBJS:
 498                         qualifies = (obj_get_root(curObj) == trav->rootObj);
 499                         break;
 500
 501                 case AB_TRAV_FILES:
 502                         qualifies= (curObj->type == AB_TYPE_FILE);
 503                         break;
 504
 505                 case AB_TRAV_GROUPS:
 506                         qualifies= obj_is_group(curObj);
 507                         break;
 508
 509                 case AB_TRAV_ITEMS:
 510                 case AB_TRAV_ITEMS_FOR_OBJ:
 511                         qualifies= obj_is_item(curObj);
 512                         break;
 513
 514                 case AB_TRAV_MENUS:
 515                         qualifies= obj_is_menu(curObj);
 516                         break;
 517
 518                 case AB_TRAV_MODULES:
 519                         qualifies= obj_is_module(curObj);
 520                         break;
 521
 522                 case AB_TRAV_SALIENT:
 523                 case AB_TRAV_SALIENT_CHILDREN:
 524                         qualifies= obj_is_salient(curObj);
 525                         break;
 526
 527                 case AB_TRAV_SALIENT_UI:
 528                 case AB_TRAV_SALIENT_UI_CHILDREN:
 529                         qualifies= obj_is_salient_ui(curObj);
 530                         break;
 531
 532                 case AB_TRAV_UI:
 533                         qualifies= obj_is_ui(curObj);
 534                         break;
 535
 536                 case AB_TRAV_WINDOWS:
 537                         qualifies= obj_is_window(curObj);
 538                         break;
 539         }
 540
 541         if ((qualifies) && (trav->testFunc != NULL))
 542         {
 543             qualifies = trav->testFunc(curObj);
 544         }
 545
 546 epilogue:
 547         return qualifies;
 548 } /* travP_qualifies */
 549
 550
 551 /*
 552  * Verifies that the traversal type is valid, and changes
 553  * it, if necessary.
 554  */
 555 static int
 556 travP_verify_type(ABTraversal trav, BOOL warn)
 557 {
 558         int             iRet= 0;
 559         unsigned        travQualifier= travP_get_qualifier(trav);
 560         char            errMsg[256];
 561         errMsg[0]= 0;
 562
 563         switch (travQualifier)
 564         {
 565             case AB_TRAV_ACTIONS:
 566             case AB_TRAV_ACTIONS_FOR_OBJ:
 567             case AB_TRAV_ALL:
 568             case AB_TRAV_CHILDREN:
 569             case AB_TRAV_COMP_SUBOBJS:
 570             case AB_TRAV_FILES:
 571             case AB_TRAV_GROUPS:
 572             case AB_TRAV_ITEMS:
 573             case AB_TRAV_ITEMS_FOR_OBJ:
 574             case AB_TRAV_MODULES:
 575             case AB_TRAV_MENUS:
 576             case AB_TRAV_SALIENT:
 577             case AB_TRAV_SALIENT_CHILDREN:
 578             case AB_TRAV_SALIENT_UI:
 579             case AB_TRAV_SALIENT_UI_CHILDREN:
 580             case AB_TRAV_SIBLINGS:
 581             case AB_TRAV_UI:
 582             case AB_TRAV_WINDOWS:
 583                 /*
 584                  * All supported
 585                  */
 586             break;
 587
 588             case AB_TRAV_PARENTS:
 589                 if (travP_is_parents_first(trav) && debugging())
 590                 {
 591                     sprintf(errMsg,
 592                         "WARNING: "
 593                         "AB_TRAV_PARENTS - Ignoring unsupported modifier "
 594                         "AB_TRAV_MOD_PARENTS_FIRST.");
 595                     trav->travType &= ~AB_TRAV_MOD_PARENTS_FIRST;
 596                 }
 597             break;
 598
 599             default:
 600                 if (debugging())
 601                 {
 602                     sprintf(errMsg, "WARNING: travType %d unknown - "
 603                         "Using AB_TRAV_ALL.",
 604                         travQualifier);
 605                 }
 606                 travQualifier= AB_TRAV_ALL;
 607                 trav->travType &= TRAV_MODIFIER_MASK;
 608                 trav->travType |= travQualifier;
 609             break;
 610         }
 611
 612         if (warn && ((*errMsg) != 0))
 613         {
 614                 fprintf(stderr, "%s\n", errMsg);
 615         }
 616
 617         return iRet;
 618 }
 619
 620
 621 /*
 622  * If parent is NULL, returns NULL.
 623  */
 624 static ABObj
 625 find_first_child_of_type(ABObj parent, ABTraversal trav, AB_OBJECT_TYPE type)
 626 {
 627     ABObj       child= NULL;
 628
 629     if (parent == NULL)
 630     {
 631         return NULL;
 632     }
 633     for (child= travP_obj_first_child(parent, trav);
 634             child != NULL; child= travP_obj_next_sibling(child, trav))
 635     {
 636         if (child->type == type)
 637         {
 638             break;
 639         }
 640     }
 641     return child;
 642 }
 643
 644
 645 static ABObj
 646 find_first_action(ABObj obj, ABTraversal trav)
 647 {
 648         obj= find_first_child_of_type(obj, trav, AB_TYPE_ACTION_LIST);
 649         if (obj != NULL)
 650         {
 651             obj= find_first_child_of_type(obj, trav, AB_TYPE_ACTION);
 652         }
 653         return obj;
 654 }
 655