qsorting & managing struct arrays, pointer arrays

[Frank Burleigh]

Suppose you have:

   typedef struct struct_name {...} struct_name;
   struct_name list[MAXSIZE], *s_start, *s_one, *s_two;

   main()
   {
      /*load the array of struct here*/
      s_start = list;
      /*other business*/
      qsort( s_start, s_members, sizeof( struct_name ), ncmp );
   }

   int ncmp( struct_name * s_one, struct_name * s_two )
   {
      return strcmp( s_one->elem, s_two->elem );
   }

This arrangement works well (less than 1000 members), but it may
be a poor design.  If we display the structure members, have to
move forward and backward among them interactively, *and may re-
move members*, then there are two nagging problems.

   1) qsort won't know that you'd like to discard members tagged
   as deleted (ncmp could always make such members greater than
   the comparison member).

   2) Going forward (backward) by, say, 20 members isn't as easy
   some pointer arithmetic, as you could land on (a) deleted
   member(s).  You'd have to walk forward (backward) until 20
   valid members had been counted.  That seems like a lot of over-
   head in an interactive environment.

Adding a field to the structure pointing to the next valid member
doesn't seem to obviate the need to deal with these two problems.

Another approach is to instead maintain an array of pointers to
struct_name.  Assuming the members are sorted, then with each
deletion you could move forward all the following elements of the
array of pointers, filling in the gap created by the deletion;
you'd also decrement a variable counting the number of valid
members.  To move forward (backware) by 20 members only requires
bumping the index into the array of pointers by that much.

First, the concrete question:

   Can the standard qsort accept not the array of structures, but
   the array of pointers to structure members?  If yes, how then
   can the declaration of ncmp (the compare function) be changed
   to accept two elements ([i], [j]) from the array of pointers,
   since the call (and i, j) is buried in the library?  If no,
   then I'll have to make my own qsort -- less desirable, since it
   makes more sense to take advantage of the library authors'
   presumed expertise at writing fast sort routines.

Second, a more global question:

   If there are fewer than 1000 members in the struct, am I mis-
   taken to believe there would be less overhead in closing the
   gap in the array of pointers with each deletion, then there
   would be in counting off valid members with *each movement* in
   the array of struct, especially considering the need to
   occasionally resort?  Alternatively, are there approaches to
   managing a list on screen than I've not thought of and that
   have greater merit than either of the ones above?

Unless this seems of general interest, please e-mail.  Thank you
much.

-- 
Frank Burleigh  burleigh at cica.cica.indiana.edu
USENET: ...rutgers!iuvax!cica!burleigh BITNET: BURLEIGH at IUBACS.BITNET
Department of Sociology, Indiana University, Bloomington, Indiana 47405