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