threadtree.h

Vá para a documentação deste arquivo.
00001 /*
00002 * Copyright 2007, 2008 Ernesto Coutinho Colla
00003 *
00004 * "BN Parallel Package" é um nome que identifica o conjunto de programas 
00005 * que forma uma biblioteca de rotinas que foram desenvolvidas como parte da 
00006 * dissertação de mestrado do autor em Ciências da Computação.
00007 *
00008 * O conjunto de programas foi integralmente desenvolvido pelo autor e está
00009 * disponível sob a licença GPL (GNU General Public License). O entendimento
00010 * integral dos termos da licença GPL é condição necessária para a utilização
00011 * parcial ou integral de qualquer parte deste conjunto de programas.
00012 *
00013 * This file is part of BN Parallel Package.
00014 * 
00015 * BN Parallel Package is free software: you can redistribute it and/or modify
00016 * it under the terms of the GNU General Public License as published by
00017 * the Free Software Foundation, either version 3 of the License.
00018 *
00019 * BN Parallel Package is distributed in the hope that it will be useful,
00020 * but WITHOUT ANY WARRANTY; without even the implied warranty of
00021 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00022 * GNU General Public License for more details.
00023 *
00024 * You should have received a copy of the GNU General Public License
00025 * along with BN Parallel Package. If not, see <http://www.gnu.org/licenses/>.
00026 */
00027 
00028 
00029 /*!
00030  * @file        threadtree.h
00031  * @author      Ernesto Colla (ernesto@gmail.com)
00032  * @version     0.0.1
00033  * @date        Abril/2007
00034  * @brief       \e ThreadTree (Árvore de Threads) para executar processamento em paralelo.
00035  *
00036  * Implementação genérica de uma árvore de threads que executa funções genéricas em paralelo. O vértice pai é executado 
00037  * apenas após os vértices filhos terem sido executados, ou seja, o pai faz um \e join dos filhos. A raiz é o 
00038  * último vértice a ser eliminado. É responsabilidade do programador garantir que o código será \e threadsafe. A biblioteca
00039  * de threadtree não faz nenhuma checagem consistência das estruturas de dados compartilhadas durante a execução do processo.
00040  * O desenvolvedor deve invocar explicitamente apenas as funções para criar/destruir/inserir a própria \e ThreadTree e os \e ThreadVertex
00041  * as funções que lidam com as estruturas internas como a lista ligada, os \e nodes da mesma e a indexação são gerenciados pela própria
00042  * biblioteca e não devem ser invocados diretamente.
00043  */
00044 
00045 #ifndef THREADTREE_H
00046 #define THREADTREE_H
00047 
00048 /* Includes */
00049 #include <pthread.h>
00050 
00051 /* Defines */
00052 
00053 // Status possíveis 
00054 #define THREAD_READY 0          //!< \e Thread está pronta para ser executada. Para executar uma thread ela NECESSARIAMENTE deve estar no estado \e READY.
00055 #define THREAD_RUNNING 1        //!< \e Thread está em execução.
00056 #define THREAD_FINISHED 2       //!< \e Thread foi concluída. Para executá-la novamente é necessária colocá-la no estado READY.
00057 
00058 /* Definição dos tipos de dados */
00059 
00060 /*! Vértice de um grafo que contém ponteiros para a função que irá executar bem como as para estruturas de dados necessárias */
00061 typedef struct struct_ThreadVertex {
00062         int id;                                                                                         //!< \e id único de um vértice no grafo. Atribuído automaticamente para o vértice ao ser adicionado a uma \e threadtree. Não deve ser manipulado pelo desenvolvedor.
00063         int status;                                                                                     //!< Estado corrente da thread.
00064         pthread_t tid;                                                                          //!< \e id interno da thread utilizado pela biblioteca \e pthread.h
00065         void *data;                                                                                     //!< Tipo genérico de dados apra armazenar dados que serão utilizados no processamento.
00066         void *task;                                                                                     //!< Função genérica a ser executada pela thread.
00067         struct struct_ThreadVertex* parent;                                     //!< \e parent do vértice, como é uma árvore tem apenas um 'pai'.
00068         struct struct_ThreadVertexLinkedList* children;         //!< \e children do vértices, lista de flihos dos vértices.
00069 } ThreadVertex;
00070 
00071 /*! Árvore de Threads */
00072 typedef struct struct_ThreadTree {
00073         struct struct_ThreadVertex* root;                                       //!< Vértice que será a raiz da árvore
00074         struct struct_ThreadVertex** index;                                     //!< Array de vértices utilizado para indexar os vértices da \e threadtree
00075         struct struct_ThreadVertexLinkedList* vertices;         //!< Lista ligadas dos vértices da \e threadtrer
00076 } ThreadTree;
00077 
00078 /*! ThreadVertexNode de uma lista ligada utilizado para armazenar o \e ThreadVertex em uma lista ligada */
00079 typedef struct struct_ThreadVertexNode {
00080         struct struct_ThreadVertex* vertex;                                     //!< \e ThreadVertex armazenado no \e node da lista ligada.
00081         struct struct_ThreadVertexNode* next;                           //!< Ponteiro para o próximo \e node da lista.
00082 } ThreadVertexNode;
00083 
00084 /*! Single Linked List de \e nodes contendo \e ThreadVertex */
00085 typedef struct struct_ThreadVertexLinkedList {
00086         int length;                                                                                     //!< Tamanho atual da lista, ou seja, número de nodes da lista ligada.
00087         struct struct_ThreadVertexNode* first;                          //!< Ponteiro para o primeiro \e node da lista.
00088         struct struct_ThreadVertexNode* last;                           //!< Ponteiro para o último \e node da lista.
00089 } ThreadVertexLinkedList;
00090 
00091 
00092 /* Funções */
00093 
00094 /*!
00095  * @brief Cria nova árvore sem vértices.
00096  * @return Ponteiro para a árvore de threads criada.
00097  */
00098 
00099 ThreadTree* buildThreadTree();
00100 
00101 /*!
00102  * @brief Destrói a árvore e desaloca a memória.
00103  *
00104  * Para liberar os recursos alocados para a \e threadtree basta invocar a função \e destroyThreadTree. As demais funções
00105  * para desalocar o index, a lista ligada de vértices, os repectivos \e nodes e os próprios vértices serão invocadas no momento da
00106  * destruição da árvore.
00107  * @param[out] refThreadTree Referência para a árvore que será destruída.
00108  */
00109 void destroyThreadTree(ThreadTree** refThreadTree);
00110 
00111 /*!
00112  * @brief Cria um novo vértice para árvore, com \e id=-1, com as listas vazias
00113  * @param[in] task Ponteiro para a função a ser executada.
00114  * @param[in] data Dados para a função que será executada.
00115  * @return Ponteiro para o vértice recém criado.
00116  */
00117 
00118 ThreadVertex* buildThreadVertex (void* task, void* data);
00119 
00120 /*!
00121  * @brief Destrói o vértice e desaloca a memória.
00122  *
00123  * Para liberar os recursos alocados para a \e threadtree basta invocar a função \e destroyThreadTree. As demais funções
00124  * para desalocar o index, a lista ligada de vértices, os repectivos \e nodes e os próprios vértices serão invocadas no momento da
00125  * destruição da árvore.
00126  * @param[out] refThreadVertex Referência para o vértice que será destruído.
00127  */
00128 
00129 void destroyThreadVertex (ThreadVertex** refThreadVertex);
00130 
00131 /*!
00132  * @brief Adiciona um vértice (\e ThreadVertex) à árvore de \e threads e atribui ao vértice o \e id sequencial.
00133  * @param[out] refThreadTree Referência para a árvore no qual o vértice será adicionado.
00134  * @param[out] refThreadVertex Referência para o vértice a ser adicionado.
00135  * @return Id sequencial para do vértice adicionado.
00136  */
00137 
00138 int addThreadVertex(ThreadTree** refThreadTree, ThreadVertex** refThreadVertex);
00139 
00140 /*!
00141  * @brief Retorna o número de vértices da \e threadtree.
00142  * @param[out] threadtree \e ThreadTree do qual se deseja saber o número de nós.
00143  * @return número de vértices da \e ThreadTree.
00144  */
00145 
00146 int sizeThreadTree(ThreadTree* threadtree);
00147 
00148 /*!
00149  * @brief Indexa a lista de vértices para acelerar a busca. Método invocado internamente, Não deve ser invocado explicitamente.
00150  * @param[out] refThreadTree Referência para a árvore que será indexado.
00151  */
00152 
00153 void createThreadTreeIndex(ThreadTree** refThreadTree);
00154 
00155 /*!
00156  * @brief Desaloca e destrói o index da árvore de \e threads.
00157  *
00158  * Para liberar os recursos alocados para a \e threadtree basta invocar a função \e destroyThreadTree. As demais funções
00159  * para desalocar o index, a lista ligada de vértices, os repectivos \e nodes e os próprios vértices serão invocadas no momento da
00160  * destruição da árvore.
00161  * @param[out] refThreadTree Referência para a árvore que será des-indexada.
00162  */
00163 
00164 void destroyThreadTreeIndex(ThreadTree** refThreadTree);
00165 
00166 /*!
00167  * @brief Retorna o n-ésimo vértice da árvore. Os \e ids atríbuidos automaticamente aos vértices ao adicioná-los à árvore são sequenciais.
00168  * @param[out] refThreadTree Referência para a árvore do qual se deseja obter o vértice.
00169  * @param[in] n Número do elemento que se deseja.
00170  * @return \e n-ésimo vétice ou \e null se não houver vértice.
00171  */
00172 
00173 ThreadVertex* getThreadVertex(ThreadTree** refThreadTree, int n);
00174 
00175 /*!
00176  * @brief Define um arco, necessariamente direcional, entre dois vértices. O arco é direcional pois estamos lidando com uma árvore.
00177  * @param[out] refThreadTree Referência à árvore na qual será adicionado o arco.
00178  * @param[in] refParent Referência para o vértice que é a origem do arco.
00179  * @param[in] refChild Referência para o vértice que é o destino do arco.
00180  * @return Números de filhos do \e parent, que corresponde ao número de arcos que tem origem no vértice \e parent.
00181  */
00182 
00183 int addTreeArc(ThreadTree** refThreadTree, ThreadVertex** refParent, ThreadVertex** refChild);
00184 
00185 /*!
00186  * @brief Define um arco, necessariamente direcional, entre dois vértices. O arco é direcional pois estamos lidando com uma árvore.
00187  * @param[out] refThreadTree Referência à árvore na qual será adicionado o arco.
00188  * @param[in] idParent Id do vértice que é a origem do arco.
00189  * @param[in] idChild Id do vértice que é o destino do arco.
00190  * @return Números de filhos do \e parent, que corresponde ao número de arcos que tem origem no vértice \e parent.
00191  */
00192 
00193 int addTreeArcByIds(ThreadTree** refThreadTree, int idParent, int idChild);
00194 
00195 /*!
00196  * @brief Dump no \e stdout do conteúdo da árvore de \e threads.
00197  * @param[in] threadtree \e ThreadTree da qual se deseja fazer o dump.
00198  */
00199 
00200 void dumpThreadTree (ThreadTree* threadtree);
00201 
00202 // LINKED LIST: Funções que lidam com a lista de vértices
00203 
00204 /*!
00205  * @brief Cria uma nova lista ligada simples para armazenar os vértices do grafo utilizado para representar \e threadtree.
00206  * @return Ponteiro para uma lista ligada.
00207  */
00208 
00209 ThreadVertexLinkedList* buildThreadVertexLinkedList ();
00210 
00211 /*!
00212  * @brief Destroy uma lista ligada simples 
00213  *
00214  * Para liberar os recursos alocados para a \e threadtree basta invocar a função \e destroyThreadTree. As demais funções
00215  * para desalocar o index, a lista ligada de vértices, os repectivos \e nodes e os próprios vértices serão invocadas no momento da
00216  * destruição da árvore.
00217  * ATENÇÃO: Considerando que o ThreadVertex pertence ao grafo e não à lista de vértice, que é apenas uma estrutura auxiliar, a
00218  * destruição a lista NÃO desaloca os, vértices, os mesmos serão desalocados quando a árvore for destruído.
00219  * @param[out] refList Referência à lista que deve ser desalocada
00220  */
00221 
00222 void destroyThreadVertexLinkedList (ThreadVertexLinkedList** refList);
00223 
00224 /*!
00225  * @brief Cria um novo \e node da lista ligada de vértices que irá armazenar o \e ThreadVertex passado como parâmetro.
00226  * @param[in] vertex \e ThreadVertex que será armazenado no \e node a ser criado.
00227  * @param[in] next Ponteiro para o próximo \e node da lista ligada.
00228  * @return Ponteiro para um novo node da lista ligada de vértices
00229  */
00230 
00231 ThreadVertexNode* buildThreadVertexNode (ThreadVertex* vertex, ThreadVertexNode* next);
00232 
00233 /*!
00234  * @brief Destrói um node da lista de vértices.
00235  * ATENÇÃO: Considerando que o ThreadVertex pertence à \e ThreadTree e não à lista de vértice,
00236  * que é apenas uma estrutura auxiliar, a destruição a lista NÃO desaloca os, vértices, os mesmos
00237  * serão desalocados quando a árvore for destruído.
00238  * @param[out] refNode Node da lista que deve ser destruído.
00239  */
00240 
00241 void destroyThreadVertexNode(ThreadVertexNode** refNode);
00242 
00243 /*!
00244  * @brief Acrescenta um \e ThreadVertexNode no final da lista ligada. 
00245  * @param[out] refList Lista na qual deve ser acrescentado o \e node.
00246  * @param[in] vertex \e ThreadVertexNode que deve ser acrescentado.
00247  * @return Posição na lista do node inserido.
00248  */
00249 
00250 int appendThreadVertexNode(ThreadVertexLinkedList** refList, ThreadVertex* vertex);
00251 
00252 /*!
00253  * @brief Dump de uma lista de vértices.
00254  * @param[in] list Lista da qual se deseja o dump 
00255  */
00256 
00257 void dumpThreadVertexLinkedList(ThreadVertexLinkedList* list);
00258 
00259 // THREADS
00260 
00261 /*!
00262  * @brief Executa uma \e thread, ou seja, a função que foi atribuída ao \e ThreadVertex com os dados armazenados no mesmo.
00263  * A invocação desta função não boqueia a execução do programa (ou da \e thread que a invocou) que continua a ser executado.
00264  * 
00265  * ATENÇÃO: Para ser executado o \e ThreadVertex deve estar com o estado \e READY. Ao iniciar a execução o \e ThreadVertex
00266  * passa para o estado \e RUNNING e ao concluí-la passa para o estado \e FINISHED.
00267  * @param[out] refVertex Referência ao vertex da thread que deve ser executada.
00268  */
00269 
00270 int run(ThreadVertex** refVertex);
00271 
00272 /*!
00273  * @brief Define um estado para a \e thread.
00274  * 
00275  * ATENÇÃO: Para ser executado o \e ThreadVertex deve estar com o estado \e READY. Ao iniciar a execução o \e ThreadVertex
00276  * passa para o estado \e RUNNING e ao concluí-la passa para o estado \e FINISHED.
00277  * @param[out] refVertex Referência ao vertex da \e thread.
00278  * @param[in] status Estado a ser definido para o \e ThreadVertex. Estados possíveis: READY, RUNNING E FINISHED.
00279  */
00280 
00281 void setStatus (ThreadVertex** refVertex, int status);
00282 
00283 /*!
00284  * @brief Retorna o estado atual da \e thread armazenada no vértice.
00285  * @param[in] vertex Vétice que contém a \e thread.
00286  * @return Estado corrente da \e ThreadVertex. Estados possíveis: READY, RUNNING E FINISHED.
00287  */
00288 
00289 int getStatus (ThreadVertex* vertex);
00290 
00291 /*!
00292  * @brief \e Join de um \e ThreadVertex, ou seja, da \e thread que esta estrutura de dados representa internamente.
00293  *
00294  * A invocação desta função bloqueia a execução do programa, ou da \e thread que a invocou, até que a \e thread aguardada seja concluída.
00295  * Esta função é utilizada internamente pelas funções \e joinDescendants e \e joinThreadTree.
00296  * @param[out] refVertex Referência ao vértice da \e thread que deve ser aguardada.
00297  */
00298 
00299 void join (ThreadVertex** refVertex);
00300 
00301 /*!
00302  * @brief \e Join de todos os descendentes (filhos) de um \e ThreadVertex.
00303  *
00304  * A invocação desta função bloqueia a execução do programa, ou da \e thread que a invocou, até que a todos os descendentes 
00305  * tenham sido concluídos.
00306  * @param[out] refVertex Referência ao vértice do qual a execução dos descendentes deve ser aguardada.
00307  */
00308 
00309 void joinDescendants (ThreadVertex** refVertex);
00310 
00311 /*!
00312  * @brief \e Join da árvore como um todo.
00313  *
00314  * A invocação desta função bloqueia a execução do programa, ou da \e thread que a invocou, até que a execução de todos os
00315  * vértices tenha sido concluída, ou seja, é equivalente a aguardar a execução dos descendentes da raiz da árvore.
00316  * @param[out] refThreadTree Referência para a árvore de threads.
00317  */
00318 
00319 void joinThreadTree (ThreadTree** refThreadTree);
00320 
00321 /*!
00322  * @brief Inicia a execução de uma árvore de threads em um processo em paralelo, ou seja, a invocação desta função
00323  * não boqueia a execução do program (ou da \e thread que a invocoua) que continua a ser executado. A aplicação deve
00324  * necessariamente definir as threads como THREAD_READY
00325  * @param[out] refThreadTree Referência à árvore que deve ser executada
00326  */
00327 
00328 void execute(ThreadTree** refThreadTree);
00329 
00330 
00331 /*!
00332  * @brief RE-Inicia a execução de uma árvore de threads em um processo em paralelo, ou seja, a invocação desta função
00333  * não boqueia a execução do program (ou da \e thread que a invocoua) que continua a ser executado. Igual execute(), mas
00334  * automaticamente define o status das threads como THREAD_READY.
00335  * @param[out] refThreadTree Referência à árvore que deve ser executada
00336  */
00337 
00338 void restart(ThreadTree** refThreadTree);
00339 
00340 /*!
00341  * @brief Define o \e root da árvore pelo \e id do \e ThreadVertex.
00342  *
00343  * Caso não seja atribuído explicitamente pelo desenvolvedor, a biblioteca, se necessário, tenta descobrir automaticamente
00344  * a raiz, ou seja, o \e node com \e parent = null. Na quase totalidade dos casos não há necessidade e não é recomendavel
00345  * que o desenvolvedor defina explicitamente o raiz, deixando esta tarefa para a biblioteca.
00346  * @param[out] refThreadTree Referência à árvore que deve ser executada
00347  * @param[in] rootId Id do node root
00348  */
00349 
00350 void setRootById(ThreadTree** refThreadTree, int rootId);
00351 
00352 /*!
00353  * @brief Define o root da árvore informando diretamente o \e ThreadVertex. 
00354  *
00355  * Caso não seja atribuído explicitamente pelo desenvolvedor, a biblioteca, se necessário, tenta descobrir automaticamente
00356  * a raiz, ou seja, o \e node com \e parent = null. Na quase totalidade dos casos não há necessidade e não é recomendavel
00357  * que o desenvolvedor defina explicitamente o raiz, deixando esta tarefa para a biblioteca.
00358  * @param[out] refThreadTree Referência à árvore que deve ser executada.
00359  * @param[in] root node root.
00360  */
00361 
00362 void setRoot(ThreadTree** refThreadTree, ThreadVertex* root);
00363 
00364 #endif

Gerado em Fri Feb 15 19:50:41 2008 para IME-Dissertação por  doxygen 1.5.1