numlockr

A Windows system tray application that monitors the state of the Num Lock key, restoring it to the active state if it is ever found to be inactive.

If you find your Num Lock key is being turned off by certain remote desktop applications, numlockr will prevent that.

Tested on Windows 10.

Download: https://sourceforge.net/projects/numlockr/

Circular Queue Class

While developing a streaming audio application, I found the need for a fast and reliable buffering mechanism. I developed a Queue Class and used it as a buffer, stuffing blocks of data in on one thread and pulling them out on another. The quality of the audio was greatly improved by this buffering mechanism. But I wanted something better, something that would perform as few conditional and allocation operations as possible. So I developed this circular queue class.

The number of elements in the queue is restricted to powers of two. Keeping track of front, back, overflow, and underflow requires only two internal member variables, one of which is incremented on every enqueue operation, the other is incremented on every dequeue operation (wrapping around to zero is expected and supported behavior). Applying a bitmask to one of these variables reduces the actual number to an “index” of the front or back of the queue, respectively. The bitmask value is calculated from the “size” (number of elements) specified during initialization. Allocation of the array of elements is also performed during initialization.

The only condition checked during an enqueue operation is an overflow test. The only condition checked during a dequeue operation is an underflow test. There is no “is initialized” test in these functions, so be sure to initialize an instance before using it!

Cross-platform permutations of the source (GitHub):
https://github.com/UniversalProgrammingOrganization/upo-lib/blob/master/upo-lib/CircularQueue.h
https://github.com/UniversalProgrammingOrganization/upo-lib/blob/master/upo-lib/CircularQueue.cpp

#define O void // for Object pointers (O*)
#define Z NULL // shorthand for NULL

class CQ // a circular queue class
{
public:
    DWORD m_dwNQs; // total number of enqueue operations
    DWORD m_dwDQs; // total number of dequeue operations
    DWORD m_dwIM;  // Index Mask - a bitmask
    O** m_ppE;     // pointer to array of elements

    CQ()
    {
        m_ppE = Z;
    };

    ~CQ()
    {
        Reset();
    };

    void Reset()
    {
        // free array of elements:
        if (m_ppE)
            delete [] m_ppE;
 
        m_dwNQs = 0;
        m_dwDQs = 0;
        m_dwIM = 0;
        m_ppE = Z;
    }
 
    bool Init(
        DWORD dwSize)
    {
        // allow object re-use:
        Reset();
 
        // verify size is not zero:
        if (dwSize == 0)
            return false;
 
        // calculate the bit mask:
        m_dwIM = dwSize - 1;
 
        // verify size is a power of 2:
        if (dwSize & (m_dwIM))
            return false;
 
        // allocate the queue elements:
        m_ppE = new O*[dwSize];
 
        // will return true only if all of the above succeeded:
        return (m_ppE != Z);
    };
 
    // enqueue function:
    O* NQ(O* pO)
    {
        // check for overflow:
        if (Size() > m_dwIM)
            return Z;
 
        // calculate the enqueue index:
        DWORD dwEi = (m_dwNQs & m_dwIM);
 
        // set the element value:
        *(m_ppE + dwEi) = pO;
 
        // increment enqueue count:
        m_dwNQs++;
 
        return pO;
    };
 
    // dequeue function:
    O* DQ()
    {
        // get the element value:
        O* pO = Peek();
 
        // increment dequeue count (if no peek error):
        if (pO != Z)
            m_dwDQs++;
 
        return pO;
    };
 
    O* Peek()
    {
        // check for underflow:
        if (Size() == 0)
            return Z;
 
        // calculate the dequeue index:
        DWORD dwDi = (m_dwDQs & m_dwIM);

        // return the element value:
        return *(m_ppE + dwDi);
    };
 
    // returns the distance between m_dwDQs and m_dwNQs
    // (the size of the actual queue contents):
    DWORD Size()
    {
        if (m_dwDQs < m_dwNQs)
            return (m_dwNQs - m_dwDQs);
        else
            return (m_dwDQs - m_dwNQs);
    };
};

The above “Size()” function would look shorter if it was constructed like this:

    DWORD Size()
    {
      return abs(m_dwDQs - m_dwNQs);
    };

But the “abs()” function is typically implemented like this:

    int abs(int n)
    {
        if (n >= 0)
            return n;
        else
            return -n;
    };

Queue Class

If you are programming with .Net, there is a queue class already implemented for you. If you have ever endured a “white board” programming interview, however, you may have discovered that it helps to have implementations already committed to memory for queues, trees, lists, stacks, and tables (among other things). There is a unique opportunity here to take ownership of your success, at the lowest level, and bring your own best work to the table. Sure, you could look up a queue implementation online (like the one illustrated in this post), memorize it, and use it for an interview question or even incorporate it into a program; but your chances of success will be much higher if you develop and test your own queue class.

In the interest of brevity (and the minimization of keystrokes or whiteboard characters), I have used shorthand code in the following example.

This queue class is far from optimal. It assumes an ideal processing environment in which the cost of allocating/deallocating memory is low and can be called repeatedly. A far better implementation would either have a fixed number of possible elements or an increment by which the element count can grow (other than 1 for each enqueue and -1 for each dequeue, as in this example).

Content of Queue.h:

#define O void // for Object pointers (O*)
#define Z NULL // shorthand for NULL
 
class E // represents a queue Element
{
public:
    O* m_pO; // pointer to an Object
    E* m_pN; // pointer to the Next element
 
    E(O* pO) // Element constructor
    {
        m_pO = pO;
        m_pN = Z;
    };
};
 
class Q // represents a Queue
{
public:
    E* m_pF; // pointer to the Front element
    E* m_pB; // pointer to the Back element
 
    Q() // Queue constructor
    {
        m_pF = Z;
        m_pB = Z;
    };
 
    ~Q() // Queue destructor
    {
        while (m_pF) // while the front element is not NULL,
        {
            DQ(); // dequeue elements
        }
    };
 
    E* NQ(O* pO) // Enqueue function
    {
        if (!pO) // if the object pointer is NULL,
        {
            return Z; // do not enqueue
        }
 
        E* pE = new E(pO); // create a new element
 
        if (pE) // if the element was allocated,
        {
            if (m_pB) // if the back element is not NULL,
            {
                m_pB->m_pN = pE; // uptate the next pointer of the back element
            }
 
            m_pB = pE; // place the new element at the back of the queue
 
            if (!m_pF) // if the front element is NULL,
            {
                m_pF = m_pB; // set the front element equal to the back element
            }
        }
 
        return pE; // return the new element pointer
    };
 
    O* DQ() // Dequeue function
    {
        E* pE = m_pF; // get the element at the front of the queue
 
        if (pE) // if the element is not NULL,
        {
            m_pF = m_pF->m_pN; // point the front element at the next element
 
            if (!m_pF) // if the front element is NULL,
            {
                m_pB = Z; // set the back element to NULL
            }
 
            O* pO = pE->m_pO; // get the object pointer from the element
 
            delete pE; // delete the element
 
            return pO; // return the object pointer
        }
        else // if the element is NULL,
        {
            return Z; // return NULL, as the queue is empty
        }
    };
};

Content of a test program (windows console application):

#define WIN32_LEAN_AND_MEAN
#define WINVER 0x0400
#define _WIN32_WINNT 0x0400
#define _CRTDBG_MAP_ALLOC
 
#include 
#include 
#include 
#include "Queue.h"
 
#define I 7
 
_TCHAR szA[] = _T("alpha");
_TCHAR szB[] = _T("bravo");
_TCHAR szC[] = _T("charlie");
_TCHAR szD[] = _T("delta");
_TCHAR szE[] = _T("echo");
_TCHAR szF[] = _T("foxtrot");
_TCHAR szG[] = _T("golf");
 
_TCHAR* items[I] = { szA, szB, szC, szD, szE, szF, szG };
 
int _tmain(int argc, _TCHAR* argv[])
{
        Q q;
    int i = 0;
    _TCHAR* szOut = NULL;
 
    //
    // verify output items match input items
    //
 
    // fill the queue:
    for (i = 0; i < I; i++)
    {
        if (NULL == q.NQ((O*)items[i]))
        {
            _tcprintf(_T("Fail: verify output items match input items; enqueue\r\n"));
            return 0;
        }
    }
    // test the queue contents:
    for (i = 0; (NULL != (szOut = (_TCHAR*)q.DQ())); i++)
    {
        if (_tcscmp(szOut, items[i]) != 0)
        {
            _tcprintf(_T("Fail: verify output items match input items; content\r\n"));
            return 0;
        }
    }
    // test the item count:
    if (i != I)
    {
        _tcprintf(_T("Fail: verify output items match input items; count\r\n"));
        return 0;
    }
    // write pass message:
    _tcprintf(_T("Pass: verify output items match input items\r\n"));
 
    //
    // verify empty queue
    //
 
    // the queue should now be empty:
    if (NULL != q.DQ())
    {
        _tcprintf(_T("Fail: verify empty queue\r\n"));
        return 0;
    }
    // write pass message:
    _tcprintf(_T("Pass: verify empty queue\r\n"));
 
    //
    // verify enqueue after partial dequeue
    //
 
    // fill the queue with 3 items:
    for (i = 0; i < 3; i++)
    {
        if (NULL == q.NQ((O*)items[i]))
        {
            _tcprintf(_T("Fail: verify enqueue after partial dequeue; enqueue\r\n"));
            return 0;
        }
    }

    // dequeue 2 items:
    for (i = 0; i < 2; i++)
    {
        if (NULL == q.DQ())
        {
            _tcprintf(_T("Fail: verify enqueue after partial dequeue; dequeue\r\n"));
            return 0;
        }
    }

    // add 4 more items to the queue:
    for (i = 0; i < 4; i++)
    {
        if (NULL == q.NQ((O*)items[i]))
        {
            _tcprintf(_T("Fail: verify enqueue after partial dequeue; enqueue\r\n"));
            return 0;
        }
    }
    // write pass message:
    _tcprintf(_T("Pass: verify enqueue after partial dequeue\r\n"));
 
    // queue now contains 5 items;
    // the queue destructor should clean these up;
    // otherwise, memory leaks will be detected below:
    q.~Q();
 
    // trigger memory leak detection:
    if (_CrtDumpMemoryLeaks())
    {
        _tcprintf(_T("Fail: verify queue destructor\r\n"));
    }
    else
    {
        _tcprintf(_T("Pass: verify queue destructor\r\n"));
    }
    return 0;
}

Example output:

Pass: verify output items match input items
Pass: verify empty queue
Pass: verify enqueue after partial dequeue
Pass: verify queue destructor

I strongly encourage all programmers, regardless of experience level, to implement and test classes similar to, but more optimal than, this. Use them in actual product code, and skip taking dependencies on pre-fabricated container classes. Run some comparative performance testing. See if you can create something better, faster, and smaller! Dare to go native!