エラトステネスの篩

馬鹿馬鹿しいほど無駄な実装のエラトステネスの篩。今の派遣先に来る時の面接に持ってったんですょね、これ。元は /.J の日記エントリ。ファイル一個に突っ込んで、そのままコンパイル出来るように書いてるのはそーゆーわけ（ファイル分けの記述するの面倒で……）。

そぃや、ちょっと前に見直した時、排他処理もれを見っけたはずなのだけど──どこだったっけ〔を〕。

#include <cassert>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

////////////////////////////////////////////////////////////////////////
// 排他キュークラス
////////////////////////////////////////////////////////////////////////
template<class T> class Queue
{
// こんすとらくた・ですとらくた ////////////////////////////////////////
public:
    //
    // 唯一のこんすとらくた
    //
    //      length: キューの最大長
    //
    Queue(int length) :
        _length(length)
    {
        int ret;    // 戻り値チェック用

        // Mutex とか条件変数とか準備
        ret = pthread_mutex_init(&_mutex, NULL);
        assert(ret == 0);
        ret = pthread_cond_init(&_less, NULL);
        assert(ret == 0);
        ret = pthread_cond_init(&_more, NULL);
        assert(ret == 0);
    }

    //
    // ですとらくた
    //
    virtual ~Queue()
    {
        // Mutex とか条件変数とか後片付け
        (void) pthread_mutex_destroy(&_mutex);
        (void) pthread_cond_destroy(&_less);
        (void) pthread_cond_destroy(&_more);
    }

// 公開めそっど ////////////////////////////////////////////////////////
public:
    //
    // キューにデータを入れる
    //
    //      data: キューに入れるデータ
    //
    void Enqueue(T data)
    {
        // キューをロックしまーす
        pthread_mutex_lock(&_mutex);
        {
            // キューに空きが出来るまで待つのです
            while (_queue.size() >= _length)
                pthread_cond_wait(&_less, &_mutex);
            assert(_queue.size() < _length);

            // キューにデータを入れるのです
            _queue.push_back(data);

            // 「キューにデータが入りましたよ〜」と待ってるスレッドに通知
            pthread_cond_signal(&_more);
        }
        // キューのロックを解除しまーす
        pthread_mutex_unlock(&_mutex);
    }

    //
    // キューにデータを入れようとする
    //
    //      戻り値: true なら成功
    //
    bool TryEnqueue(T data)
    {
        bool enqueued = false;  // 成否フラグ

        // キューをロックしまーす
        pthread_mutex_lock(&_mutex);
        {
            // キューに空きがあるなら
            if (_queue.size() < _length)
            {
                // キューにデータを入れるのです
                _queue.push_back(data);

                // 「キューにデータが入りましたよ〜」と待ってるスレッドに通
                // 知
                pthread_cond_signal(&_more);

                // 成否フラグを立てる
                enqueued = true;
            }
        }
        // キューのロックを解除しまーす
        pthread_mutex_unlock(&_mutex);

        // 成否フラグを返す
        return enqueued;
    }

    //
    // キューからデータを取り出す
    //
    //      戻り値: キューから取り出したデータ
    //
    T Dequeue(void)
    {
        T data;     // 取り出す値

        // キューをロックしまーす
        pthread_mutex_lock(&_mutex);
        {
            // キューにデータが入るまで待つのです
            while (_queue.size() == 0)
                pthread_cond_wait(&_more, &_mutex);
            assert(_queue.size() > 0);

            // キューからデータを取り出すのです
            data = _queue.front();
            _queue.pop_front();

            // 「キューに空きができましたよ〜」と待ってるスレッドに通知
            pthread_cond_signal(&_less);
        }
        // キューのロックを解除しまーす
        pthread_mutex_unlock(&_mutex);

        // 取り出した値を返すのです
        return data;
    }

    //
    // キューからデータを取り出そうとする
    //
    //      data: キューから取り出したデータの格納先の参照
    //
    //      戻り値: true なら成功
    //
    bool TryDequeue(T& data)
    {
        bool dequeued = false;  // 成否フラグ

        // キューをロックしまーす
        pthread_mutex_lock(&_mutex);
        {
            // キューにデータが入っているなら
            if (_queue.size() > 0)
            {
               // キューからデータを取り出すのです
                data = _queue.front();
                _queue.pop_front();

                // 「キューに空きができましたよ〜」と待ってるスレッドに通知
                pthread_cond_signal(&_less);

                // 成否フラグを立てる
                dequeued = true;
            }
        }
        // キューのロックを解除しまーす
        pthread_mutex_unlock(&_mutex);

        // 成否フラグを返す
        return dequeued;
    }

// 非公開でーためんば //////////////////////////////////////////////////
private:
    int             _length;            // キューの最大長
    deque<T>        _queue;             // キュー
    pthread_mutex_t _mutex;             // キューのロック用 mutex
    pthread_cond_t  _less;              // キューの空き待ち条件変数
    pthread_cond_t  _more;              // キューの値待ち条件変数
};


////////////////////////////////////////////////////////////////////////
// スレッド実行インターフェース
//
//      スレッドクラスを使って非同期に実行できるクラスのインターフェース
//      なのです。インターフェースって言っても C++ でゎ単に抽象クラスです
//      けどね。
////////////////////////////////////////////////////////////////////////
class ThreadRunner
{
// こんすとらくた・ですとらくた ////////////////////////////////////////
public:
    //
    // なにもしないですとらくた
    //
    virtual ~ThreadRunner() {};

// 公開めそっど ////////////////////////////////////////////////////////
public:
    //
    // スレッドで実行される関数
    //
    //      この中で永久ループに入れてゎいけませぬ。一単位のお仕事をした
    //      ら直ぐに return してスレッド資源を返さなければならないのです。
    //
    virtual void Run(void) = 0;
};

////////////////////////////////////////////////////////////////////////
// スレッドクラス
//
//      限りあるスレッド資源をリサイクルして使い回すのです。
////////////////////////////////////////////////////////////////////////
class Thread
{
// すたてぃっくな公開めそっど //////////////////////////////////////////
public:
    //
    // スレッドによる実行要求
    //
    //      runner: 要求元スレッド実行クラスインスタンスへのポインタ
    //
    static void RequestExecution(ThreadRunner* runner)
    {
        // スレッドの準備が出来ていなければ
        if (!_ignited)
        {
            // 指定された数のスレッドインスタンスを作成する
            for (int i = 0; i < NR_THREADS; i++)
            {
                _instance.push_back(new Thread());
            }

            // スレッド準備完了フラグを立てる
            _ignited = true;
        }

        // 要求をキューに入れる
        _runner.Enqueue(runner);
    }

    //
    // 全スレッド停止
    //
    //      でもこれ、呼ぶタイミングあるのかなぁ……（←をぃ）
    //
    static void TerminateAllThreads(void)
    {
        // 作ったインスタンスを全部破壊
        for (vector<Thread*>::iterator i = _instance.begin();
            i != _instance.end();
            i++)
        {
            delete *i;
        }
    }

// こんすとらくた・ですとらくた ////////////////////////////////////////
private:
    //
    // こっそりこんすとらくた
    //
    //      同時に存在するスレッド数を制限したいので、他所様に勝手に作ら
    //      れちゃ困るのです。
    //
    Thread()
    {
        // スレッドを作るのです
        int ret = pthread_create(&_thread, NULL, ThreadCtrlRelay, this);
        assert(ret == 0);
    }

public:
    //
    // ですとらくた
    //
    ~Thread()
    {
        // スレッドを止めて回収するのです
        (void) pthread_cancel(_thread);
        (void) pthread_join(_thread, NULL);
    }

// すたてぃっくな非公開めそっど ////////////////////////////////////////
private:
    //
    // スレッド制御リレー関数
    //
    //      instance: リレー先インスタンスへのポインタ
    //
    static void* ThreadCtrlRelay(void* instance)
    {
        // 与えられたインスタンスにリレーするのです
        static_cast<Thread*>(instance)->ThreadCtrl();
            // pthread_create() はスレッド制御関数として非スタティックメ
            // ンバー関数を直接取れないからねぃ。

        // 戻り値に意味ゎありませぬ
        return NULL;
    }

// 非公開めそっど //////////////////////////////////////////////////////
private:
    //
    // スレッド制御関数
    //
    virtual void ThreadCtrl(void)
    {
        // 実行待ちスレッド実行クラスのインスタンスを取り出しては実行する
        // のです
        while (true)
        {
            _runner.Dequeue()->Run();
                // Queue::Dequeue() の中で pthread_cond_wait() があるから
                // キャンセルポイントになってるのでご心配なく〜
        }
    }

// 非公開定数 //////////////////////////////////////////////////////////
private:
    static const int NR_THREADS = 10;   // スレッド数
    static const int NR_REQUEST = 100;  // 実行待ちキュー長

// すたてぃっくな非公開でーためんば ////////////////////////////////////
private:
    static bool             _ignited;   // スレッド準備完了フラグ
    static vector<Thread*>  _instance;  // インスタンスのベクタ
    static Queue<ThreadRunner*>
                            _runner;    // 実行待ちキュー

// 非公開でーためんば //////////////////////////////////////////////////
private:
    pthread_t               _thread;    // スレッド

};
// すたてぃっくめんばの初期化 //////////////////////////////////////////
bool Thread::_ignited = false;
vector<Thread*> Thread::_instance;
Queue<ThreadRunner*> Thread::_runner(Thread::NR_REQUEST);

////////////////////////////////////////////////////////////////////////
// 非同期篩い機能つき素数クラス
//
//      自分自身の倍数を篩い落とすスレッドを持ってる素数クラスなのです。
//      新しい素数が見付かると勝手にインスタンスが増殖するのです。
////////////////////////////////////////////////////////////////////////
class Prime : public ThreadRunner
{
// こんすとらくた・ですとらくた ////////////////////////////////////////
public:
    //
    // 唯一のこんすとらくた
    //
    //      n: 自分自身の値（ちゃんと使えば素数が入る）
    //
    //      引数なしならデフォルト引数で最初の素数 2 が出来るのです。
    //
    Prime(int n = 2) :
        _n(n),
        _next(NULL),
        _queue(QUEUE_MAX)
    { /* なにもしない */ }

    //
    // ですとらくた
    //
    virtual ~Prime()
    {
        // 断末魔で自分自身の値を叫ぶ
        cout << _n;

        // 次の素数が無いなら改行
        if (_next == NULL) { cout << endl; }
        // 有るなら空白区切り
        else { cout << " "; }

        // 次の素数を道連れにする
        delete _next;
            // delete NULL; ゎ何もしないのよん
    }

// 公開めそっど ////////////////////////////////////////////////////////
public:
    //
    // 篩い待ちキューに数を渡す
    //
    //      d: 篩い待ちキューに渡す数
    //
    void Receive(vector<int>& d)
    {
        // 篩い待ちキューに値を渡す
        for (vector<int>::iterator i = d.begin();
             i != d.end();
             i++)
        {
            // 入るまでキューに入れようとする
            bool c = true;
            while (!_queue.TryEnqueue(*i))
            {
                // 入らなかったら１回だけ実行要求を出す
                if (c)
                {
                    Thread::RequestExecution(this);
                    c = false;
                }
            }
        }

        // 実行要求を出す
        Thread::RequestExecution(this);
    }

    //
    // スレッド実行関数
    //
    virtual void Run(void)
    {
        // <<< キューから数を取り出せる間、その数について >>>
        int d;
        vector<int> v;
        while(_queue.TryDequeue(d))
        {
            // 受け取った数が自分の値で割り切れちゃうなら篩い落とし
            // 念の為自分の値以下のも
            if ((d <= _n) || (d % _n == 0)) continue;

            // で、割り切れないなら……

            // 次の素数がまだ無ければ
            if (_next == NULL)
            {
                try
                {
                    // 受け取った値は素数だから新しく作るのさ
                    _next = new Prime(d);
                }
                catch (bad_alloc)
                {
                    // 新しい素数が作れなきゃほっとけ
                    _next = NULL;
                        // 無けりゃ無いでその先何もしないだけだし。
                }
            }
            // 既に次の素数が有るなら
            else
            {
                // 次の素数に渡す数のリストを更新
                v.push_back(d);
            }
        }
        // >>> キューから数を取り出せる間、その数について <<<

        // 数のリストを次の素数に渡す
        if ((_next != NULL) && (v.size() > 0)) _next->Receive(v);

        // 処理が終わったからスレッドを返す
        return;
    }

// すたてぃっくな非公開メンバ //////////////////////////////////////////
private:
    static const int QUEUE_MAX = 5; // 篩い待ちキュー最大長

// 非公開メンバ ////////////////////////////////////////////////////////
private:
    int              _n;            // 自分自身の値（素数）
    Prime*           _next;         // 次の素数へのポインタ
    Queue<int>       _queue;        // 篩い待ちキュー
};

////////////////////////////////////////////////////////////////////////
// めいん
////////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
    const int MAX = 100000;    // MAX までの素数を求めようとする
        // えぇ、あたしの試した環境ではここまで出せましたわよん♪　めちゃ
        // くちゃ遅いけど〔笑〕。

    Prime prime;         // 最初の素数

    // 篩に小さい順に値を送る
    vector<int> v;
    for (int i = 1; i <= MAX; i++) v.push_back(i);
    prime.Receive(v);

    // おしまい
    return 0;
}