Strutture di dati

Liste

glib fornisce generiche liste single-linked e double-linked, GSList e GList, rispettivamente. Sono implementate come liste di gpointer; potete usarle per memorizzare interi con le macro GINT_TO_POINTER e GPOINTER_TO_INT. GSList e GList hanno API identiche, con l'eccezione di g_list_previous() a cui non corrisponde una g_slist_previous(). In questa sezione discuteremo il comportamento di GSList ma le stesse regole possono essere applicate alle liste double-linked.

Nella implementazione di glib, la lista vuota è rappresentata semplicemente da un puntatore NULL. E sempre possibile passare NULL alle funzioni che gestiscono le liste poichè questo valore rappresenta una lista valida di lunghezza 0. Il codice per creare una lista e aggiungere un elemento potrebbe essere il seguente:

GSList* list = NULL;
gchar* element = g_strdup("una stringa");
list = g_slist_append(list, element);

glib è evidentemente influenzata dal linguaggio Lisp; La lista vuota è un valore "nil" speciale per questa ragione. g_slist_prepend() assomiglia molto a cons: è una operazione a tempo costante che aggiunge una nuova cella all'inizio della lista.

Tenete presente che dovete rimpiazzare la lista passata come parametro alle funzioni che la modificano con il valore restituito da quest'ultime, poiché è possibile che la testa della lista cambi. glib si occuperà di allocare/deallocare i collegamenti necessari.

Per esempio, il codice seguente rimuove l'elemento inserito nel listato precedente, svuotando cosi la lista:

list = g_slist_remove(list, element);

list adesso è NULL. Chiaramente, dovete ancora deallocare element. Per svuotare l'intera lista usate g_slist_free(), la quale rimuove tutti i collegamenti in un colpo solo. g_slist_free() non restituisce alcun valore, poichè dovrebbe resistuire sempre NULL e potete semplicemente assegnare questo valore alla vostra lista, se volete. Ovviamente, g_slist_free() libera soltanto la memoria occupata dalle celle della lista, non ha modo di sapere cosa fare con il contenuto.

Per accedere a un elemento delle lista utilizzate la struttura GSList direttamente:

gchar* my_data = list->data;

Per muoversi all'interno della lista potete usare un codice simile al seguente:

GSList* tmp = list;
while (tmp != NULL)
  {
    printf("List data: %p\n", tmp->data);
    tmp = g_slist_next(tmp);
  }

Figura 13 mostra le funzioni base per alterare i contenuti di una GSList. Per tutte queste funzioni, dovete assegnare il valore restituito al puntatore alla vostra lista. È utile notare che glib non conserva un puntatore alla coda della lista, quindi inserire un elemento in testa è un operazione a tempo costante, mentre in coda le operazioni di insert (append) e remove richiedono un tempo proporzionale alla lunghezza della lista.

In particolare, questo significa che costruire una lista usando g_slist_append() è un idea terribile; Utilizzate g_slist_prepend() e poi chiamate g_slist_reverse() se avete bisogno di avere la lista in un ordine particolare. Se sapete anticipatamente che dovete inserire frequentemente degli elementi in coda, potete tenere un puntatore all'ultimo elemento. Il codice seguente può essere utilizzato per implementare degli efficienti inserimenti in coda:

void
efficient_append(GSList** list, GSList** list_end, gpointer data)
{
  g_return_if_fail(list != NULL);
  g_return_if_fail(list_end != NULL);

  if (*list == NULL)
    {
      g_assert(*list_end == NULL);
      
      *list = g_slist_append(*list, data);
      *list_end = *list;     
    }
  else 
    {
      *list_end = g_slist_append(*list_end, data)->next;
    }
} 

Per utilizzare questa funzione dovreste salvare la lista e la sua coda da qualche parte e passare i loro indirizzi a efficient_append():

  GSList* list = NULL;
  GSList* list_end = NULL;

  efficient_append(&list, &list_end, g_strdup("Foo"));
  efficient_append(&list, &list_end, g_strdup("Bar"));
  efficient_append(&list, &list_end, g_strdup("Baz"));

Chiaramente dovete fare attenzione a non utilizzare alcuna funzione che modifichi la coda della lista senza aggiornare list_end.

#include <glib.h>

Per accedere agli elementi della lista sono fornite le funzioni elencate in Figura 14 . Nessuna di esse cambia la struttura della lista. g_slist_foreach() applica una funzione GFunc ad ogni elemento della lista. La funzione GFunc è definita come segue:

typedef void (*GFunc)(gpointer data, gpointer user_data);

Utilizzandola in g_slist_foreach(), la vostra GFunc verrebbe chiamata per ogni list->data della list, passando il parametro user_data che avete fornito a g_slist_foreach(). g_slist_foreach() è comparabile alla funzione map di Scheme.

Per esempio, avendo una lista di stringhe, per creare una lista parallela con una serie di trasformazioni applicate a ogni stringa. L'esempio seguente utilizza la funzione efficient_append() definita precedentemente:

typedef struct _AppendContext AppendContext;
struct _AppendContext {
  GSList* list;
  GSList* list_end;
  const gchar* append;
};

static void 
append_foreach(gpointer data, gpointer user_data)
{
  AppendContext* ac = (AppendContext*) user_data;
  gchar* oldstring = (gchar*) data;

  efficient_append(&ac->list, &ac->list_end, 
                   g_strconcat(oldstring, ac->append, NULL));
}

GSList*
copy_with_append(GSList* list_of_strings, const gchar* append)
{
  AppendContext ac;

  ac.list = NULL;
  ac.list_end = NULL;
  ac.append = append;

  g_slist_foreach(list_of_strings, append_foreach, &ac);

  return ac.list;
}

glib e GTK+ usano l'idioma del puntatore a funzione e dato utente molto frequentemente. Se avete esperienza di programmazione funzionale, questo assomiglia molto all'utilizzo di espressioni lambda per creare una chiusura. (Una chiusura combina una funzione con un ambiente - un set di associazioni nome-valore. In questo caso, l'ambiente è il dato utente (user_data) passato a append_foreach() e la chiusura è la combinazione del puntatore a funzione e del dato utente.)

#include <glib.h>

Troverete alcune utili funzioni per maneggiare le liste, elencate in Figura 15. Ad eccezione di g_slist_copy(), tutte queste funzioni modificano la lista passata come parametro. Questo vuol dire che dovete rimpiazzare il puntatore alla testa con il valore di ritorno come facevate nel caso di aggiunte e rimozioni di elementi. g_slist_copy() restituisce una lista allocata, quindi potete utilizzare entrambe le liste, che devono essere deallocate.

#include <glib.h>

Infine, esistono alcune funzioni per l'ordinamento delle liste, elencate in Figura 16. Per utilizzarle dovete scrivere una GCompareFunc, che assomiglia molto alla funzione di confronto che viene utilizzata nella funzione standard C qsort(). Utilizzando i tipi di glib, questo diventa:

typedef gint (*GCompareFunc) (gconstpointer a, gconstpointer b);

Se a < b, la funzione dovrebbe tornare un valore negativo; se a > b un valore positivo; se a == b dovrebbe restituire 0.

Una volta che la funzione di confronto è stata scritta, potete inserire elementi in una lista ordinata, oppure ordinare una lista non ordinata. Viene utilizzato l'ordine ascendente. Potete anche riciclare la vostra GCompareFunc per cercare elementi della lista utilizzando g_slist_find_custom(). (Un attimo di attenzione: GCompareFunc è utilizzata incoerentemente nella implementazione di glib: a volte glib richiede un predicato di equità invece di una normale funzione in stile di qsort(). Comunque, l'utilizzo è coerente all'interno della API.)

Fate attenzione con le liste ordinate: un utilizzo sconsiderato può diventare molto inefficiente. Per esempio, g_slist_insert_sorted() è un operazione O(n), ma se usata in un ciclo per inserire elementi multipli, il ciclo assume una complessità esponenziale. È molto meglio inserire in testa alla lista e poi chiamare g_slist_sort().

#include <glib.h>

Alberi

Ci sono due diversi tipi di alberi in glib; GTree è un albero binario bilanciato, utile per memorizzare coppie chiave-valore utilizzando la chiave come elemento di riferimento; GNode memorizza dati arbitrari strutturati ad albero, come alberi sintattici oppure la tassonomia.

#include <glib.h>

#include <glib.h>

#include <glib.h>

typedef gint (*GTraverseFunc)(gpointer key, gpointer value, gpointer data);

#include <glib.h>

typedef struct _GNode GNode;

struct _GNode
{
  gpointer data;
  GNode   *next;
  GNode   *prev;
  GNode   *parent;
  GNode   *children;
};

#include <glib.h>

#include <glib.h>

#include <glib.h>

#include <glib.h>

#include <glib.h>

#include <glib.h>

#include <glib.h>

typedef gboolean (*GNodeTraverseFunc) (GNode* node, gpointer data);
typedef void (*GNodeForeachFunc) (GNode* node, gpointer data);

#include <glib.h>

Tabelle hash

GHashTable è una semplice implementazione di una tabella hash, che fonisce un array associativo con ricerche a tempo costante. Per usare la tabella hash dovete fornire una GHashFunc, che dovrebbe restituire un intero positivo quando gli viene passata una chiave hash.

typedef guint (*GHashFunc) (gconstpointer key);

Ogni guint restituito (modulo la dimensione della tabella) corrisponde a uno "slot" o "bucket" nella tabella; GHashTable gestisce le collisioni memorizzando una lista linkata di coppie chiave-valore in ogni slot. Quindi il valore guint restituito dalla vostra GHashFunc deve essere ben distribuito su tutto il set dei possibili valori guint, oppure la tabella degenererà presto in una lista collegata. La vostra GHashFunc deve essere veloce, poiché viene usata per ogni ricerca (lookup).

In aggiunta a GHashFunc, è richiesta una GCompareFunc per controllare l'uguaglianza di due chiavi. GHashTable non usa la GCompareFunc nel modo in cui GSList e GTree fanno, anche se il nome della funzione è lo stesso. In questo caso la GCompareFunc assume il ruolo di un operatore di confronto che restituisce TRUE se gli argomenti sono uguali. Non dovrebbe essere nello stile di qsort(). La funzione per il confronto delle chiavi viene utilizzata per trovare la corretta coppia chiave-valore nel caso in cui le collisioni portino ad avere più di una coppia in uno stesso "slot".

Per creare e distruggere una GHashTable, utilizzate il costruttore e il distruttore mostrati in Figura 29. Ricordate che glib non ha modo di sapere come distruggere i dati contentuti nella vostra tabella; essa distrugge soltanto la tabella stessa.

#include <glib.h>

Esistono delle funzioni hash e di confronto pronte per l'uso e adattate per i tipi di chiave più comuni: interi, puntatori interi, puntatori e stringhe. Sono elencate in Figura 30. Le funzioni per gli interi accettano un puntatore ad un gint, anziché gint stesso. Passando NULL come funzione hash alla g_hash_table_new(), viene utilizzata la funzione predefinita g_direct_hash(). Passando NULL come funzione di confronto viene utilizzato un confronto di puntatori (equivalente a g_direct_equal(), ma senza la chiamata di funzione).

#include <glib.h>

La manipolazione della tabella hash è semplice. Le funzioni sono riassunte in Figura 31. L'inserimento non copia le chiavi né i valori, questi sono inseriti nella tabella esattamente come vengono passati alla funzione, sovrascrivendo ogni coppia chiave-valore preesistente nelo slot definito dalla stessa chiave (ricordate, "stessa chiave" è definito dalle vostre funzioni hash e di confronto). Se questo è un problema, dovete fare una ricerca e rimuovere prima di inserire. Dovete stare attenti specialmente se usate l'allocazione dinamica per la chiavi o per i valori.

La semplice g_hash_table_lookup() restituisce il valore che trova associato con key, oppure NULL se non esiste un tale valore. Questo può non andare a buon fine. Per esempio, NULL potrebbe essere un valore valido. Se utilizzate stringhe come chiavi, specialmente se sono stringhe allocate dinamicamente, sapere che una chiave è nella tabella potrebbe non essere sufficiente; potreste aver bisogno di ottenere l'esatto gchar* che la tabella usa per rappresentare la chiave "foo". Una seconda funzione di ricerca è stata appositamente creata per casi come questi. g_hash_table_lookup_extended() restituisce TRUE se la ricerca ha esito positivo; se restituisce TRUE, memorizza la chiave e il valore trovato nella locazione che gli viene passata.

#include <glib.h>

GHashTable mantiene un array interno la cui dimensione è un numero primo. Tiene anche il conto delle coppie chiave-valore memorizzate nella tabella. Se il numero medio delle coppie disponibili scende sotto 0.3, l'array viene reso più piccolo; se sale sopra 3, l'array viene ingrandito per ridurre le collisioni. Il ridimensionamento viene fatto automaticamente ogni volta che inserite una coppia nella tabella. Questo ci assicura un uso ottimale della memoria. Sfortunatamente, è inefficiente ricostruire la tabella molte volte se fate un gran numero di inserimenti o rimozioni. Per risolvere il problema, la tabella può essere congelata, sopprimendo temporaneamente ogni azione di ridimensionamento. Quando avete finito di aggiungere e rimuovere elementi scongelate la tabella; questo porterà a un singolo calcolo per la dimensione ottimale. (Fate attenzione però, una tabella congelata può finire con moltissime collisioni se aggiungete una grande quantità di elementi.) Le funzioni sono descritte in Figura 32.

#include <glib.h>