Universal Digital Library

http://www.ulib.org/index.html

c++ qsort, threaded qsort and shell sort

Shell sort, qsort recurisve, and threaded qsort.
Threaded qsort runs out of memory for creating new threads at around 600 threads.
Making the stack size smaller with NEED_STACK might be able to fix is but I couldn't work out how.

PTHREAD_THREADS_MAX is set to 16384 on this system so that is not the problem.

 It relies on the fact that C++ vectors are stored in contiguous memory.

/*
 * "The C++ Programming Language 3rd Ed. Bjarne Stroustrup Pg. 334"
 * Copyright 2007 Timothy O'Hare
 */
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <pthread.h>
#include <memory>

using namespace std;

/*****************************************************
 * template sort
 */
template<class T> void sort(vector<T>&); // declaration

void f(vector<int>& vi, vector<string>& vs)
{
    time_t start = time(0);
    sort(vi);
    time_t taken = time(0) - start;
    cout << "time taken for roll your own: " << taken << " secs" << endl;
    sort(vs);
}

template<class T> void sort(vector<T>& v) // definition
    // Shell sort (Knuth, Vol.13, pg.84)
{
    const size_t n = v.size();

    for (int gap=n/2; 0<gap; gap/=2)
        for (int i=gap; i<n; i++)
            for (int j=i-gap; 0<=j; j-=gap) {
                //cout << "i:" << i << ", j:" << j << ", gap: " << gap << ", n:" << n << ", v[j]: " << v[j] << endl;
                if (v[j+gap] < v[j])
                    swap(v[j], v[j+gap]);
            }
}

/*****************************************************
 * Log
 */

class Log {
    public:
        void co(string s);
        static Log Instance();
        ostream& operator << (ostream& os );
    protected:
        Log() { pthread_mutex_init(&logMutex, NULL); };
    private:
        static std::auto_ptr<Log> theSingleInstance;
        //static Log * l;
        pthread_mutex_t logMutex;
};

Log Log::Instance()
{
    if (theSingleInstance.get() == 0)
      theSingleInstance.reset (new Log);
    return *theSingleInstance;
    /*if (!l) {
        l = new Log();
    }
    return *l;*/
}

void Log::co(string s)
{
    pthread_mutex_lock(&logMutex);
    cout << s;
    pthread_mutex_unlock(&logMutex);
}

ostream& Log::operator << (ostream& os)
{
    pthread_mutex_lock(&logMutex);
    cout << os;
    pthread_mutex_unlock(&logMutex);
}

/*****************************************************
 * q sort
 */

template<class T> int partition(vector<T>& v, int left, int right, int pivot)
{
    T pivotVal = v[pivot];
    swap(v[pivot], v[right]);
    int store = left;
    for (int i = left; i < right; i++) {
        if (v[i] < pivotVal) {
            swap(v[i], v[store]);
            store++;
        }
    }
    swap(v[store], v[right]);
    return store;
}

template<class T> void qsort(vector<T>& v, int left, int right)
{
   if (right > left) {
       int pivot = left;
       int newPivot = partition(v, left, right, pivot);
       //cout << "recursive newpviot: " << newPivot << ", left: " << left << ", right: " << newPivot-1 << endl;
       qsort(v, left, newPivot-1);
       //cout << "recursive newpviot: " << newPivot << ", left: " << newPivot+1 << ", right: " << right << endl;
       qsort(v, newPivot+1, right);
   }
}


/*****************************************************
 * q sort threaded
 */
void prtv(string s, vector<int> &v)
{
    ostringstream st;
    Log log = Log::Instance();
    if (v.size() > 1) {
        st << s << ": size:" << v.size() << ":";
        log.co(st.str());
        st.str("");
        for (int i = 0; i <= v.size()-2; i++) {
            //cout << "v[" << i << "]:" << v[i] << ",";
            st << v[i] << ",";
           log.co(st.str ());
            st.str("");
        }
    }
    if (v.size() > 0) {
        //cout << "v[" << v.size()-1 << "]:" << v[v.size()-1] << endl;
        st << v[v.size()-1] << endl;
        log.co(st.str());
        st.str("");
    } else {
        st << s << ": size:" << v.size() << endl;
        log.co(st.str());
        st.str("");
    }
}

int partition2(vector<int> &v, int left, int right, int pivot)
{
    /*ostringstream st;
    Log log = Log::Instance();
    st << "End of partition: pivot: " << pivot << ", l: " << left << ", r: " << right << endl;
    log.co(st.str());*/

    int pivotVal = v[pivot];
    swap(v[pivot], v[right]);
    int store = left;
    for (int i = left; i < right; i++) {
        if (v[i] < pivotVal) {
            swap(v[i], v[store]);
            store++;
        }
    }
    swap(v[store], v[right]);
    //prtv("end of partition2", v);
    return store;
}

typedef struct {
    vector<int>& v;
    int left;
    int right;
} qs_t;


int threads;

void *qsort_threaded(void * q)
{
   Log log = Log::Instance();
   ostringstream s;
   qs_t r1 =  *(qs_t *)q;
   vector<int> &v = r1.v;
   int left = r1.left;
   int right = r1.right;
   qs_t r2 = *(qs_t *)q;
   //vector<int> &v = r2.v;
   //int left = r2.left;
   //int right = r2.right;
   //vector<int> &v = ((qs_t *)q)->v;
   //int left = ((qs_t *)q)->left;
   //int right = ((qs_t *)q)->right;

    /*ostringstream st;
    st << "begin: left " << left << ", right " << right << endl;
    log.co(st.str());*/
    //prtv("begin", v);

   if (right > left) {
       //int pivot = right/2;
       int pivot = left;
       int newPivot = partition2(v, left, right, pivot);
       pthread_t *tid1 = NULL;
       pthread_t *tid2 = NULL;

       //s << "pivot:" << newPivot << ", left: " << left << ", right: " << right << endl;
        //log.co(s.str());
        r1.left = left;
        r1.right = newPivot-1;
        /*s.str("");
        s << "th1: pivot:" << newPivot << ", left: " << r1.left << ", right: " << r1.right << endl;
        log.co(s.str());*/
        threads++;
        tid1 = new pthread_t;
        if (pthread_create(tid1, NULL, &qsort_threaded, (void*)&r1)) {
            perror("Failed to create initial allocation thread 1:");
            return (void*)-1;
       }

        r2.left = newPivot + 1;
        r2.right = right;
        /*s.str("");
        s << "th2: pivot:" << newPivot << ", left: " << r2.left << ", right: " << r2.right << endl;
        log.co(s.str());*/
        threads++;
        tid2 = new pthread_t;
        if (pthread_create(tid2, NULL, &qsort_threaded, (void*)&r2)) {
            perror("Failed to create initial allocation thread 2:");
            return (void*)-1;
         }

       int i = 0;
       if (tid1) {
           if (0 !=  pthread_join(*tid1, NULL)) {
            perror("pthread join tid1");
           }
       }

       if (tid2) {
           if (0 !=  pthread_join(*tid2, NULL)) {
            perror("pthread join tid2");
           }
       }

   } /*else {
    st.str("");
    st << "end: left " << left << " <= right " << right << endl;
    log.co(st.str());
   }*/
 /*  for (int j=0; j<v.size()-1; j++) {
       t[j] = v[j];
   }*/

   return (void*)0;
}

std::auto_ptr<Log> Log::theSingleInstance;

int main(int argc, char * argv[])
{
    vector<int> vi;
    threads = 0;
    // create a vector of random ints
    int loop_cnt;
    if (argc == 1)
        loop_cnt = 600;
    else
        loop_cnt = atoi(argv[1]);
    srand(time(NULL));
    for( int i = 0; i < loop_cnt; i++ ) {
        int num = (int) rand() % loop_cnt;
        vi.push_back(num);
        //cout << num << ",";
    }
    //cout << endl;

    // copy it
    vector<int> vi_builtin(vi);
    vector<int> vi_qsort(vi);
    vector<int> vi_qsort_threaded(vi);

    // create a vector of strings
    vector<string> vs;
    vs.push_back("1");
    vs.push_back("zerbra");
    vs.push_back("towel");
    vs.push_back("shovel");
    vs.push_back("apple");

    // built in sort
    time_t start = time(0);
    sort(vi_builtin.begin(), vi_builtin.end());
    time_t taken = time(0) - start;
    cout << "time taken for builtin: " << taken << " secs" << endl;

    // qsort
    start = time(0);
    qsort(vi_qsort, 0, vi_qsort.size()-1);
    taken = time(0) - start;
    cout << "time taken for qsort: " << taken << " secs" << endl;

    // qsort threaded
    qs_t q = {vi_qsort_threaded, 0, vi_qsort_threaded.size()-1};
    start = time(0);
    qsort_threaded((void*)&q);
    taken = time(0) - start;
    cout << "time taken for qsort threaded: " << taken << " secs" << endl;

    // shell sort
    f(vi, vs);

    // check if any values are different
    for( int i = 0; i < vi.size(); i++ ) {
        if (vi[i] != vi_builtin[i] ||
            vi_qsort[i] != vi_builtin[i] ||
            vi_qsort_threaded[i] != vi_builtin[i] )
                cerr << "vi[i] " << vi[i] << " != " << vi_builtin[i]
                     << " or vi_qsort[i] " << vi_qsort[i]
                     << " or vi_qsort_threaded[i] " << vi_qsort_threaded[i] << endl;
    }
    // print them out
    /*cout << "qsort_threaded result" << endl;
    for( int i = 0; i < vi_qsort_threaded.size(); i++ ) {
        cout << vi_qsort_threaded[i] << ",";
    }
    cout << endl;*/
    cout << "thread count: " << threads << endl;
    return 0;
}

Only the Paranoid Survive

http://www.intel.com/pressroom/kits/bios/grove/paranoid.htm
Andrew S. Grove

Sooner or later, something fundamental in your business world will change.

I'm often credited with the motto, "Only the paranoid survive." I have no
idea when I first said this, but the fact remains that, when it comes to
business, I believe in the value of paranoia. Business success contains the
seeds of its own destruction. The more successful you are, the more people
want a chunk of your business and then another chunk and then another until
there is nothing left. I believe that the prime responsibility of a manager
is to guard constantly against other people's attacks and to inculcate this
guardian attitude in the people under his or her management.

Using pictures as a captcha

http://research.microsoft.com/asirra/

BZFlag - Multiplayer 3D Tank Game

OpenSource OpenGL Multiplayer Multiplatform Battle Zone capture the Flag.
3D first person Tank Simulation.
http://sourceforge.net/projects/bzflag/

Bugzilla Addons

Get around that horrible and useless bugzilla search:
http://wiki.mozilla.org/Bugzilla:Addons

• 1 End-User Utilities
  • 1.1 Desktop Clients
  • 1.2 Desktop Libraries
  • 1.3 Browser integration
  • 1.4 Handheld Clients
  • 1.5 IDE integration
  • 1.6 IRC client integration
  • 1.7 Project management software integration
  • 1.8 Integration with Source Code Management utilities
• 2 Server-side Utilities
  • 2.1 Integration with other web applications
  • 2.2 Integration with Source Code Management programs
  • 2.3 Test case management systems
  • 2.4 IRC Bots
  • 2.5 Data harvesting
  • 2.6 Quips
  • 2.7 Skins
  • 2.8 Localization Packs

Infrarecorder free CD/DVD burning

http://infrarecorder.sourceforge.net/

InfraRecorder is a free CD/DVD burning solution for Microsoft Windows. It
offers a wide range of powerful features; all through an easy to use
application interface and Windows Explorer integration.

InfraRecorder is released under GPL version 2.

Features
Create custom data, audio and mixed-mode projects and record them to
physical discs as well as disc images.
Supports recording to dual-layer DVDs.
Blank (erase) rewritable discs using four different methods.
Record disc images (ISO and BIN/CUE).
Fixate discs (write lead-out information to prevent further data from
being added to the disc).
Scan the SCSI/IDE bus for devices and collect information about their
capabilities.
Create disc copies, on the fly and using a temporary disc image.
Import session data from multi-session discs and add more sessions to
them.
Display disc information.
Save audio and data tracks to files (.wav, .wma, .ogg, .mp3 and
.iso).