パスワードを忘れた? アカウント作成

etsav (7596) の日記

2003 年 12 月 11 日
午後 07:34

非同期でーたふろー型えらとすてねすの篩(←大馬鹿)

#include <assert.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <iostream>
#include <queue>

using namespace std;

//
// 非同期篩い機能つき素数クラス
//
class Prime
{
// こんすとらくた・ですとらくた ////////////////////////////////////////
public:
    //
    // 唯一のこんすとらくた
    //      n: 自分自身の値(ちゃんと使えば素数が入る)
    //
    Prime(int n) :
        _n(n),
        _next(NULL),
        _energized(false)
    {
        // Mutex とか 条件変数とか準備
        pthread_mutex_init(&_mutex, NULL);
        pthread_cond_init(&_less, NULL);
        pthread_cond_init(&_more, NULL);
    }

    //
    // ですとらくた
    //
    virtual ~Prime()
    {
        // 篩いスレッドの終了待ち
        if (_energized) pthread_join(_thread, NULL);

        // Mutex とか条件変数とかお片付け
        pthread_mutex_destroy(&_mutex);
        pthread_cond_destroy(&_less);
        pthread_cond_destroy(&_more);

        // 断末魔で自分自身の値を叫ぶ
        cout << _n;

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

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

// 公開めそっど ////////////////////////////////////////////////////////
public:
    //
    // 篩いスレッド起動
    //
    void Energize(void)
    {
        // 既に起動してるなら何もしない
        if (_energized) return;

        // スレッド起動
        int ret = pthread_create(&_thread, NULL, ThreadCtrlRelay, this);
        assert(ret == 0);

        // 起動フラグを立てる
        _energized = true;
    }

    //
    // 篩いスレッドに停止要求を出す
    //
    void Terminate(void)
    {
        // 自分自身の篩い待ちキューに停止要求コードを渡す
        Receive(TERM);
    }

    //
    // 篩い待ちキューに数を渡す
    //      d: 篩い待ちキューに渡す数
    //
    void Receive(int d)
    {
        // 篩いスレッドは起動していなければいけない
        assert(_energized);

        // キューをロックしまーす
        pthread_mutex_lock(&_mutex);
        {
            // キューに空きが出来るまで待つのです
            while (_queue.size() >= QUEUE_MAX)
                pthread_cond_wait(&_less, &_mutex);
            assert(_queue.size() < QUEUE_MAX);

            // キューに数を入れるのです
            _queue.push_back(d);

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

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

// 非公開めそっど //////////////////////////////////////////////////////
private:
    //
    // スレッド制御関数
    //
    void* ThreadCtrl(void)
    {
        // <<< 停止要求コードを受け取るまで >>>
        while (true)
        {
            int d; // キューから取り出す値

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

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

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

            // 停止要求コードを受け取ったら
            if (d == TERM)
            {
                // 次の素数があったらその篩いスレッドに停止要求を出す
                if (_next != NULL) _next->Terminate();

                // ループから抜ける
                break;
            }

            // 受け取った数が自分の値で割り切れちゃうなら篩い落とし
            if (d % _n == 0) continue;

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

            // 次の素数がまだ無ければ
            if (_next == NULL)
            {
                // 受け取った値は素数だから新しく作るのさ
                _next = new Prime(d);

                // 作った新しい素数の篩いスレッドを起動
                _next->Energize();
            }
            // 既に次の素数が有るなら
            else
            {
                // 受け取った値を渡す
                _next->Receive(d);
            }
        }
        // >>> 停止要求コードを受け取るまで <<<

        // スレッドおしまい
        return NULL;
    }

// すたてぃっくな非公開メンバ //////////////////////////////////////////
private:
    static const int TERM = -1;     // 停止要求コード
    static const int QUEUE_MAX = 5; // 篩い待ちキュー最大長

// 非公開メンバ ////////////////////////////////////////////////////////
private:
    int              _n;            // 自分自身の値(素数)
    Prime*           _next;         // 次の素数へのポインタ

    bool             _energized;    // 篩いスレッド起動フラグ

    pthread_t        _thread;       // 篩いスレッド
    pthread_mutex_t  _mutex;        // 篩い待ちキュー用 mutex
    pthread_cond_t   _more;         // キューの値待ち条件変数
    pthread_cond_t   _less;         // キューの空き待ち条件変数

    deque<int>       _queue;        // 篩い待ちキュー
};

//
// めいん
//
int
main(
    int argc,
    char* argv[]
)
{
    const int MAX = 200;    // MAX までの素数を求める
        // あんまし大きいとスレッド増えすぎちゃうので注意

    Prime prime(2);         // 最初の素数

    // 最初の素数の篩いスレッドを起動
    prime.Energize();

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

    // 篩いスレッドに停止要求を送る
    prime.Terminate();

    // おしまい
    return 0;
}

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

未知のハックに一心不乱に取り組んだ結果、私は自然の法則を変えてしまった -- あるハッカー

処理中...