The Practical Guide to Multithreading - Part 2

// PrimeNumberSearchPage.cpp : implementation file
//

#include "stdafx.h"
#include "ParallelSearch_MFC.h"
#include "PrimeNumberSearchPage.h"

#include "RelationalSearchPage.h"

// For sqrt
#include <math.h>


// CPrimeNumberSearchPage dialog

IMPLEMENT_DYNAMIC(CPrimeNumberSearchPage, CPropertyPage)

CPrimeNumberSearchPage::CPrimeNumberSearchPage()
	: CPropertyPage(CPrimeNumberSearchPage::IDD)
{

}

CPrimeNumberSearchPage::~CPrimeNumberSearchPage()
{
}

void CPrimeNumberSearchPage::DoDataExchange(CDataExchange* pDX)
{
	CPropertyPage::DoDataExchange(pDX);
	DDX_Control(pDX, IDC_SEARCH_RESULT, m_cSearchResult);
	DDX_Control(pDX, IDC_STATUS, m_cStatus);
}


BEGIN_MESSAGE_MAP(CPrimeNumberSearchPage, CPropertyPage)
	ON_BN_CLICKED(IDOK, &CPrimeNumberSearchPage::OnBnClickedOk)
	ON_MESSAGE(WM_SEARCH_REPLY_MESSAGE, OnSearchReplyMessage)
	ON_NOTIFY(LVN_GETDISPINFO, IDC_SEARCH_RESULT, &CPrimeNumberSearchPage::OnLvnGetdispinfoSearchResult)
END_MESSAGE_MAP()


// CPrimeNumberSearchPage message handlers


int CPrimeNumberSearchPage::OnInitDialog()
{
	CPropertyPage::OnInitDialog();

	// Set it as default for 'threads-for-search'
	SetDlgItemInt(IDC_THREAD_COUNT, theApp.m_nProcessorCount);

	m_cSearchResult.InsertColumn(0, _T("From Thread"), LVCFMT_LEFT, 90);
	m_cSearchResult.InsertColumn(1, _T("Number"), LVCFMT_LEFT,156);

	m_cSearchResult.SetExtendedStyle(LVS_EX_FULLROWSELECT);

	// Set it as default for 'threads-for-search'
	SetDlgItemInt(IDC_THREAD_COUNT, theApp.m_nProcessorCount);

	EnableWindow(true);

	return 0;
}

bool IsPrimeNumber(int nNumber);

UINT PrimeNumberSearchThread(void* pArg)
{
	SearchInfo* pSearchInfo = static_cast<SearchInfo*> ( pArg );

	// From where to search (just put the address, instead of index)
	int* pNumberBegin =  m_gNumberCollection.m_pNumbers + pSearchInfo->LowIndex;
	// &m_gNumberCollection.m_pRandomNumbers[pSearchInfo->LowIndex]

	// Till where?
	int* pNumberEnd=	m_gNumberCollection.m_pNumbers+ pSearchInfo->HighIndex;
	// &m_gNumberCollection.m_pRandomNumbers[pSearchInfo->HighIndex]

	const int nGreaterThan = pSearchInfo->NumberToSearch;


	int nCurrentNumber;

	NumberCollection* pNumberCollection = new NumberCollection(pSearchInfo->NotifyThreshold);
	int nCount=0;	// Current found count, will be reset after posting


	while (pNumberBegin < pNumberEnd)
	{
		nCurrentNumber = *pNumberBegin;
		pNumberBegin++;

		// Discard less-than required 'minimum'	and even numbers.

		if( nCurrentNumber%2==0 || nCurrentNumber <= nGreaterThan  )
			continue;

		if(IsPrimeNumber(nCurrentNumber))
			//nCurrentNumber < nNumberToSearch)
		{
			pNumberCollection->m_pNumbers[nCount++] = nCurrentNumber;

			if(nCount == pSearchInfo->NotifyThreshold)
			{
				pSearchInfo->m_pWnd->PostMessage(WM_SEARCH_REPLY_MESSAGE,
					(WPARAM)pNumberCollection,
					pSearchInfo->ThreadID);


				pNumberCollection  = new NumberCollection(pSearchInfo->NotifyThreshold);


				nCount=0;
			}
		}
	}

	// Send whatever collected by this time.
	// But send the ThreadID to be negative, so that GUI-thread knows
	// this thread has finished.
	// Other ideas exists for letting thread know about 'completion'
	// this is one of them (though a dirty one). Take it! :)

	// Send correct count, ignore rest of values in pointer.
	pNumberCollection->m_nCount = nCount;

	pSearchInfo->m_pWnd->PostMessage(WM_SEARCH_REPLY_MESSAGE,
		(WPARAM)pNumberCollection,
		-pSearchInfo->ThreadID);		// Note the negative sign

	delete pSearchInfo;

	return 0;
}

LRESULT CPrimeNumberSearchPage::OnSearchReplyMessage(WPARAM wParam, LPARAM lParam)
{
	CString strItem;
	CString strText;
	NumberCollection* pNumbers = (NumberCollection*)wParam;

	int nThreadId = (int)lParam;

	bool bIsSearchFinished=false;

	// If nThread ID was send negative, it means thread has finished.
	if(nThreadId < 0)
	{
		nThreadId = -nThreadId;
		m_nThreadFinishedCount++;

		if(m_nThreadFinishedCount == m_nThreadCount)
		{
			EndTime = GetTickCount();
			bIsSearchFinished = true;
		}
	}


	ItemData item_data;
	item_data.ThreadId = static_cast<BYTE> ( nThreadId );


	for (int nItem = 0; nItem<pNumbers->m_nCount;++nItem)
	{
		// Just put into vector
		// this is needed for fast response
		item_data.Number = pNumbers->m_pNumbers[nItem];
		ItemDataVector.push_back(item_data);			
	}

	// Update virtual list control
	// The callback would display
	m_cSearchResult.SetItemCount( (int) ItemDataVector.size() );


	if(bIsSearchFinished)
	{
		EnableControls(true);
		strText.Format(_T("Search finished with %d results in %.2f seconds"),  
			ItemDataVector.size(), 
			(EndTime - StartTime) / 1000.0f );
		m_cStatus.SetWindowText( strText);

		GetDlgItem(IDC_GREATER_THAN)->SetFocus();
	}


	delete pNumbers;

	return 0;
}

void CPrimeNumberSearchPage::OnBnClickedOk()
{
	// Just validate threads-count
	m_nThreadCount = GetDlgItemInt(IDC_THREAD_COUNT);
	const int nGreaterThan= GetDlgItemInt(IDC_GREATER_THAN);

	if(m_nThreadCount<1 || m_nThreadCount>MAX_THREAD_COUNT)
	{
		AfxMessageBox( _T("Please set thread-count be in 1 to 32 range."));
		return;
	}

	if(nGreaterThan < 10)
	{
		AfxMessageBox( _T("Please specify value more than 10"));
		return;

	}

	EnableControls(false);
	ItemDataVector.clear();
	m_cSearchResult.SetItemCount(0);

	m_nThreadFinishedCount=0;

	int nStartIndex = 0 ;


	int nBreakAt = m_gNumberCollection.m_nCount / m_nThreadCount;

	// First END index.
	int nEndIndex = 0;

	StartTime = GetTickCount();

	// Spawn up the number of threads, and let them know the range.
	// Range: low and high index in Number-array where the thread has to lookup
	for(int nThread = 1; nThread <= m_nThreadCount; nThread++)
	{
		// Since int is 4-byte, we cannot pass two integers (low and high index values)
		// The size of pointer (void*) is 4-bytes, thus we must pass this way.
		// The 0th index will be array-index from where the thread would begin search
		// The 1st index is the last-index PLUS 1 till where thread should search.
		// So 100,200 would mean: 100-199 indexes

		// Yes, we can also pass the addresses within the number-array
		// instead of indexes. But this is easier to understand.

		// The thread would delete this pointer.

		SearchInfo* pSearchInfo = new SearchInfo;
		pSearchInfo->NotifyThreshold = 1000;

		// Utilize NumberToSearch member to let thread know of 'minimum' number
		pSearchInfo->NumberToSearch = nGreaterThan;

		// pSearchInfo->m_pCompFunc = pFunctionAddress;

		// Calculated EndIndex...
		// If this is last thread to be created.
		// It MUST Handle all remaining items.
		// For example, if there are 100 items to search
		// And user specified 8 threads, the first seven threads would 
		// handle 12 items to search, but the last has to search 16 items.
		// Please calculate and understand yourself!
		if(nThread == m_nThreadCount )
			nEndIndex = m_gNumberCollection.m_nCount;
		else
			nEndIndex += nBreakAt;


		pSearchInfo->ThreadID = static_cast<short>  (nThread);

		pSearchInfo ->m_pWnd = this;		// To notify
		pSearchInfo->LowIndex	= nStartIndex;		// LOW-INDEX
		pSearchInfo ->HighIndex 	= nEndIndex;	// HIGH-INDEX (excluding the index itself).	

		// Next start index. Remember that High/End index means last-index to search PLUS ONE.
		nStartIndex = nEndIndex;


		AfxBeginThread(PrimeNumberSearchThread, pSearchInfo);
	}

	m_cStatus.SetWindowText( _T("Searching..."));
}

void CPrimeNumberSearchPage::EnableControls(bool bEnable)
{
	GetDlgItem(IDOK)->EnableWindow(bEnable);
	// m_cRelationalOperatorCombo.EnableWindow(bEnable);

	GetDlgItem(IDC_THREAD_COUNT)->EnableWindow(bEnable);
	GetDlgItem(IDC_GREATER_THAN)->EnableWindow(bEnable);
}


// Prime Number function
bool IsPrimeNumber(int nNumber)
{
	// As controlled in calling program, nNumber cannot be EVEN or less than 10
	// So we can start off with 3 till square-root of number, incrementing by 2
	// Any number can ONLY be divisible in range: 1 to sqrt(n)
	// Formulas exist for more optimal solution, but would add more complexity.
	// I chose this one.

	const int nCheckTill = static_cast<int> ( sqrt((float)nNumber) );

	for(int nCheckWith = 3; nCheckWith <= nCheckTill; ++nCheckWith)
	{
		if(nNumber % nCheckWith == 0)
			return false;
	}
	
	// Reached here, that means number is prime
	return true;
}

// The callback for displaying content to list-control
// This would be called whenever some item content is to be displayed
// We kept data in vector, so just returning them.
// This list-control must have OWNER DATA style set.
void CPrimeNumberSearchPage::OnLvnGetdispinfoSearchResult(NMHDR *pNMHDR, LRESULT *pResult)
{
	NMLVDISPINFO *pDispInfo = reinterpret_cast<NMLVDISPINFO*>(pNMHDR);
	
	LV_ITEM& Item= pDispInfo->item;

	if (Item.mask & LVIF_TEXT)
	{
		CString text;

		//Which column?
		switch (Item.iSubItem)
		{
		case 0: // Location name
			text.Format( _T("%d"), ItemDataVector[Item.iItem].ThreadId);
			break;

		case 1:	// STD Code
			text.Format( _T("%d"), ItemDataVector[Item.iItem].Number );
			break;		
		}	

		//Copy the text to the LV_ITEM structure
		//Maximum number of characters is in pItem->cchTextMax
		wcsncpy(Item.pszText, text, Item.cchTextMax);
	}

	*pResult = 0;
}