C Problem 1 C Problem Task description We will develop a key value store called YmirDB in the C programming language using dynamic data structures, ensuring that no memory errors occur. Each entry of the database is identified by a unique key string and contains a dynamically sized list of integer values and possibly other keys. Simple entry (strictly integer values) The simple entry is a key value store, where only integers are used as values. The following defines and initialises an entry with key identifier a with values: > SET a 1 2 3 ok > GET a [1 2 3] The values can be updated with other commands > SET a 1 2 3 ok > PUSH a 5 ok > GET a [5 1 2 3] > APPEND a 7 ok > GET a [5 1 2 3 7] > SET a 9 8 7 ok > GET a [9 8 7] An entry is termed simple if its values are only integers. C Problem 2 Managing states of the database What is state? The state of the database is comprised of all the keys, and their associated values at a given point in time. For example, when creating multiple keys, and their values, their state is preserved in memory. What are snapshots? A user may choose to save the current state of the database by calling SNAPSHOT. By doing so, a copy of the current state is saved and can be later referred to by its snapshot number. > SET a 1 2 3 ok > SNAPSHOT saved as snapshot 1 At a later time, the user may choose to replace the current state with a snapshot created at an earlier time. This is done using the CHECKOUT command. This does not affect other snapshots in memory. > SET a 1 2 3 ok > SNAPSHOT saved as snapshot 1 > SET a 4 5 6 ok > SNAPSHOT saved as snapshot 2 > SET a 7 8 9 ok > CHECKOUT 1 ok > GET a [ 1 2 3 ] > CHECKOUT 2 ok C Problem 3 > GET a [ 4 5 6 ] Alternatively, the user may choose to restore the state by loading a particular snapshot and discard all changes or snapshots made since that time. This is the ROLLBACK command. > SET a 1 2 3 ok > SNAPSHOT saved as snapshot 1 > SET a 4 5 6 ok > SNAPSHOT saved as snapshot 2 > SET a 7 8 9 ok > ROLLBACK 1 ok > GET a [ 1 2 3 ] > CHECKOUT 2 no such snapshot Snapshots and the current state are mutually disjoint. Actions on the current state should not influence any other snapshots Implementation details Write a program in C that implements YmirDB as shown in the examples. You can assume that our test cases will contain only valid input commands. You are guaranteed not to have NULL returned from malloc() or realloc() in this context. Keys are case sensitive and do not contain spaces. Keys are alphanumeric and must begin with an alphabetical character [a-z][A-Z]. The key length is no greater than 15 characters. Commands are case insensitive. C Problem 4 Entry values are indexed from 1. Snapshots are indexed from 1 and are unique for the lifetime of the program. Keys, entries and snapshots are to be displayed in the order from most recently added to least recently added. A snapshots keys and values should not have allocated memory associated with other snapshots. When listing snapshots, each snapshot should be separated by a newline character. Output for commands forward or backward references present the sorted lexicographical order by key and unique keys only. Your program must be contained in ymirdb.c and ymirdb.h and produce no errors Your program output must match the exact output format shown in the examples Your program must free all of the dynamic memory it allocates - This will be automatically checked using address sanitizer. No Variable Length Arrays (VLAs) No Excessive CPU usage (algorithms must be better than T(n2) average quadratic time) Using the header file structures as a guide for storage requirements of n entries, you will not be given examples that will exhaust more than 2n the memory required. Marks will be deducted if your program has memory leaks. excessive memory is used, e.g preallocation or over allocation of what is required. your program avoids malloc family of C functions to instantiate memory dynamically. uses unjustifiable magic numbers. uses files, or mapped memory. HEADER FILE C Problem 5 #ifndef YMIRDB_H #define YMIRDB_H #define MAX_KEY 16 #define MAX_LINE 1024 #include #include enum item_type { INTEGER=0, ENTRY=1 }; typedef struct element element; typedef struct entry entry; typedef struct snapshot snapshot; struct element { enum item_type type; union { int value; struct entry *entry ;} ;}; struct entry { char key[MAX_KEY]; char is_simple; element * values; size_t length; entry* next; entry* prev; size_t forward_size; size_t forward_max; entry** forward; // this entry depends on these size_t backward_size; size_t backward_max; entry** backward; // these entries depend on this }; struct snapshot { int id; entry* entries; snapshot* next; snapshot* prev; }; #endif Command C Problem 6 Your program should implement the following commands, look at the examples to see how they work. If a does not exist in the current state, output: no such key If a does not exist in the database, output: no such snapshot If an does not exist in an entry, output: index out of range If an cannot be removed, output: not permitted BYE clear database and exit HELP display this help message LIST KEYS displays all keys in current state LIST ENTRIES displays all entries in current state LIST SNAPSHOTS displays all snapshots in the database GET displays entry values DEL deletes entry from current state PURGE deletes entry from current state and snapshots SET sets entry values PUSH pushes values to the front APPEND appends values to the back PICK displays value at index PLUCK displays and removes value at index POP displays and removes the front value DROP deletes snapshot ROLLBACK restores to snapshot and deletes newer snapshots CHECKOUT replaces current state with a copy of snapshot SNAPSHOT saves the current state as a snapshot MIN displays minimum value MAX displays maximum value SUM displays sum of values LEN displays number of values REV reverses order of values UNIQ removes repeated adjacent values SORT sorts values in ascending order FORWARD lists all the forward references of this key BACKWARD lists all the backward references of this key TYPE displays if the entry of this key is simple or general EXAMPLES C Problem 7 C Problem 8 C Problem 9 C Problem 10

Attachments:

C-Problem.pdf