MinHeap implementation.

Description:  The below program is an implementation of MinHeap. While creating the MinHeap, youneed to specify the max. no of elements it can hold. It provides two operations insert() and getMinimum().


HeaderFile:

#include <exception>

using namespace std;

#define HEAP_EMPTY 1

#define HEAP_FULL 2

class MinHeapException : public exception
{
    private:
    int code;

    public:
    MinHeapException(int n) : code(n)
    {

    }

    const char* what() const throw()
    {
        switch(code)
        {
            case HEAP_EMPTY:
                return "Heap is empty.";

            case HEAP_FULL:
                return "Heap is full.";
        }
    }   
};


class MinHeap
{
    private:
   
    const int capacity;
    int size;
    int* ptr;

    public:

    MinHeap(int n);
       
    void insert(int n) throw(MinHeapException);

    int getMinimum() throw(MinHeapException);

    void display();

    ~MinHeap();   
};

Implementation of our MinHeap:

#include "MinHeap.h"
#include <iostream>

using namespace std;

MinHeap :: MinHeap(int n) : capacity(n), size(0), ptr(new int[n+1])
{
       
}


void MinHeap :: insert(int n) throw(MinHeapException)
{
    /*
     * If the heap is already full, throw a exception.
     */   
    if(size == capacity)
    {
        throw MinHeapException(HEAP_FULL);
    }

    int hole;

    /*Increment the size of heap*/
    size++;

     /*The hole points  to the last position.
     *Move up the hole, still we get suitable position. i.e the parent of the hole
     *must be greater than the new no. that we want to insert in the hole.
     */    for(hole = size ; hole > 1 && ptr[hole/2] > n; hole = hole/2)
    {
        ptr[hole] = ptr[hole/2];
    }

    ptr[hole] = n;
}


int MinHeap :: getMinimum() throw(MinHeapException)
{

    /*
     *If the heap is empty throw an exception.
     */        if(0 == size)
    {
        throw MinHeapException(HEAP_EMPTY);   
    }

    int firstelement = ptr[1];

    int lastelement = ptr[size];

    int hole;
    int smallelement;

    /*
     * Decrement the size of heap.
     */
    size--;

    /*
     * Intially the hole is created in the first element.
     * The hole is moved down till we get to a poistion where the childrens are greater than the last element.
     */      for(hole = 1;  hole <= size/2; hole = smallelement)
    {
       
        if(2*hole+1 <= size)
        {
            /*Ther are two childs*/
            if(lastelement < ptr[2*hole] && lastelement < ptr[2*hole+1])
            {
                /*Bot the children are greater than the lastelement. So last element can be placed here*/                break;
            }
           
            /*Find to which subtree the hole should be moved*/
            smallelement = ptr[2*hole] < ptr[2*hole+1] ? 2*hole : 2*hole+1;

        }
        else
        {       
            /*There is one child*/
            if(lastelement < ptr[2*hole])
            {
                /*The child is greater than the lastelement*/
                break;
            }
            smallelement = 2*hole;
        }

        /*Move the samllest children into hole. hole is moved done to smallest children  posistion*/            ptr[hole] = ptr[smallelement];   
    }
   
    /*Replace the hole with the last element*/
    ptr[hole] = lastelement;

    /*Return the first element*/
    return firstelement;

}

void MinHeap :: display()
{
    int i;

    for(i=1; i <= size; i++)
    {
        cout << ptr[i] << " ";
    }
    cout << endl;   
}

MinHeap :: ~MinHeap()
{
    delete [] ptr;
}


int main(int argc, char** argv)
{

    try
    {

            MinHeap heap(11);

            heap.insert(13);
            heap.insert(14);
            heap.insert(16);
            heap.insert(19);
            heap.insert(21);
            heap.insert(19);
            heap.insert(68);
            heap.insert(65);
            heap.insert(26);
            heap.insert(32);
            heap.insert(31);
            heap.insert(41);

            cout << "1st Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "2nd Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "3rd Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "4th Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "5th Minimum:" << heap.getMinimum() << endl;
    }
    catch(MinHeapException& e)
    {
        cout << e.what();
    }
}

Converting string representation of time to unix epoch time.

#include <iostream>
#include <string>
#include <time.h>
#include <stdlib.h>

using namespace std;

int main(int argc, char** argv)
{
    string s_time = "Thu, 19 Oct 2006 11:52:22 +0200";

    struct tm tm;

    /*Convert from string representation to struct tm */

    char* ptr = strptime(s_time.c_str(), "%a, %d %b %Y %T %z", &tm);

    if('\0' != *ptr)
    {
        /*A part of the string was not  processed*/
        cout << "Following part of string not processed:" << ptr  << endl;
    }

    /*Convert from struct tm to time_t structure.*/

    time_t time = mktime(&tm);

    if(-1 == time)
    {
        cout << "Failed to convert from 'struct tm' to 'time_t'" << endl;
        exit(1);
    }
    else
    {
        cout << "Given time in unix time stamp:" << time << endl;
    }

    exit(0);
}

Output:

Given time in unix time stamp:1161238942

Example Apache module for reading request body.

Description: 

An apache c module, that reads the request body from a PUT/POST request body, saves it on the disk  and returns HTTP 201 (Created) status code if successful and returns the URI which the user can use to retrieve back the contents in "Location" response header and the name of the file in which the contents were saved in the response body.

Generating template for the module using 'apxs' tool:

  Using the -g option of 'apxs' tool, we can generate a basic template of a module and add our logic to it.

    #> /usr/local/apache2/bin/apxs -g -n putfile
    Creating [DIR]  putfile
    Creating [FILE] putfile/Makefile
    Creating [FILE] putfile/modules.mk
    Creating [FILE] putfile/mod_putfile.c
    Creating [FILE] putfile/.deps

  The above command creates a template for a module named 'putfile' and a Makefile to compile.
 

Module source code:

#include <sys/time.h>
#include <sys/types.h>
#include <fcntl.h>
#include <string.h>
#include <errno.h>
#include "httpd.h"
#include "http_config.h"
#include "http_protocol.h"
#include "http_log.h"
#include "ap_config.h"

#define BLOCKSIZE 4096

const char* documentRoot = "/usr/local/apache2/htdocs/";

int readAndWriteData(request_rec *r, int fd)
{
     int ret = ap_setup_client_block(r, REQUEST_CHUNKED_ERROR);

     if(OK == ret && ap_should_client_block(r))
     {
          char* buffer = (char*)apr_pcalloc(r->pool, BLOCKSIZE);

          int len;

          while((len=ap_get_client_block(r, buffer, BLOCKSIZE)) > 0)
          {
                if(-1 == write(fd, buffer, len))
                        return -1;
          }

          return (-1 == len ? -1 : 0);
     }

     return -1;

}


static int putfile_handler(request_rec *r)
{

    /*
    * For each request, apache decides based on the 'SetHanlder' and 'AddHandler'
   * directive, the module which would handle the request and populates the request_rec::handler
     * field with the name of the module.
     *
   * A well behaving mo1dule should check if the value of this field matches with its name and
     * process the request only if it does. 
     */    if (strcmp(r->handler, "putfile")) {
        return DECLINED;
    }

    /*
     * This module supports only 'PUT'/'POST' requests.
     */    if(M_PUT != r->method_number && M_POST != r->method_number)
    {
        return DECLINED;
    }


    char fileName[200] = {'\0'};

    struct timeval tv;

    gettimeofday(&tv, NULL);

    sprintf(fileName, "%sputfile/%ld.%ld", documentRoot, tv.tv_sec, tv.tv_usec);


    int fd = creat(fileName, 0644);

    if(-1 == fd)
    {
        return HTTP_INTERNAL_SERVER_ERROR;
    }
    close(fd);

    if(0 != ret)
    {
        return HTTP_INTERNAL_SERVER_ERROR;
    }

    r->content_type = "text/plain";

    /* Set response HTTP status */
    r->status = HTTP_CREATED;

    apr_table_add(r->headers_out, "Location", fileName + strlen(documentRoot));

    ap_rputs(fileName + strlen(documentRoot), r);

    return OK;
}

static void putfile_register_hooks(apr_pool_t *p)
{
    ap_hook_handler(putfile_handler, NULL, NULL, APR_HOOK_MIDDLE);
}

/* Dispatch list for API hooks */
module AP_MODULE_DECLARE_DATA putfile_module = {
    STANDARD20_MODULE_STUFF,
    NULL,                  /* create per-dir    config structures */
    NULL,                  /* merge  per-dir    config structures */
    NULL,                  /* create per-server config structures */
    NULL,                  /* merge  per-server config structures */
    NULL,                  /* table of config file commands       */
    putfile_register_hooks  /* register hooks                      */
};

Compiling and Installing the module:

Running the below command would compile the module and copy the shared library created to the modules directory (/usr/local/apache2/modules)

#> /usr/local/apache2/bin/apxs -c -i  mod_putfile.c

Apache configuration:

LoadModule putfile_module     modules/mod_putfile.so

<Location /putfile>
  SetHandler putfile
</Location>

Testing the module:

i) Create a sample file to send in the request.

#> echo "Sample Module" > input_file
 

#> cat input_file
Sample Module

ii) Send a PUT request.

#> curl -T ./input_file  -D header http://127.0.0.1/putfile/
putfile/1378555086.385071

#> cat header
HTTP/1.1 100 Continue

HTTP/1.1 201 Created
Date: Sat, 07 Sep 2013 11:58:06 GMT
Server: Apache/2.2.22 (Unix) mod_ssl/2.2.22 OpenSSL/1.0.0e
Location: putfile/1378555086.385071
Content-Length: 25
Content-Type: text/plain

iii) Retrieve the file from the server.

#>wget http://127.0.0.1/putfile/1378555086.385071
--2013-09-07 17:29:19--  http://127.0.0.1/putfile/1378555086.385071
Connecting to 127.0.0.1:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 14 [text/plain]
Saving to: `1378555086.385071'

100%[===========================================================================================================>] 14          --.-K/s   in 0s     

2013-09-07 17:29:19 (754 KB/s) - `1378555086.385071' saved [14/14]

#> cat 1378555086.385071
Sample Module