Autoreleasing di oggetti nei sistemi di conteggio di riferimento

Le matrici non sono l'unica opzione per l'implementazione di pool di autorelease. Qualunque cosa sia adatta per un'implementazione set dovrebbe essere adatta per un pool di autorelease, incluso (single o double-linked) ) liste, alberi e tabelle hash. Quando scegli la struttura dei dati da utilizzare, considera i tempi delle varie operazioni e abbinali all'utilizzo.

Per un pool di autorelease, l'inserimento è un'operazione comunemente utilizzata, come lo è la rimozione di elementi aggiunti di recente (che è lo scenario in questione: conservare oggetti autoreleased). Il drenaggio del pool sarà almeno O (n) per l'iterazione, che dovrebbe essere supportato da qualsiasi tipo di dati (sebbene possibilmente con un costo di spazio O (n) complessivo per un puntatore aggiuntivo per record sull'elemento successivo nella sequenza).

• Elenchi collegati supportano l'inserimento & rimozione della testa in tempo O (1), sebbene la rimozione di oggetti arbitrari da un pool avvenga anche relativamente frequentemente, ed è O (n) per la lista collegata.
• Gli alberi possono supportare l'inserimento e l'amp; rimozione in tempo O (log n), ma l'iterazione è O (n log n) senza puntatori "next item".
• Le operazioni sulle tabelle hash variano da O (1) a O (n), a seconda della funzione di hash e dei dati specifici memorizzati in esso.
• Per gli array, il caso migliore per l'inserimento è O (1); colpisci solo il caso peggiore di O (n + f (m)) quando l'array si rovescia, dove n è la vecchia dimensione dell'array, m la nuova dimensione dell'array e f(m) la complessità di allocazione. Puoi ridurre il tempo complessivo per l'inserimento utilizzando un array dinamico (raddoppiando la dimensione dell'array in overflow) per un O (1) ) costo ammortizzato (assumendo f (m) ≤ m). Tuttavia, esiste un compromesso spazio-tempo: una parte dell'array viene allocata ma non utilizzata. La rimozione di elementi recenti è O (1), sebbene la rimozione sia O (n) in generale.

Puoi potenzialmente ottenere ulteriori guadagni in termini di prestazioni (a costo di spazio) definendo una classe di livello superiore da cui discendono tutte le altre classi (il tuo analogo a NSObject ) e includi un puntatore al record dell'oggetto nella autorelease piscina. Usando questo puntatore, la ricerca impiega O (1) tempo, che può ridurre la complessità della rimozione se la ricerca è l'operazione dominante durante la rimozione (come per gli elenchi collegati).

Se dichiari il puntatore del record dell'oggetto come lo stesso tipo del tipo di record del pool di autorelease, creerai un accoppiamento stretto tra gli oggetti e la gestione della memoria, il che è indesiderabile. Invece, puoi applicare il schema del ponte (aka il Idioma di Handle-Body in cerchi C ++): ha una classe di strategia di gestione della memoria astratta che collega una famiglia di tipi di gestione della memoria astratta (incluso un tipo per i record di gestione della memoria e per la memoria pool), con il puntatore del record dell'oggetto del tipo di record astratto. La strategia includerebbe una serie di pool di AR. Potresti quindi definire il pool di autorelease concreto e i tipi di record per qualsiasi strategia tu voglia. Avresti un puntatore statico a una strategia di gestione della memoria, che le funzioni di base della gestione della memoria ( retain() , release() , autorelease() e pool() (per inviare un nuovo pool AR) farebbero riferimento.

Il modo usuale è di conservare il codice chiamante, per renderlo coerente devi farlo per tutti gli oggetti che restituisci.

//popFromQueue will remove from the queue and pass the buck to the calling code
Foo* pop(FooQueue* q){
    Node* foo = q.head;
    q->head = foo->next;
    foo->next=null;//make sure new head isn't released; could have also retain the new head instead
    Foo retValue = retain(foo->value);
    release(foo);//will release next and value
    return retValue; //passes our ownership to calling code
}
// peekQueue will return the head value and give ownership to calling code
Foo* peek(FooQueue q){
    return retain(q->head->value);//add a retain and pass to calling code
}

Ad esempio quando crei un oggetto: Foo* foo = createFoo(); è già stato retain ed una volta che il codice chiamante è diventato proprietario.

Questo ha il rovescio della medaglia che tutti i valori restituiti devono essere rilasciati e devi assicurarti che siano stati retian ed prima di restituirli.