#242

Committed 04 Dec 2023 08:28AM UTC coverage: 96.629% (-3.4%) from 100.0%

Build # #242

Build Type

push

coveralls-ruby

Committed by

web-flow

Commit Message

Merge 2a94419fe into e9198ad03

Run Details

85 of 94 new or added lines in 1 file covered. (90.43%)

258 of 267 relevant lines covered (96.63%)

1003.29 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.43

/source/niknaks/containers.d

/**
 * Container types
 */
module niknaks.containers;

import core.sync.mutex : Mutex;


import std.datetime : Duration, dur;
import std.datetime.stopwatch : StopWatch, AutoStart;
import core.thread : Thread;
import core.sync.condition : Condition;
import std.functional : toDelegate;

version(unittest)
{
    import std.stdio : writeln;
}

/** 
 * Represents an entry of
 * some value of type `V`
 *
 * Associated with this
 * is a timer used to
 * check against for
 * expiration
 */
private template Entry(V)
{
    /**
     * The entry type
     */
    public struct Entry
    {
        private V value;
        private StopWatch timer;

        @disable
        private this();

        /** 
         * Creates a new entry
         * with the given value
         *
         * Params:
         *   value = the value
         */
        public this(V value)
        {
            setValue(value);
            timer = StopWatch(AutoStart.yes);
        }

        /** 
         * Sets the value of this
         * entry
         *
         * Params:
         *   value = the value
         */
        public void setValue(V value)
        {
            this.value = value;
        }

        /** 
         * Returns the value associated
         * with this entry
         *
         * Returns: the value
         */
        public V getValue()
        {
            return this.value;
        }

        /** 
         * Resets the timer back
         * to zero
         */
        public void bump()
        {
            timer.reset();
        }

        /** 
         * Gets the time elapsed
         * since this entry was
         * instantiated
         *
         * Returns: the elapsed
         * time
         */
        public Duration getElapsedTime()
        {
            return timer.peek();
        }
    }
}

/** 
 * A `CacheMap` with a key type of `K`
 * and value type of `V`
 */
public template CacheMap(K, V)
{
    private alias ReplacementDelegate = V delegate(K);
    private alias ReplacementFunction = V function(K);

    /** 
     * A caching map which when queried
     * for a key which does not exist yet
     * will call a so-called replacement
     * function which produces a result
     * which will be stored at that key's
     * location
     *
     * After this process a timer is started,
     * and periodically entries are checked
     * for timeouts, if they have timed out
     * then they are removed and the process
     * begins again.
     *
     * Accessing an entry will reset its
     * timer ONLY if it has not yet expired
     * however accessing an entry which
     * has expired causing an on-demand
     * replacement function call, just not
     * a removal in between
     */
    public class CacheMap
    {
        private Entry!(V)[K] map;
        private Mutex lock;
        private Duration expirationTime;
        private ReplacementDelegate replFunc;

        private Thread checker;
        private bool isRunning;
        private Condition condVar;
        
        /** 
         * Constructs a new cache map with the
         * given replacement delegate and the
         * expiration deadline.
         *
         * Params:
         *   replFunc = the replacement delegate
         *   expirationTime = the expiration
         * deadline
         */
        this(ReplacementDelegate replFunc, Duration expirationTime = dur!("seconds")(10))
        {
            this.replFunc = replFunc;
            this.lock = new Mutex();
            this.expirationTime = expirationTime;

          
            this.condVar = new Condition(this.lock);
            this.checker = new Thread(&checkerFunc);
            this.isRunning = true;
            this.checker.start();
          
        }

        /** 
         * Constructs a new cache map with the
         * given replacement function and the
         * expiration deadline.
         *
         * Params:
         *   replFunc = the replacement function
         *   expirationTime = the expiration
         * deadline
         */
        this(ReplacementFunction replFunc, Duration expirationTime = dur!("seconds")(10))
        {
            this(toDelegate(replFunc));
        }

        /** 
         * Creates an entry for the given
         * key by creating the `Entry`
         * at the key and then setting
         * that entry's value with the
         * replacement function
         *
         * Params:
         *   key = the key
         * Returns: the value set
         */
        private V makeKey(K key)
        {
            // Lock the mutex
            this.lock.lock();

            // On exit
            scope(exit)
            {
                // Unlock the mutex
                this.lock.unlock();
            }

            // Run the replacement function for this key
            V newValue = replFunc(key);

            // Create a new entry with this value
            Entry!(V) newEntry = Entry!(V)(newValue);

            // Save this entry into the hashmap
            this.map[key] = newEntry;
            
            return newValue;
        }

        /** 
         * Called to update an existing
         * `Entry` (already present) in
         * the map. This will run the 
         * replacement function and update
         * the value present.
         *
         * Params:
         *   key = the key
         * Returns: the value set
         */
        private V updateKey(K key)
        {
            // Lock the mutex
            this.lock.lock();

            // On exit
            scope(exit)
            {
                // Unlock the mutex
                this.lock.unlock();
            }

            // Run the replacement function for this key
            V newValue = replFunc(key);

            // Update the value saved at this key's entry
            this.map[key].setValue(newValue);

            return newValue;
        }

        /** 
         * Check's a specific key for expiration,
         * and if expired then refreshes it if
         * not it leaves it alone.
         *
         * Returns the key's value
         *
         * Params:
         *   key = the key to check
         * Returns: the key's value
         */
        private V expirationCheck(K key)
        {
            // Lock the mutex
            this.lock.lock();

            // On exit
            scope(exit)
            {
                // Unlock the mutex
                this.lock.unlock();
            }

            // Obtain the entry at this key
            Entry!(V)* entry = key in this.map;

            // If the key exists
            if(entry != null)
            {
                // If this entry expired, run the refresher
                if(entry.getElapsedTime() >= this.expirationTime)
                {
                    version(unittest) { writeln("Expired entry for key '", key, "', refreshing"); }
                    
                    updateKey(key);
                }
                // Else, if not, then bump the entry
                else
                {
                    entry.bump();
                }
            }
            // If it does not exist (then make it)
            else
            {
                version(unittest) { writeln("Hello there, we must MAKE key as it does not exist"); }
                makeKey(key);
                version(unittest) { writeln("fic"); }
            }

            return this.map[key].getValue();
        }

        /** 
         * Gets the value of
         * the entry at the
         * provided key
         *
         * This may or may not
         * call the replication
         * function
         *
         * Params:
         *   key = the key to
         * lookup by
         *
         * Returns: the value
         */
        public V get(K key)
        {
            // Lock the mutex
            this.lock.lock();

            // On exit
            scope(exit)
            {
                // Unlock the mutex
                this.lock.unlock();
            }

            // The key's value
            V keyValue;

            // On access expiration check
            keyValue = expirationCheck(key);

            return keyValue;
        }

        /** 
         * Removes the given key
         * returning whether or
         * not it was a success
         *
         * Params:
         *   key = the key to
         * remove
         * Returns: `true` if the
         * key existed, `false`
         * otherwise
         */
        public bool removeKey(K key)
        {
            // Lock the mutex
            this.lock.lock();

            // On exit
            scope(exit)
            {
                // Unlock the mutex
                this.lock.unlock();
            }

            // Remove the key
            return this.map.remove(key);
        }

        /** 
         * Runs at the latest every
         * `expirationTime` ticks
         * and checks the entire
         * map for expired
         * entries
         */
        private void checkerFunc()
        {
            while(this.isRunning)
            {
                // Lock the mutex
                this.lock.lock();

                // On loop exit
                scope(exit)
                {
                    // Unlock the mutex
                    this.lock.unlock();
                }

                // Sleep until timeout
                this.condVar.wait(this.expirationTime);

                // Run the expiration check
                K[] marked;
                foreach(K curKey; this.map.keys())
                {
                    Entry!(V) curEntry = this.map[curKey];

                    // If entry has expired mark it for removal
                    if(curEntry.getElapsedTime() >= this.expirationTime)
                    {
                        version(unittest) { writeln("Marked entry '", curEntry, "' for removal"); }
                        marked ~= curKey;
                    }
                }

                foreach(K curKey; marked)
                {
                    Entry!(V) curEntry = this.map[curKey];

                    version(unittest) { writeln("Removing entry '", curEntry, "'..."); }
                    this.map.remove(curKey);
                }
            }
        }

        /** 
         * Wakes up the checker
         * immediately such that
         * it can perform a cycle
         * over the map and check
         * for expired entries
         */
        private void doLiveCheck()
        {
            // Lock the mutex
            this.lock.lock();

            // Signal wake up
            this.condVar.notify();

            // Unlock the mutex
            this.lock.unlock();
        }

        /** 
         * On destruction, set
         * the running status
         * to `false`, then
         * wake up the checker
         * and wait for it to
         * exit
         */
        ~this()
        {
            version(unittest)
            {
                writeln("Dtor running");

                scope(exit)
                {
                    writeln("Dtor running [done]");
                }
            }

            // Set run state to false
            this.isRunning = false;

            // Signal to stop
            doLiveCheck();

            // Wait for it to stop
            this.checker.join();
        }
    }
}

/**
 * Tests the usage of the `CacheMap` type
 * along with the expiration of entries
 * mechanism
 */
unittest
{
    int i = 0;
    int getVal(string)
    {
        i++;
        return i;
    }

    CacheMap!(string, int) map = new CacheMap!(string, int)(&getVal, dur!("seconds")(10));

    // Get the value
    int tValue = map.get("Tristan");
    assert(tValue == 1);

    // Get the value (should still be cached)
    tValue = map.get("Tristan");
    assert(tValue == 1);

    // Wait for expiry (by sweeping thread)
    Thread.sleep(dur!("seconds")(11));

    // Should call replacement function
    tValue = map.get("Tristan");
    assert(tValue == 2);

    // Wait for expiry (by sweeping thread)
    writeln("Sleeping now 11 secs");
    Thread.sleep(dur!("seconds")(11));

    // Destroy the map (such that it ends the sweeper)
    destroy(map);
}

/**
 * Tests the usage of the `CacheMap`,
 * specifically the explicit key
 * removal method
 */
unittest
{
    int i = 0;
    int getVal(string)
    {
        i++;
        return i;
    }

    CacheMap!(string, int) map = new CacheMap!(string, int)(&getVal, dur!("seconds")(10));

    // Get the value
    int tValue = map.get("Tristan");
    assert(tValue == 1);

    // Remove the key
    assert(map.removeKey("Tristan"));

    // Get the value
    tValue = map.get("Tristan");
    assert(tValue == 2);

    // Destroy the map (such that it ends the sweeper
    destroy(map);
}

1	/**
2	* Container types
3	*/
4	module niknaks.containers;
5
6	import core.sync.mutex : Mutex;
7
8
9	import std.datetime : Duration, dur;
10	import std.datetime.stopwatch : StopWatch, AutoStart;
11	import core.thread : Thread;
12	import core.sync.condition : Condition;
13	import std.functional : toDelegate;
14
15	version(unittest)
16	{
17	import std.stdio : writeln;
18	}
19
20	/**
21	* Represents an entry of
22	* some value of type `V`
23	*
24	* Associated with this
25	* is a timer used to
26	* check against for
27	* expiration
28	*/
29	private template Entry(V)
30	{
31	/**
32	* The entry type
33	*/
34	public struct Entry
35	{
36	private V value;
37	private StopWatch timer;
38
39	@disable
40	private this();
41
42	/**
43	* Creates a new entry
44	* with the given value
45	*
46	* Params:
47	* value = the value
48	*/
49	public this(V value)	4✔
50	{
51	setValue(value);	4✔
52	timer = StopWatch(AutoStart.yes);	4✔
53	}
54
55	/**
56	* Sets the value of this
57	* entry
58	*
59	* Params:
60	* value = the value
61	*/
62	public void setValue(V value)
63	{
64	this.value = value;	4✔
65	}
66
67	/**
68	* Returns the value associated
69	* with this entry
70	*
71	* Returns: the value
72	*/
73	public V getValue()
74	{
75	return this.value;	5✔
76	}
77
78	/**
79	* Resets the timer back
80	* to zero
81	*/
82	public void bump()
83	{
84	timer.reset();	1✔
85	}
86
87	/**
88	* Gets the time elapsed
89	* since this entry was
90	* instantiated
91	*
92	* Returns: the elapsed
93	* time
94	*/
95	public Duration getElapsedTime()
96	{
97	return timer.peek();	4✔
98	}
99	}
100	}
101
102	/**
103	* A `CacheMap` with a key type of `K`
104	* and value type of `V`
105	*/
106	public template CacheMap(K, V)
107	{
108	private alias ReplacementDelegate = V delegate(K);
109	private alias ReplacementFunction = V function(K);
110
111	/**
112	* A caching map which when queried
113	* for a key which does not exist yet
114	* will call a so-called replacement
115	* function which produces a result
116	* which will be stored at that key's
117	* location
118	*
119	* After this process a timer is started,
120	* and periodically entries are checked
121	* for timeouts, if they have timed out
122	* then they are removed and the process
123	* begins again.
124	*
125	* Accessing an entry will reset its
126	* timer ONLY if it has not yet expired
127	* however accessing an entry which
128	* has expired causing an on-demand
129	* replacement function call, just not
130	* a removal in between
131	*/
132	public class CacheMap
133	{
134	private Entry!(V)[K] map;
135	private Mutex lock;
136	private Duration expirationTime;
137	private ReplacementDelegate replFunc;
138
139	private Thread checker;
140	private bool isRunning;
141	private Condition condVar;
142
143	/**
144	* Constructs a new cache map with the
145	* given replacement delegate and the
146	* expiration deadline.
147	*
148	* Params:
149	* replFunc = the replacement delegate
150	* expirationTime = the expiration
151	* deadline
152	*/
153	this(ReplacementDelegate replFunc, Duration expirationTime = dur!("seconds")(10))	2✔
154	{
155	this.replFunc = replFunc;	2✔
156	this.lock = new Mutex();	2✔
157	this.expirationTime = expirationTime;	2✔
158
159
160	this.condVar = new Condition(this.lock);	2✔
161	this.checker = new Thread(&checkerFunc);	2✔
162	this.isRunning = true;	2✔
163	this.checker.start();	2✔
164
165	}
166
167	/**
168	* Constructs a new cache map with the
169	* given replacement function and the
170	* expiration deadline.
171	*
172	* Params:
173	* replFunc = the replacement function
174	* expirationTime = the expiration
175	* deadline
176	*/
NEW 177	this(ReplacementFunction replFunc, Duration expirationTime = dur!("seconds")(10))	×
178	{
NEW 179	this(toDelegate(replFunc));	×
180	}
181
182	/**
183	* Creates an entry for the given
184	* key by creating the `Entry`
185	* at the key and then setting
186	* that entry's value with the
187	* replacement function
188	*
189	* Params:
190	* key = the key
191	* Returns: the value set
192	*/
193	private V makeKey(K key)
194	{
195	// Lock the mutex
196	this.lock.lock();	4✔
197
198	// On exit
199	scope(exit)
200	{
201	// Unlock the mutex
202	this.lock.unlock();	4✔
203	}
204
205	// Run the replacement function for this key
206	V newValue = replFunc(key);	4✔
207
208	// Create a new entry with this value
209	Entry!(V) newEntry = Entry!(V)(newValue);	4✔
210
211	// Save this entry into the hashmap
212	this.map[key] = newEntry;	4✔
213
214	return newValue;	4✔
215	}
216
217	/**
218	* Called to update an existing
219	* `Entry` (already present) in
220	* the map. This will run the
221	* replacement function and update
222	* the value present.
223	*
224	* Params:
225	* key = the key
226	* Returns: the value set
227	*/
228	private V updateKey(K key)
229	{
230	// Lock the mutex
NEW 231	this.lock.lock();	×
232
233	// On exit
234	scope(exit)
235	{
236	// Unlock the mutex
NEW 237	this.lock.unlock();	×
238	}
239
240	// Run the replacement function for this key
NEW 241	V newValue = replFunc(key);	×
242
243	// Update the value saved at this key's entry
NEW 244	this.map[key].setValue(newValue);	×
245
NEW 246	return newValue;	×
247	}
248
249	/**
250	* Check's a specific key for expiration,
251	* and if expired then refreshes it if
252	* not it leaves it alone.
253	*
254	* Returns the key's value
255	*
256	* Params:
257	* key = the key to check
258	* Returns: the key's value
259	*/
260	private V expirationCheck(K key)
261	{
262	// Lock the mutex
263	this.lock.lock();	5✔
264
265	// On exit
266	scope(exit)
267	{
268	// Unlock the mutex
269	this.lock.unlock();	5✔
270	}
271
272	// Obtain the entry at this key
273	Entry!(V)* entry = key in this.map;	5✔
274
275	// If the key exists
276	if(entry != null)	5✔
277	{
278	// If this entry expired, run the refresher
279	if(entry.getElapsedTime() >= this.expirationTime)	1✔
280	{
NEW 281	version(unittest) { writeln("Expired entry for key '", key, "', refreshing"); }	×
282
NEW 283	updateKey(key);	×
284	}
285	// Else, if not, then bump the entry
286	else
287	{
288	entry.bump();	1✔
289	}
290	}
291	// If it does not exist (then make it)
292	else
293	{
294	version(unittest) { writeln("Hello there, we must MAKE key as it does not exist"); }	4✔
295	makeKey(key);	4✔
296	version(unittest) { writeln("fic"); }	4✔
297	}
298
299	return this.map[key].getValue();	5✔
300	}
301
302	/**
303	* Gets the value of
304	* the entry at the
305	* provided key
306	*
307	* This may or may not
308	* call the replication
309	* function
310	*
311	* Params:
312	* key = the key to
313	* lookup by
314	*
315	* Returns: the value
316	*/
317	public V get(K key)
318	{
319	// Lock the mutex
320	this.lock.lock();	5✔
321
322	// On exit
323	scope(exit)
324	{
325	// Unlock the mutex
326	this.lock.unlock();	5✔
327	}
328
329	// The key's value
330	V keyValue;	5✔
331
332	// On access expiration check
333	keyValue = expirationCheck(key);	5✔
334
335	return keyValue;	5✔
336	}
337
338	/**
339	* Removes the given key
340	* returning whether or
341	* not it was a success
342	*
343	* Params:
344	* key = the key to
345	* remove
346	* Returns: `true` if the
347	* key existed, `false`
348	* otherwise
349	*/
350	public bool removeKey(K key)
351	{
352	// Lock the mutex
353	this.lock.lock();	1✔
354
355	// On exit
356	scope(exit)
357	{
358	// Unlock the mutex
359	this.lock.unlock();	1✔
360	}
361
362	// Remove the key
363	return this.map.remove(key);	1✔
364	}
365
366	/**
367	* Runs at the latest every
368	* `expirationTime` ticks
369	* and checks the entire
370	* map for expired
371	* entries
372	*/
373	private void checkerFunc()
374	{
375	while(this.isRunning)	5✔
376	{
377	// Lock the mutex
378	this.lock.lock();	3✔
379
380	// On loop exit
381	scope(exit)
382	{
383	// Unlock the mutex
384	this.lock.unlock();	3✔
385	}
386
387	// Sleep until timeout
388	this.condVar.wait(this.expirationTime);	3✔
389
390	// Run the expiration check
391	K[] marked;	3✔
392	foreach(K curKey; this.map.keys())	18✔
393	{
394	Entry!(V) curEntry = this.map[curKey];	3✔
395
396	// If entry has expired mark it for removal
397	if(curEntry.getElapsedTime() >= this.expirationTime)	3✔
398	{
399	version(unittest) { writeln("Marked entry '", curEntry, "' for removal"); }	2✔
400	marked ~= curKey;	2✔
401	}
402	}
403
404	foreach(K curKey; marked)	15✔
405	{
406	Entry!(V) curEntry = this.map[curKey];	2✔
407
408	version(unittest) { writeln("Removing entry '", curEntry, "'..."); }	2✔
409	this.map.remove(curKey);	2✔
410	}
411	}
412	}
413
414	/**
415	* Wakes up the checker
416	* immediately such that
417	* it can perform a cycle
418	* over the map and check
419	* for expired entries
420	*/
421	private void doLiveCheck()
422	{
423	// Lock the mutex
424	this.lock.lock();	2✔
425
426	// Signal wake up
427	this.condVar.notify();	2✔
428
429	// Unlock the mutex
430	this.lock.unlock();	2✔
431	}
432
433	/**
434	* On destruction, set
435	* the running status
436	* to `false`, then
437	* wake up the checker
438	* and wait for it to
439	* exit
440	*/
441	~this()
442	{
443	version(unittest)
444	{
445	writeln("Dtor running");	2✔
446
447	scope(exit)
448	{
449	writeln("Dtor running [done]");	2✔
450	}
451	}
452
453	// Set run state to false
454	this.isRunning = false;	2✔
455
456	// Signal to stop
457	doLiveCheck();	2✔
458
459	// Wait for it to stop
460	this.checker.join();	2✔
461	}
462	}
463	}
464
465	/**
466	* Tests the usage of the `CacheMap` type
467	* along with the expiration of entries
468	* mechanism
469	*/
470	unittest
471	{
472	int i = 0;	1✔
473	int getVal(string)
474	{
475	i++;	2✔
476	return i;	2✔
477	}
478
479	CacheMap!(string, int) map = new CacheMap!(string, int)(&getVal, dur!("seconds")(10));	1✔
480
481	// Get the value
482	int tValue = map.get("Tristan");	1✔
483	assert(tValue == 1);	1✔
484
485	// Get the value (should still be cached)
486	tValue = map.get("Tristan");	1✔
487	assert(tValue == 1);	1✔
488
489	// Wait for expiry (by sweeping thread)
490	Thread.sleep(dur!("seconds")(11));	1✔
491
492	// Should call replacement function
493	tValue = map.get("Tristan");	1✔
494	assert(tValue == 2);	1✔
495
496	// Wait for expiry (by sweeping thread)
497	writeln("Sleeping now 11 secs");	1✔
498	Thread.sleep(dur!("seconds")(11));	1✔
499
500	// Destroy the map (such that it ends the sweeper)
501	destroy(map);	1✔
502	}
503
504	/**
505	* Tests the usage of the `CacheMap`,
506	* specifically the explicit key
507	* removal method
508	*/
509	unittest
510	{
511	int i = 0;	1✔
512	int getVal(string)
513	{
514	i++;	2✔
515	return i;	2✔
516	}
517
518	CacheMap!(string, int) map = new CacheMap!(string, int)(&getVal, dur!("seconds")(10));	1✔
519
520	// Get the value
521	int tValue = map.get("Tristan");	1✔
522	assert(tValue == 1);	1✔
523
524	// Remove the key
525	assert(map.removeKey("Tristan"));	1✔
526
527	// Get the value
528	tValue = map.get("Tristan");	1✔
529	assert(tValue == 2);	1✔
530
531	// Destroy the map (such that it ends the sweeper
532	destroy(map);	1✔
533	}

deavmi / niknaks / #242

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous