#231

Committed 02 Dec 2023 09:47AM UTC coverage: 95.331% (-4.7%) from 100.0%

Build # #231

Build Type

Pull #11

coveralls-ruby

Committed by

deavmi

Commit Message

CacheMap

- Implemented `removeKey(K key)`

Pull Request Pull Request #11: Feature: CacheMap, CacheList

Run Details

72 of 84 new or added lines in 1 file covered. (85.71%)

245 of 257 relevant lines covered (95.33%)

1042.02 hits per line

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

85.71

/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;
        }

        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);

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

    tValue = map.get("Tristan");
    assert(tValue == 1);

    // Thread.sleep(dur!("seconds")(5));

    // tValue = map.get("Tristan");
    // assert(tValue == 81);

    Thread.sleep(dur!("seconds")(11));

    tValue = map.get("Tristan");
    assert(tValue == 2);


    writeln("Sleeping now 11 secs");
    Thread.sleep(dur!("seconds")(11));
    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)	2✔
50	{
51	setValue(value);	2✔
52	timer = StopWatch(AutoStart.yes);	2✔
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;	2✔
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;	3✔
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))	1✔
154	{
155	this.replFunc = replFunc;	1✔
156	this.lock = new Mutex();	1✔
157	this.expirationTime = expirationTime;	1✔
158
159
160	this.condVar = new Condition(this.lock);	1✔
161	this.checker = new Thread(&checkerFunc);	1✔
162	this.isRunning = true;	1✔
163	this.checker.start();	1✔
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();	2✔
197
198	// On exit
199	scope(exit)
200	{
201	// Unlock the mutex
202	this.lock.unlock();	2✔
203	}
204
205	// Run the replacement function for this key
206	V newValue = replFunc(key);	2✔
207
208	// Create a new entry with this value
209	Entry!(V) newEntry = Entry!(V)(newValue);	2✔
210
211	// Save this entry into the hashmap
212	this.map[key] = newEntry;	2✔
213
214	return newValue;	2✔
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();	3✔
264
265	// On exit
266	scope(exit)
267	{
268	// Unlock the mutex
269	this.lock.unlock();	3✔
270	}
271
272	// Obtain the entry at this key
273	Entry!(V)* entry = key in this.map;	3✔
274
275	// If the key exists
276	if(entry != null)	3✔
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"); }	2✔
295	makeKey(key);	2✔
296	version(unittest) { writeln("fic"); }	2✔
297	}
298
299	return this.map[key].getValue();	3✔
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();	3✔
321
322	// On exit
323	scope(exit)
324	{
325	// Unlock the mutex
326	this.lock.unlock();	3✔
327	}
328
329	// The key's value
330	V keyValue;	3✔
331
332	// On access expiration check
333	keyValue = expirationCheck(key);	3✔
334
335	return keyValue;	3✔
336	}
337
338	public bool removeKey(K key)
339	{
340	// Lock the mutex
NEW 341	this.lock.lock();	×
342
343	// On exit
344	scope(exit)
345	{
346	// Unlock the mutex
NEW 347	this.lock.unlock();	×
348	}
349
350	// Remove the key
NEW 351	return this.map.remove(key);	×
352	}
353
354	/**
355	* Runs at the latest every
356	* `expirationTime` ticks
357	* and checks the entire
358	* map for expired
359	* entries
360	*/
361	private void checkerFunc()
362	{
363	while(this.isRunning)	4✔
364	{
365	// Lock the mutex
366	this.lock.lock();	3✔
367
368	// On loop exit
369	scope(exit)
370	{
371	// Unlock the mutex
372	this.lock.unlock();	3✔
373	}
374
375	// Sleep until timeout
376	this.condVar.wait(this.expirationTime);	3✔
377
378	// Run the expiration check
379	K[] marked;	3✔
380	foreach(K curKey; this.map.keys())	18✔
381	{
382	Entry!(V) curEntry = this.map[curKey];	3✔
383
384	// If entry has expired mark it for removal
385	if(curEntry.getElapsedTime() >= this.expirationTime)	3✔
386	{
387	version(unittest) { writeln("Marked entry '", curEntry, "' for removal"); }	2✔
388	marked ~= curKey;	2✔
389	}
390	}
391
392	foreach(K curKey; marked)	15✔
393	{
394	Entry!(V) curEntry = this.map[curKey];	2✔
395
396	version(unittest) { writeln("Removing entry '", curEntry, "'..."); }	2✔
397	this.map.remove(curKey);	2✔
398	}
399	}
400	}
401
402	/**
403	* Wakes up the checker
404	* immediately such that
405	* it can perform a cycle
406	* over the map and check
407	* for expired entries
408	*/
409	private void doLiveCheck()
410	{
411	// Lock the mutex
412	this.lock.lock();	1✔
413
414	// Signal wake up
415	this.condVar.notify();	1✔
416
417	// Unlock the mutex
418	this.lock.unlock();	1✔
419	}
420
421	/**
422	* On destruction, set
423	* the running status
424	* to `false`, then
425	* wake up the checker
426	* and wait for it to
427	* exit
428	*/
429	~this()
430	{
431	version(unittest)
432	{
433	writeln("Dtor running");	1✔
434
435	scope(exit)
436	{
437	writeln("Dtor running [done]");	1✔
438	}
439	}
440
441	// Set run state to false
442	this.isRunning = false;	1✔
443
444	// Signal to stop
445	doLiveCheck();	1✔
446
447	// Wait for it to stop
448	this.checker.join();	1✔
449	}
450	}
451	}
452
453	/**
454	* Tests the usage of the `CacheMap` type
455	* along with the expiration of entries
456	* mechanism
457	*/
458	unittest
459	{
460	int i=0;	1✔
461	int getVal(string)
462	{
463	i++;	2✔
464	return i;	2✔
465	}
466
467	CacheMap!(string, int) map = new CacheMap!(string, int)(&getVal);	1✔
468
469	// Get the value
470	int tValue = map.get("Tristan");	1✔
471	assert(tValue == 1);	1✔
472
473	tValue = map.get("Tristan");	1✔
474	assert(tValue == 1);	1✔
475
476	// Thread.sleep(dur!("seconds")(5));
477
478	// tValue = map.get("Tristan");
479	// assert(tValue == 81);
480
481	Thread.sleep(dur!("seconds")(11));	1✔
482
483	tValue = map.get("Tristan");	1✔
484	assert(tValue == 2);	1✔
485
486
487	writeln("Sleeping now 11 secs");	1✔
488	Thread.sleep(dur!("seconds")(11));	1✔
489	destroy(map);	1✔
490	}

deavmi / niknaks / #231

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