singlelinkedlist.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        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

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