11
\$\begingroup\$

I was recently doing an assignment for a job interview, which asked to create a simple key value database with 4 command line operations:

  1. create key value: Adds a key value pair/updates an existing key
  2. get key: Prints the value corresponding to key, if it exists
  3. del key: Deletes a key value pair
  4. ts key: Returns the timestamps a key was first set and last set

It was to be written in C with no external database libraries. I successfully implemented it (although it took longer than recommended- hadn't worked with C strings for a while). However, I did not progress to the next step of the application process.

What ways can I improve? Even some general tips would be great. I've only been programming for a year and a half (undergraduate was in mathematics), so I am aware that the code is probably packed with bad conventions etc.

General Idea

The general idea of my implementation was to have an index binary file which would provide file offsets for each key index (first two letters of key) to allow fast lookup. Another binary file would store the key value pairs and any timestamps etc contiguously to save memory.

To set, the key is added to the index file. This calculated offset then gives the offset at which the key should be added/updated. The data file is then rewritten to include the new key/updated key. The rewriting is expensive, but if the database was large you could implement multiple data files pointed to by the index file. Plus I wasn;t sure how you'd get around rewriting the files for .bin/.txt files.

To get, the index file is used to calculate the file offset. The key is then searched for using this offset and the corresponding value (if there is one) is returned.

main.c

/**
 * @brief   Main function for implementing IO for the database.
 *          Database is a binary file, with an index file to make getting values faster.
 *          Binary file is quicker to write and read to. Data is stored dynamically and contiguously so memory footprint is small.
 *          All values are stored in alphabetical order in both index.bin and data.bin. This implementation is scalable. If database 
 *          will be large, can extend implementation to have multiple data files holding different alphabetical ranges. 
 *          These will be pointed to by the index file. 
 * @date    24-10-2023
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h> 
#include <sys/file.h>
#include <semaphore.h>
#include "definitions.h"
#include "index.h"
#include "set.h"
#include "get.h"

int main(int argc, char* argv[]){
    sem_t mutex;
    if (sem_init(&mutex, 0, 1) != 0) {
        perror("sem_init");
        return -1;
    }
    // Open files if they exist, else create them 
    FILE* index = fopen("index.bin", "r");
    if (index == NULL) index = fopen("index.bin", "w+");
    FILE* data = fopen("data.bin", "r");
    if (data == NULL) data = fopen("data.bin", "w+");
    
    if (index == NULL){
        perror("Error opening index.bin\n");
        return -1;
    }
    if (data == NULL){
        perror("Error opening data.bin\n");
        return -1;
    }
    char command[10];
    strncpy(command, argv[1], 10);

    if (strcmp(command, "set") == 0){
        if (argc != 4){
            printf("Incorrect numer of arguments entered\nUsage: ./test set key value\n");
            fclose(data); fclose(index);
            return 0;
        }
        // Begin by initialising a Pair struct
        Pair* entry = malloc(sizeof(Pair));
        entry -> keySize = strlen(argv[2]) + 1;
        if (entry -> keySize > MAX_KEY_SIZE){
            fprintf(stderr, "Entered key is too long. To adjust maximum key size, please edit #define in utility.h\n");
            fclose(data); fclose(index);
            return -1;
        }
        entry -> valueSize = strlen(argv[3]) + 1;
        if (entry -> valueSize > MAX_VALUE_SIZE){
            fprintf(stderr, "Entered value is too long. To adjust maximum value size, please edit #define in utility.h\n");
            fclose(data); fclose(index);
            return -1;
        }
        time(&(entry -> firstSet));
        time(&(entry -> lastSet));

        // Use semaphores to ensure exclusive write access 
        sem_wait(&mutex);
        set(data, index, argv[2], argv[3], entry, 0);
        sem_post(&mutex);

        free(entry);
    }
    else if (strcmp(command, "get") == 0){
        if (argc != 3){
            printf("Incorrect number of arguments entered.\nUsage: ./test get key\n");
            fclose(data); fclose(index);
            return -1;
        }
        // Don't need any semaphores here - writing processes write to a temp file then rename so no issues with reading
        get(data, index, argv[2], 0);

    }
    else if (strcmp(command, "ts") == 0){
        if (argc != 3){
            printf("Incorrect number of arguments entered.\nUsage: ./test ts key\n");
            fclose(data); fclose(index);
            return -1;
        }

        // Don't need any semaphores here - writing processes write to a temp file then rename so no issues with reading
        get(data, index, argv[2], 1);

    }
    else if (strcmp(command, "del") == 0){
        if (argc != 3){
            printf("Incorrect number of arguments entered.\nUsage: ./test del key\n");
            fclose(data); fclose(index);
            return -1;
        }
        char value[] = "null";
        Pair* entry = malloc(sizeof(Pair));
        // Use semaphores to ensure exclusive write
        sem_wait(&mutex);
        set(data, index, argv[2], value, entry, 1);
        sem_post(&mutex);
        free(entry);
    }
    else if (strcmp(command, "help") == 0){
        printf("Usage:\n");
        printf("./kvdb set key value\tSets a key value pair in the database\n");
        printf("./kvdb get key\t\tGets the value correspoding to the entered key from the database\n");
        printf("./kvdb ts key\t\tReturns the timestamp that this key was first and last set.\n");
        printf("./kvdb del key\t\tDeletes a key value pair from the database\n");
    }
    else{
        printf("Unknown command entered. For help type ./kvdb help\n");
    }
    sem_destroy(&mutex);
    fclose(index);
    fclose(data);
    return 0;
}

set.h

#ifndef SET_H_
#define SET_H_


int writePair(FILE* data, char* key, char* value, Pair* kv);
int addToData(FILE* data, char* key, char* value, Pair* entry, long int* difference, int mode);
int set(FILE* data, FILE* index, char* key, char* value, Pair* entry, int mode);

#endif

set.c

/**
 * @brief   File containing function definitions for setting/deleting lines to/from the database
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "definitions.h"
#include "index.h"

/**
 * @brief   Simple function to write a KV entry to file
 * @param[in]   data    Pointer to data file
 * @param[in]   key     String containing key
 * @param[in]   value   String containing value
 * @param[in]   kv      Pair object containing sizes of key and value as well as time first set and time last set
*/
int writePair(FILE* data, char* key, char* value, Pair* kv){
    if(fwrite(&(kv -> keySize), sizeof(size_t), 1, data) != 1) perror("ERROR: Failed writing key size\n");
    if(fwrite(&(kv -> valueSize), sizeof(size_t), 1, data) != 1) perror("ERROR: Failed writing value size\n");
    fwrite(key, 1, (kv -> keySize), data);
    fwrite(value, 1, (kv -> valueSize) , data);
    if(fwrite(&(kv -> firstSet), sizeof(time_t), 1, data) != 1) perror("ERROR: Failed writing firstSet\n");
    if(fwrite(&(kv -> lastSet), sizeof(time_t), 1, data) != 1) perror("ERROR: Failed writing lastSet\n");
    return 0;
}

/**
 * @brief   Function to write a new entry into the data file in the correct alphabetical position.
 * @param[in]   data    Pointer to data file
 * @param[in]   key     String containing key to be added
 * @param[in]   value   String containing value to be added
 * @param[in]   entry   Pair object containing sizes of key and value and times key was first set and last set
 * @param[in]   mode    Determines if a key is being added with set or deleted with del
 * @param[out]  difference  Contains, if the key is new, the size of the entry in bytes. If key exists and is being updated, 
 *                          contains the difference in size between the old and new value. If key is being deleted, contains
 *                          the size of the deleted chunk
*/
int addToData(FILE* data, char* key, char* value, Pair* entry, long int* difference, int mode){
    // Check if this is first value to be added
    rewind(data);
    // Open temp file
    FILE* tempData = fopen("tempData.bin", "w") ;
    if(tempData == NULL) printf("Error opening tempData.bin\n");
    Pair* read = malloc(sizeof(Pair));
    char* readKey = malloc(MAX_KEY_SIZE);
    char* readValue = malloc(MAX_VALUE_SIZE); 
    // Pair struct to hold read in entries
    if (fread(&(read -> keySize), sizeof(size_t), 1, data) == 0){
        writePair(tempData, key, value, entry);
    }
    else{
        rewind(data);
        int updated = 0;
        while(fread(&(read -> keySize), sizeof(size_t), 1, data) == 1){
            // Read in current KV entry from data file
            fread(&(read -> valueSize), sizeof(size_t), 1, data);
            readKey = realloc(readKey, read -> keySize);
            readValue = realloc(readValue, read -> valueSize);
            fread(readKey, 1, (read -> keySize), data);
            fread(readValue, 1, (read -> valueSize), data);
            readKey[(read -> keySize)-1] = '\0'; readValue[(read -> valueSize)-1] = '\0';
            if (fread(&(read -> firstSet), sizeof(time_t), 1, data) == 0) printf("firstSet not read in correctly\n");
            if (fread(&(read -> lastSet), sizeof(time_t), 1, data) == 0) printf("lastSet not read in correctly\n");

            // If the key already exists i.e. readKey == key, update and skip writing
            if (strcmp(key, readKey) == 0){
                if (mode == 0){
                    entry -> firstSet = read -> firstSet;   // Update first write
                    // Difference in size of new key value pair
                    *difference = ((entry -> keySize) + (entry -> valueSize)) - ((read -> keySize) + (read -> valueSize));  
                    writePair(tempData, key, value, entry);
                }
                else if (mode == 1){
                    // If deleting key, set difference to be minus the size of the deleted entry
                    *difference = -((read -> keySize) + (read -> valueSize) + 2*sizeof(size_t) + 2*sizeof(time_t));
                }
                updated = 1;
                continue;   // Replace line - don't write current line
            }
            // If the key didn't exist (we've passed where it should be in file), no updates required and don't skip writing
            else if (compareString(key, readKey) == 1 && updated == 0 && mode == 0){
                writePair(tempData, key, value, entry); // Don't replace line
                updated = 1;
            }
            // Write read entry to new temp file
            writePair(tempData, readKey, readValue, read);
        }
        // If not updated by the end of the file, add the entry to the end of file
        if (updated == 0 && mode == 0){
            writePair(tempData, key, value, entry);
            
        }
        else if (updated == 0 && mode == 1){
            printf("Key not found\n");
        }
    }
    // Free dynamically allocated memory
    free(readValue);
    free(readKey);
    free(read);
    // Now close files, delete old file and rename new file
    fclose(tempData);
    remove("data.bin");
    rename("tempData.bin", "data.bin");
    data = fopen("data.bin", "r");

    return 0;
}

/**
 * @brief Function to set a new key, update an old key or delete a key from the database. Handles updates to both index and data files
 * @param[in]   data    Pointer to file containing data
 * @param[in]   index   Pointer to file containing index
 * @param[in]   key     String containing key to be added/updated/deleted
 * @param[in]   value   If key to be added/updated, contains corresponding value. If key is to be deleted, contains "null"
 * @param[in]   entry   Holds other relevant variables; key size, value size and times key was first and last set
 * @param[in]   mode    Determines if key is to be added/updated (mode = 0) or deleted (mode = 1)
*/
int set(FILE* data, FILE* index, char* key, char* value, Pair* entry, int mode){
    size_t keySize = entry -> keySize;  // Extract values from struct
    size_t valueSize = entry -> valueSize;
    long int difference = 2*sizeof(size_t) + 2*sizeof(time_t) + keySize + valueSize;    // Initialise difference to be size of new KV entry
    addToData(data, key, value, entry, &difference, mode);  // Insert this line in data file and update difference var
    addIndexLine(index, key, difference);   // Update index.bin to account for this new/updated/deleted key
    return 0;
}

get.h

#ifndef GET_H_
#define GET_H_

#include <stdlib.h>
#include <stdio.h>

void printTime(time_t time);
int get(FILE* data, FILE* index, char* key, int mode);

#endif

get.c

/**
 * @brief   File containing functions to get KV pair/timestamp given the key
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "definitions.h"
#include "index.h"
/**
 * @brief Small function to print time in the required format to stdout
 * @param[in]   time    Time object containing seconds since 1/1/1970
*/
void printTime(time_t time){
    char buf[50];
    struct tm *ts = localtime(&time);
    strftime(buf, 50, "%Y-%m-%d %H:%M:%S", ts);
    printf("%s", buf);
}
/**
 * @brief Function that uses the index and file offsets in the index.bin file to quickly retrieve KV pairs.
 * @param[in]   data    Pointer to file containing data
 * @param[in]   index   Pointer to file holding index
 * @param[in]   mode    Whether get function should return KV or timestamp. mode == 0 => KV pair, mode == 1 => timestamp
 * @return  Returns 1 if key is found, 0 otherwise.
*/
int get(FILE* data, FILE* index, char* key, int mode){
    // First get index of key, if it exists
    long int startCount, endCount;
    int exists = getDataIndex(index, key, &startCount, &endCount);
    if (exists==0){
        printf("Key not found\n");
        return -1;
    }
    // Seek the starting offset given by the index file
    fseek(data, startCount, SEEK_SET);
    size_t readKeySize = 0; size_t readValueSize = 0;
    time_t firstSet, lastSet;

    // While within bounds given by index file, search for the key
    while(fread(&readKeySize, sizeof(size_t), 1, data) != 0 && ftell(data) <= endCount){
        fread(&readValueSize, sizeof(size_t), 1, data);
        // Use dynamically allocated memory due to variable array length
        char* readKey = malloc(readKeySize);
        char* readValue = malloc(readValueSize);
        fread(readKey, 1, readKeySize, data);
        fread(readValue, 1, readValueSize, data);
        readKey[readKeySize-1] = '\0'; readValue[readValueSize-1] = '\0';
        fread(&firstSet, sizeof(time_t), 1, data);
        fread(&lastSet, sizeof(time_t), 1, data);
        // If keys match, return either the KV pair or the timestamp
        if (strcmp(key, readKey) == 0){
            if (mode == 0)
                printf("Key: %s, value %s\n", key, readValue);
            else if (mode == 1){
                printf("Time first set:\t");
                printTime(firstSet);
                printf("\nTime last set:\t");
                printTime(lastSet);
                printf("\n");
            }
            return 1;
        }
        free(readKey);
        free(readValue);
    }
    printf("Key not found\n");
    return 0;
}

index.h

#ifndef INDEX_C_
#define INDEX_C_
#include <stdio.h>
int compareString(char* a, char* b);
void writeEntry(FILE* tempIndex, char* keyStart, size_t dataCount);
int addIndexLine(FILE* index, char *key, long int pairSize);
size_t getDataIndex(FILE* index, char *key, long int* startCount, long int* endCount);
#endif

index.c

/**
 * @brief   Function definitions for creating an ordered index of key starts, and their accompanying file offsets in the data.bin file
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
 * @brief   Compares the first two letters of two entered strings. Return is based on which string comes first when 
 *          ordered alphabetically
 * @param[in]   a   Pointer to the beginning of the first string
 * @param[in]   b   Pointer to the beginning of the second string
 * @return  Returns 0 if start of strings are equal, 1 if the first string is smaller and 2 if the first string is larger
*/
int compareString(char* a, char* b){
    char aStart[3]; char bStart[3];
    strncpy(aStart, a, 2);
    strncpy(bStart, b, 2);
    aStart[2] = '\0'; bStart[2] = '\0';
    if (strcmp(aStart, bStart) == 0)
        return 0;
    else if (a[0]<b[0])
        return 1;
    else if (a[0] == b[0] && a[1] < b[1] && strlen(a) >= 2 && strlen(b) >= 2)
        return 1;
    return 2;
}
/**
 * @brief Small function to write entries to index.bin
 * @param[in]   tempIndex   Pointer to the new index file that is being written to
 * @param[in]   keyStart    Pointer to char array holding the null terminated start of the key.
 * @param[in]   dataCount   Number of bytes written to the file after this entry is written
*/
void writeEntry(FILE* tempIndex, char* keyStart, size_t dataCount){
    if (fwrite(keyStart, 1, 2, tempIndex) != 2) 
        fprintf(stderr, "Error writing key start %s to index file\n", keyStart);
    if (fwrite(&dataCount, sizeof(size_t), 1, tempIndex) != 1) 
        fprintf(stderr, "Error writing dataCount for key start %s to index file\n", keyStart);
}

/**
 * @brief   This function updates the index.bin file when "set" or "del" commands are called. It handles a
 *          number of different cases:
 *              -   set: New key index (i.e. Key with unique two letter start): Creates new entry in index.bin with
 *                  the index and the file offset at which the key ends. 
 *              -   set: Existing key index: Updates the offset of the existing index to account for another KV pair 
 *                  being stored at this index.
 *              -   del: Non existant key: Prints "Key not found"
 *              -   del: Index corresponding to >1 KV pair: Updates the offset to remove element corresponding to entered key
 *              -   del: Index corresponding to 1 KV pair: Deletes this index record from index.bin
 * @param[in]   index       Pointer to index file
 * @param[in]   key         String containing key
 * @param[in]   pairSize    Contains one of the following (measures in bytes) depending on context:
 *                              - Size of new KV pair.
 *                              - Difference in size between new and old KV pairs (they have same key)
 *                              - Size of deleted entry (will be negative)
*/
int addIndexLine(FILE* index, char *key, long int pairSize){
    rewind(index);
    FILE* tempIndex = fopen("tempIndex.bin", "w");
    char ind[3];
    char keyStart[3];
    strncpy(keyStart, key, 2);
    keyStart[2] = '\0';
    int found = 0;
    size_t dataCount = 0;
    size_t prevDataCount = 0;
    // If file is new or wrong format encountered, add as first line
    if (fread(ind, 1, 2, index) == 0){
        dataCount += pairSize;
        writeEntry(tempIndex, keyStart, dataCount);
    }
    else{
        rewind(index);
        while(fread(ind, 1, 2, index) != 0){
            ind[2] = '\0';
            fread(&dataCount, sizeof(size_t), 1, index);
            // If correct posiiton already found, increase offset and continue to writing
            if (found != 0) dataCount += pairSize;
            // Else, check if this is the correct position
            else {
                int result = compareString(keyStart, ind);
                // If strings are equal, increase the count for the next string
                if (result == 0){
                    dataCount += pairSize;
                    found = 1;
                    if (prevDataCount == dataCount){
                        // In this case, the key has no bytes associated with it in data file i.e. it is deleted
                        continue;
                    }
                }
                // If key is less, must update this data count to be prevDataCount + pairSize and update next dataCount 
                else if (result == 1){
                    size_t thisCount = prevDataCount + pairSize;    // Update the new entry's count
                    dataCount = thisCount + (dataCount - prevDataCount);    // Update next 
                    writeEntry(tempIndex, keyStart, thisCount);
                    found = 1;
                }
                prevDataCount = dataCount;
            }
            // Now write back to file
            writeEntry(tempIndex, ind, dataCount);
        }
        // If adding to end of file, must update dataCount accordingly
        if (found == 0){
            dataCount += pairSize;
            writeEntry(tempIndex, keyStart, dataCount);
        }
    }
//    fclose(index);
    fclose(tempIndex);
    remove("index.bin");
    rename("tempIndex.bin", "index.bin");
    index = fopen("index.bin", "r");
    return 0;
}

/**
 * @brief Function to obtain a file offset range that contains a particular key. This can be used to rapidly obtain
 *        keys in the data file. 
 * @param[in]   index   Pointer to index.bin file.
 * @param[in]   key     Pointer to string containing key.
 * @param[out]  startCount  On return, holds the start file offset in bytes, where the key is located within [startCount, endCount]
 * @param[out]  endCount    On return, holds the end file offset in bytes.
*/
size_t getDataIndex(FILE* index, char *key, long int* startCount, long int* endCount){
    rewind(index);
    char ind[3];
    char keyStart[3];
    strncpy(keyStart, key, 2);
    keyStart[2] = '\0';
    // Initialise to 0 in case file is empty
    *startCount = 0;
    *endCount = 0;
    size_t dataCount = 0;
    // Read through to find the correct key start (if there is one) and return it's accompanying file offset range
    while(fread(ind, 1, 2, index) != 0){
        ind[2] = '\0';
        int result = compareString(keyStart, ind);
        fread(&dataCount, sizeof(size_t), 1, index);
        if (result == 0){
            *endCount = dataCount;
            return 1;
        }
        else if (result == 1){
            *endCount = *startCount;
            return 0;
        }
        *startCount = dataCount;
    }
    *endCount = *startCount;
    rewind(index);
    return 0;
}
\$\endgroup\$
3
  • \$\begingroup\$ Did you manually format the code? Is there a github repository I can clone? \$\endgroup\$
    – Harith
    Commented Nov 8, 2023 at 17:00
  • \$\begingroup\$ @Harith The github repo is github.com/AdamPapla/Key-Value-Database \$\endgroup\$
    – P4PL4
    Commented Nov 8, 2023 at 17:08
  • 3
    \$\begingroup\$ @P4PL4 Review char command[10]; strncpy(command, argv[1], 10); if (strcmp(command, "set") ... With argv[1] as "1234567890", command is not a string as it lacks a null character. Then strcmp(command, ... is UB. \$\endgroup\$ Commented Nov 9, 2023 at 13:46

4 Answers 4

10
\$\begingroup\$
  • mutex serves no purpose. It is not shared between processes, and your program is not multithreaded.

    If you want an exclusion between unrelated instances of the program, you need to place it in a named shared memory segment (see example).

  • // Don't need any semaphores here - writing processes write to a temp file then rename so no issues with reading

    Not so. First of all, every process writes to the same temp file (tempIndex.bin).

    After you fix this, there is still a race condition. Process P1 writes to temp1. Meanwhile, process P2 writes to temp2. After renaming, one of the edits is lost.

  • The line

      index = fopen("index.bin", "r");
    

    at the end of addIndexLine has no effect. The caller still has the original file pointer. BTW, after the call to addIndexLin the pointed file is closed, and cannot be used by a caller anymore. Doesn't look promising.

  • remove("data.bin") is superfluous. Just rename works as well.

  • Don't spell out the program name in the help/error messages. Use argv[0].

  • const-qualification of arguments is sorely missing.

  • compareString... What's wrong with strncmp?

PS: I didn't dig deep into the design of the DB files. To be honest, I was quickly lost.

\$\endgroup\$
3
  • \$\begingroup\$ How would I structure my code base so people don't get quickly lost? Should I split into smaller functions and more files or was it an issue of insufficient commenting? \$\endgroup\$
    – P4PL4
    Commented Nov 9, 2023 at 7:45
  • 1
    \$\begingroup\$ "Don't spell out the program name in the help/error messages. Use argv[0]." --> Now the help message includes the path/program name, rather than the just program name. Through executive call agrv[0] may be "". \$\endgroup\$ Commented Nov 11, 2023 at 10:25
  • 1
    \$\begingroup\$ @chux-ReinstateMonica True. However, (first) the chances of such invocation are infinitesimal, and (second) this is a rare case to advocate a global variable, as in char * progname = argv[0]; if (*progname == 0) { progname = "foobar"; }, to be used throughout the program. \$\endgroup\$
    – vnp
    Commented Nov 11, 2023 at 21:45
10
\$\begingroup\$

Enable more compiler warnings:

Adding:

-std=c99 -fPIC -gdwarf-4 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-      bounds -Wconversion  -Wstrict-prototypes -fanalyzer 

to the Makefile, I received:

$ make

gcc -g -std=c99 -fPIC -gdwarf-4 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion  -Wstrict-prototypes -fanalyzer  index.c set.c get.c -o kvdb kvdb.c

index.c: In function ‘addIndexLine’:

index.c:69:19: warning: conversion to ‘long unsigned int’ from ‘long int’ may change the sign of the result [-Wsign-conversion]

   69 |         dataCount += pairSize;

      |                   ^~

index.c:78:39: warning: conversion to ‘long unsigned int’ from ‘long int’ may change the sign of the result [-Wsign-conversion]

   78 |             if (found != 0) dataCount += pairSize;

      |                                       ^~

index.c:84:31: warning: conversion to ‘long unsigned int’ from ‘long int’ may change the sign of the result [-Wsign-conversion]

   84 |                     dataCount += pairSize;

      |                               ^~

index.c:93:54: warning: conversion to ‘long unsigned int’ from ‘long int’ may change the sign of the result [-Wsign-conversion]

   93 |                     size_t thisCount = prevDataCount + pairSize;    // Update the new entry's count

      |                                                      ^

index.c:105:23: warning: conversion to ‘long unsigned int’ from ‘long int’ may change the sign of the result [-Wsign-conversion]

  105 |             dataCount += pairSize;

      |                       ^~

index.c: In function ‘getDataIndex’:

index.c:141:25: warning: conversion to ‘long int’ from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]

  141 |             *endCount = dataCount;

      |                         ^~~~~~~~~

index.c:148:23: warning: conversion to ‘long int’ from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]

  148 |         *startCount = dataCount;

      |                       ^~~~~~~~~

index.c: In function ‘writeEntry’:

index.c:34:9: warning: use of possibly-NULL ‘tempIndex’ where non-null expected [CWE-690] [-Wanalyzer-possible-null-argument]

   34 |     if (fwrite(keyStart, 1, 2, tempIndex) != 2)

      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  ‘addIndexLine’: events 1-5

    |

    |   57 | int addIndexLine(FILE* index, char *key, long int pairSize){

    |      |     ^~~~~~~~~~~~

    |      |     |

    |      |     (1) entry to ‘addIndexLine’

    |   58 |     rewind(index);

    |   59 |     FILE* tempIndex = fopen("tempIndex.bin", "w");

    |      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~

    |      |                       |

    |      |                       (2) this call could return NULL

    |......

    |   68 |     if (fread(ind, 1, 2, index) == 0){

    |      |        ~

    |      |        |

    |      |        (3) following ‘true’ branch...

    |   69 |         dataCount += pairSize;

    |      |                   ~~

    |      |                   |

    |      |                   (4) ...to here

    |   70 |         writeEntry(tempIndex, keyStart, dataCount);

    |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    |      |         |

    |      |         (5) calling ‘writeEntry’ from ‘addIndexLine’

    |

    +--> ‘writeEntry’: events 6-7

           |

           |   33 | void writeEntry(FILE* tempIndex, char* keyStart, size_t dataCount){

           |      |      ^~~~~~~~~~

           |      |      |

           |      |      (6) entry to ‘writeEntry’

           |   34 |     if (fwrite(keyStart, 1, 2, tempIndex) != 2)

           |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

           |      |         |

           |      |         (7) argument 4 (‘tempIndex’) from (2) could be NULL where non-null expected

           |

In file included from index.c:4:

/usr/include/stdio.h:681:15: note: argument 4 of ‘fwrite’ must be non-null

  681 | extern size_t fwrite (const void *__restrict __ptr, size_t __size,

      |               ^~~~~~

index.c: In function ‘addIndexLine’:

index.c:114:12: warning: leak of FILE ‘index’ [CWE-775] [-Wanalyzer-file-leak]

  114 |     return 0;

      |            ^

  ‘addIndexLine’: events 1-2

    |

    |  113 |     index = fopen("index.bin", "r");

    |      |             ^~~~~~~~~~~~~~~~~~~~~~~

    |      |             |

    |      |             (1) opened here

    |  114 |     return 0;

    |      |            ~ 

    |      |            |

    |      |            (2) ‘index’ leaks here; was opened at (1)

    |

index.c:114:12: warning: leak of ‘index’ [CWE-401] [-Wanalyzer-malloc-leak]

  114 |     return 0;

      |            ^

  ‘addIndexLine’: events 1-2

    |

    |  113 |     index = fopen("index.bin", "r");

    |      |             ^~~~~~~~~~~~~~~~~~~~~~~

    |      |             |

    |      |             (1) allocated here

    |  114 |     return 0;

    |      |            ~ 

    |      |            |

    |      |            (2) ‘index’ leaks here; was allocated at (1)

    |

set.c: In function ‘addToData’:

set.c:71:35: warning: conversion to ‘long int’ from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]

   71 |                     *difference = ((entry -> keySize) + (entry -> valueSize)) - ((read -> keySize) + (read -> valueSize));

      |                                   ^

set.c:76:35: warning: conversion to ‘long int’ from ‘long unsigned int’ may change the sign of the result [-Wsign-conversion]

   76 |                     *difference = -((read -> keySize) + (read -> valueSize) + 2*sizeof(size_t) + 2*sizeof(time_t));

      |                                   ^

set.c: In function ‘set’:

set.c:123:27: warning: conversion to ‘long int’ from ‘long unsigned int’ may change the sign of the result [-Wsign-conversion]

  123 |     long int difference = 2*sizeof(size_t) + 2*sizeof(time_t) + keySize + valueSize;    // Initialise difference to be size of new KV entry

      |                           ^

set.c: In function ‘writePair’:

set.c:19:8: warning: use of NULL ‘data’ where non-null expected [CWE-476] [-Wanalyzer-null-argument]

   19 |     if(fwrite(&(kv -> keySize), sizeof(size_t), 1, data) != 1) perror("ERROR: Failed writing key size\n");

      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  ‘set’: events 1-2

    |

    |  120 | int set(FILE* data, FILE* index, char* key, char* value, Pair* entry, int mode){

    |      |     ^~~

    |      |     |

    |      |     (1) entry to ‘set’

    |......

    |  124 |     addToData(data, key, value, entry, &difference, mode);  // Insert this line in data file and update difference var

    |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    |      |     |

    |      |     (2) calling ‘addToData’ from ‘set’

    |

    +--> ‘addToData’: events 3-10

           |

           |   39 | int addToData(FILE* data, char* key, char* value, Pair* entry, long int* difference, int mode){

           |      |     ^~~~~~~~~

           |      |     |

           |      |     (3) entry to ‘addToData’

           |......

           |   43 |     FILE* tempData = fopen("tempData.bin", "w") ;

           |      |                      ~~~~~~~~~~~~~~~~~~~~~~~~~~

           |      |                      |

           |      |                      (4) allocated here

           |   44 |     if(tempData == NULL) printf("Error opening tempData.bin\n");

           |      |       ~                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

           |      |       |                  |

           |      |       |                  (7) ...to here

           |      |       (5) assuming ‘tempData’ is NULL

           |      |       (6) following ‘true’ branch (when ‘tempData’ is NULL)...

           |......

           |   49 |     if (fread(&(read -> keySize), sizeof(size_t), 1, data) == 0){

           |      |        ~

           |      |        |

           |      |        (8) following ‘true’ branch...

           |   50 |         writePair(tempData, key, value, entry);

           |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

           |      |         |

           |      |         (9) ...to here

           |      |         (10) calling ‘writePair’ from ‘addToData’

           |

           +--> ‘writePair’: events 11-12

                  |

                  |   18 | int writePair(FILE* data, char* key, char* value, Pair* kv){

                  |      |     ^~~~~~~~~

                  |      |     |

                  |      |     (11) entry to ‘writePair’

                  |   19 |     if(fwrite(&(kv -> keySize), sizeof(size_t), 1, data) != 1) perror("ERROR: Failed writing key size\n");

                  |      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                  |      |        |

                  |      |        (12) argument 4 (‘data’) NULL where non-null expected

                  |

In file included from set.c:6:

/usr/include/stdio.h:681:15: note: argument 4 of ‘fwrite’ must be non-null

  681 | extern size_t fwrite (const void *__restrict __ptr, size_t __size,

      |               ^~~~~~

set.c: In function ‘addToData’:

set.c:58:23: warning: dereference of possibly-NULL ‘read’ [CWE-690] [-Wanalyzer-possible-null-dereference]

   58 |             readKey = realloc(readKey, read -> keySize);

      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  ‘set’: events 1-2

    |

    |  120 | int set(FILE* data, FILE* index, char* key, char* value, Pair* entry, int mode){

    |      |     ^~~

    |      |     |

    |      |     (1) entry to ‘set’

    |......

    |  124 |     addToData(data, key, value, entry, &difference, mode);  // Insert this line in data file and update difference var

    |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    |      |     |

    |      |     (2) calling ‘addToData’ from ‘set’

    |

    +--> ‘addToData’: events 3-11

           |

           |   39 | int addToData(FILE* data, char* key, char* value, Pair* entry, long int* difference, int mode){

           |      |     ^~~~~~~~~

           |      |     |

           |      |     (3) entry to ‘addToData’

           |......

           |   44 |     if(tempData == NULL) printf("Error opening tempData.bin\n");

           |      |       ~

           |      |       |

           |      |       (4) following ‘false’ branch (when ‘tempData’ is non-NULL)...

           |   45 |     Pair* read = malloc(sizeof(Pair));

           |      |                  ~~~~~~~~~~~~~~~~~~~~

           |      |                  |

           |      |                  (5) ...to here

           |      |                  (6) this call could return NULL

           |......

           |   49 |     if (fread(&(read -> keySize), sizeof(size_t), 1, data) == 0){

           |      |        ~

           |      |        |

           |      |        (7) following ‘false’ branch...

           |......

           |   53 |         rewind(data);

           |      |         ~~~~~~~~~~~~

           |      |         |

           |      |         (8) ...to here

           |   54 |         int updated = 0;

           |   55 |         while(fread(&(read -> keySize), sizeof(size_t), 1, data) == 1){

           |      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

           |      |                                                                  |

           |      |                                                                  (9) following ‘true’ branch...

           |   56 |             // Read in current KV entry from data file

           |   57 |             fread(&(read -> valueSize), sizeof(size_t), 1, data);

           |      |                   ~~~~~~~~~~~~~~~~~~~~

           |      |                   |

           |      |                   (10) ...to here

           |   58 |             readKey = realloc(readKey, read -> keySize);

           |      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

           |      |                       |

           |      |                       (11) ‘read’ could be NULL: unchecked value from (6)

           |

get.c: In function ‘get’:

get.c:30:18: warning: conversion from ‘size_t’ {aka ‘long unsigned int’} to ‘int’ may change value [-Wconversion]

   30 |     int exists = getDataIndex(index, key, &startCount, &endCount);

      |                  ^~~~~~~~~~~~

kvdb.c: In function ‘main’:

kvdb.c:52:26: warning: dereference of possibly-NULL ‘entry’ [CWE-690] [-Wanalyzer-possible-null-dereference]

   52 |         entry -> keySize = strlen(argv[2]) + 1;

      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

  ‘main’: events 1-16

    |

    |   23 |     if (sem_init(&mutex, 0, 1) != 0) {

    |      |        ^

    |      |        |

    |      |        (1) following ‘false’ branch...

    |......

    |   28 |     FILE* index = fopen("index.bin", "r");

    |      |                   ~~~~~~~~~~~~~~~~~~~~~~~

    |      |                   |

    |      |                   (2) ...to here

    |   29 |     if (index == NULL) index = fopen("index.bin", "w+");

    |      |        ~

    |      |        |

    |      |        (3) following ‘false’ branch (when ‘index’ is non-NULL)...

    |   30 |     FILE* data = fopen("data.bin", "r");

    |      |                  ~~~~~~~~~~~~~~~~~~~~~~

    |      |                  |

    |      |                  (4) ...to here

    |   31 |     if (data == NULL) data = fopen("data.bin", "w+");

    |      |        ~

    |      |        |

    |      |        (5) following ‘false’ branch (when ‘data’ is non-NULL)...

    |   32 | 

    |   33 |     if (index == NULL){

    |      |        ~

    |      |        |

    |      |        (6) ...to here

    |      |        (7) following ‘false’ branch (when ‘index’ is non-NULL)...

    |......

    |   37 |     if (data == NULL){

    |      |        ~

    |      |        |

    |      |        (8) ...to here

    |      |        (9) following ‘false’ branch (when ‘data’ is non-NULL)...

    |......

    |   42 |     strncpy(command, argv[1], 10);

    |      |                          ~

    |      |                          |

    |      |                          (10) ...to here

    |   43 | 

    |   44 |     if (strcmp(command, "set") == 0){

    |      |        ~

    |      |        |

    |      |        (11) following ‘true’ branch (when the strings are equal)...

    |   45 |         if (argc != 4){

    |      |            ~

    |      |            |

    |      |            (12) ...to here

    |      |            (13) following ‘false’ branch (when ‘argc == 4’)...

    |......

    |   51 |         Pair* entry = malloc(sizeof(Pair));

    |      |                       ~~~~~~~~~~~~~~~~~~~~

    |      |                       |

    |      |                       (14) ...to here

    |      |                       (15) this call could return NULL

    |   52 |         entry -> keySize = strlen(argv[2]) + 1;

    |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    |      |                          |

    |      |                          (16) ‘entry’ could be NULL: unchecked value from (15)

    |

Though intimidating, these are all avoidable.

Magic Numbers:

There are magic numbers in the code: 2, 3, 50, et cetera. It would be better to create symbolic constants for them to make the code more readable and easier to maintain.

Formatting:

The formatting is inconsistent, and the line length used is too great. Consider using an automatic code formatter (perhaps GNU indent) and limiting the line length to 80.

Break main() into smaller functions.:

The main() function is too long and does too much. The code for opening/creating the file should be in a separate function. Similarly, the code for parsing the command-line arguments should be in a separate function.

Undefined behavior:

When run without arguments, the program exhibits undefined behavior and a segmentation fault occurs. This is likely due to copying argv[1] to command without checking if any arguments were provided. Note that argv[0] == NULL is also possible.

You do not need to make a copy of argv[1], use it directly in place of command.

Use standard status codes:

<stdlib.h> provides EXIT_SUCCESS and EXIT_FAILURE. Prefer using them to 0, 1, -1, et cetera.

Check the return value of library functions:

malloc() and family returns NULL to indicate failure. Failing to check the return value risks invoking undefined behavior by a subsequent NULL pointer deference.

Similarly, fopen() returns NULL to signal failure. Its return value is ignored in most cases.

FILE* tempData = fopen("tempData.bin", "w") ;
if(tempData == NULL) printf("Error opening tempData.bin\n");
...
// Pair struct to hold read in entries
if (fread(&(read -> keySize), sizeof(size_t), 1, data) == 0){
    writePair(tempData, key, value, entry);
}

I'd expect the function to return an error code in this case, instead of printing an error message to stdout, and then passing a NULL pointer to fwrite().

Half the calls to fread() and fwrite() have their return values ignored.

The return value of localtime() is also ignored. It returns NULL on failure.

realloc() is used incorrectly in the code. Given:

x = realloc(x, size);

if realloc() fails to allocate memory, it will assign NULL to x, and you'd lose access to the original memory, which would result in a memory leak.

Consider using a temporary variable like so:

const void *tmp = realloc(x, size);

if (!tmp) {
    /* realloc() failed. The original memory is left untouched. Handle error here. */
}

/* The original memory has been freed. It is safe to assign tmp to x now. */
x = tmp;

Functions that do not need to be visible outside of a translation unit should be declared as having internal linkage:

addToData(), writePair(), and compareString() should be declared with the static keyword.

Others:

  • Use a consistent brace style.
  • Use const for data that is not modified.
  • restrict in function parameters could allow for select optimizations.
  • main() should include definitions.h.
  • Use true and false from stdbool.h to represent a binary state instead of 1 and 0.
  • Send error messages to stderr.
  • Chains the calls to fwrite() into a single if statement like so:
    if (fwrite(...) != size 
        || fwrite(...) != size 
        ...
        || fwrite(...) != size) {
        /* Handle error here. */
    
  • Adjacent string literal tokens are concatenated. Use a single call to puts() for the help message.
  • Don't use spaces around the arrow operator. It doesn't help with readability.
  • There's a discrepancy in the usage messages. Usage messages for the commands get, set, ts, and del specify the program name to be ./test, whilst the help message specifies the program name to be ./kvdb.
  • Don't use printf()/fprintf() when their formatting capabilities are not required. Use puts()/fputs().
  • Don't write more than one statement on a single line unless you have something to hide.
  • CompareString() is not required. Consider using memcmp().
  • See: No, strncpy() is not a "safer" strcpy().
  • There's a memory leak in addIndexLine(), index was never passed to fclose(). Consider running the program under Valgrind.
  • It might be better to parse the command-line arguments with getopt() or argparse(). See: Parsing command-line arguments in C.
\$\endgroup\$
3
  • \$\begingroup\$ All fantastic points, I'll try to pay more attention to these things in future. Was there anything else about the implementation that you noticed from a logic standpoint? Was the idea of how to implement a KV database alright or was it a poor approach to begin with? I'm just wondering whether I got passed over due to the above poor practices or because I fundamentally didn't approach the problem correctly \$\endgroup\$
    – P4PL4
    Commented Nov 8, 2023 at 22:30
  • 1
    \$\begingroup\$ @P4PL4 I'm not very familiar with key-value databases, so I do not have much insight to offer on that topic. \$\endgroup\$
    – Harith
    Commented Nov 9, 2023 at 9:26
  • \$\begingroup\$ @Downvoter Do you have anything to say? \$\endgroup\$
    – Harith
    Commented Nov 12, 2023 at 13:21
4
\$\begingroup\$

Review .h include needs

Do not rely on other code to include the files for a given .c, .h file.

set.h needs <stdio.h> for FILE.
set.h needs TBD for Pair.
get.h needs <time.h> for time_t.
get.h does not need <stdlib.h>.
set.c should include "set.h", first.

A .h should include only the .h files it needs for a stand-alone compilation. A .c file likewise the .h files for a stand alone compilation, yet some extra .h files are not an issue and do provide collision detection.

Additional soapbox:
I wish the standard C library offered a simple <std.h> that included everything. We waste much time crafting .c files to include just the right ones and detect collisions. Compilers then readily can pre-compile one standard header. Some IDEs offer a tool to set these.

Simplify/improve compareString()

int compareString(const char* a, const char* b) {
  int cmp = strncmp(a,b, 2);
  if (cmp < 0) return 1;
  if (cmp > 0) return 2;
  return 0;
}

Perhaps re-write calling code to use strncmp() result directly?

Wrong use of strncpy()

Code uses strncpy() to prevent overrun, yet risks failing to form a string.

char command[10];
strncpy(command, argv[1], 10);  // BAD as `command` may now lack a null character

snprintf(command, sizeof command, "%s", argv[1]); is better.
Good compilers will emit efficient code.

Even this lacks error reporting.

I'd write a helper function for this as program arguments can be quite wild.

Something like:

char *my_strcpy(size_t sz, char dest[sz], char *source) {
  if (strlen(source) >= sz) {
    fprintf(stderr, "Destination buffer size [%zu] too small for <%s>.\n",
        sz, source);
    exit(EXIT_FAILURE);
  }
  return strcpy(dest, source);
}

Avoid naked magic number

// Add
#define TIME_BUF_YMDHMS_SZ 50

// char buf[50];
char buf[TIME_BUF_YMDHMS_SZ];

struct tm *ts = localtime(&time);
// strftime(buf, 50, "%Y-%m-%d %H:%M:%S", ts);
strftime(buf, sizeof buf, "%Y-%m-%d %H:%M:%S", ts);

With error checking:

#define TIME_YMDHMS_FMT "%Y-%m-%d %H:%M:%S"
#define TIME_BUF_YMDHMS_SZ (sizeof TIME_YMDHMS_FMT + 6 * 11/* typical longest int string */)

char buf[TIME_BUF_YMDHMS_SZ];

struct tm *ts = localtime(&time);
if (ts == NULL) {
  TBD_handle_error();
} 
if (strftime(buf, sizeof buf, TIME_YMDHMS_FMT, ts) == 0) {
  TBD_handle_error();
} 
\$\endgroup\$
3
\$\begingroup\$

Seems you are looping through index to get to your key position...at this point id suggest looking at hashtables/dictionaries, since this is what first comes to mind when talking about key-value data stores

\$\endgroup\$
4
  • 1
    \$\begingroup\$ IMHO, this should be a comment, not an answer. \$\endgroup\$ Commented Nov 11, 2023 at 13:21
  • 1
    \$\begingroup\$ @Billal the OP was asking: "What ways can I improve?"...in my humble opinion, this is the BEST way to improve, and excuse me if this sounds harsh: the main reason he didn't progress to the next step in the application process...Hashtables are a basic concept, and if you do programming, you must know them \$\endgroup\$ Commented Nov 11, 2023 at 13:32
  • \$\begingroup\$ @PerdiEstaquel Good and fair point about looping vs hashtable (vs BST vs whatever). \$\endgroup\$ Commented Nov 11, 2023 at 15:55
  • \$\begingroup\$ @PerdiEstaquel Thanks for the feedback! I had considered a BST and hash map, however I haven't encountered them in the context of writing to a file. From my understanding, these methods require the ability to index into an array. So, should I have made the KV entries of fixed size in the file so I could calculate file offsets (like one calculates memory offsets for an array)? \$\endgroup\$
    – P4PL4
    Commented Nov 12, 2023 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.