AppPkg: Replace BSD License with BSD+Patent License

[mirror_edk2.git] / AppPkg / Applications / OrderedCollectionTest / OrderedCollectionTest.c

/** @file\r
  A simple "fuzzer" application for OrderedCollectionLib, reading commands from\r
  the standard input, and writing results to the standard output.\r
\r
  Make sure you configure your platform so that the console stderr device is\r
  visible to the user (or else run the program from wherever stderr is visible\r
  per default, eg. serial line).\r
\r
  Copyright (C) 2014, Red Hat, Inc.\r
  Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.<BR>\r
\r
  SPDX-License-Identifier: BSD-2-Clause-Patent\r
**/\r
\r
#include <assert.h> // assert()\r
#include <errno.h>  // errno\r
#include <limits.h> // INT_MIN\r
#include <stdio.h>  // fgets()\r
#include <stdlib.h> // EXIT_FAILURE\r
#include <string.h> // strerror()\r
#include <unistd.h> // getopt()\r
\r
#include <Library/OrderedCollectionLib.h>\r
\r
//\r
// We allow the user to select between stdin+stdout and regular input+output\r
// files via command line options. We don't rely on shell redirection for two\r
// reasons:\r
//\r
// - The "old shell" doesn't support input redirection (<a, <);\r
//\r
// - The "new shell" supports input redirection (<a, <), but those redirections\r
//   break fgets(stdin). Both when redirecting stdin from an ASCII file (<a),\r
//   and when redirecting stdin from a UCS-2 file (<), the very first fgets()\r
//   spirals into an infinite loop, spewing ^@ on the serial console.\r
//\r
// Performing fopen() manually (made available to the user with the -i option),\r
// and reading from that stream with fgets() work under both old and new shell.\r
// Only ASCII encoded files are supported.\r
//\r
static FILE *Input, *Output;\r
\r
\r
//\r
// Define a (potentially aggregate) key type.\r
//\r
typedef struct {\r
  int Value;\r
} USER_KEY;\r
\r
//\r
// The user structure includes the key as one of its fields. (There can be\r
// several, optionally differently typed, keys, if we link user structures into\r
// several collections, with different comparators.)\r
//\r
typedef struct {\r
  unsigned char  Supplementary1[4];\r
  USER_KEY       Key;\r
  unsigned short Supplementary2[2];\r
} USER_STRUCT;\r
\r
\r
/**\r
  Compare a standalone key against a user structure containing an embedded key.\r
\r
  @param[in] StandaloneKey  Pointer to the bare key.\r
\r
  @param[in] UserStruct     Pointer to the user structure with the embedded\r
                            key.\r
\r
  @retval <0  If StandaloneKey compares less than UserStruct's key.\r
\r
  @retval  0  If StandaloneKey compares equal to UserStruct's key.\r
\r
  @retval >0  If StandaloneKey compares greater than UserStruct's key.\r
**/\r
static\r
INTN\r
EFIAPI\r
KeyCompare (\r
  IN CONST VOID *StandaloneKey,\r
  IN CONST VOID *UserStruct\r
  )\r
{\r
  const USER_KEY    *CmpKey;\r
  const USER_STRUCT *CmpStruct;\r
\r
  CmpKey    = StandaloneKey;\r
  CmpStruct = UserStruct;\r
\r
  return CmpKey->Value < CmpStruct->Key.Value ? -1 :\r
         CmpKey->Value > CmpStruct->Key.Value ?  1 :\r
         0;\r
}\r
\r
\r
/**\r
  Comparator function type for two user structures.\r
\r
  @param[in] UserStruct1  Pointer to the first user structure.\r
\r
  @param[in] UserStruct2  Pointer to the second user structure.\r
\r
  @retval <0  If UserStruct1 compares less than UserStruct2.\r
\r
  @retval  0  If UserStruct1 compares equal to UserStruct2.\r
\r
  @retval >0  If UserStruct1 compares greater than UserStruct2.\r
**/\r
static\r
INTN\r
EFIAPI\r
UserStructCompare (\r
  IN CONST VOID *UserStruct1,\r
  IN CONST VOID *UserStruct2\r
  )\r
{\r
  const USER_STRUCT *CmpStruct1;\r
\r
  CmpStruct1 = UserStruct1;\r
  return KeyCompare (&CmpStruct1->Key, UserStruct2);\r
}\r
\r
\r
/**\r
  Empty the collection by iterating forward through its entries.\r
\r
  This function demonstrates that iterators different from the one being\r
  removed remain valid.\r
\r
  @param[in,out] Collection  The collection to empty.\r
**/\r
static void\r
CmdForwardEmpty (\r
  IN OUT ORDERED_COLLECTION *Collection\r
  )\r
{\r
  ORDERED_COLLECTION_ENTRY *Entry;\r
\r
  Entry = OrderedCollectionMin (Collection);\r
  while (Entry != NULL) {\r
    ORDERED_COLLECTION_ENTRY *Next;\r
    void                     *Ptr;\r
    USER_STRUCT              *UserStruct;\r
\r
    Next = OrderedCollectionNext (Entry);\r
    OrderedCollectionDelete (Collection, Entry, &Ptr);\r
\r
    UserStruct = Ptr;\r
    fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value);\r
    free (UserStruct);\r
\r
    Entry = Next;\r
  }\r
}\r
\r
\r
/**\r
  Empty the collection by iterating backward through its entries.\r
\r
  This function demonstrates that iterators different from the one being\r
  removed remain valid.\r
\r
  @param[in,out] Collection  The collection to empty.\r
**/\r
static void\r
CmdBackwardEmpty (\r
  IN OUT ORDERED_COLLECTION *Collection\r
  )\r
{\r
  ORDERED_COLLECTION_ENTRY *Entry;\r
\r
  Entry = OrderedCollectionMax (Collection);\r
  while (Entry != NULL) {\r
    ORDERED_COLLECTION_ENTRY *Prev;\r
    void                     *Ptr;\r
    USER_STRUCT              *UserStruct;\r
\r
    Prev = OrderedCollectionPrev (Entry);\r
    OrderedCollectionDelete (Collection, Entry, &Ptr);\r
\r
    UserStruct = Ptr;\r
    fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value);\r
    free (UserStruct);\r
\r
    Entry = Prev;\r
  }\r
}\r
\r
\r
/**\r
  List the user structures linked into the collection, in increasing order.\r
\r
  @param[in] Collection  The collection to list.\r
**/\r
static void\r
CmdForwardList (\r
  IN ORDERED_COLLECTION *Collection\r
  )\r
{\r
  ORDERED_COLLECTION_ENTRY *Entry;\r
\r
  for (Entry = OrderedCollectionMin (Collection); Entry != NULL;\r
       Entry = OrderedCollectionNext (Entry)) {\r
    USER_STRUCT  *UserStruct;\r
\r
    UserStruct = OrderedCollectionUserStruct (Entry);\r
    fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value);\r
  }\r
}\r
\r
\r
/**\r
  List the user structures linked into the collection, in decreasing order.\r
\r
  @param[in] Collection  The collection to list.\r
**/\r
static void\r
CmdBackwardList (\r
  IN ORDERED_COLLECTION *Collection\r
  )\r
{\r
  ORDERED_COLLECTION_ENTRY *Entry;\r
\r
  for (Entry = OrderedCollectionMax (Collection); Entry != NULL;\r
       Entry = OrderedCollectionPrev (Entry)) {\r
    USER_STRUCT  *UserStruct;\r
\r
    UserStruct = OrderedCollectionUserStruct (Entry);\r
    fprintf (Output, "%s: %d\n", __FUNCTION__, UserStruct->Key.Value);\r
  }\r
}\r
\r
\r
/**\r
  Create a new user structure and attempt to insert it into the collection.\r
\r
  @param[in]     Value       The key value of the user structure to create.\r
\r
  @param[in,out] Collection  The collection to insert the new user structure\r
                             into.\r
**/\r
static void\r
CmdInsert (\r
  IN     int     Value,\r
  IN OUT ORDERED_COLLECTION *Collection\r
  )\r
{\r
  USER_STRUCT              *UserStruct, *UserStruct2;\r
  RETURN_STATUS            Status;\r
  ORDERED_COLLECTION_ENTRY *Entry;\r
\r
  UserStruct = calloc (1, sizeof *UserStruct);\r
  if (UserStruct == NULL) {\r
    fprintf (Output, "%s: %d: calloc(): out of memory\n", __FUNCTION__, Value);\r
    return;\r
  }\r
\r
  UserStruct->Key.Value = Value;\r
  Status = OrderedCollectionInsert (Collection, &Entry, UserStruct);\r
\r
  switch (Status) {\r
  case RETURN_OUT_OF_RESOURCES:\r
    fprintf (Output, "%s: %d: OrderedCollectionInsert(): out of memory\n",\r
      __FUNCTION__, Value);\r
    goto ReleaseUserStruct;\r
\r
  case RETURN_ALREADY_STARTED:\r
    UserStruct2 = OrderedCollectionUserStruct (Entry);\r
    assert (UserStruct != UserStruct2);\r
    assert (UserStruct2->Key.Value == Value);\r
    fprintf (Output, "%s: %d: already exists\n", __FUNCTION__,\r
      UserStruct2->Key.Value);\r
    goto ReleaseUserStruct;\r
\r
  default:\r
    assert (Status == RETURN_SUCCESS);\r
    break;\r
  }\r
\r
  assert (OrderedCollectionUserStruct (Entry) == UserStruct);\r
  fprintf (Output, "%s: %d: inserted\n", __FUNCTION__, Value);\r
  return;\r
\r
ReleaseUserStruct:\r
  free (UserStruct);\r
}\r
\r
\r
/**\r
  Look up a user structure by key in the collection and print it.\r
\r
  @param[in] Value       The key of the user structure to find.\r
\r
  @param[in] Collection  The collection to search for the user structure with\r
                         the key.\r
**/\r
static void\r
CmdFind (\r
  IN int                Value,\r
  IN ORDERED_COLLECTION *Collection\r
  )\r
{\r
  USER_KEY                 StandaloneKey;\r
  ORDERED_COLLECTION_ENTRY *Entry;\r
  USER_STRUCT              *UserStruct;\r
\r
  StandaloneKey.Value = Value;\r
  Entry = OrderedCollectionFind (Collection, &StandaloneKey);\r
\r
  if (Entry == NULL) {\r
    fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value);\r
    return;\r
  }\r
\r
  UserStruct = OrderedCollectionUserStruct (Entry);\r
  assert (UserStruct->Key.Value == StandaloneKey.Value);\r
  fprintf (Output, "%s: %d: found\n", __FUNCTION__, UserStruct->Key.Value);\r
}\r
\r
\r
/**\r
  Look up a user structure by key in the collection and delete it.\r
\r
  @param[in] Value       The key of the user structure to find.\r
\r
  @param[in] Collection  The collection to search for the user structure with\r
                         the key.\r
**/\r
static void\r
CmdDelete (\r
  IN int                Value,\r
  IN ORDERED_COLLECTION *Collection\r
  )\r
{\r
  USER_KEY                 StandaloneKey;\r
  ORDERED_COLLECTION_ENTRY *Entry;\r
  void                     *Ptr;\r
  USER_STRUCT              *UserStruct;\r
\r
  StandaloneKey.Value = Value;\r
  Entry = OrderedCollectionFind (Collection, &StandaloneKey);\r
\r
  if (Entry == NULL) {\r
    fprintf (Output, "%s: %d: not found\n", __FUNCTION__, Value);\r
    return;\r
  }\r
\r
  OrderedCollectionDelete (Collection, Entry, &Ptr);\r
\r
  UserStruct = Ptr;\r
  assert (UserStruct->Key.Value == StandaloneKey.Value);\r
  fprintf (Output, "%s: %d: removed\n", __FUNCTION__, UserStruct->Key.Value);\r
  free (UserStruct);\r
}\r
\r
\r
typedef struct {\r
  const char *Command;\r
  void       (*Function) (ORDERED_COLLECTION *Collection);\r
  const char *Description;\r
} KEYLESS_COMMAND;\r
\r
typedef struct {\r
  const char *Command;\r
  void       (*Function) (int Value, ORDERED_COLLECTION *Collection);\r
  const char *Description;\r
} KEYED_COMMAND;\r
\r
static const KEYLESS_COMMAND KeylessCommands[] = {\r
  { "forward-empty",  CmdForwardEmpty,\r
                      "empty the collection iterating forward" },\r
  { "fe",             CmdForwardEmpty,\r
                      "shorthand for forward-empty" },\r
  { "backward-empty", CmdBackwardEmpty,\r
                      "empty the collection iterating backward" },\r
  { "be",             CmdBackwardEmpty,\r
                      "shorthand for backward-empty" },\r
  { "forward-list",   CmdForwardList,\r
                      "list contents, iterating forward" },\r
  { "fl",             CmdForwardList,\r
                      "shorthand for forward-list" },\r
  { "backward-list",  CmdBackwardList,\r
                      "list contents, iterating backward" },\r
  { "bl",             CmdBackwardList,\r
                      "shorthand for backward-list" },\r
  { NULL }\r
};\r
\r
static const KEYED_COMMAND KeyedCommands[] = {\r
  { "insert ", CmdInsert, "insert value into collection" },\r
  { "i ",      CmdInsert, "shorthand for insert"         },\r
  { "find ",   CmdFind,   "find value in collection"     },\r
  { "f ",      CmdFind,   "shorthand for find"           },\r
  { "delete ", CmdDelete, "delete value from collection" },\r
  { "d ",      CmdDelete, "shorthand for delete"         },\r
  { NULL }\r
};\r
\r
\r
/**\r
  List the supported commands on stderr.\r
**/\r
static void\r
ListCommands (\r
  void\r
  )\r
{\r
  const KEYLESS_COMMAND *KeylessCmd;\r
  const KEYED_COMMAND   *KeyedCmd;\r
\r
  fprintf (stderr, "Supported commands:\n\n");\r
  for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL;\r
       ++KeylessCmd) {\r
    fprintf (stderr, "%-14s: %s\n", KeylessCmd->Command,\r
      KeylessCmd->Description);\r
  }\r
  for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) {\r
    fprintf (stderr, "%-9s<int>: %s\n", KeyedCmd->Command,\r
      KeyedCmd->Description);\r
  }\r
}\r
\r
\r
/**\r
  Configure stdio FILEs that we'll use for input and output.\r
\r
  @param[in] ArgC  The number of elements in ArgV, from main(). The environment\r
                   is required to ensure ArgC >= 1 (ie. that the program name,\r
                   ArgV[0], is available).\r
\r
  @param[in] ArgV  Command line argument list, from main().\r
**/\r
static void\r
SetupInputOutput (\r
  IN int  ArgC,\r
  IN char **ArgV\r
  )\r
{\r
  char *InputName, *OutputName;\r
  int  Loop;\r
\r
  assert (ArgC >= 1);\r
\r
  InputName  = NULL;\r
  OutputName = NULL;\r
  Loop       = 1;\r
\r
  while (Loop) {\r
    switch (getopt (ArgC, ArgV, ":i:o:h")) {\r
    case 'i':\r
      InputName = optarg;\r
      break;\r
\r
    case 'o':\r
      OutputName = optarg;\r
      break;\r
\r
    case 'h':\r
      fprintf (stderr,\r
        "%1$s: simple OrderedCollectionLib tester\n"\r
        "\n"\r
        "Usage: 1. %1$s [-i InputFile] [-o OutputFile]\n"\r
        "       2. %1$s -h\n"\r
        "\n"\r
        "Options:\n"\r
        "  -i InputFile : read commands from InputFile\n"\r
        "                 (will read from stdin if absent)\n"\r
        "  -o OutputFile: write command responses to OutputFile\n"\r
        "                 (will write to stdout if absent)\n"\r
        "  -h           : print this help and exit\n"\r
        "\n", ArgV[0]);\r
      ListCommands ();\r
      exit (EXIT_SUCCESS);\r
\r
//\r
// The current "compatibility" getopt() implementation doesn't support optopt,\r
// but it gracefully degrades these branches to the others (one of the optarg\r
// ones or the excess operands one).\r
//\r
#if 0\r
    case ':':\r
      fprintf (stderr, "%s: option -%c requires an argument; pass -h for "\r
        "help\n", ArgV[0], optopt);\r
      exit (EXIT_FAILURE);\r
\r
    case '?':\r
      fprintf (stderr, "%s: unknown option -%c; pass -h for help\n", ArgV[0],\r
        optopt);\r
      exit (EXIT_FAILURE);\r
#endif\r
\r
    case -1:\r
      if (optind != ArgC) {\r
        fprintf (stderr, "%s: excess operands on command line; pass -h for "\r
          "help\n", ArgV[0]);\r
        exit (EXIT_FAILURE);\r
      }\r
      Loop = 0;\r
      break;\r
\r
    default:\r
      assert (0);\r
    }\r
  }\r
\r
  if (InputName == NULL) {\r
    Input = stdin;\r
  } else {\r
    Input = fopen (InputName, "r");\r
    if (Input == NULL) {\r
      fprintf (stderr, "%s: fopen(\"%s\", \"r\"): %s\n", ArgV[0], InputName,\r
        strerror (errno));\r
      exit (EXIT_FAILURE);\r
    }\r
  }\r
\r
  if (OutputName == NULL) {\r
    Output = stdout;\r
  } else {\r
    Output = fopen (OutputName, "w");\r
    if (Output == NULL) {\r
      fprintf (stderr, "%s: fopen(\"%s\", \"w\"): %s\n", ArgV[0], OutputName,\r
        strerror (errno));\r
      exit (EXIT_FAILURE);\r
    }\r
  }\r
\r
  //\r
  // When reading commands from the standard input, assume interactive mode,\r
  // and list the supported commands. However, delay this until both streams\r
  // are set up.\r
  //\r
  if (InputName == NULL) {\r
    ListCommands ();\r
  }\r
}\r
\r
\r
int\r
main (\r
  IN int  ArgC,\r
  IN char **ArgV\r
  )\r
{\r
  int                RetVal;\r
  ORDERED_COLLECTION *Collection;\r
  char               Line[256];\r
\r
  SetupInputOutput (ArgC, ArgV);\r
\r
  Collection = OrderedCollectionInit (UserStructCompare, KeyCompare);\r
  if (Collection == NULL) {\r
    fprintf (stderr, "%s: OrderedCollectionInit(): out of memory\n",\r
      __FUNCTION__);\r
      return EXIT_FAILURE;\r
  }\r
\r
  RetVal = EXIT_SUCCESS;\r
  while (fgets (Line, sizeof Line, Input) != NULL) {\r
    size_t                Length;\r
    const KEYLESS_COMMAND *KeylessCmd;\r
    const KEYED_COMMAND   *KeyedCmd;\r
\r
    Length = strlen (Line);\r
    assert (Length > 0);\r
    if (Line[Length - 1] != '\n') {\r
      fprintf (stderr, "%s: overlong line\n", __FUNCTION__);\r
      RetVal = EXIT_FAILURE;\r
      break;\r
    }\r
\r
    //\r
    // Strip [\r]\n.\r
    //\r
    Line[Length - 1] = '\0';\r
    if (Length >= 2 && Line[Length - 2] == '\r') {\r
      Line[Length - 2] = '\0';\r
    }\r
    //\r
    // Ignore empty lines and comments.\r
    //\r
    if (Line[0] == '\0' || Line[0] == '#') {\r
      if (Input != stdin) {\r
        //\r
        // ... but echo them back in non-interactive mode.\r
        //\r
        fprintf (Output, "%s\n", Line);\r
      }\r
      continue;\r
    }\r
\r
    //\r
    // Ironically, this is the kind of loop that should be replaced with an\r
    // ORDERED_COLLECTION.\r
    //\r
    for (KeylessCmd = KeylessCommands; KeylessCmd->Command != NULL;\r
         ++KeylessCmd) {\r
      if (strcmp (KeylessCmd->Command, Line) == 0) {\r
        KeylessCmd->Function (Collection);\r
        break;\r
      }\r
    }\r
    if (KeylessCmd->Command != NULL) {\r
      continue;\r
    }\r
\r
    for (KeyedCmd = KeyedCommands; KeyedCmd->Command != NULL; ++KeyedCmd) {\r
      size_t CmdLength;\r
\r
      CmdLength = strlen (KeyedCmd->Command);\r
      assert (CmdLength >= 2);\r
      if (strncmp (KeyedCmd->Command, Line, CmdLength) == 0) {\r
        char *CommandArg, *EndPtr;\r
        long Value;\r
\r
        CommandArg = Line + CmdLength;\r
        errno = 0;\r
        Value = strtol (CommandArg, &EndPtr, 10);\r
        if (EndPtr == CommandArg ||            // no conversion performed\r
            errno != 0 ||                      // not in long's range, etc\r
            *EndPtr != '\0' ||                 // final string not empty\r
            Value < INT_MIN || Value > INT_MAX // parsed long not in int range\r
            ) {\r
          fprintf (stderr, "%s: %.*s: \"%s\": not an int\n", __FUNCTION__,\r
            (int)(CmdLength - 1), Line, CommandArg);\r
        } else {\r
          KeyedCmd->Function (Value, Collection);\r
        }\r
\r
        break;\r
      }\r
    }\r
    if (KeyedCmd->Command != NULL) {\r
      continue;\r
    }\r
\r
    fprintf (stderr, "%s: \"%s\": unknown command\n", __FUNCTION__, Line);\r
  }\r
\r
  if (RetVal == EXIT_SUCCESS && ferror (Input)) {\r
    fprintf (stderr, "%s: fgets(): %s\n", __FUNCTION__, strerror (errno));\r
    RetVal = EXIT_FAILURE;\r
  }\r
\r
  CmdForwardEmpty (Collection);\r
  OrderedCollectionUninit (Collection);\r
  return RetVal;\r
}\r