2
\$\begingroup\$

Write a multithreaded C++ application (executable) for Windows Platform. This program uses the two threads to read and process the input data and store it into an output file. Candidate is free to make it console or UI based Windows application. Detailed description

  1. Program should accept an input text file with HTML content (xxx.html).
  2. ‘Thread1’ reads the input file and stores the data into a ‘buffer’. As soon as ‘buffer’ is full, it pauses and waits for some of the data to be processed by ‘Thread 2’ and then continues again. ‘Thread1’ never waits for ‘buffer’ to be completely empty. As soon as even few bytes space becomes available, it starts filling it again.
  3. As soon as data starts getting stored in ‘buffer’, ‘Thread2’ starts reading it. It removes the html tags associated with text data and pushes the text only data to ‘output_file.txt’ with total text words count as summary at the end of output file.

HTMLReader.h

#pragma once

#ifndef _HTMLReader_HEADER_
#define _HTMLReader_HEADER_
#include  "Common.h"

class HTMLReader
{
public:
    HTMLReader();
    ~HTMLReader(void);



    HANDLE startReading(ThreadObject*);
    static queue<unsigned char> buffer;

private:
    static const size_t buffer_size;
    static bool isBufferFull();
    static  DWORD __stdcall FetchHTML(LPVOID params);

};

#endif _HTMLReader_HEADER_

HTMLReader.cpp

#include "HTMLReader.h"

#include <istream>

//initilize static members
const size_t HTMLReader::buffer_size = 1024;
queue<unsigned char> HTMLReader::buffer;

HTMLReader::HTMLReader()
{
}


HTMLReader::~HTMLReader(void)
{

}

//starts a thread which reads HTML file
HANDLE HTMLReader::startReading(ThreadObject* threadObject)
{
    HANDLE handle = CreateThread(NULL,NULL,HTMLReader::FetchHTML,threadObject,0,NULL);

    return handle;
}

//buffer is restricted to a size
bool HTMLReader::isBufferFull()
{
    return HTMLReader::buffer.size() >= HTMLReader::buffer_size;
}

//thread function, 
DWORD __stdcall HTMLReader::FetchHTML(LPVOID params)
{
    ThreadObject threadObject = *(ThreadObject*)params;

    FILE* fp = fopen(threadObject.data.c_str(),"r");

    if(!fp)
    {
        cout<<"Error reading file."<<std::endl;
        return -1;
    }

    //keep reading file till end of file
    while(1)
    {
        //if buffer is full wait for reader to make space by poping from queue
        while(HTMLReader::isBufferFull())
        {
            Sleep(100);
        }

        char ch = -1;

        //take lock and add to queue till buffer is full
        if(TryEnterCriticalSection(&threadObject.criticlaSection))
        {
            while(!(HTMLReader::isBufferFull()) && (ch = fgetc(fp)) !=EOF)
            {
                HTMLReader::buffer.push(ch);
            }

            LeaveCriticalSection(&threadObject.criticlaSection);
        }

        //if fp reaches eof then file reading is done
        if(ch == EOF) break;

    }

    return 0;
}

HTMLParser.cpp (which contains main)

#include "Common.h"

#include "HTMLParser.h"
#include "HTMLReader.h"
#include <fstream>
#include <vector>

static std::vector<unsigned char> data;

//thread function which reads data and from queue and adds to buffer
DWORD __stdcall getData(LPVOID params)
{
    ThreadObject threadObject = *(ThreadObject*)params;

    while(1)
    {

        //retry 10 times, if still does not get data then kill the thread
        int retry_count = 0;
        while(HTMLReader::buffer.empty())
        {
            Sleep(100);
            retry_count++;

            if(retry_count >= 10) return 0;
        }


        if(TryEnterCriticalSection(&threadObject.criticlaSection))
        {
            Sleep(10); 

            //read all the data in the buffer and then leave critical section 
            while(!HTMLReader::buffer.empty())
            {
                data.push_back(HTMLReader::buffer.front());
                HTMLReader::buffer.pop();
            }

            LeaveCriticalSection(&threadObject.criticlaSection);
        }
    }
    return 0;
}


int main(int argc, char* argv[], char* envp[])
{
    string inputFilePath; 

    if(argc == 2)
        inputFilePath += string(argv[1]); //get input from command line

    CRITICAL_SECTION criticalSection;

    ThreadObject threadObject; 

    InitializeCriticalSection(&criticalSection); //initilize critical secion

    threadObject.criticlaSection = criticalSection; //fill thead object

    if(inputFilePath.empty())
        threadObject.data = "C:/assn/test.html"; //default path if user does not provide path
    else
        threadObject.data = inputFilePath;

    HTMLReader htmlReader;

    HANDLE fileReaderThread = htmlReader.startReading((ThreadObject*)&threadObject); // start reader therad

    HANDLE dataStoreThread =  CreateThread(NULL,NULL,getData,(ThreadObject*)&threadObject,0,NULL); //start parser thread

    if(fileReaderThread) WaitForSingleObject(fileReaderThread,INFINITE); //wait for thread to return 

    if(dataStoreThread) WaitForSingleObject(dataStoreThread,INFINITE); //wait for thread to return

    std::vector<unsigned char> finalOutput;

    std::vector<unsigned char> :: const_iterator it = data.begin();

    //process html data, remove html tags and store in file
    while(it!=data.end())
    {
        while(*it == '<') //there can be <, immediately after >, so checkin in while
        {
            while(++it != data.end() && *it != '>');

            it++;
        }


        if(it != data.end())
            finalOutput.push_back(*it++);

        if(it == data.end())
            break;
    }


    it = finalOutput.begin();

    std::ofstream out("output_file.txt");


    int word_cont = 0;
    string output;

    for(; it!=finalOutput.end(); it++)
    {
        if(*it == '\n' || *it =='\t')
            continue;

        if(*it == ' ')
            word_cont++;

        output.push_back(*it);
    }
    word_cont++;

    output += "\n\n\nSummary:\n";

    output += "Word Count = "; 
    output += std::to_string(word_cont) + string("\n");

    cout<<output;

    out<<output;
    out.close();
    return 0;
}

Common.h

#ifndef _COMMON_HEADER_
#define _COMMON_HEADER_ 

#include "stdafx.h"
#include <vector>
#include <queue>
#include <string>

using std::vector;
using std::queue;
using std::string;
using std::cout;

struct ThreadObject
{
    CRITICAL_SECTION criticlaSection;
    string data;
};

#endif
\$\endgroup\$
  • 1
    \$\begingroup\$ I sure hope this design is imposed as part of homework, or something on that order. It's nearly the worst possible way to use threads, not only making the task substantially more difficult, but virtually guaranteeing slower execution than a single-threaded version as well. Even "homework" is a terrible excuse though--if you're going to teach people to use multi-threading, you should teach them to use it at least sort of well, rather than requiring that they do it as badly as possible. \$\endgroup\$ – Jerry Coffin May 18 '16 at 16:22
  • \$\begingroup\$ @JerryCoffin Yes it's kind of homework, just self imposed one. Can you please give some pointers where I am wrong and how should I use threads correctly? Thanks for taking time to read code and write comment. \$\endgroup\$ – Pranit Kothari May 18 '16 at 16:38
  • \$\begingroup\$ Since you're apparently open to modifying that part of things (or at least interested in comments on it) I've posted an answer covering it (along with one other issue). \$\endgroup\$ – Jerry Coffin May 18 '16 at 17:27
1
\$\begingroup\$

This is primarily about the high-level design of the code rather than the details.

Lock/buffer usage

At least as I see it, the basic design here is quite problematic. You have a producer (the reader) and a consumer (the parser) sharing a single buffer. This means (in essence) that each time the producer needs to put something into the buffer, it needs to lock the buffer. Likewise, every time the consumer needs to get something from the buffer, it needs to lock the buffer.

This means the lock for that buffer is almost certain to be under heavy contention at nearly all times--the producer and the consumer are both trying to use the buffer almost constantly.

To fix that, I'd have the producer and the consumer use separate buffers. For example, you can create a small pool of buffers. The producer (the reader) gets a buffer from the pool, fills it, and puts that buffer into a queue.

The consumer (the parser) gets a buffer from the queue, parses it, and then releases the buffer back to the buffer pool.

This way, the reader has exclusive ownership of a buffer the entire time it's filling that buffer. Likewise, the parser has exclusive ownership of a buffer the entire time it's draining that buffer. Neither one does any locking anywhere.

This way, the only places we need to lock anything are in the queue (i.e., lock while we insert a buffer into the queue or remove a buffer from the queue), and the buffer allocator (lock while we get a buffer from the allocator or release a buffer back to the allocator).

From a code viewpoint, we can even merge those two pretty easily. Our buffer allocator can be implemented as a queue of free buffers, so we just have two instances of a queue of buffer: one going from the reader to the parser, and the other going back from the parser to the reader:

enter image description here

This way, our locks are relatively low-contention. For example, if we use 4K buffers, the worst-case is contending over a lock once every 4K characters we process. Since lock contention is inversely proportional to buffer size, it's trivial to adjust the buffer size to reduce lock contention to/below whatever level we decide we need.

This also simplifies both the reader and the parser quite a bit, because neither of them needs to deal with locks at all any more--the only locking that's needed is handled in the queues, doing a synchronized push or pop.

This also makes it pretty easy to ensure against anything like a deadlock. Since the only thing we do under a lock is push/pop an item into/off of a queue, it becomes trivial to ensure that once we obtain a lock, we do the push/pop and release the lock again, all entirely deterministically.

Parsing bug

As it stands right now, your parser fails for a slightly unusual (but entirely legitimate) corner case. The most obvious example would be a tag that contains some code. In a case like this it's fairly common for the code in the tag to be only a function call, like this:

<input type="text" onKeyDown="handleKey()">

Although that's common, it's not restricted to a single function call. It can be other code, such as something like this:

<input type="text" onKeyDown="If (a > b) then ...">

In this case, the > in the code will be parsed as the end of the tag, so b) then..." will all be seen as normal text instead of an attribute inside the tag.

More generally, a quoted attribute value containing a > character is allowed. As such, if you encounter a quoted attribute value, you need to skip across that value in its entirety, even if it contains a > that would otherwise signal the end of the tag.

\$\endgroup\$
  • \$\begingroup\$ Thanks really helpful review. One question, are you OK with queue data structure used as buffer, or should I use some other data structure? \$\endgroup\$ – Pranit Kothari May 19 '16 at 4:06
1
\$\begingroup\$

Does the assignment specifically mandate the explicit use of Windows threading APIs or should the code simply compile and run under Windows? In the case of the latter, the C++ standard library now provides cross-platform threading APIs which can be easier to use.

Regarding your choice of C++: you start out by showing us a class, but it is filled mostly with static methods/variables. This is not the way a class should be designed. You've probably written it this way because of the callback that needs to be passed into CreateThread. As CreateThread also accepts a payload, you can simply pass it a method/lambda that just casts the payload pointer into this and calls an instance method on the specific instance.

Another design issue is that you create a class for the Reader, but then fill the main function with logic on how to perform the parsing. If you create classes, the main function's job would simply be to create an instance for each, tell them to start doing their jobs and wait for them to finish.

Why are you using C++ streams in one place, but FILE* and fopen in another?

Finally, getting to the threading part. I noticed a Sleep being performed why holding a critical section. This isn't recommended. The Windows API provides events which can be used to do a much better job of signalling another thread that "it's your turn to work".

\$\endgroup\$
  • \$\begingroup\$ Can't pass lambda to CreateThread(). It must be An application-defined function See: msdn.microsoft.com/en-us/library/windows/desktop/… \$\endgroup\$ – Martin York May 18 '16 at 13:48
  • \$\begingroup\$ Sure you can. Here's a proof-of-concept: pastebin.com/XwEW4L9F Under VS 2015 it works even without the cast to the function pointer. \$\endgroup\$ – D. Jurcau May 18 '16 at 14:46
  • \$\begingroup\$ @D.Jurcau: Undefined behavior can look like its working. Does not make it any more valid. This static_cast<DWORD(__stdcall *)(LPVOID)>([](LPVOID parameter){}) just makes me cry blood. \$\endgroup\$ – Martin York May 18 '16 at 18:06
  • \$\begingroup\$ The type of the third parameter is: LPTHREAD_START_ROUTINE which is DWORD (__stdcall *) (LPVOID lpThreadParameter). On the other hand lambda's have there own type that is not convertable to that type. So no they can't be called. If it does work it is querk of the ABI and unlikely to continue working long term. \$\endgroup\$ – Martin York May 18 '16 at 18:15
  • \$\begingroup\$ It's a feature introduced in the C++ standard, § 5.1.2 The closure type for a non-generic lambda-expression with no lambda-capture has a public non-virtual nonexplicit const conversion function to pointer to function with C++ language linkage (7.5) having the same parameter and return types as the closure type’s function call operator. The value returned by this conversion function shall be the address of a function that, when invoked, has the same effect as invoking the closure type’s function call operator \$\endgroup\$ – D. Jurcau May 18 '16 at 18:30
0
\$\begingroup\$

Instead of this:

std::vector<unsigned char> :: const_iterator it = data.begin();

//process html data, remove html tags and store in file
while(it!=data.end())
{
    while(*it == '<') //there can be <, immediately after >, so checkin in while
    {
        while(++it != data.end() && *it != '>');

        it++;
    }


    if(it != data.end())
        finalOutput.push_back(*it++);

    if(it == data.end())
        break;
}

You can write like this using STL:

std::vector<unsigned char> finalOutput;

auto it = data.begin();
auto end = data.end();

auto write = finalOutput.begin();
while (it != end)
{
    auto openBrace = std::find(it, end, '<');
    if (openBrace != end)
    {
        // Copy the thing before the brace into output
        write = finalOutput.insert(write, it, openBrace);

        // Move write head and current iterator forward
        write = std::next(write, std::distance(it, openBrace));
        it = std::next(it, std::distance(it, openBrace));
    }

    auto closeBrace = std::find(it, end, '>');
    if (closeBrace != end)
    {
        // skip the things inside the braces
        it = std::next(it, std::distance(it, closeBrace));
    }

        // Move on
    it = std::next(it);
}

Which might seem longer, but much less error prone.

Also, would this leak?

 FILE* fp = fopen(threadObject.data.c_str(),"r");
\$\endgroup\$
-1
\$\begingroup\$

Use std::thread and C++11 multithreading resources instead of Windows system calls. Also you can use C++11 regular expression to do that replacement job.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Quill May 18 '16 at 10:22
  • 1
    \$\begingroup\$ stackoverflow.com/a/1732454/14065 \$\endgroup\$ – Martin York May 18 '16 at 13:50
  • \$\begingroup\$ xkcd.com/1171 \$\endgroup\$ – Martin York May 18 '16 at 14:26
  • \$\begingroup\$ @LokiAstari: At least he didn't use Java. \$\endgroup\$ – Jerry Coffin May 18 '16 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.