Tagged: source

Design Patterns: Object Pool

Last one from the family of creational patterns is Object Pool. The main purpose of object pool and why designers choose to incorporate to the software is a performance boost. Construction and destruction of object can become very expensive operation in some cases (especially if it occurs very often). Constant building and throwing away instances may significantly slow down your application. Object Pool pattern offers a solution to this problem.

Object pool is a managed set of reusable objects. Clients then “check out” objects from the pool return them back when they don’t need them any more. But it’s not that easy as it sounds. The manager of the pool has to deal with various problems.

  • What happens if the pool is empty and a client asks for an object?
    Some implementations work with growing pool of objects. That means if there’s no object available at the time of the request the pool manager creates one more. The manager can also destroy objects periodically when they’re not used. But what was the initial goal? Performance boost? Well, with this amount of overhead it might not be as fast. Another solution to the problem is simply to decline a client’s request if the pool is empty. This also slows down your system, because clients needs to do things right now and not wait for someone else to free up resources.
  • When the reservation expires?
    The other problem is dealing with errors. Every client must explicitly free up the resource when he’s done. But programmers are also only humans (well, in most cases) and there will be errors and your pool can easily become a hole full of zombies. So you might need to implement an algorithm for detecting and freeing expired reservations on resources in order to make stuff work properly.
  • Synchronization in multi-threaded applications
    Multi-threading brings into the game a whole other aspect. Two processes asking for resources at the same time. Some synchronization tools might be necessary as well.

As you can see, there are some serious drawbacks in this pattern. It’s a huge amount of work in the first place, if you decide to implement all the above. You need to consider every aspect very carefully before you implement the object pool and evaluate whether it really is, what you need.

The resource manager can be implemented many ways. Static class or singleton will work. I personally chose singleton. Here is my implementation of object pool:

C++

/*
 * Example of `object pool' design pattern
 * Copyright (C) 2011 Radek Pazdera
 */

class Resource
{
    int value;

    public:
        Resource()
        {
            value = 0;
        }

        void reset()
        {
            value = 0;
        }

        int getValue()
        {
            return value;
        }

        void setValue(int number)
        {
            value = number;
        }
};

/* Note, that this class is a singleton. */
class ObjectPool
{
    private:
        std::list<Resource*> resources;
        
        static ObjectPool* instance;
        ObjectPool() {}

    public:
        /**
         * Static method for accessing class instance.
         * Part of Singleton design pattern.
         *
         * @return ObjectPool instance.
         */
        static ObjectPool* getInstance()
        {
            if (instance == 0)
            {
                instance = new ObjectPool;
            }
            return instance;
        }

        /**
         * Returns instance of Resource.
         * 
         * New resource will be created if all the resources
         * were used at the time of the request.
         *
         * @return Resource instance.
         */
        Resource* getResource()
        {
            if (resources.empty())
            {
                std::cout << "Creating new." << std::endl;
                return new Resource;
            }
            else
            {
                std::cout << "Reusing existing." << std::endl;
                Resource* resource = resources.front();
                resources.pop_front();
                return resource;
            }
        }

        /**
         * Return resource back to the pool.
         *
         * The resource must be initialized back to
         * the default settings before someone else
         * attempts to use it.
         *
         * @param object Resource instance.
         * @return void
         */
        void returnResource(Resource* object)
        {
            object->reset();
            resources.push_back(object);
        }
};

int main()
{
    ObjectPool* pool = ObjectPool::getInstance();
    Resource* one;
    Resource* two;

    /* Resources will be created. */
    one = pool->getResource();
    one->setValue(10);
    std::cout << "one = " << one->getValue() << " [" << one << "]" << std::endl;

    two = pool->getResource();
    two->setValue(20);
    std::cout << "two = " << two->getValue() << " [" << two << "]" << std::endl;

    pool->returnResource(one);
    pool->returnResource(two);

    /* Resources will be reused. 
     * Notice that the value of both resources were reset back to zero.
     */
    one = pool->getResource();
    std::cout << "one = " << one->getValue() << " [" << one << "]" << std::endl;

    two = pool->getResource();
    std::cout << "two = " << two->getValue() << " [" << two << "]" << std::endl;
   
    return 0;
}

Download the fully working example from github.

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Example of `object pool' design pattern
# Copyright (C) 2011 Radek Pazdera

class Resource:

    """ Some resource, that clients need to use.
    
    The resources usualy have a very complex and expensive
    construction process, which is definitely not a case
    of this Resource class in my example.
    """

    __value = 0

    def reset(self):
        """ Put resource back into default setting. """
        self.__value = 0

    def setValue(self, number):
        self.__value = number

    def getValue(self):
        return self.__value


class ObjectPool:
    
    """ Resource manager.

    Handles checking out and returning resources from clients.
    It's a singleton class.
    """

    __instance = None
    __resources = list()

    def __init__(self):
        if ObjectPool.__instance != None:
            raise NotImplemented("This is a singleton class.")

    @staticmethod
    def getInstance():
        if ObjectPool.__instance == None:
            ObjectPool.__instance = ObjectPool()

        return ObjectPool.__instance

    def getResource(self):
        if len(self.__resources) > 0:
            print "Using existing resource."
            return self.__resources.pop(0)
        else:
            print "Creating new resource."
            return Resource()

    def returnResource(self, resource):
        resource.reset()
        self.__resources.append(resource)

def main():
    pool = ObjectPool.getInstance()

    # These will be created
    one = pool.getResource()
    two = pool.getResource()

    one.setValue(10)
    two.setValue(20)

    print "%s = %d" % (one, one.getValue())
    print "%s = %d" % (two, two.getValue())

    pool.returnResource(one)
    pool.returnResource(two)

    one = None
    two = None

    # These resources will be reused
    one = pool.getResource()
    two = pool.getResource()
    print "%s = %d" % (one, one.getValue())
    print "%s = %d" % (two, two.getValue())

Download the fully working example from github.

Sources

Brute-Force String Generation in C

Earlier this week, I posted an article about string generation for brute-force attacks and a couple of example solutions. I emphasized, that the key aspect of brute-force is speed. We want to try as many combinations of input data as possible in the minimum amount of time. And part of this is also efficient algorithm that will generate input combinations. But the examples I posted were written in Python, which is kind of a high level scripting language, not nearly as fast as C.

Hence, here is my implementation of the same in C:

/*
 * Basic string generation for brute-force attacks
 * Copyright (C) 2011 Radek Pazdera
 */

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

/* I chose to use an one way linked list data structure
 * to avoid restrictions on the generated string length.
 * The thing is, the list must be converted to string so
 * it could be used. This conversion have to happen in
 * each cycle and causes unnecessary slowdown.
 * 
 * Faster solution would be to implement the generation
 * directly on some staticaly allocated string with fixed
 * size (20 characters are more than enough).
 */
typedef struct charlist charlist_t;
struct charlist
{
    unsigned char character;
    charlist_t* next;
};

/* Return new initialized charlist_t element.
 *
 * Elements are initialized
 * @return charlist_t
 */
charlist_t* new_charlist_element()
{
    charlist_t* element;

    if ((element = malloc(sizeof(charlist_t))) != 0)
    {
        element->character = 0;
        element->next = NULL;
    }
    else
    {
        perror("malloc() failed.");
    }

    return element;
}

/* Free memory allocated by charlist.
 *
 * @param list Pointer at the first element.
 * @return void
 */
void free_charlist(charlist_t* list)
{
    charlist_t* current = list;
    charlist_t* next;

    while (current != NULL)
    {
        next = current->next;
        free(current);
        current = next;
    }
}

/* Print the charlist_t data structure.
 *
 * Iterates through the whole list and prints all characters
 * in the list including any '\0'.
 * 
 * @param list Input list of characters.
 * @return void
 */
void print_charlist(charlist_t* list)
{
    charlist_t* next = list;
    while (next != NULL)
    {
        printf("%d ", next->character);
        next = next->next;
    }
    printf("\n");
}

/* Get next character sequence.
 *
 * It treats characters as numbers (0-255). Function tries to
 * increment character in the first position. If it fails,
 * new character is added to the back of the list.
 *
 * It's basicaly a number with base = 256.
 *
 * @param list A pointer to charlist_t.
 * @return void
 */
void next(charlist_t* list)
{
    list->character++;
    if (list->character == 0)
    {
        if (list->next == NULL)
        {
            list->next = new_charlist_element();
        }
        else
        {
            next(list->next);
        }
    }
}

int main()
{
    charlist_t* sequence;
    sequence = new_charlist_element();

    while (1)
    {
        next(sequence);
        print_charlist(sequence);
    }

    free_charlist(sequence);
}

Download the fully working code from github.

Design Patterns: Prototype

Prototype is one of the easier to understand design patterns. The intent of prototype is to create new instances of classes by cloning a prototype instance, rather than building them from scratch. This is particularly useful when the initialization of the objects is very expensive and very similar among the majority of created instances.

Take this for instance, you have some data stored on a remote server. You need them to initialize 1000 instances of some class during your program runtime. This data are static and very unlikely to be changed during the runtime of your application. You see, that downloading the data during initialization in constructor is pretty ineffective. Design like that would lead to exactly 999 pointless connections to the server and a lot of unnecessary network traffic, which is a gigantic waste of resources and time. If you use prototype instead, the application will download the data just once and the 1000 more instances will be cloned from the first one, saving us all the trouble.

There are three participants in the prototype pattern:

  • Client – creates a new object by asking a prototype to clone itself.
  • Prototype – declares an interface for cloning itself.
  • Concrete Prototype – implements the operation for cloning itself.

You also need a place where all the prototypes will be stored. A good practice is using a factory class that will cover the initial prototype setup  and will handle the cloning operations. This might remind you of the abstract factory design pattern. This is because they both are creational patterns and can be used to achieve the same behavior. The thing about prototype is that, you can dynamically change the prototype instance during the runtime and begin constructing something completely different with the same factory without sub-classing it.

Another way of dynamic handling a lot of prototype instances is prototype manager. A class that stores a pool of prototypes and makes decisions on which one to instantiate based on some parameters. This is particularly useful when the amount of prototypes isn’t fixed.

Now, let’s proceed to the code examples. I went with the first variant — a factory class for storing the prototypes.

C++

/*
* Example of `prototype' design pattern.
* Copyright (C) 2011 Radek Pazdera
*/

#include <iostream>
#include <string>

/* Prototype base class. */
class Prototype
{
    protected:
        std::string type;
        int value;

    public:
        virtual Prototype* clone() = 0;

        std::string getType()
        {
            return type;
        }

        int getValue()
        {
            return value;
        }
};

class ConcretePrototype1 : public Prototype
{
    public:
        ConcretePrototype1(int number)
        {
            type  = "Type1";
            value = number;
        }
        
        Prototype* clone()
        {
            return new ConcretePrototype1(*this);
        }
};

class ConcretePrototype2 : public Prototype
{
    public:
        ConcretePrototype2(int number)
        {
            type  = "Type2";
            value = number;
        }

        Prototype* clone()
        {
            return new ConcretePrototype2(*this);
        }
};

/* Factory that manages prorotype instances and produces their clones. */
class ObjectFactory
{
    static Prototype* type1value1;
    static Prototype* type1value2;
    static Prototype* type2value1;
    static Prototype* type2value2;

    public:
        static void  initialize()
        {
            type1value1 = new ConcretePrototype1(1);
            type2value1 = new ConcretePrototype2(1);
        }

        static Prototype* getType1Value1()
        {
            return type1value1->clone();
        }

        static Prototype* getType2Value1()
        {
            return type2value1->clone();
        }
};

int main()
{
    ObjectFactory::initialize();
    Prototype* object;

    /* All the object were created by cloning the prototypes. */
    object = ObjectFactory::getType1Value1();
    std::cout << object->getType() << ": " << object->getValue() << std::endl;

    object = ObjectFactory::getType2Value1();
    std::cout << object->getType() << ": " << object->getValue() << std::endl;

    return 0;
}

Download the fully working example from github.

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Example of `prototype' design pattern
# Copyright (C) 2011 Radek Pazdera

import copy

class Prototype:

    """ Object, that can be cloned.

    This is just a base class, so the clone() method
    is not implemented. But all subclasses have to
    override it.
    """

    _type  = None
    _value = None

    def clone(self):
        pass

    def getType(self):
        return self._type

    def getValue(self):
        return self._value

class Type1(Prototype):

    """ Concrete prototype.
    
    Implementation of Prototype. Important part is the
    clone() method.
    """

    def __init__(self, number):
        self._type = "Type1"
        self._value = number

    def clone(self):
        return copy.copy(self)

class Type2(Prototype):
    """ Concrete prototype. """

    def __init__(self, number):
        self._type = "Type2"
        self._value = number

    def clone(self):
        return copy.copy(self)

class ObjectFactory:

    """ Manages prototypes.

    Static factory, that encapsulates prototype
    initialization and then allows instatiation
    of the classes from these prototypes.
    """

    __type1Value1 = None
    __type2Value1 = None

    @staticmethod
    def initialize():
        ObjectFactory.__type1Value1 = Type1(1)
        ObjectFactory.__type2Value1 = Type2(1)
        
    @staticmethod
    def getType1Value1():
        return ObjectFactory.__type1Value1.clone()

    @staticmethod
    def getType2Value1():
        return ObjectFactory.__type2Value1.clone()


def main():
    ObjectFactory.initialize()

    instance = ObjectFactory.getType1Value1()
    print "%s: %s" % (instance.getType(), instance.getValue())

    instance = ObjectFactory.getType2Value1()
    print "%s: %s" % (instance.getType(), instance.getValue())

Download the fully working example from github.

Sources

Documenting Python Code with Sphinx

One of the essential tasks in software development is documenting your code. With no documentation, hardly anyone will be able to understand your code and therefore contribute to your project. Sometimes you might find even yourself looking at your own code wandering, “What the hell is this supposed to mean?” Well, that’s where documentation comes in!

Good idea is to include documentation right into the source files. First of all, it helps coders read the source, because if they don’t get something, the documentation is right there! It’s much easier to maintain correct documentation. If you change something, you also change it 10 lines above in the documentation string. There are lots of utilities for analyzing source files and generating documentation from them. JavaDoc for Java, doxygen for C++ and Sphinx for Python.

I assume you know the awesome-looking Python docs, right? Well, that documentation is generated by Sphinx! In this post I’ll try to explain how to get sphinx and most importantly how to get that sweet-looking documentation out of it :-).

Installation

Sphinx is distributed as a python module, so you can use easy_install to get it. Install sphinx and all the dependencies by writing:

$ sudo easy_install sphinx

Easy install is a part of setuptools. So if this doesn’t run anything you probably need to install them. Look for package python-setuptools in your distribution’s repositary.

Setting up the doc folder

Documentation is usualy placed in a separate folder in your project directory. It’s really up to you, but I recomend using doc/ folder. Then you need to setup basic files for sphinx in that particular folder (sphinx calls it a source directory). This can be done by sphinx-quickstart command that will guide you through the whole setup process. The important thing here is to answer yes to the question of enabling autodoc extension. This extension then collect the documentation from your code.

$ mkdir doc
$ cd doc/
$ sphinx-quickstart

Writing documentation

The above mentioned sequence of commands should create a basic directory structure of your sphinx documentation. Somewhere in that structure (it depends on how did you answer to the questions of sphinx-quickstart) will be an index file of the whole docs. By default it will be called index.rst. Content of this file is in reStructured text. It’s a syntax for formating plain text documents. It’s not very hard to learn. Using either rst quick reference, sphinx guide or my personal favorite way — ripping off python docs.

On every html page generated by sphinx is a link to the source rst file it were generated from. And so it is in the python docs. The link is at the bottom of the menu right above the search box. You see, the documentation of python is not only quite large, but also really well formed. So by looking at that you’ll be soon able to write some pretty good docs yourself.

Sphinx documentation example

If you decide to crate a new page, you can simply add a file to the doc/ directory and sphinx will find it and include it into the documentation.

Documentation from docs string isn’t included automatically like in doxygen. You need to specify where to include what. In-depth explanation on how to do that is here.

Conclusion

Well, this was my very brief experience with sphinx. It’s a great tool for creating documentation for your python projects. Hopefully, I’ll get back to it at some point in the future and expand this article.

Sources

Licensing Your Software

When it comes to releasing your software publicly, you need to specify at what conditions may others use, modify, copy and redistribute it. This is usually done by supplying some kind of a document along with your software called license. Writing a good license could mean a pretty rough times over a fat pile of lawyer books for a common software developer …

Luckily for us, there are a plenty of existing licenses, that you can use and under which you can distribute your software. Some are more restrictive than others and it’s only up to you which licensing path you want to take :-). Since you’re reading my blog about Linux, I’ll assume you probably want to distribute your application’s sources as well. There are numerous ways to go. So let’s have a look …

Public Domain

One way to publish your software is by forfeiting your copyright a thereby releasing it into public domain. Anything that belongs to the public domain is without copyright. That means, that everybody can do anything they want with is. This might be useful for someone.

The thing is, that by default, if you write a piece of software, you automatically become it’s copyright holder. This is stated in a thing called Berne Convention, which most of the countries have signed. So, in order to make your software public domain, you need to make clear, that you forfeit your copyright.

Open Source vs. Free Software

Another great ways to distribute your software. Generally, there are two ways. Using an open source license or a free software license. What is the difference between these two? Well, there are two separate camps — OSI (Open Source Initiative) and FSF (Free Software Foundation).

By making your project open source you allow others to “do whatever they want” with the sources (as long as you don’t violate the licensing terms). The open source is more practical. It gives the user a lot of freedom in copying and modifying the software.

On the other hand, making your project a free software will allow users to “do whatever they want” (under the terms of the license) and if they modify the software, they have to publish the changes and give it back to the community. This makes the derivative works also publicly available. The free software is more philosophical. It wants to make sure, that the software once released as free will retain it’s freedoms.

Popular licenses

Here are some examples of popular and widely used licenses for your software. My personal favorite is GNU GPLv3.0. It’s a free software license, pretty restrictive about usage in proprietary software, but I like the philosophy behind it. It was initially written by this guy named Richard Stallman :-). The lesser version of this license (allowing linking in proprietary software) is GNU LGPL.

Other popular ones are the BSD licenses. There are multiple variants of the BSD license. They are more open source, than free software.

The MIT License is pretty straight-forward as well as permissive.

Great comparison of various free software and open source licenses is available on Wikipedia.

Sources: