Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I

O pré-processador C

A linguagem de programação C prevê que o texto de um programa C seja primeiramente submetido a um componente denominado “pré-processador”. O pré-processador permite que certas sequências de caracteres sejam tratadas de forma a criar, alterar e remover outras seqüências segundo as regras discutidas a seguir.

Inclusão de arquivos:

Nos locais onde aparecem #include “nome” ou #include <nome>, estas seqüências são removidas e substituidas pelo conteúdo dos arquivos identificados entre aspas ou entre “menor” e “maior”. Arquivos cujos nomes estejam entre aspas são procurados a partir do diretório do fonte onde apareceu e se ele não for encontrado, ou se o nome estiver entre menor e maior, a busca será feita segundo regras ad-hoc (os arquivos incluidos também podem ter #include). A ocorrência de #include texto onde o texto não corresponde às duas formas anteriores é interpretada com sendo uma macro (veja à frente) e após a expansão da macro o texto resultante deve ser uma das duas formas anteriores.

“macros”

A palavra macro foi escolhida em função do significado “proeminente, largo, grande”, a idéia aqui é, tipicamente, substituir um nome por um texto. Existe o que é denominado “definição” cuja forma geral é #define nome texto_a_ser_colocado_no_lugar_do_nome, e partir desta definição podem ocorrer as “invocações” ou chamadas da macro que correspondem às ocorrências de nome, estas ocorrências serão substituidas pelo texto que o segue na definição. Dizemos também que nas ocorrências de nome haverá uma “expansão de macro”. Se o texto for realmente “macro” as linhas deverão terminar com o caractere “\”(barra invertida” e poderá consistir de várias linhas de texto. O escopo do nome será do ponto de definição até fim do arquivo. Uma definição pode usar outras definições. As substituições são baseadas em símbolos sintáticos (tokens).

É possível definir macros com argumentos, por exemplo
#define max(A, B) ((A)>(B)? (A):(B))
cada ocorrência de um parâmetro formal será substituida pelo parâmetro real correspondente a linha de texto
x=max(p+q,r+s);
será substituida pela linha de texto
x=((p+q)>(r+s)?(p+q):(r+s));

Observe esta macro e as armadilhas que o programador pode enfrentar, por exemplo, acostumado com funções ele pensa que trá um resultado e terá outro no caso de :
max(i++, j++)
Veja esta outra armadilha:
#define square(x) x*x /*armadilha, perigo */
um pouco menos perigosa é a definição
#define square(x) (x)*(x)

Um identificador X definido via #define X <texto> pode ter sua definição removida (e pode aparecer sem ser substituido) utilizando a diretiva #undef (por exemplo: #undef X )

Se um parâmetro formal for precedido do caractere # então haverá a expansão do texto corresponde a este parâmetro entre aspas.Lembrando que na linguagem C a ocorrência contígüa de duas seqüências de caracteres entre aspas corresponde à concatenação de strings( ou seja “abc” “def” equivale a “abcdef”) temos uma capacidade de expansão bastante expressiva.

Consider a macro
#define escreve(expr) printf(#expr “=%g\n”, expr)
quando houver uma invocação do tipo
escreve(x/y);
a macro será expandida da seguinte forma
printf(“x/y” “%g\n”, x/y);
com a concatenação dos strings o efeito corresponde a
printf(“x/y=%g\n”, x/y);
no argumento real cada aspas é trocada por barra aspas e cada barra é trocada por barra barra na tentativa de que o string seja correto.

O pré-processador permite o uso do operador ## que prove concatenação de argumentos reais durante a expansão e o resultado é verificado para novas expansões. Em outras palavras logo após serem feitas expansões, envolvendo ou não parâmetros, ocorrências de ## são removidas juntamente com os espaços adjacentes de forma a concatenar os símbolos adjacentes que poderão assim forma novos símbolos. As regras relacionadas ao uso aninhado do operador ## são bastante esotéricas. Para a definição
#define concatena(x,y) x##y
a chamada concatena(var,123) resulta em var123, entretanto a chamada concatena(concatena(1,2),3) é indefinida.

Processamento condicional de texto

É possível controlar o preprocessamento com comandos denominados “condicionais” e que são avaliados durante o pré-processamento. Pode ser feita então inclusão condicional de texto. A linha #if avalia uma expressão do tipo int se a expressão for diferente de zero as linhas subsequentes são incluidas no texto até que apareça uma linha #endif ou #elif ou #else . A expressão defined (nome) em uma linha #if corresponde a 1 se o nome foi definido e 0 caso contrário. Para ter certeza de que um certo cabecalho seja incluido somente uma vez podemos escrever
#if !defined(MASTERMIND)
#define MASTERMIND
/* conteudo do arquivo*/
#endif

ou ainda

#ifndef MASTERMIND
#define MASTERMIND
/* conteudo do arquivo*/
#endif

#iifdef nome e #ifndef nome são linhas especializadas que testam a definição de nome

Typedef

A linguagem C permite o uso de cláusulas ou declarações denominadas “typedef”, para criar novos nomes de tipos de dados. A declaração

typedef int Tamanho;

faz de Tamanho um sinônimo de int e podemos usa-lo de maneira a tornar mais legível um programa:

Tamanho tam, tamMax;
Tamanho *tamanho[];

De forma similar a declaração:

typedef char *String;

faz de String um sinônimo de char * (ponteiro para caracteres) e podemos usá-lo em declarações e elencamentos:

String p, aptLinha[LINHAMAX], alloc(int);

int strcmp(String, String);

p=(String) malloc(100);

Para entender a sintaxe do “typedef”: considere qualquer declaração válida, por exemplo int ii, jj; quando uma declaração é prefixada com “typedef” os identificadores não correspondem mais às variáveis mas sim aos nomes de tipos. O seguinte trecho:
typedef int ii, jj;
ii v1;
jj v2;

corresponde a definir dois sinônimos para o tipo int (ii~int, jj~int) e usar estes sinônimos para definir as variáveis v1 e v2. A convenção usual é usar nomes com letras maiúsculas ou iniciados com letras maiúsculas.

Uma declaração “typedef” não cria um novo tipo nem acrescenta nenhuma nova semântica , uma variável declarada via um identificador definido via typedef tem as mesmas propriedades das variáveis declaradas sem o uso do mecanismo provido pelo typedef. Ou seja estes dois trechos são equivalentes:

Com typedef	Sem typedef
typedef int Nome1, Nome2; Nome1 v1; Nome2 v2;	int v1; int v2;

O mecanismo associado ao typedef é similar ao mecanismo do #define, mas o typedef é interpretado pelo compilador, isto possibilita substituições que estão além da capacidade do pré-processador que é o elemento responsável pelo #define. Por exemplo
typedef int (*PFI)(char *, char *);
cria um identificador, PFI, que é sinônimo do tipo “ponteiro para função que tem dois parâmetros, ambos do tipo char *, e que retorna um valor do tipo int. Uma vez definido este identificador podemos de uma maneira bem legível declarar ou definir identificadores:
PFI strcmp, numcmp;

Além das questões estéticas existem duas razões principais para o uso de “typedef”s: (i) parametrização de um programa com relação a questões de portabilidade. Ao ser usado o typedef para tipos de dados que têm dependências de máquinas somente os typedefs são alterados nas mudanças de máquinas (este é o caso de size_t). O segundo propósito dos typedefs é prover melhor legibilidade e entendimento em um programa.

A definição em C de uma estrutura utilizando typedefs poderia ser:
typedef struct nodol *Nodoptr;
typedef struct nodol {
char *info;
Nodoptr anterior;
Nodoptr proximo;
} NodoDeLista;

O trecho acima define nodol como uma etiqueta de estrutura, Nodoptr como identificador de tipo, e NodoDeLista como um identificador de uma instância de struct nodol. Uma função que aloca um nodo de lista e retorna seu endereço pode ser definida da seguinte forma:
Nodoptr aloca_nodolista(void){
return (Nodoptr) malloc(sizeof(NodoDeLista));
}

Unions

Uma união ou “union” denota o tipo de uma variável que pode manter uma certa configuração de bits que pode ser “percebida” como sendo de diferentes tipos e tamanhos. Os elementos componentes de uma união ocupam o mesmo espaço da memória e só é reservado espaço sufiente para o maior componente. O conceito de “union” tenta disciplinar a visão e uso de uma mesma região da memória a partir de diferentes tipos e envolve a cooperação do compilador e do sistema de execução. Na linguagem Pascal o conceito correspondente é “variant records”. outra maneira de entender o conceito de união é: quando uma variável é do tipo união então a região de memória reservada para esta variável (o tamanho corresponde ao tamanho do maior componente) pode ser “tipada” de mais de uma forma:

union identificador{ int IDint; char *IDchar;} var;

Outra forma de definir var é:
union { int IDint; char *IDchar;} var;

Similarmente às estruturas o identificador que segue a palavra reservada union é uma etiqueta opcional.

é comum a definição de uma variável que rastreia qual o tipo de valor foi atribuido a var:
int temINT=0;

então podemos escrever código da seguinte forma:

if(temINT)
printf(“%d\n”, var.IDint);
else
printf(“%s\n”, var.IDchar);

A forma de acessar os membros de uma união é idêntica à forma usada para estruturas. E podemos usar ponteiros para uniões:

union identificador *pu;
pu=&var;
printf(“%d\n”, pu->IDint);

A inicialização de uma instância de união pode ser feita e o tipo do “inicializador” deve corresponder ao tipo do primeiro componente.

Campos de bits

A linguagem C foi originalmente projetada pensando não só em programação em “alto nível” mas também na chamada “programação de baixo nível”.Programação de baixo nível é a programação voltada para aspectos de máquina!

Em alguns tipos de plataforma o espaço de memória é um bem muito precioso e pode ser necessário colocar ou compartilhar vários valores em uma “palavra de memória” (a memória principal além de ser organizada e endereçada byte a byte é comumente organizada e eficientemente endereçada palavra a palavra, onde uma palavra correponde a um certo grupo de bytes, usualmente a 2, 4 ou 8 bytes). Além deste tipo de requisito também é comum quer os registradores (por exemplo no caso de dispositivos de entrada e saída) exijam a manipulação de grupos de bits em palavras ou bytes. Neste tipo de contexto podemos usar o pré-processador C para definir “máscaras de bits” para certos grupos:

#define BIT0 01
#define BIT1 02
#define BIT2e3 0xC

ou ainda

enum {BIT0=01, BIT1=02, BIT2e3=0xC};

Agora podemos operar com deslocamentos, operar com máscaras, complementos etc.

int flags=0;
flags|=BIT0; /* liga o bit menos significativo */
flags|=BIT2e3; /*liga os bits 2 e 3 sem alterar os demais!*/

flags &=~(BIT0 | BIT2e3); /* desliga os bits 0 2 e 3 sem alterar os demais */

Além destes “estilos” a linguagem C oferece a capacidade de definição e acesso de bits de forma direta ao invés do uso de operadores lógicos. Um campo de bits (bit-field) ou campo é um conjunto de bits adjacentes em uma abstração conhecida como palavra (uma sequencia de bits). A metáfora a ser seguida é uma estrutura:

struct {unsigned int BIT0:1; unsigned int BIT1:1; unsigned int BIT2e3:2} flags;

A sentence acima define uma variável flags que contém dois campos de 1 bit e um campo de 2 bits. a expressão unsigned int é um açucar sintático com significado <campo de bits>. Os campos são acessados de forma similar a expressões de acesso a campos de estruturas. Os campos funcionam como “pequenos ints” e podem participar de expressões em geral:

flags.BIT2e3=3; /* 3 corresponde aos dois bits menos significativos ligados */
flags.BIT1=0;
flags.BIT0=0;
printf(“%d\n”, flags); /*>>pode<< imprimir 12 */

Os campos podem não ter nome (ou seja constituem-se apenas de dois pontos e largura): campos sem nome (p.ex. unsigned int antesDoSemNome:2; :3; unsigned int depoisDoSemNome:4;) são úteis para regiões de bits que não têm utilidade.

Quase tudo sobre campos de bits é dependente de implementação: um campo pode sobrepassar palavras? os campos devem ser alocados da direita para esquerda ou da esquerda para direita? A largura 0 alinha o campo na próxima palavra?

Um exemplo utilizando a arquitetura do Computador Simplificado

Considere o trecho de programa C abaixo:

typedef struct {unsigned int CodOp15:15;} Inst15;
typedef struct {unsigned int op1:4; unsigned int codOp11:11;} Inst11;
typedef struct {unsigned int op1:4; unsigned int op2:4; unsigned int codOp7:7;} Inst7;
typedef struct {unsigned int op1:4; unsigned int op2:4; unsigned int op3:4; unsigned int codOp3:3;} Inst3;

typedef union{int i; Inst15 inst15; Inst11 inst11; Inst7 inst7; Inst3 inst3;} Inst;

Inst memoriaCS[16];

Neste contexto:

memoriaCS é um aranjo de 16 uniões, as uniões são do tipo Inst. O elemento de maior comprimento da união é o i (int i), porque os demais elementos (inst15, inst11, inst7 e inst3) são campos de 15 bits.
memoriaCS[k] corresponde à união de índice k.
memoriaCS[k].inst11 corresponde à um elemento da união onde temos dois campos de bits: um campo dos 4 bits menos significativos e um campo dos 11 bits seguintes aos 4 bits menos significativos.
memoriaCS[5].inst11.op1=15; atribui o valor 15 ao campo de operando da sexta posição de memória (que provavelmente deverá conter uma instrução de um só operando...).

Exercicio: Considere que houve uma atribuição à posição índice k do arranjo de uniões memoriaCS: memoriaCS[k].i=valor; Escreva um trecho de programa C que determina se este valor corresponde a uma das sete instruções do computador simplificado. Por exemplo:

if(memoriaCS[k].inst15.codOp15==0x7030)
printf(“instrução é [Pare]\n”);

...

if(memoriaCS[k].inst11.codOp11==0x700)
printf(“instrução é [Leia Cartão e guarde em E%d]\n”, memoriaCS[k].inst11.op1);

...

if(memoriaCS[k].inst7.codOp7==0x71)
printf(“instrução é [Copie E%d em E%d]\n”, memoriaCS[k].inst7.op2, memoriaCS[k].inst7.op1);

...

if(memoriaCS[k].inst3.codOp3==0)
printf(“instrução é [Some E%d e E%d e guarde em E%d]\n”,
memoriaCS[k].inst3.op3, memoriaCS[k].inst3.op2, memoriaCS[k].inst3.op1);

Números pseudoaleatórios (rand() )e time.h

O programa abaixo simula 20 lançamentos de um dado de 6 faces
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char *argv[])
{ int i;
time_t timer;
timer=time(NULL);
srand(timer);
for(i=0;i<20 ; i++)printf("%d\n",rand()%6+1);
system("PAUSE");
return 0;
}

A função rand() retorna um valor pseudo aleatório a partir de uma certa “semente” geradora. A inicialização da semente é sempre a mesma e para que seja possível resultados diferentes a cada execução temos que modificar a semente. A iniciação da semente é feita utilizando a função srand(). No caso do programa acima a variável timer do tipo time_t (definido em time.h) é ajustada com o valor retornado pela função time() (definida em time.h). O valor retornado por time() varia potencialmente para cada chamada e portanto a cada execução o dado será lançado de forma diferente.