SDA - Homework 1

Implementation by Andrei N. FLOREA (313CA)

Usage

To build, run make build. The binary is called tema1.

The program expects input in tema1.in and outputs in tema1.out and stderr.

The input should be formatted as such:

• <num_units>
• for the next <num_units> lines, <unit_id> <unit_type>
• <num_operations>
• <operation> [arguments]

Operations

ADD_INCIDENT <ID_incident> <priority> <description>

Adds an incident to the system, to be processed later

• ID_incident is an integer that should be unique from any previously added incidents
• priority can be one of high, medium or low
• description is a string of any length that must be delimited between double quotes (e.g. "description")

The added incident will be in the queued state until it is processed

CHECK_UNITS_AVAILABILITY

Outputs how many units are available to handle incidents (i.e. how many available units are queued)

DISPATCH

Starts an intervention (i.e. processes an incident using the first available unit from the unit queue)

The intervention is saved in the system for future reference

If an intervention cannot be started (either because there are no incidents to process or because there are no units available), outputs the INVALID OPERATION! ERROR 404 error

UNDO_LAST_DISPATCH

Stops the most recently started intervention that has not been finished, returns its unit to the unit queue and places the incident at the front of its specific incident queue

The stopped intervention is removed from the system, as it was cancelled temporarily

If there is no intervention to be stopped, outputs the INVALID OPERATION! ERROR 404 error

SOLVED_INCIDENT <ID_incident>

Marks the incident with id ID_incident as solved and returns the unit assigned to the incident to the unit queue

• ID_incident is an integer that should correspond to a previously added incident

If there is no incident with id ID_incident, outputs the INVALID OPERATION! ERROR 404 error

SHOW_UNIT <ID_unit>

Outputs the unit with id ID_unit

• ID_unit is an integer that should correspond to a previously added unit

The output is formatted as such:

Unit <ID_unit> is type <type[’A’/’B’/’C’]> and is [available/unavailable]

If there is no unit with id ID_unit, outputs the INVALID OPERATION! ERROR 404 error

SHOW_INCIDENT <ID_incident>

Outputs the incident with id ID_incident

• ID_incident is an integer that should correspond to a previously added incident

The output is formatted as such:

Incident <ID_incident> has <priority["low"/"medium"/"high"]> priority, the following description: "<description>" and is [queued/intervened/solved]

If there is no unit with id ID_incident, outputs the INVALID OPERATION! ERROR 404 error

SHOW_INTERVENTIONS

Outputs all interventions that were started (and, optionally, completed), in the order they were started

Each intervention is formatted as such:

Incident <ID_incident> was assigned to unit <ID_unit>, and has the following status: "<status_incident>"

If there are no interventions saved in the system, outputs the No intervention has been initiated error

Implementation details

The C standard I chose for this homework is ISO C11, for a good mix between modernity and C99. It would have been nice to have ISO C23 available but we use what we can, and fill in the gaps where needed (see Helper Functions)

Data Structures

Doubly Linked List with Sentinel (dlls)

This is a nice data type to implement, because the sentinel eliminates some of the headaches when adding/removing nodes and such

The dlls_t struct stores such a list. Notable additions besides the typical head and data_size are:

• size - how many elements are currently in the list, excluding the sentinel
• free_data_func - the function to be used when freeing the data member of a dlls node. I chose to add this so that the list may be used to store more complex data types which require additional handling to properly free (e.g. incident_t, which contains a description which must also be freed)

For ease of use, a default free_data_func is provided (i.e. default_dlls_free_data_func()) and also the dlls_create_simple() function, which calls dlls_create() with this default free_data_func function, so that a more "classic" interface for creating a list is available

Another notable addition is the dlls_get_index_by_key() function, which returns the index to the first node (i.e. with the lowest index) that satisfies the filter function (i.e. it returns true / a non-zero integer). The filter function must take in an id that is passed to dlls_get_index_by_key() to be used for its filtering. If no suitable node is found, returns DLLS_NO_SUCH_NODE

What could have been done better is the indexing in functions such as dlls_add_nth_node(), dlls_get_nth_node() or dlls_remove_nth_node(), by taking advantage of the fact that the list is doubly linked and circular, making node search operations take at most size / 2

Queue

The queue is implemented using a dlls, in which data is added to the end (except for queue_enqueue_at_start(), which is very sparsely used) and removed from the front

The queue_enqueue_at_start() was needed to implement the UNDO_LAST_DISPATCH operation

Stack

The stack is implemented using a dlls, in which data is added to the front and removed from the front

The Command Interpreter

The interpret_command() function is responsible for parsing an operation into the operation name (i.e. which function to call next) and, optionally, the operation's argument(s)

• op_add_incident() implements the ADD_INCIDENT operation
• op_check_units_availability() implements the CHECK_UNITS_AVAILABILITY operation
• op_dispatch() implements the DISPATCH operation
• op_undo_last_dispatch() implements the UNDO_LAST_DISPATCH operation
• op_solved_incident() implements the SOLVED_INCIDENT operation
• op_show_unit() implements the SHOW_UNIT operation
• op_show_incident() implements the SHOW_INCIDENT operation
• op_show_interventions() implements the SHOW_INTERVENTIONS operation

Helper Functions

This section wholly refers to the functions found in strings.c

dup_str()

Full header: char *dup_str(const char *str)

• str is expected to be a null-terminated byte string

Replicates strdup(), which is not available until ISO C23

Returns a copy of the string pointed to by str that takes up exactly as much space as is needed by the text + the null terminator, or NULL on failure

read_line_to_string()

Full header: char *read_line_to_string(FILE *stream)

• stream is expected to be a file descriptor of a file that was opened with the "rt" flags

Replicates getline(), which is a standard extension

Returns a null-terminated byte string containing a whole line read from stream, without the ending newline character

Note that if the file cursor is placed right before a newline, it will read an empty string (i.e. ensure there are no trailing newlines before calling)