Ferramentas de Usuário

Ferramentas de Site


dev_geral:c:listas

Alocação de Listas com Macros

Este artigo faz um uso de macros pouco recomendável, e de utilidade, no mínimo, discutível. Ainda assim, permite ao leitor conhecer potencialidades das macros.

Neste snippet está o header lalloc, que disponibiliza alocação de listas feita inteiramente por macros (pela performance).

Este header depende de xalloc, que implementa as funções de allocação dinâmica de memória com verificação implícita.

NOTA: O lalloc.h usa uma extenção da gnu nas macros:

#define mumble() ({ /*...*/ })

Isto é equivalente ao tipico

#define mumble() do { /*...*/ } while (0)

lalloc.h:

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2007 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef LALLOC_H_
#define LALLOC_H_
 
#include <stdlib.h>
#include "xalloc.h"
 
/* Nota: As macros neste ficheiro devem assegurar apenas as ligações das listas.
 *       So' aos membros next e prev devem ser atribuidos valores.
 *
 * *SO'* devera' ser feito free() se a função tiver explicitamente "free" no identificador
 */
 
/* Listas bidirecionais:
 *      #define alloc_something(plst) _alloc_bi_node(plst)
 *      #define alloc_something_with_last(plst,last_node) _alloc_bi_node_with_last(plst,last_node)
 *      #define alloc_something_in_head(plst) _alloc_bi_node_in_head(plst)
 *      #define rm_something(plst,torm) _rm_bi_node(plst,torm)
 *      #define free_entire_something(plst,do_something_with_each_node) _free_entire_list(plst,do_something_with_each_node)
 *
 * Listas unidirecionais
 *      #define alloc_something(plst) _alloc_uni_node(plst)
 *      #define alloc_something_with_last(plst,last_node) _alloc_uni_node_with_last(plst,last_node)
 *      #define alloc_something_in_head(plst) _alloc_uni_node_in_head(plst)
 *      #define free_entire_something(plst,do_something_with_each_node) _free_entire_list(plst,do_something_with_each_node)
 */
 
/* Aloca nós de listas bidirecionais */
#define _alloc_bi_node(_lst)                                                  
        (                                                                     
        {                                                                     
                typeof(*_lst) _node;                                          
                typeof(_lst) _plst=(_lst);                                    
 
                if (*_plst == NULL)                                           
                {                                                             
                        _node=*_plst=xmalloc(sizeof(**_plst));                
                        _node->prev=NULL;                                     
                }                                                             
                else                                                          
                {                                                             
			for (_node=*_plst; _node != NULL; _node=_node->next)  
                                if (_node->next == NULL)                      
                                        break;                                
 
                        _node->next=xmalloc(sizeof(*_node->next));            
 
                        _node->next->prev=_node;                              
 
                        _node=_node->next;                                    
                }                                                             
 
                _node->next=NULL;                                             
 
                _node;                                                        
        }                                                                     
        )
 
/* Aloca nós de listas bidirecionais, no inicio da lista */
#define _alloc_bi_node_in_head(_lst)                                            
        (                                                                       
        {                                                                       
                typeof(_lst) _plst=(_lst);                                      
                typeof(*_lst) _next=*_plst;                                     
                typeof(*_lst) _node;                                            
 
                _node=*_plst=xmalloc(sizeof(**_plst));                          
 
                _node->next=_next;                                              
                _node->prev=NULL;                                               
 
                if (_node->next != NULL)                                        
                        _node->next->prev=_node;                                
 
                _node;                                                          
        }                                                                       
        )
 
/* Aloca nós de listas bidirecionais sabendo o ultimo no', para melhorar a performance */
#define _alloc_bi_node_with_last(_lst,_last_node)                                       
        (                                                                               
        {                                                                               
                typeof(*_lst) _node;                                                    
                typeof(_lst) _plst=(_lst);                                              
 
                if (*_plst == NULL)                                                     
                {                                                                       
                        _node=*_plst=xmalloc(sizeof(**_plst));                          
                        _node->prev=NULL;                                               
                }                                                                       
                else                                                                    
                {                                                                       
 
                        if ((_last_node) == NULL)                                       
                        {                                                               
                                for (_node=*_plst; _node != NULL; _node=_node->next)    
                                        if (_node->next == NULL)                        
                                                break;                                  
                        }                                                               
                        else                                                            
                        {                                                               
                                _node=(_last_node);                                     
                                assert(_node->next == NULL);                            
                        }                                                               
 
                        _node->next=xmalloc(sizeof(*_node->next));                      
 
                        _node->next->prev=_node;                                        
 
                        _node=_node->next;                                              
                }                                                                       
 
                _node->next=NULL;                                                       
 
                _node;                                                                  
        }                                                                               
        )
 
/* Retira nós de listas bidirecionais */
#define _rm_bi_node(_lst,_torm)                                                 
        (                                                                       
        {                                                                       
                typeof(_torm) _torm2=(_torm);                                   
                typeof(_lst) _lst2=(_lst);                                      
 
                if (_torm2 != NULL && *_lst2 != NULL)                           
                {                                                               
                        if (_torm2->prev == NULL)                               
                        {                                                       
                                *_lst2=_torm2->next;                            
 
                                if (_torm2->next != NULL)                       
                                        _torm2->next->prev=NULL;                
                        }                                                       
                        else                                                    
                        {                                                       
                                _torm2->prev->next=_torm2->next;                
 
                                if (_torm2->next != NULL)                       
                                        _torm2->next->prev=_torm2->prev;        
                        }                                                       
                }                                                               
        }                                                                       
        )
 
/* Aloca nós de listas unidirecionais */
#define _alloc_uni_node(_lst)                                                   
        (                                                                       
        {                                                                       
                typeof(*_lst) _node;                                            
                typeof(_lst) _plst=(_lst);                                      
 
                if (*_plst == NULL)                                             
                        _node=*_plst=xmalloc(sizeof(**_plst));                  
                else                                                            
                {                                                               
                        for (_node=*_plst; _node != NULL; _node=_node->next)    
                                if (_node->next == NULL)                        
                                        break;                                  
 
                        _node->next=xmalloc(sizeof(*_node->next));              
                        _node=_node->next;                                      
                }                                                               
 
                _node->next=NULL;                                               
 
                _node;                                                          
        }                                                                       
        )
 
/* Aloca nós de listas unidirecionais no inicio da lista */
#define _alloc_uni_node_in_head(_lst)                                           
        (                                                                       
        {                                                                       
                typeof(_lst) _plst=(_lst);                                      
                typeof(*_lst) _next=*_plst;                                     
                typeof(*_lst) _node;                                            
 
                _node=*_plst=xmalloc(sizeof(**_plst));                          
 
                _node->next=_next;                                              
 
                _node;                                                          
        }                                                                       
        )
 
/* Aloca nós de listas unidirecionais sabendo o ultimo no', para melhorar a performance */
#define _alloc_uni_node_with_last(_lst,_last_node)                                      
        (                                                                               
        {                                                                               
                typeof(*_lst) _node;                                                    
                typeof(_lst) _plst=(_lst);                                              
 
                if (*_plst == NULL)                                                     
                        _node=*_plst=xmalloc(sizeof(**_plst));                          
                else                                                                    
                {                                                                       
                        if ((_last_node) == NULL)                                       
                        {                                                               
                                for (_node=*_plst; _node != NULL; _node=_node->next)    
                                        if (_node->next == NULL)                        
                                                break;                                  
                        }                                                               
                        else                                                            
                        {                                                               
                                _node=(_last_node);                                     
                                assert(_node->next == NULL);                            
                        }                                                               
 
                        _node->next=xmalloc(sizeof(*_node->next));                      
                        _node=_node->next;                                              
                }                                                                       
 
                _node->next=NULL;                                                       
 
                _node;                                                                  
        }                                                                               
        )
 
/* Liberta listas unidirecionais/bidirecionais */
#define _free_entire_list(_lst,do_something_with_each_node)               
        (                                                                 
        {                                                                 
                typeof(*_lst) _node;                                      
                typeof(*_lst) _next_node;                                 
                typeof(_lst) _plst=(_lst);                                
 
 
                for (_node=*_plst; _node != NULL; _node=_next_node)       
                {                                                         
                        _next_node=_node->next;                           
                        if (do_something_with_each_node != NULL)          
                                do_something_with_each_node(_node);       
                        free(_node);                                      
                }                                                         
 
                *_plst=NULL;                                              
        }                                                                 
        )
#endif /*alloc.h included*/
dev_geral/c/listas.txt · Última modificação em: 2018/05/14 21:37 (edição externa)