AppPkg: introduce OrderedCollectionTest
[mirror_edk2.git] / 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 }