Hash table with "Time To Live" elements

Recently, I got a very interesting task: to realize the hash table that works in multi-process server in common memory, each element of which must have a TTL property. It was suggested to implement the TTL, as an additional process that walks through the table every second and corrects the TTLs of elements. I think this solution is not enough elegant.

There is another way to realize this feature: while inserting and deleting check the TTL of handling element. This way also has a disadvantages: bigger worst time indexing, because it must shift some elements, non-unquet time in each process. But, I think it is more elegant, because it is only needed to check necessary elements.

Other limitations:

• hashtable works in common memory (Unix shared memory in core).

From 1st point follows

• Fixed size (N lines)

• Method "open addressing"

I think it is a very interesting task, so I decided to share with you my realization:

```
//-----------------------------------------
typedef int32_t ht_key_t;
typedef int32_t ht_val_t;
typedef uint32_t hash_t;

typedef struct hashtable_record
{ ht_key_t key;
ht_val_t val;
time_t ttl;
} ht_rec;
//-----------------------------------------
typedef struct hashtable_line
{ bool busy;
ht_rec data;
} ht_line;
//-----------------------------------------
typedef struct hash_table
{ char *shmemory;
size_t shm_size;
size_t lines_count;
ht_line *lines;
//------------------------
#ifdef _LOCK
mysem_t ln_semid;
mysem_t tb_semid;
myshm_t tb_shmid;
#endif // _LOCK
//------------------------
} hashtable;
//-----------------------------------------
#define TIME_EPS 0.01
/ Relative TTL to absolute TTL (in seconds) /
time_t ttl_converted (int32_t ttl)
{ return (time (NULL) + ttl); }
bool ttl_completed (time_t ttl)
{ return (difftime (time (NULL), ttl) > TIME_EPS); }
//-----------------------------------------
void hashtable_init (hashtable *ht, size_t lines_count, size_t shm_size);
void hashtable_

C++ is not C

Your code is very C - and very excessively brief and hard to follow. Let's C++ify it up. hashtable should be a class with member functions:

class Hashtable
{
public:
    struct rec {
        int32_t key;
        int32_t value;
        time_t ttl;
    };

    Hashtable(size_t lines_count, size_t shm_size);

    rec* find(int32_t key) const;
    bool insert(const rec& elem);
    // etc.

private:
    // whatever members as appropriate
};

This way, rather than your users having to deal with all these free functions (especially _init()), we can use this like a normal C++ container. Furthermore, if you make the important members private, your users can mess your container up accidentally - they just won't have access.

In that vein, prefer

static constexpr double TIME_EPSILON = 0.01;

to:

#define TIME_EPS 0.01

both for the better name (see below), and that generally avoiding macros is a good thing.

Naming

Characters are NOT at a premium. Your code will not run slower if you spend the time to write out variables names in a way that readers will understand. For instance, I have no idea what your he and h and ht mean in your get() function - where hashtable search is actually a really straightforward algorithm.

You want to provide names that are meaningful. That any other programmer can come to your code later and understand what is going on. Or even, that you coming back 6 months later can understand.

Spacing

There's a lot of different conventions for spacing and brace placement in C++. But this one is not good:

time_t  ttl_converted (int32_t ttl)
{ return (time (NULL) + ttl); }

I'd highly recommend either:

time_t ttl_converted(int32_t ttl) {
    return (time(NULL) + ttl);
}

or:

time_t ttl_converted(int32_t ttl)
{
    return (time(NULL) + ttl);
}

Either way, no space between function name and parentheses, no code on same line as opening brace. It's incredibly hard to read. And no run on else statements like:

else h = ht->lines_count;

Prefer:

else {
    h = ht->lines_count;
}

If you always use braces, you won't run into issues if you ever add a second line to your code blocks.

Also, one statement per line! Strongly prefer:

++h;
h_ret = h;

To:

++h; h_ret = h;

Though you can write both on the same line in a readable way:

h_ret = ++h;

walk

I don't know what hashtable_walk() is doing. It's the bulk of your code, but I can't follow it in the slightest. Sorry.

StackExchange Code Review Q#94645, answer score: 4