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