🚀 go-pugleaf

On Tue, 13 Jul 1999 21:05:00 +0100 (BST), Terrance Richard Boyes 
   <tez@pierrot.co.uk> wrote:

>I'm looking for an efficient way to check for duplicate Message-IDs
>in a large NewsHistory file against the output of NEWNEWS (or XOVER
>after extracting the Message-ID).

>As in those languages it's much quicker than scanning through
>an array.
>
>Any thoughts on the best way to do it in C ?

The way I'd do it would be to read in the file, in file order, then use
qsort (ANSI C routine) to sort it (or rather sort an array of pointers
to the strings) and then use bsearch to find them.  You don't need to
add the new IDs to the list as they come in, as they should be unique
anyway among themselves.

>NB a pointer to some source what I want will do just as well as
>a detailed answer ;)

If you want a general facility for adding elements to a database and
searching quickly, have a look for packages called btree and ctree.
These maintain a database in "balanced tree" style, so that the lookup
time is proportional to log(n) (n is number of elements in the
database).  There used to be at least one implementation which was
public domain generic C source.

Alternatively (my favourite solution), use C++ where the map class is
explicitly designed for that sort of thing.  However, it's a relatively
recent addition to C++ (in the last couple of years) and older C++
compilers didn't always have it implemented.

HTH

Chris C