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 singlelinkedlist.h 00031 * @author Ernesto Colla (ernesto@gmail.com) 00032 * @version 0.0.1 00033 * @date 2007-04-30 00034 * @brief Implementação uma biblioteca de lista simplesmente ligada genérica (Single Linked List) 00035 * 00036 * Implementação de uma biblioteca de lista ligada simples genérica 00037 * com ponteiros para o primeiro e o último elementos para que a 00038 * a inserção de um novo elemento no início e no final seja em tempo 00039 * constante. 00040 * A implentação foi feita para ser \e threadsafe, ou seja, pode ser 00041 * utilizada para aplicação multithreads. 00042 * 00043 */ 00044 00045 #ifndef SINGLELINKEDLIST_H 00046 #define SINGLELINKEDLIST_H 00047 00048 /* Includes */ 00049 #include <math.h> 00050 #include <pthread.h> 00051 #include <stdio.h> 00052 #include <stdlib.h> 00053 00054 /* Defines */ 00055 00056 /* Definição dos tipos de dados */ 00057 00058 /*! Alias para ponteiro void para armazenar dados nos nodes da lista ligada */ 00059 typedef void* SLLDATA; 00060 00061 /*! Node de uma Single Linked Liste de uma lista ligada */ 00062 typedef struct struct_SingleLinkedListNode { 00063 SLLDATA data; //!< Variável que armazena o conteúdo do node 00064 struct struct_SingleLinkedListNode* next; //!< Ponteiro para o próximo elemento da lista ligada ou \e NULL se for o último 00065 } SingleLinkedListNode; 00066 00067 /*! Single Linked List */ 00068 typedef struct struct_SingleLinkedList { 00069 int length; //!< Tamanho da lista, ou seja, número de nós atual 00070 struct struct_SingleLinkedListNode* first; //!< Ponteiro para o primeiro nó da lista 00071 struct struct_SingleLinkedListNode* last; //!< Ponteiro para o último elemento da lista 00072 } SingleLinkedList; 00073 00074 00075 /* Funções */ 00076 00077 /*! 00078 * @brief Cria uma nova lista ligada simples. 00079 * 00080 * Para desalocar a memória utilizar destroySingleLinkedList 00081 * @return Ponteiro para uma lista ligada 00082 */ 00083 00084 SingleLinkedList* newSingleLinkedList (); 00085 00086 /*! 00087 * @brief Destrói uma lista ligada simples, mas NÃO destrói o conteúdo dos nós da lista ligada. 00088 * @param[out] refList Referência à lista que deve ser desalocada, atribui NULL para refêrencia 00089 */ 00090 00091 void destroySingleLinkedList (SingleLinkedList** refList); 00092 00093 /*! 00094 * @brief Cria um novo node da lista ligada com conteúdo NULL 00095 * @return Ponteiro para um novo node da lista ligada de vértices 00096 */ 00097 00098 SingleLinkedListNode* newSingleLinkedListNode (); 00099 00100 /*! 00101 * @brief Cria e inicializa o conteúdo de um novo node da lista ligada 00102 * @param[in] data Dado a ser armazenado no Node 00103 * @return Ponteiro para um novo node da lista ligada de vértices 00104 */ 00105 00106 SingleLinkedListNode* buildSingleLinkedListNode (SLLDATA data); 00107 00108 /*! 00109 * @brief Destrói um node da lista ligada simples, mas NÃO destrói o conteúdo dos nós da lista ligada 00110 * @param[out] refNode Referência ao Node da lista que deve ser destruido, atribui NULL para refêrencia 00111 */ 00112 00113 void destroySingleLinkedListNode(SingleLinkedListNode** refNode); 00114 00115 /*! 00116 * @brief Retorna o tamanho da lista 00117 * @param[in] list Lista da qual se deseja saber o tamanho 00118 * @return Tamanho da lista 00119 */ 00120 00121 int slllength(SingleLinkedList* list); 00122 00123 /*! 00124 * @brief Acrescenta um SingleLinkedListNode no início da lista ligada. 00125 * 00126 * O tempo de inserção de um novo elemento no início ou no fim da lista é linear. 00127 * O \e node inserido passa a ser o \e first. 00128 * @param[out] refList Referência para lista na qual deve ser acrescentado o node 00129 * @param[in] data Conteúdo do SingleLinkedListNode que será criado e que dever ser acrescentado no início da lista 00130 * @return 1 se inseriu com sucesso; 0 caso contrário 00131 */ 00132 00133 int sllpush (SingleLinkedList** refList, SLLDATA data); 00134 00135 /*! 00136 * @brief Acrescenta um SingleLinkedListNode no início da lista ligada garantindo a atomicidade da operação versão que deve ser utilizada em aplicações multi-thread que compartilham listas ligadas 00137 * 00138 * O tempo de inserção de um novo elemento no início ou no fim da lista é linear. 00139 * O \e node inserido passa a ser o \e first. 00140 * @param[out] refList Referência para lista na qual deve ser acrescentado o node 00141 * @param[in] data Conteúdo do SingleLinkedListNode que será criado e que dever ser acrescentado no início da lista 00142 * @param[in] mutex Mutex utilizado para sincronizar a operação 00143 * @return 1 se inseriu com sucesso; 0 caso contrário 00144 */ 00145 00146 int sllsyncpush (SingleLinkedList** refList, SLLDATA data, pthread_mutex_t* refMutex); 00147 00148 /*! 00149 * @brief Acrescenta um SingleLinkedListNode no final da lista ligada. 00150 * 00151 * O tempo de inserção de um novo elemento no início ou no fim da lista é linear. 00152 * O \e node inserido passa a ser o \e last. 00153 * @param[out] refList Referência para lista na qual deve ser acrescentado o node 00154 * @param[in] data Conteúdo do SingleLinkedListNode que será criado e que dever 00155 * ser acrescentado no final da lista 00156 * @return 1 se inseriu com sucesso; 0 caso contrário 00157 */ 00158 00159 int sllappend(SingleLinkedList** refList, SLLDATA data); 00160 00161 /*! 00162 * @brief Acrescenta um SingleLinkedListNode no final da lista ligada garantindo a atomicidade da operação versão que deve ser utilizada em aplicações multi-thread que compartilham listas ligadas 00163 * 00164 * O tempo de inserção de um novo elemento no início ou no fim da lista é linear. 00165 * O \e node inserido passa a ser o \e last. 00166 * @param[out] refList Referência para lista na qual deve ser acrescentado o node 00167 * @param[in] data Conteúdo do SingleLinkedListNode que será criado e que dever 00168 * ser acrescentado no final da lista 00169 * @param[in] mutex Mutex utilizado para sincronizar a operação 00170 * @return 1 se inseriu com sucesso; 0 caso contrário 00171 */ 00172 00173 int sllsyncappend (SingleLinkedList** refList, SLLDATA data, pthread_mutex_t* refMutex); 00174 00175 /*! 00176 * @brief Remove o primeiro elemento da lista 00177 * @param[out] refList Referência para lista da qual deve ser removido o node 00178 * @return O conteúdo que estava armazenado no SingleLinkedListNode 00179 */ 00180 00181 SLLDATA sllremove_first(SingleLinkedList** refList); 00182 00183 /*! 00184 * @brief Remove o último elemento da lista 00185 * @param[out] refList Referência para lista da qual deve ser removido o node 00186 * @return O conteúdo que estava armazenado no SingleLinkedListNode 00187 */ 00188 00189 SLLDATA sllremove_last(SingleLinkedList** refList); 00190 00191 /*! 00192 * @brief Dump do conteúdo da lista ligada 00193 * @param[in] list Lista ligada 00194 */ 00195 00196 void dumpSingleLinkedList(SingleLinkedList* list); 00197 00198 #endif // SINGLELINKEDLIST_H