Newsgroup: it.comp.os.linux.development
Titolo: struttura dati per una lista di intervalli

Saluti, popolo pinguino, e buon Natale a tutti. (-:
Sto incominciando a  scrivere un client news un po'  particolare, e dato
che  il mio  rudimentale stile  di programmazione  mi impone  di partire
dalle funzioni di  più basso livello per poi costruirci  sopra, il primo
problema con cui mi sono scontrato è l'interpretazione del .newsrc.
Tale file, come  ben sapete, è composto di diverse  righe, ognuna con il
nome di un newsgroup e la lista degli intervalli dei messaggi letti.
La mia idea per rappresentare questa  cosa in un modo comprensibile alla
macchina è la seguente:
	struct interval
	{
		int begin;
		int end;
	}; /* un intervallo è una coppia di interi */
	struct mlist_s
	{
		interval msgint;
		mlist_s *next;
	}; /* un elemento della lista contiene un intervallo e il
	      puntatore all'elemento successivo */
	typedef mlist_s *mlist;
Su queste strutture dati implementerei poi le seguenti procedure:
	int insert_interval(mlist*, interval);
	int merge_lists(mlist*, mlist*);
	bool is_in_mlist(mlist, int);
	mlist build_rmlist(char*);
	mlist build_dmlist(mlist, interval);
Tralasciando i particolari, build_rmlist()  interpreterebbe una riga del
.newsrc per un dato gruppo, e costruirebbe la lista degli intervalli dei
messaggi letti. build_dmlist(), in base  alla lista dei messaggi letti e
all'intervallo dei messaggi presenti sul server (ottenuto con il comando
GROUP) costruirebbe una lista dei messaggi da scaricare, e merge_lists()
si occuperebbe di aggiornare il  .newsrc dopo aver scaricato i messaggi.
Le altre funzioni sono di supporto a queste e dovrebbero essere chiare.
Il problema è  che con newsgroup come  quelli che ho sul  server che uso
come "archivio", che viaggiano  sui 40k messaggi, un'implementazione con
delle semplici liste rischierebbe di essere terribilmente inefficiente.
Avevo  pensato a  creare una  bitmap dei  messaggi letti,  e sebbene  lo
spazio in byte  richiesto sia pari al numero di  messaggi diviso 8 (ogni
messaggio verrebbe rappresentato con un bit), il numero di newsgroup non
potrebbe più essere arbitrario, ma sarebbe limitato dalla RAM. E siccome
il server della mia BBS ne ha poca ed è piena per via dei servizi che ci
girano sopra, non si può fare.
Ho pensato a  delle tabelle di hashing (spero si  chiamino così: intendo
delle liste multiple suddivise a blocchi di 4096 messaggi, per esempio),
e sebbene  quest'ultimo metodo  mi sembri  piuttosto efficiente  a prima
vista, non di meno il codice si  complica di brutto... e già scrivere le
procedure di merging non sarà semplice.
La morale  della favola  è la seguente:  avete qualche  suggerimento per
delle strutture dati efficienti e semplici da gestire?
Mi scuso per il post lungo, lo so che mi sono tirato la zappa sui piedi,
ma ho veramente  fatto il possibile per descrivere il  problema nel modo
più semplice possibile.
Di nuovo buone feste a tutti. ;-)
-- 
  _      ___ ____
 | | /| / (_)_  /
 | |/ |/ / / / /_	ANTI-SPAM WARNING:
 |__/|__/_/ /___/	the e-mail address is fake.
 
Se il cane e` il miglior amico dell'uomo, il pinguino e` di certo il miglior
amico del computer. (Wiz)

il 26 Dec 1999 14:34:43 GMT, 
luc...@phoenix.radiance.it
 (Wiz) scrivette:
--->La morale  della favola  è la seguente:  avete qualche  suggerimento per
--->delle strutture dati efficienti e semplici da gestire?
--->
Potresti usare la map di STL, con stringhe per l'oggetto del msg, una cosa del
tipo
typedef msg_map std::map<std::string, interval, less<std::string> >
oppure un albero n-ario costruito alla stessa maniera, ordinato sulle stringhe.
in quest'ultimo modo l'inserzione ha o(log (N)), la giunzione puoi farla con un
merge sort della visita in preordine ( o(N) )
____ __         __,_      __  _____  
\  _\_ \  ___ _/ / /\  /\/  \/ / _/ It is better to reign in Hell 
 \  _ \ \/ _ '/ , |\ VV / / / / _/ Than serve in Heaven.- MILTON 
  \_,_/\_\_,_/_/|_| \__/\__/_/_/  
      -- the one and only --     e-mail : 
blak...@tiscalinet.it
 
                                ICQ    : 59394345  
The UNIX Guru's View of Sex:   
$unzip;strip;touch;finger;mount;fsck;more;yes;umount;sleep

