[Risolto][C] Numeri consecutivi

[vbextreme]

il problema è questo, devo creare degli oggetti che hanno un id che gli assegno io da 0 a poco più di 1000.
Ogni volta che creo un oggetto il suo id sara l'ultimo id precedente+1 e fin qui tutto OK.
Ora se rimuovo un oggetto come posso fare a trovare l'ID libero e utilizzare quello?
Adesso uso una sorta di algoritmo simile a questo ma è a dir poco pietoso!

Codice: Seleziona tutto

MYOBJ* o;
int id = 0;
RETRY:
for( o = first; o; o=o->next)
    if ( o->id == id ){++id; goto RETRY;}
return id;

[M_A_W_ 1968]

Se hai n oggetti e rimuovi l'oggetto i-esimo, con i ovviamente minore di n, prendi anche l'oggetto n-esimo e gli riassegni l'id i-esimo.
Così avrai n-1 oggetti, sempre consecutivi.

Se l'ordine ha una qualche importanza, usa un array di appoggio contenente il vettore di permutazione, ossia l'ordine effettivo in cui considerare gli elementi per id.

[vbextreme]

L'ordine non ha nessuna importanza ma l'ID no può cambiare per nessun motivo.
es:
0 1 2 3 n
rimuovo 2
0 1 3 n
aggiungo un nuovo oggetto che dovrà avere id 2 e non 4.
Io pensavo ad un vettore che contenesse gli id rimossi ordinati in maniera decrescente, una specie di stack, una volta che ho bisogno di un id se lo stack è vuoto allora n+1 altrimenti pop.
Il problema è che in realtà io non ho la più pallida idea del limite massimo di id allocati e rimossi, uno potrebbe inserire 10000 e rimuoverne 5000 di che dimensione creo lo stack?
non mi va ne di sprecare memoria ne di usare liste e nemmeno di reallocare la memoria.
Potrei ad esempio usare un piccolo stack sui 100 elementi se è pieno non inserisco più niente, se faccio un pop dal pieno controllo con l'algoritmo postato sopra se c'è un ulteriore indice da aggiungere e lo aggiungo.
Penso cosi perché è raro che si elimanono più di 100 oggetti di colpo senza crearne altri.
Cosa ne dici?

[M_A_W_ 1968]

Usa un bitarray da 1024 bit per mappare tutti gli id occupati (=0) e liberi. Con i builtins del compilatore, che poi corrispondono a singole istruzioni Intel e AMD, trovi immediatamente il bit più significativo a sinistra. Ne abbiamo anche già discusso in passato, da qualche parte, proprio con te (e il buon vecchio Oregon): c'erano di mezzo le solite istruzioni BSR e LZCNT dei processori mainstream.

In questo modo perde totalmente importanza il numero di oggetti che vengono cancellati complessivamente, e conseguentemente non si pone il problema di dimensionare a priori la coda FIFO delle cancellazioni - che comunque andrebbe tenuta ordinata, e quindi per i soliti motivi di complessità algoritmica dovrebbe infine essere uno heap o albero bilanciato col valore minimo disponibile nella foglia più a sinistra.

[vbextreme]

si mi ricordo, solo che sono su arm! e proprio non riesco a digerire il suo set di istruzioni assembly, in più dovrà essere portabile e dunque mi troverei a scrivere un bel po di codice solo per scrollare il bitarray(e io non mi chiamo Master Assembly Wizard), cosa comunque possibile anche usando il c puro anche se con qualche calo prestazionale.
Ma usando un bitarray di 1024 bit e arrivando a id 1025 come mi comporto?
l'idea mi piace parecchio, la modificherei cosi:
offset primo id libero
bitarray 2048 bit

usando anche un offset di base il range si ingrandirebbe, causando però una qualche sorta di probabilità di perdere qualche id in qua e la, potrei sempre tenere quell'assurdo codice e trasformarlo in una sottospecie di garbage collector in modo che in determinate circostanze(tipo quando il bitarray=0 o quando cambia l'offset) lo sistemi.
in questo modo è come se scrollassi il bitarray in una regione più grossa, cosi potrebbe andare anche perché si riduce drasticamente l'oneroso richiamo al "nuovo id garbage collector".
altresì potrei creare solo un bitarray da 10240bit ma cosi forse diventa lo stesso abnorme.
per contare i bit potrei usare una semplicissima

Codice: Seleziona tutto

int i;
unsigned int k;
for ( i = 0, k = 0; i < bytearray, ++i)
{
    int b;
    for ( b = 0; ( b < 8 ); ++b,++k)
         if ( !(bitarray[i] >> b)  & 0x1) goto FINDIT;
}
FINDIT:
return k;

o qualcosa di simile magari scritto meglio al PC più che sullo smartphone.

[M_A_W_ 1968]

Il mero bitarray è ampiamente sufficiente, l'indirizzamento è un gioco da bambini. Se sei su una piattaforma a 32 bit, prendi i 5 bit bassi dell'indice e li usi per creare una maschera come bit index all'interno del byte, il quale è semplicemente indirizzato dai rimanenti bit più alti dell'indice (ovviamente con right shift di 5 posizioni). Funziona in C su qualsiasi piattaforma, cambiando opportunamente i numeretti se necessario...

Non ti serve l'offset iniziale, e in caso assoluta necessità puoi espandere il bit array riallocandolo con dimensione doppia.

[vbextreme]

Codice: Seleziona tutto

unsigned bitarray[32];
...
int setbitarray(unsigned id)
{
    if ( id > 0x1FF) return -1;
    bitarray[id & 0x1F] |=  (0x1 << (id >> 5));
}

int getbitarray(int id)
{
    if ( id > 0x1FF) return -1;
    return bitarray[id & 0x1F] & (0x1 << (id >> 5));
}

ho fatto un casino?
cosi però arrivo a massimo 512 come id giusto?

[vbextreme]

no,

Codice: Seleziona tutto

if ( id > 0x3FF) return -1;

posso usare 10bit e volendo posso modificare cosi:

Codice: Seleziona tutto

unsigned bitarray[32];
...
int setbitarray(unsigned id)
{
    bitarray[id & 0x1F] |=  (0x1 << ( (id >> 5) & 0x1F));
}
....

quindi 10 bit sono 1024 esatto! ora torna quello che dicevi

grazie!

[vbextreme]

per trovare l'ID libero:

Codice: Seleziona tutto

for (i = 0; i < 32; ++i)
    if (bitarray[i]) return (firstbit(bitarray[i]) << 5) | i;
return -1;

OK metto risolto

[M_A_W_ 1968]

Il codice di accesso al bitarray è molto più semplice.

Codice: Seleziona tutto

#define ASIZE 32
...
size_t bitarray[ASIZE];
...
void setbit(size_t pos)
{
    bitarray[pos >> 5] |= 1 << (pos & 0x1F);
}
void clrbit(size_t pos)
{
    bitarray[pos >> 5] &= ~(1 << (pos & 0x1F));
}

Ovviamente si può usare un bella maschera AND 0x1F (pura coincidenza, 1024 bit sono 32 entries da 32 bit cadauna! ) anche sull'indice, per evitare ogni sorta di potenziale buffer overflow, senza ricorrere a salti impliciti e controlli di range.

[vbextreme]

hai usato la parte alta per indirizzare il vettore e la bassa come maschera, praticamente il contrario di quello che ho fatto io, non è che poi sia cambiato di molto, io scorrevo di 5 nell'id della maschera e tu scorri di 5 nell'indice!ahahahah, si è più leggibile però!
io però nell'indice ci metterei un and come hai detto(e come avevo fatto) proprio per evitare buffer overflow.

bello, lo metto insieme alla libreria easymath cosi non me lo dimentico più.
Grazie ancora.

[M_A_W_ 1968]

hai usato la parte alta per indirizzare il vettore e la bassa come maschera, praticamente il contrario di quello che ho fatto io, non è che poi sia cambiato di molto, io scorrevo di 5 nell'id della maschera e tu scorri di 5 nell'indice!ahahahah, si è più leggibile però!

Non è solo più leggibile: così facendo si hanno in modo immediato i 5 bit che occorrono per indirizzare 32 bit all'interno di un uint32_t, e rimangono ben 27 bit per coprire l'intero spazio di indirizzamento dell'array di booleani, ammesso di usare (come è d'obbligo) un bel size_t per gli indici.

[vbextreme]

OK, l'ho compreso meglio dopo averlo implementato realmente.
Alla fine non ho neppure messo il controllo con l'and perché mi è bastato un if durante l'input utente per assicurare il corretto valore.
Ho anche lasciato il valore a 1024, ora che il mio driver è passato alla 0.3 tale numero è forse anche eccessivo.
L'ho lasciato ancora un po grezzo come tutto il resto del codice, ma essendo il mio primo driver,oops,modulo, sto cercando di farlo funzionare "bene".
Offtopic, ho avuto solo 2 blocchi di sistema (con annesso obbligo di spegnimento forzato) il tutto grazie ai tuoi insegnamenti di programmazione difensiva con l'aggiunta di una " extra" dose di log ho risolto in 4 e 4 = 8.

Grazie ancora.
[dimenticato]
ma in questo caso non è meglio un unsigned int?
il size_t è 32 per il 32 e 64 per 64 e via dicendo, parlando da "professionisti" non sarebbe meglio una selezione di architettura e quant'altro?
OK che lo sto imparando ad usare per le dimensioni in generale, ma per certi casi specifici forse è meglio non generalizzare e per di piu sarebbe meglio che imparassi sto maledetto assembly RISC!
[/dimenticato]

[M_A_W_ 1968]

L'array di unsigned, per questo tipo di applicazione (bit array), è praticamente obbligatorio. Sull'ampiezza, in generale, vale il principio di usare quella massima purché contenibile in un singolo registro, in modo da ottenere il massimo bitpacking senza penalità prestazionali. Dunque se la CPU ARM in questione ha registri a 32 bit, come presumo, direi di orientarsi senz'altro su un uint32_t, per usare la terminologia ufficializzata dal C'99 (di fatto quasi tutti i cross compiler usavano già nomi di tipo analoghi fin da un decennio prima...).

In ogni caso è sempre bene, come si ripete in continuazione, dare una bella sbirciatina alle defines per il compilatore in uso e al codice Assembly prodotto (quindi sì, in definitiva è bene che tu impari anche quella manciata di istruzioni RISC dei core ARM).

[vbextreme]

OK per l'unsigned ma hai detto di usare size_t!
Forse la cigliegina sarebbe usare un "bel paio" di define a secondo dell'esigenza, perchè mentre l'indice rimane variabile la maschera invece è legata all'architettura e va ottimizzata di volta in volta.
Pertanto dato che so dei miei 32 bit ho usato unsigned int che comunque mi rimane portabile anche su quasi tutte le rimanenti architetture a 64 bit.

I RISC sono un pelo "bastardi", già a passare all'assembly di at&t ho sudato ma su questi arm!
Non ho l'istruzione(scolastica) adeguata per sapere le reali differenze tra i chip in commercio, quali comandi sono portabili e quali no.Per darti una idea io ho letto 2 libri cartacei sui moduli di linux e 3 on-line e alla fine di tutto ho scoperto che le funzioni utilizzate dal mio driver erano per il kernel < 2.6 e non per quello che utilizzavo.
Trovare la giusta soluzione mi ha richiesto un enorme lavoro, più che imparare il secondo libro!


Mi spieghi una cosa?
volevo inizializzare l'array tutto settato e ho scritto {0xFFFFFFFFFFFFFFFF} ma il compilatore si è arrabbiato, e allora ho scritto più semplicemente {~0} perché mi dava errore?

[M_A_W_ 1968]

Mi spieghi una cosa?
volevo inizializzare l'array tutto settato e ho scritto {0xFFFFFFFFFFFFFFFF} ma il compilatore si è arrabbiato, e allora ho scritto più semplicemente {~0} perché mi dava errore?

Molto semplicemente, la definizione di size_t realizza quasi ovunque quanto richiesto: è un unsigned di grande estensione, possibilmente la massima disponibile, e può ancora essere contenuto nei registri della CPU.

Riguardo alle costanti, ogni compilatore aggiunge qualche sua idiosincrasia a quanto sancito dallo standard. In genere occorre e basta appiccicare qualche suffisso ai numeretti, come L e UL o loro estensioni LL e ULL previste dal C'99.

[vbextreme]

Riguardo alle costanti, ogni compilatore aggiunge qualche sua idiosincrasia a quanto sancito dallo standard. In genere occorre e basta appiccicare qualche suffisso ai numeretti, come L e UL o loro estensioni LL e ULL previste dal C'99.

Ma è ammissibile la forma che ho usato? Non l'ho mai letta da nessuna parte o non ci ho mai fatto caso al suo utilizzo.
Non mi piace quel 0xFFF.... è fin troppo facile sbagliarsi(infatti ne avevo messi il doppio ) e mettere un F in piu o un F in meno porterebbe a errori a dir poco introvabili.
dopotutto se inverto uno 0 ho per forza tutti uno, come si comporta il compilatore con quella "bizzarra" assegnazione? non è che mi fa degli scherzetti?

[M_A_W_ 1968]

La forma esplicita è sicuramente ammissibile e maggiormente leggibile, anche se in genere è maggiormente opportuno usare le costanti di limits.h.
Per il resto, dipende dal compilatore. Per questo è doppiamente opportuno controllare l'assembly generato, e usare i qualificatori di estensione delle costanti. Molti compilatori emettono warning in caso di costanti fuori dal range, comunque.