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//
47static FILE *Input, *Output;
48
49
50//
51// Define a (potentially aggregate) key type.
52//
53typedef 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//
62typedef 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**/
83static
84INTN
85EFIAPI
86KeyCompare (
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**/
116static
117INTN
118EFIAPI
119UserStructCompare (
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**/
139static void
140CmdForwardEmpty (
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**/
172static void
173CmdBackwardEmpty (
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**/
202static void
203CmdForwardList (
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**/
224static void
225CmdBackwardList (
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**/
249static void
250CmdInsert (
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
291ReleaseUserStruct:
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**/
304static void
305CmdFind (
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**/
336static void
337CmdDelete (
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
364typedef struct {
365  const char *Command;
366  void       (*Function) (ORDERED_COLLECTION *Collection);
367  const char *Description;
368} KEYLESS_COMMAND;
369
370typedef struct {
371  const char *Command;
372  void       (*Function) (int Value, ORDERED_COLLECTION *Collection);
373  const char *Description;
374} KEYED_COMMAND;
375
376static 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
396static 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**/
410static void
411ListCommands (
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**/
440static void
441SetupInputOutput (
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
546int
547main (
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}
656