SDA - Homework 2

Implementation by Andrei N. FLOREA (313CA)

Usage

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

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

The input should be formatted as such:

• <num_operations>
• <operation> [arguments]

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)

Operations

ADD <id> <score> <num_keywords> [keywords] ...

Adds a file to the search index

• id is a string that identifies the file
• score is an int and is the file's relevance
• num_keywords is the number of keywords associated with the file (more can be added later using ADDKW)
• keywords is a space-separated list of keywords associated with the file

The file gets created. Each keyword gets added to the file and to the keyword trie, saving a pointer to the file in the trie. The file is inserted into the file list.

The files are inserted lexicographically into the trie's nodes, so that the FIND command is easy to implement, only needing to find the end node for a given keyword and then simply print the file list.

Outputs OK if the file was added successfully, or EXISTS if a file with the given id already exists

DEL <id>

Deletes a file

• id is a string that identifies the file to be deleted

Each keyword associated with the file is searched in the keyword trie, and the pointer to the file is removed from the trie. If a keyword has no pointers left, it gets removed from the trie (as there are no files associated with it left). The file is deleted from the file list.

Outputs OK if the file was deleted successfully, or NOT FOUND a file with the given id does not exist

ADDKW <id> <keyword>

Adds a keyword to a file

• id is a string that identifies the file to be modified
• keyword is a string

The keyword is added to the file and to the keyword trie, saving a pointer to the file in the trie.

Outputs OK if the keyword was added successfully, or NOT FOUND a file with the given id does not exist

DELKW <id> <keyword>

Deletes a keyword from a file

• id is a string that identifies the file to be modified
• keyword is a string

The keyword is deleted from the file and it is searched in the keyword trie. The pointer to the file is removed from the trie. If the keyword has no pointers left, it gets removed from the trie.

Outputs OK if the keyword was deleted successfully, or NOT FOUND a file with the given id does not exist

FIND <keyword>

Prints all files that contain a given keyword

• keyword is a string

The keyword is searched in the keyword trie and, using the saved file pointers, the files that contain it are printed.

Outputs <num_files> <files> ... or EMPTY if there are no files or the keyword does not exist

TOPK <keyword> <k>

Prints the top k files that contain a given keyword. The files are sorted by their relevance score and by their name, if scores are equal. Prints at most k files, but can print less if the keyword is found in less than k files

• keyword is a string
• k is the number of files to print

The keyword is searched in the keyword trie and, using the saved file pointers, a max-heap is created based on the files' relevance score (and lexicographical order, if needed). k files are removed from the heap and printed in the order of their removal.

Outputs <num_files> <files> ... or EMPTY if there are no files or the keyword does not exist

PRINT

Prints all files that contain keywords, in lexicographical order

Does a recursive depth-first search on the keyword trie, saving partial keywords while doing so. If the current node is an end node, prints the partial (now full) keyword.

Outputs one line per keyword, with the format: <keyword> <num_files> or EMPTY if there are no keywords

PREFIX <prefix>

Prints all files that contain at least one keyword starting with a given prefix

• prefix is a string

The prefix is searched in the keyword trie, then, using a recursive depth-first search, adds all files in the resulting sub-trie into a lexicographically sorted file pointer list, which is subsequently printed.

Outputs <num_files> <files> ... or EMPTY if there are no files or the keyword does not exist

Data Structures

Search Index

struct search_index_t {
    FILE *in_file;
    FILE *out_file;

    dlls_t *files;
    trie_t *keyword_trie;
};

The search index is what stores the files and the keyword trie. It gets passed around the command interpreter to facilitate the program's functionality.

Doubly Linked List with Sentinel (dlls)

typedef struct dlls_node_t dlls_node_t;
struct dlls_node_t {
    void *data;
    dlls_node_t *prev, *next;
};

struct dlls_t {
    dlls_node_t *head;
    unsigned int data_size;
    unsigned int size;

    void (*free_data_func)(void *data);
};

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

For ease of use the dlls_create_simple() function is provided, which calls dlls_create() with free() as its 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

Trie

struct trie_t {
    trie_t *children[LETTERS_IN_ALPHABET];
    size_t num_children;

    dlls_t *files;
};

I chose to implement the trie without a containing structure, purely using trie nodes. This is helpful because every child of the trie is a trie itself, without having to place it in a containing structure; so the same functions that work on the trie will also work on its children.

Another choice I made was not having a field to mark nodes as the end of a node, instead using whether the node had a file list (files != NULL) or not.

What could have been done better is that the trie could have been more generic, but it wouldn't be too hard to take my implementation and make it more generic, if needed in the future.

Heap

struct heap_t {
    void **data;

    size_t heap_size;
    size_t heap_max_size;

    size_t data_size;
    void (*data_free)(void *);

    int (*compare)(void *, void *);
};

I implemented the heap as described in the course and in the lab. I chose to index the heap data starting at 0 and use the following formulas:

• parent index is at (child_index - 1) / 2
• left child index is at 2 * parent_index + 1
• right child index is at 2 * parent_index + 2

What could have been done better is that there could have been a mechanism to automatically resize the heap if it got full, but thankfully the default size I chose (1024 nodes) was plenty for this project.

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() implements the ADD operation
• op_del() implements the DEL operation
• op_addkw() implements the ADDKW operation
• op_delkw() implements the DELKW operation
• op_find() implements the FIND operation
• op_topk() implements the TOPK operation
• op_print() implements the PRINT operation
• op_prefix() implements the PREFIX 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)

tokenise_string()

Full header: char **tokenise_string(const char *str, const char *delim, int *ntokens)

• str is the string to tokenise. It is expected to be a null-terminated byte string
• delim is a string containing all delimitators. It is expected to be a null-terminated byte string
• ntokens is the number of tokens extracted by the function (return value)

Tokenises a string using strtok()

Returns a char * array containing all of the tokens found or NULL on failure

free_string_array()

Full header: void free_string_array(char **arr, size_t size)

Frees a char * array of the given size

Is useful for freeing the token array returned by tokenise_string()

Ending notes

The comments in the code could have been better, and I also did not manage to turn all of the comments before functions into Doxygen-formatted comments by the deadline.