+/** @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
+ This program and the accompanying materials are licensed and made available\r
+ under the terms and conditions of the BSD License which accompanies this\r
+ distribution. The full text of the license may be found at\r
+ http://opensource.org/licenses/bsd-license.\r
+\r
+ THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT\r
+ WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\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