Re: [Devel] Use of qsort

[David Turner]

Hi Antoine,

> >
> > The easy thing is to provide our own implementation of quick sort
> > (or heap sort, shell sort, whatever seems simpler and not too quadratic),
> > since this completely avoids the problem. Actually, there already is
> > so rather "reusable" quick sort algorithm in the smooth rasterizer
> > (using a custom algorithm is critical for performance here)
> 
> OK, but I feel this is not as easy as it should...
> Remember, the problem occurs in Freetype 1, in an extension...
> 
> Now, if you feel this is easy, and below one hour of work, please hack it!
>
OK, I've just commited a custom shell-sort in "ftxkern.c" in the FreeType 1
repository. Please have a look. I've only compiled it, not tested it !!

(I've used a shell sort because it's simpler to write than a quick sort,
and results in smaller code, performance isn't exaclt critical in this code
as Just pointed out)
 
> > I just hope that the special keyword doesn't need to be within the
> > return type and the function name in the definition.
> 
> Guess what...
> Yes, it needs to be inside, as always (I would struggle the guy at
> Lattice, Microsoft or whatever that insisted for these additional
> keywords far, near and cdecl to go between the type and the name, and
> nowhere else. Even if I know why (it has to do with far/near being
> able to decorate either the function, or the returned type if it is
> a pointer)).
>

Aarg, OK, I've just commited changes to the FT2 sources in order 
to change the definition of FT_CALLBACK_DEF. Seems to work well,
though it's been a bit tough to get correct (i.e. I originally
forgot to modify "builds/unix/ftconfig.in")
 
> > Otherwise, we'll need to define FT_CALLBACK_DEF(), and replace all
> > uses in the source code..
> 
> Yes, the ugly way.
> Since I have to hack all this part to implement FT_EXPORT_DEF() in
> Freetype 1.x anyway (it is still a non-function macro, and this does
> not work for DLLs, as you know), this is something that can be done.
> Food for work.
>
Done :-) But you'll need to define FT_CALLBACK_DEF yourself for
16-bit systems..
 
> > > Also, a thing worth checking is whether any other part of our libraries, 
> > > being
> > > 1.x or 2.x, use any callback back to a standard library (qsort is just an 
> > > example,
> > > although it is probably the one which is the most probable).
> > >
> > I believe that I didn't use any standard library function when writing
> > the library. The "qsort" was introduced later, and I should have checked
> > the issue at that time !!
> 
Humm, it seems I was on crack lately. I've just checked the source code,
and FT2 uses qsort in at least three places now :-)

Anyway, it seems the problem is solved now in both library versions..

Regards,

- David