Programmazione orientata agli oggetti in ANSI-C. Un esempio: Liste, code e Stack

Permetteteci di dare un'occhiata a poche classi implementate da zero utilizzando ooc così che possiate apprezzare gli sforzi che abbiamo fatto nei paragrafi precedenti. Inizieremo con una implementazione di List, un buffer ad anello double-ended che ha la funzione di espandersi dinamicamente quando necessario.

Begin e end delimitanto le parti utilizzate della lista, dim è la dimensione massima del buffer e count è il numero di elementi correntemente memorizzati nel buffer. Count rende semplice distinguere una lista piena da una lista vuota. Ecco la descrizione di List.d:

% ListClass: Class List: Object {
const void ** buf; // const void * buf [dim]
unsigned dim; // current buffer dimension
unsigned count; // # elements in buffer
unsigned begin; // index of takeFirst slot, 0..dim
unsigned end; // index of addLast slot, 0..dim
%
Object @ addFirst (_self, const Object @ element);
Object @ addLast (_self, const Object @ element);
unsigned count (const _self);
Object @ lookAt (const _self, unsigned n);
Object @ takeFirst (_self);
Object @ takeLast (_self);
%— // abstract, for Queue/Stack
Object @ add (_self, const Object @ element);
Object @ take (_self);
%}

L'implementazione in List.dc non è molto difficile. Il costruttore provvede ad effettuare un'inizializzazione del buffer:

% List ctor {
struct List * self = super_ctor(List, _self, app);
if (! (self —> dim = va_arg(* app, unsigned)))
self —> dim = MIN;
self —> buf = malloc(self —> dim * sizeof * self —> buf);
assert(self —> buf);
return self;
}

Normalmente l'utente determina la dimensione minima del buffer. Come default definiremo MIN con un valore compatibile per l'uso che ne faremo.

Il distruttore elimina il buffer ma non gli elementi che esistono al suo interno.

% List dtor {
%casts
free(self —> buf), self —> buf = 0;
return super_dtor(List, self);
}

AddFirst() e addLast() aggiungono un elemento rispettivamente all'inizio e alla fine:

% List addFirst {
%casts
if (! self —> count)
return add1(self, element);
extend(self);
if (self —> begin == 0)
self —> begin = self —> dim;
self —> buf[—— self —> begin] = element;
return (void *) element;
}
% List addLast {
%casts
if (! self —> count)
return add1(self, element);
extend(self);
if (self —> end >= self —> dim)
self —> end = 0;
self —> buf[self —> end ++] = element;
return (void *) element;
}

Entrambe le funzioni condividono il codice per aggiungere un singolo elemento

static void * add1 (struct List * self, const void * element)
{
self —> end = self —> count = 1;
return (void *) (self —> buf[self —> begin = 0] = element);
}

Le invarianti sono diverse tuttavia: se count non è zero, ossia c'è almeno un elemento nel buffer, begin punta a un elemento mentre end punta a uno slot libero da riempire. Il buffer è usato ad anello, così avremo che dovremo mappare le variabile attorno all'anello prima di accedere al buffer. Extend() è la parte più difficile: se non c'è più spazio, useremo realloc() per raddoppiare la dimensione del buffer:

static void extend (struct List * self) // one more element
{
if (self —> count >= self —> dim)
{ self —> buf =
realloc(self —> buf, 2 * self —> dim
* sizeof * self —> buf);
assert(self —> buf);
if (self —> begin && self —> begin != self —> dim)
{ memcpy(self —> buf + self —> dim + self —> begin,
self —> buf + self —> begin,
(self —> dim — self —> begin)
* sizeof * self —> buf);
self —> begin += self —> dim;
}
else
self —> begin = 0;
}
++ self —> count;
}

realloc() copia i puntatori memorizzati in buf[] ma il nostro anello non inizia all'inizio del buffer, dobbiamo usare memcpy per spostare l'inizio dell'anello alla fine del nuovo buffer.

Le funzioni rimanenti sono molto più semplici. Count() è una funzione di accesso per il componente count. LookAt() usa un trucco aritmetico per ritornare l'elemento proprio dell'anello:

% List lookAt {
%casts
return (void *) (n >= self —> count ? 0 :
self —> buf[(self —> begin + n) % self —> dim]);
}

takeFirst() e takeLast() sono l'equivalente al contrario delle funzioni add. Ecco un esempio:

% List takeFirst {
%casts
if (! self —> count)
return 0;
—— self —> count;
if (self —> begin >= self —> dim)
self —> begin = 0;
return (void *) self —> buf[self —> begin ++];
}

takeLast è lasciata ai lettori come esercizio – come tutti i selettori e le funzioni di inizializzazione.

List dimostra che ooc ci lascia comunque realizzare l'implementazione e risolvere i problemi di implementazione di una classe come tipo di dato piuttosto che con le idiosincrasie di uno stile di codifica object-oriented. Data una ragionevole classe base, possiamo facilmente derivare classi rivolte a risolvere un problema specifico. List introduce metodi linkati dinamicamente, metodi add() e take() cos' che una sottoclasse può imporre una disciplina di accesso. Gli Stack invece operano avendo un solo ingresso/uscita.

Stack.d
% ListClass Stack: List {
%}
Stack.dc
% Stack add {
return addLast(_self, element);
}
% Stack take {
return takeLast(_self);
}
%init

Queue può essere derivato da Stack e sovrascrive take() oppure può essere una sottoclasse di List e definire entrambi i metodi. List non definisce di per sé i metodi linkati dinamicamente e potrebbe pertanto essere chiamata classe astratta. I nostri selettori sono robusti a sufficienza tanto che qualcuno cercherà di utilizzare add() o take() metodi della List piuttosto che i metodi propri della sottoclasse. Ecco un programma di test che mostra la versatilità della soluzione utilizzata tanto che possiamo aggiungere oggetti a Stack o Queue ma anche stringhe etc etc:

#include "Queue.h"
int main (int argc, char ** argv)
{ void * q;
unsigned n;
initQueue();
q = new(Queue, 1);
while (* ++ argv)
switch (** argv) {
case ’+’:
add(q, *argv + 1);
break;
case ’—’:
puts((char *) take(q));
break;
default:
n = count(q);
while (n —— > 0)
{ const void * p = take(q);
puts(p), add(q, p);
}
}
return 0;
}

Se un argomento a linea di comando inizia con + questo viene aggiunto alla coda; per un – un elemento viene eliminato. Ogni altro argomento illustra il contenuto della coda:

$ queue +axel — +is +here . — . — .
axel
is
here
is
here
here

Nel Sostituire la Queue by a Stack possiamo vedere la differenza nell'ordine di eliminazione:

$ stack +axel — +is +here . — . — .
axel
is
here
here
is
is

poiché uno Stack è la sottoclasse di List ci sono vari metodi per mostrare il contenuto della struttura senza distruggerla: ad esempio:

n = count(q);
while (n —— > 0)
{ const void * p = takeFirst(q);
puts(p), addLast(q, p);
}
Scarica subito una copia gratis

Scrivi un commento

Seguici anche sul tuo Social Network preferito!

Send this to a friend