AppPkg/Applications/OrderedCollectionTest/OrderedCollectionTest.c

   1 /** @file
   2   A simple "fuzzer" application for OrderedCollectionLib, reading commands from
   3   the standard input, and writing results to the standard output.
   4
   5   Make sure you configure your platform so that the console stderr device is
   6   visible to the user (or else run the program from wherever stderr is visible
   7   per default, eg. serial line).
   8
   9   Copyright (C) 2014, Red Hat, Inc.
  10   Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.<BR>
  11
  12   This program and the accompanying materials are licensed and made available
  13   under the terms and conditions of the BSD License which accompanies this
  14   distribution. The full text of the license may be found at
  15   http://opensource.org/licenses/bsd-license.
  16
  17   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
  18   WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  19 **/
  20
  21 #include <assert.h> // assert()
  22 #include <errno.h>  // errno
  23 #include <limits.h> // INT_MIN
  24 #include <stdio.h>  // fgets()
  25 #include <stdlib.h> // EXIT_FAILURE
  26 #include <string.h> // strerror()
  27 #include <unistd.h> // getopt()
  28
  29 #include <Library/OrderedCollectionLib.h>
  30
  31 //
  32 // We allow the user to select between stdin+stdout and regular input+output
  33 // files via command line options. We don't rely on shell redirection for two
  34 // reasons:
  35 //
  36 // - The "old shell" doesn't support input redirection (<a, <);
  37 //
  38 // - The "new shell" supports input redirection (<a, <), but those redirections
  39 //   break fgets(stdin). Both when redirecting stdin from an ASCII file (<a),
  40 //   and when redirecting stdin from a UCS-2 file (<), the very first fgets()
  41 //   spirals into an infinite loop, spewing ^@ on the serial console.
  42 //
  43 // Performing fopen() manually (made available to the user with the -i option),
  44 // and reading from that stream with fgets() work under both old and new shell.
  45 // Only ASCII encoded files are supported.
  46 //
  47 static FILE *Input, *Output;
  48
  49
  50 //
  51 // Define a (potentially aggregate) key type.
  52 //
  53 typedef struct {
  54   int Value;
  55 } USER_KEY;
  56
  57 //
  58 // The user structure includes the key as one of its fields. (There can be
  59 // several, optionally differently typed, keys, if we link user structures into
  60 // several collections, with different comparators.)
  61 //
  62 typedef struct {
  63   unsigned char  Supplementary1[4];
  64   USER_KEY       Key;
  65   unsigned short Supplementary2[2];
  66 } USER_STRUCT;
  67
  68
  69 /**
  70   Compare a standalone key against a user structure containing an embedded key.
  71
  72   @param[in] StandaloneKey  Pointer to the bare key.
  73
  74   @param[in] UserStruct     Pointer to the user structure with the embedded
  75                             key.
  76
  77   @retval <0  If StandaloneKey compares less than UserStruct's key.
  78
  79   @retval  0  If StandaloneKey compares equal to UserStruct's key.
  80
  81   @retval >0  If StandaloneKey compares greater than UserStruct's key.
  82 **/
  83 static
  84 INTN
  85 EFIAPI
  86 KeyCompare (
  87   IN CONST VOID *StandaloneKey,
  88   IN CONST VOID *UserStruct
  89   )
  90 {
  91   const USER_KEY    *CmpKey;
  92   const USER_STRUCT *CmpStruct;
  93
  94   CmpKey    = StandaloneKey;
  95   CmpStruct = UserStruct;
  96
  97   return CmpKey->Value < CmpStruct->Key.Value ? -1 :
  98          CmpKey->Value > CmpStruct->Key.Value ?  1 :
  99          0;
 100 }
 101
 102
 103 /**
 104   Comparator function type for two user structures.
 105
 106   @param[in] UserStruct1  Pointer to the first user structure.
 107
 108   @param[in] UserStruct2  Pointer to the second user structure.
 109
 110   @retval <0  If UserStruct1 compares less than UserStruct2.
 111
 112   @retval  0  If UserStruct1 compares equal to UserStruct2.
 113
 114   @retval >0  If UserStruct1 compares greater than UserStruct2.
 115 **/
 116 static
 117 INTN
 118 EFIAPI
 119 UserStructCompare (
 120   IN CONST VOID *UserStruct1,
 121   IN CONST VOID *UserStruct2
 122   )
 123 {
 124   const USER_STRUCT *CmpStruct1;
 125
 126   CmpStruct1 = UserStruct1;
 127   return KeyCompare (&CmpStruct1->Key, UserStruct2);
 128 }
 129
 130
 131 /**
 132   Empty the collection by iterating forward through its entries.
 133
 134   This function demonstrates that iterators different from the one being
 135   removed remain valid.
 136
 137   @param[in,out] Collection  The collection to empty.
 138 **/
 139 static void
 140 CmdForwardEmpty (
 141   IN OUT ORDERED_COLLECTION *Collection
 142   )
 143 {
 144   ORDERED_COLLECTION_ENTRY *Entry;
 145
 146   Entry = OrderedCollectionMin (Collection);
 147   while (Entry != NULL) {
 148     ORDERED_COLLECTION_ENTRY *Next;
 149     void                     *Ptr;
 150     USER_STRUCT              *UserStruct;
 151
 152     Next = OrderedCollectionNext (Entry);
 153     OrderedCollectionDelete (Collection, Entry, &Ptr);
 154
 155     UserStruct = Ptr;
 156     fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value);
 157     free (UserStruct);
 158
 159     Entry = Next;
 160   }
 161 }
 162
 163
 164 /**
 165   Empty the collection by iterating backward through its entries.
 166
 167   This function demonstrates that iterators different from the one being
 168   removed remain valid.
 169
 170   @param[in,out] Collection  The collection to empty.
 171 **/
 172 static void
 173 CmdBackwardEmpty (
 174   IN OUT ORDERED_COLLECTION *Collection
 175   )
 176 {
 177   ORDERED_COLLECTION_ENTRY *Entry;
 178
 179   Entry = OrderedCollectionMax (Collection);
 180   while (Entry != NULL) {
 181     ORDERED_COLLECTION_ENTRY *Prev;
 182     void                     *Ptr;
 183     USER_STRUCT              *UserStruct;
 184
 185     Prev = OrderedCollectionPrev (Entry);
 186     OrderedCollectionDelete (Collection, Entry, &Ptr);
 187
 188     UserStruct = Ptr;
 189     fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value);
 190     free (UserStruct);
 191
 192     Entry = Prev;
 193   }
 194 }
 195
 196
 197 /**
 198   List the user structures linked into the collection, in increasing order.
 199
 200   @param[in] Collection  The collection to list.
 201 **/
 202 static void
 203 CmdForwardList (
 204   IN ORDERED_COLLECTION *Collection
 205   )
 206 {
 207   ORDERED_COLLECTION_ENTRY *Entry;
 208
 209   for (Entry = OrderedCollectionMin (Collection); Entry != NULL;
 210        Entry = OrderedCollectionNext (Entry)) {
 211     USER_STRUCT  *UserStruct;
 212
 213     UserStruct = OrderedCollectionUserStruct (Entry);
 214     fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value);
 215   }
 216 }
 217
 218
 219 /**
 220   List the user structures linked into the collection, in decreasing order.
 221
 222   @param[in] Collection  The collection to list.
 223 **/
 224 static void
 225 CmdBackwardList (
 226   IN ORDERED_COLLECTION *Collection
 227   )
 228 {
 229   ORDERED_COLLECTION_ENTRY *Entry;
 230
 231   for (Entry = OrderedCollectionMax (Collection); Entry != NULL;
 232        Entry = OrderedCollectionPrev (Entry)) {
 233     USER_STRUCT  *UserStruct;
 234
 235     UserStruct = OrderedCollectionUserStruct (Entry);
 236     fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value);
 237   }
 238 }
 239
 240
 241 /**
 242   Create a new user structure and attempt to insert it into the collection.
 243
 244   @param[in]     Value       The key value of the user structure to create.
 245
 246   @param[in,out] Collection  The collection to insert the new user structure
 247                              into.
 248 **/
 249 static void
 250 CmdInsert (
 251   IN     int     Value,
 252   IN OUT ORDERED_COLLECTION *Collection
 253   )
 254 {
 255   USER_STRUCT              *UserStruct, *UserStruct2;
 256   RETURN_STATUS            Status;
 257   ORDERED_COLLECTION_ENTRY *Entry;
 258
 259   UserStruct = calloc (1, sizeof *UserStruct);
 260   if (UserStruct == NULL) {
 261     fprintf (Output, "%s: %d: calloc(): out of memory\n", __FUNCTION__, Value);
 262     return;
 263   }
 264
 265   UserStruct->Key.Value = Value;
 266   Status = OrderedCollectionInsert (Collection, &Entry, UserStruct);
 267
 268   switch (Status) {
 269   case RETURN_OUT_OF_RESOURCES:
 270     fprintf (Output, "%s: %d: OrderedCollectionInsert(): out of memory\n",
 271       __FUNCTION__, Value);
 272     goto ReleaseUserStruct;
 273
 274   case RETURN_ALREADY_STARTED:
 275     UserStruct2 = OrderedCollectionUserStruct (Entry);
 276     assert (UserStruct != UserStruct2);
 277     assert (UserStruct2->Key.Value == Value);
 278     fprintf (Output, "%s: %d: already exists\n", __FUNCTION__,
 279       UserStruct2->Key.Value);
 280     goto ReleaseUserStruct;
 281
 282   default:
 283     assert (Status == RETURN_SUCCESS);
 284     break;
 285   }
 286
 287   assert (OrderedCollectionUserStruct (Entry) == UserStruct);
 288   fprintf (Output, "%s: %d: inserted\n", __FUNCTION__, Value);
 289   return;
 290
 291 ReleaseUserStruct:
 292   free (UserStruct);
 293 }
 294
 295
 296 /**
 297   Look up a user structure by key in the collection and print it.
 298
 299   @param[in] Value       The key of the user structure to find.
 300
 301   @param[in] Collection  The collection to search for the user structure with
 302                          the key.
 303 **/
 304 static void
 305 CmdFind (
 306   IN int                Value,
 307   IN ORDERED_COLLECTION *Collection
 308   )
 309 {
 310   USER_KEY                 StandaloneKey;
 311   ORDERED_COLLECTION_ENTRY *Entry;
 312   USER_STRUCT              *UserStruct;
 313
 314   StandaloneKey.Value = Value;
 315   Entry = OrderedCollectionFind (Collection, &StandaloneKey);
 316
 317   if (Entry == NULL) {
 318     fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value);
 319     return;
 320   }
 321
 322   UserStruct = OrderedCollectionUserStruct (Entry);
 323   assert (UserStruct->Key.Value == StandaloneKey.Value);
 324   fprintf (Output, "%s: %d: found\n", __FUNCTION__, UserStruct->Key.Value);
 325 }
 326
 327
 328 /**
 329   Look up a user structure by key in the collection and delete it.
 330
 331   @param[in] Value       The key of the user structure to find.
 332
 333   @param[in] Collection  The collection to search for the user structure with
 334                          the key.
 335 **/
 336 static void
 337 CmdDelete (
 338   IN int                Value,
 339   IN ORDERED_COLLECTION *Collection
 340   )
 341 {
 342   USER_KEY                 StandaloneKey;
 343   ORDERED_COLLECTION_ENTRY *Entry;
 344   void                     *Ptr;
 345   USER_STRUCT              *UserStruct;
 346
 347   StandaloneKey.Value = Value;
 348   Entry = OrderedCollectionFind (Collection, &StandaloneKey);
 349
 350   if (Entry == NULL) {
 351     fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value);
 352     return;
 353   }
 354
 355   OrderedCollectionDelete (Collection, Entry, &Ptr);
 356
 357   UserStruct = Ptr;
 358   assert (UserStruct->Key.Value == StandaloneKey.Value);
 359   fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value);
 360   free (UserStruct);
 361 }
 362
 363
 364 typedef struct {
 365   const char *Command;
 366   void       (*Function) (ORDERED_COLLECTION *Collection);
 367   const char *Description;
 368 } KEYLESS_COMMAND;
 369
 370 typedef struct {
 371   const char *Command;
 372   void       (*Function) (int Value, ORDERED_COLLECTION *Collection);
 373   const char *Description;
 374 } KEYED_COMMAND;
 375
 376 static const KEYLESS_COMMAND KeylessCommands[] = {
 377   { "forward-empty",  CmdForwardEmpty,
 378                       "empty the collection iterating forward" },
 379   { "fe",             CmdForwardEmpty,
 380                       "shorthand for forward-empty" },
 381   { "backward-empty", CmdBackwardEmpty,
 382                       "empty the collection iterating backward" },
 383   { "be",             CmdBackwardEmpty,
 384                       "shorthand for backward-empty" },
 385   { "forward-list",   CmdForwardList,
 386                       "list contents, iterating forward" },
 387   { "fl",             CmdForwardList,
 388                       "shorthand for forward-list" },
 389   { "backward-list",  CmdBackwardList,
 390                       "list contents, iterating backward" },
 391   { "bl",             CmdBackwardList,
 392                       "shorthand for backward-list" },
 393   { NULL }
 394 };
 395
 396 static const KEYED_COMMAND KeyedCommands[] = {
 397   { "insert ", CmdInsert, "insert value into collection" },
 398   { "i ",      CmdInsert, "shorthand for insert"         },
 399   { "find ",   CmdFind,   "find value in collection"     },
 400   { "f ",      CmdFind,   "shorthand for find"           },
 401   { "delete ", CmdDelete, "delete value from collection" },
 402   { "d ",      CmdDelete, "shorthand for delete"         },
 403   { NULL }
 404 };
 405
 406
 407 /**
 408   List the supported commands on stderr.
 409 **/
 410 static void
 411 ListCommands (
 412   void
 413   )
 414 {
 415   const KEYLESS_COMMAND *KeylessCmd;
 416   const KEYED_COMMAND   *KeyedCmd;
 417
 418   fprintf (stderr, "Supported commands:\n\n");
 419   for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL;
 420        ++KeylessCmd) {
 421     fprintf (stderr, "%-14s: %s\n", KeylessCmd->Command,
 422       KeylessCmd->Description);
 423   }
 424   for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) {
 425     fprintf (stderr, "%-9s<int>: %s\n", KeyedCmd->Command,
 426       KeyedCmd->Description);
 427   }
 428 }
 429
 430
 431 /**
 432   Configure stdio FILEs that we'll use for input and output.
 433
 434   @param[in] ArgC  The number of elements in ArgV, from main(). The environment
 435                    is required to ensure ArgC >= 1 (ie. that the program name,
 436                    ArgV[0], is available).
 437
 438   @param[in] ArgV  Command line argument list, from main().
 439 **/
 440 static void
 441 SetupInputOutput (
 442   IN int  ArgC,
 443   IN char **ArgV
 444   )
 445 {
 446   char *InputName, *OutputName;
 447   int  Loop;
 448
 449   assert (ArgC >= 1);
 450
 451   InputName  = NULL;
 452   OutputName = NULL;
 453   Loop       = 1;
 454
 455   while (Loop) {
 456     switch (getopt (ArgC, ArgV, ":i:o:h")) {
 457     case 'i':
 458       InputName = optarg;
 459       break;
 460
 461     case 'o':
 462       OutputName = optarg;
 463       break;
 464
 465     case 'h':
 466       fprintf (stderr,
 467         "%1$s: simple OrderedCollectionLib tester\n"
 468         "\n"
 469         "Usage: 1. %1$s [-i InputFile] [-o OutputFile]\n"
 470         "       2. %1$s -h\n"
 471         "\n"
 472         "Options:\n"
 473         "  -i InputFile : read commands from InputFile\n"
 474         "                 (will read from stdin if absent)\n"
 475         "  -o OutputFile: write command responses to OutputFile\n"
 476         "                 (will write to stdout if absent)\n"
 477         "  -h           : print this help and exit\n"
 478         "\n", ArgV[0]);
 479       ListCommands ();
 480       exit (EXIT_SUCCESS);
 481
 482 //
 483 // The current "compatibility" getopt() implementation doesn't support optopt,
 484 // but it gracefully degrades these branches to the others (one of the optarg
 485 // ones or the excess operands one).
 486 //
 487 #if 0
 488     case ':':
 489       fprintf (stderr, "%s: option -%c requires an argument; pass -h for "
 490         "help\n", ArgV[0], optopt);
 491       exit (EXIT_FAILURE);
 492
 493     case '?':
 494       fprintf (stderr, "%s: unknown option -%c; pass -h for help\n", ArgV[0],
 495         optopt);
 496       exit (EXIT_FAILURE);
 497 #endif
 498
 499     case -1:
 500       if (optind != ArgC) {
 501         fprintf (stderr, "%s: excess operands on command line; pass -h for "
 502           "help\n", ArgV[0]);
 503         exit (EXIT_FAILURE);
 504       }
 505       Loop = 0;
 506       break;
 507
 508     default:
 509       assert (0);
 510     }
 511   }
 512
 513   if (InputName == NULL) {
 514     Input = stdin;
 515   } else {
 516     Input = fopen (InputName, "r");
 517     if (Input == NULL) {
 518       fprintf (stderr, "%s: fopen(\"%s\", \"r\"): %s\n", ArgV[0], InputName,
 519         strerror (errno));
 520       exit (EXIT_FAILURE);
 521     }
 522   }
 523
 524   if (OutputName == NULL) {
 525     Output = stdout;
 526   } else {
 527     Output = fopen (OutputName, "w");
 528     if (Output == NULL) {
 529       fprintf (stderr, "%s: fopen(\"%s\", \"w\"): %s\n", ArgV[0], OutputName,
 530         strerror (errno));
 531       exit (EXIT_FAILURE);
 532     }
 533   }
 534
 535   //
 536   // When reading commands from the standard input, assume interactive mode,
 537   // and list the supported commands. However, delay this until both streams
 538   // are set up.
 539   //
 540   if (InputName == NULL) {
 541     ListCommands ();
 542   }
 543 }
 544
 545
 546 int
 547 main (
 548   IN int  ArgC,
 549   IN char **ArgV
 550   )
 551 {
 552   int                RetVal;
 553   ORDERED_COLLECTION *Collection;
 554   char               Line[256];
 555
 556   SetupInputOutput (ArgC, ArgV);
 557
 558   Collection = OrderedCollectionInit (UserStructCompare, KeyCompare);
 559   if (Collection == NULL) {
 560     fprintf (stderr, "%s: OrderedCollectionInit(): out of memory\n",
 561       __FUNCTION__);
 562       return EXIT_FAILURE;
 563   }
 564
 565   RetVal = EXIT_SUCCESS;
 566   while (fgets (Line, sizeof Line, Input) != NULL) {
 567     size_t                Length;
 568     const KEYLESS_COMMAND *KeylessCmd;
 569     const KEYED_COMMAND   *KeyedCmd;
 570
 571     Length = strlen (Line);
 572     assert (Length > 0);
 573     if (Line[Length - 1] != '\n') {
 574       fprintf (stderr, "%s: overlong line\n", __FUNCTION__);
 575       RetVal = EXIT_FAILURE;
 576       break;
 577     }
 578
 579     //
 580     // Strip [\r]\n.
 581     //
 582     Line[Length - 1] = '\0';
 583     if (Length >= 2 && Line[Length - 2] == '\r') {
 584       Line[Length - 2] = '\0';
 585     }
 586     //
 587     // Ignore empty lines and comments.
 588     //
 589     if (Line[0] == '\0' || Line[0] == '#') {
 590       if (Input != stdin) {
 591         //
 592         // ... but echo them back in non-interactive mode.
 593         //
 594         fprintf (Output, "%s\n", Line);
 595       }
 596       continue;
 597     }
 598
 599     //
 600     // Ironically, this is the kind of loop that should be replaced with an
 601     // ORDERED_COLLECTION.
 602     //
 603     for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL;
 604          ++KeylessCmd) {
 605       if (strcmp (KeylessCmd->Command, Line) == 0) {
 606         KeylessCmd->Function (Collection);
 607         break;
 608       }
 609     }
 610     if (KeylessCmd->Command != NULL) {
 611       continue;
 612     }
 613
 614     for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) {
 615       size_t CmdLength;
 616
 617       CmdLength = strlen (KeyedCmd->Command);
 618       assert (CmdLength >= 2);
 619       if (strncmp (KeyedCmd->Command, Line, CmdLength) == 0) {
 620         char *CommandArg, *EndPtr;
 621         long Value;
 622
 623         CommandArg = Line + CmdLength;
 624         errno = 0;
 625         Value = strtol (CommandArg, &EndPtr, 10);
 626         if (EndPtr == CommandArg ||            // no conversion performed
 627             errno != 0 ||                      // not in long's range, etc
 628             *EndPtr != '\0' ||                 // final string not empty
 629             Value < INT_MIN || Value > INT_MAX // parsed long not in int range
 630             ) {
 631           fprintf (stderr, "%s: %.*s: \"%s\": not an int\n", __FUNCTION__,
 632             (int)(CmdLength - 1), Line, CommandArg);
 633         } else {
 634           KeyedCmd->Function (Value, Collection);
 635         }
 636
 637         break;
 638       }
 639     }
 640     if (KeyedCmd->Command != NULL) {
 641       continue;
 642     }
 643
 644     fprintf (stderr, "%s: \"%s\": unknown command\n", __FUNCTION__, Line);
 645   }
 646
 647   if (RetVal == EXIT_SUCCESS && ferror (Input)) {
 648     fprintf (stderr, "%s: fgets(): %s\n", __FUNCTION__, strerror (errno));
 649     RetVal = EXIT_FAILURE;
 650   }
 651
 652   CmdForwardEmpty (Collection);
 653   OrderedCollectionUninit (Collection);
 654   return RetVal;
 655 }