Sorting a Dynamic Array of Pointers

[jehugaleahsa]

Hello:

I am playing around with a data structure in C. It is a dynamically
growing array of pointers. So, really, it is just a void** with a
count and capacity.

I want to provide a sorting algorithm that takes a comparison function
with the signature qsort expects.

However, qsort is sending a void** instead of a void*, so all the
comparison functions need to be written like this:

int person_comparison(void const* value1, void const* value2)
{
person *const* t1 = (person *const*)value1;
person *const* t2 = (person *const*)value2;
person *const p1 = *t1;
person *const p2 = *t2;
/* compare the two people */
}

I want to avoid forcing clients of my class to do this double
dereference. However, I have no clue how to transform what qsort sends
to the comparison. I was thinking about creating a function that would
dereference the void**'s and then call the comparison the user passed
in with the dereferenced void*'s. In C++, I would accomplish using a
functor, but I don't know how to do this in C. I'd like to avoid
writing my own quick sort.

Let me know if you need to see more code. Any help would be
appreciated.

Thanks,
Travis Parks

 

[Barry Schwarz]

Hello:

I am playing around with a data structure in C. It is a dynamically
growing array of pointers. So, really, it is just a void** with a
count and capacity.

I want to provide a sorting algorithm that takes a comparison function
with the signature qsort expects.

However, qsort is sending a void** instead of a void*, so all the
comparison functions need to be written like this:

int person_comparison(void const* value1, void const* value2)
{
person *const* t1 = (person *const*)value1;
person *const* t2 = (person *const*)value2;
person *const p1 = *t1;
person *const p2 = *t2;
/* compare the two people */
}

I want to avoid forcing clients of my class to do this double
dereference. However, I have no clue how to transform what qsort sends
to the comparison. I was thinking about creating a function that would
dereference the void**'s and then call the comparison the user passed
in with the dereferenced void*'s. In C++, I would accomplish using a
functor, but I don't know how to do this in C. I'd like to avoid
writing my own quick sort.

qsort will always send the address of two array elements, each with
type const void*. Since the elements of your array are in fact
pointers, then each address your compare function receives is of
necessity the address of a pointer to your object of interest,
conveniently represented by the ** notation. You have no choice but
to dereference this address to obtain the pointer you are really
interested in.

Now you need to figure out what type you want the result of this
dereference to be. What you have coded above defines p1 as a constant
pointer to person. While I doubt you will change the value of p1, I'm
pretty sure it is more important to insure you never change the value
of the person. What you want is a pointer to a constant person. (See
6.2.5-28 for an explanation) I guess you could combine the two into a
constant pointer to a constant person but the declaration of the
compare function is really intended to insure you never change the
objects being compared.

The cast and the dereference can be combined into a single statement,
either
const person *p1 = *(const person**)value1;
or
const person * const p1 = *(const person*const*)value1;

Furthermore, all the const qualifiers inside the casts are unnecessary
since you are allowed to add the qualification implicitly
const person *p1 = *(person**)value1;
const person * const p2 = *(person**)value2;

 

[Jehu Galeahsa]

qsort will always send the address of two array elements, each with
type const void*.  Since the elements of your array are in fact
pointers, then each address your compare function receives is of
necessity the address of a pointer to your object of interest,
conveniently represented by the ** notation.  You have no choice but
to dereference this address to obtain the pointer you are really
interested in.

Now you need to figure out what type you want the result of this
dereference to be.  What you have coded above defines p1 as a constant
pointer to person.  While I doubt you will change the value of p1, I'm
pretty sure it is more important to insure you never change the value
of the person.  What you want is a pointer to a constant person.  (See
6.2.5-28 for an explanation)  I guess you could combine the two into a
constant pointer to a constant person but the declaration of the
compare function is really intended to insure you never change the
objects being compared.

The cast and the dereference can be combined into a single statement,
either
     const person *p1 = *(const person**)value1;
or
    const person * const p1 = *(const person*const*)value1;

Furthermore, all the const qualifiers inside the casts are unnecessary
since you are allowed to add the qualification implicitly
    const person *p1 = *(person**)value1;
    const person * const p2 = *(person**)value2;

Yeah, I figured out my const mistake last night. I also made it one
line, but thanks for the pointers. I'm rusty, let me tell ya.

So, are you telling me I can't provide a qsort-like interface without
reinventing the wheel?

In general, would you say that data structures like my class are
avoided in C?

The reason for my question: We have a huge application at work that
uses Pro*C. The big problem with it is that it is tens of thousands of
lines of code and all of the Pro*C is mixed in-line with the business
logic. There is a massive amount of code simply for converting between
VARCHARs and char*s. If the code were rewritten so that the Pro*C was
encapsulated within methods, such that the results were converted to
raw ADTs and stored in a data structure, we wouldn't have such a hard
time maintaining it. Nothing is more annoying than finding a 20 year
old bug because someone forgot to NULL-terminate a VARCHAR before
passing it to strcmp!

We are currently analyzing possible approaches to take when writing
new features and reworking old ones. We are hoping to find an easily
repeatable process. Without a data structure, we have to do all of the
processing while looping through the SQL results. You can't even
determine how many results there were without running once through. We
can't use plain-Jane arrays because we don't necessarily have an upper
limit. We want to isolate any dynamic array allocation logic to a
single set of code.

Well, just thought I would share. If we really can't provide a qsort
interface, I suppose we'll just copy our libraries and tweak it.

 

[Jehu Galeahsa]

Why aren't you using a (person**) instead of a (void**)?

We want to reuse the same code for all pointer types. A little casting
here and there isn't a big deal.

I suspect that it isn't.

The signature is a const void *. But, that (const void *) is really a
const pointer to another (void *). That (void *) is really a (person
*). Since qsort sends a void * pointing to the element being sorted, I
am getting a void **, effectively. At least that's as far as I want to
wrap my mind around it.

Show me a C definition of a person.

I will paste my test file for you in a different post.

 

[Jehu Galeahsa]

#include "array_list.h"
#include <assert.h>
#include <stdio.h>

typedef struct person_
{
char * name;
int age;
} person;

person * create_person(char * name, int age)
{
person * p = (person *)malloc(sizeof(person));
p->age = age;
p->name = name;
return p;
}

char * person_get_name(person const* person)
{
return person->name;
}

int person_get_age(person const* person)
{
return person->age;
}

void print_person(void * item)
{
person * p = (person *)item;
printf("%s is %d.\n", person_get_name(p), person_get_age(p));
}

int person_comparison(void const* value1, void const* value2)
{
person const* p1 = *(person const**)value1;
person const* p2 = *(person const**)value2;
int age1 = person_get_age(p1);
int age2 = person_get_age(p2);
return age1 - age2;
}

int main(int argc, char ** argv)
{
int capacity = 10;
int index = 0;
person * last = 0;
person * replacement = 0;

array_list lst;
array_list_init(&lst, sizeof(person), capacity);
assert(array_list_get_capacity(&lst) == capacity);
assert(array_list_get_count(&lst) == 0);

printf("Printing empty list:\n");
array_list_for_each(&lst, print_person);

for (index = 0; index != 10; ++index)
{
person * p = create_person("Tom", index);
array_list_add(&lst, p);
}

printf("Printing added items:\n");
array_list_for_each(&lst, print_person);

last = create_person("Tom", index);
array_list_add(&lst, last);

printf("Printing items after adding last item:\n");
array_list_for_each(&lst, print_person);

for (index = 0; index != array_list_get_count(&lst); ++index)
{
person * p = (person *)array_list_get_item(&lst, index);
assert(person_get_age(p) == index);
}

replacement = create_person("Tom", -1);
array_list_set_item(&lst, 0, replacement);
replacement = array_list_get_item(&lst, 0);
assert(person_get_age(replacement) == -1);

printf("Printing item after replacing first item:\n");
array_list_for_each(&lst, print_person);

replacement = create_person("Tom", 2);
array_list_insert(&lst, 0, replacement);
replacement = array_list_get_item(&lst, 0);
assert(person_get_age(replacement) == 2);

printf("Printing item after inserting at the front:\n");
array_list_for_each(&lst, print_person);

replacement = create_person("Tom", 4);
array_list_insert(&lst, 3, replacement);
replacement = array_list_get_item(&lst, 3);
assert(person_get_age(replacement) == 4);

printf("Printing item after inserting at the end:\n");
array_list_for_each(&lst, print_person);

array_list_trim(&lst);
replacement = create_person("Tom", 5);
index = array_list_get_count(&lst);
array_list_insert(&lst, index, replacement);
replacement = array_list_get_item(&lst, index);
assert(person_get_age(replacement) == 5);

printf("Printing item after inserting at the end:\n");
array_list_for_each(&lst, print_person);

//array_list_sort(&lst, person_comparison);

//printf("Printing after sorting by age:\n");
//array_list_for_each(&lst, print_person);

array_list_clear(&lst);
for (index = 0; index != 1000; ++index)
{
person * p = create_person("Tom", rand());
array_list_add(&lst, p);
}
//array_list_sort(&lst, person_comparison);

//printf("Printing after sorting a large number of people by age:
\n");
//array_list_for_each(&lst, print_person);

array_list_destroy(&lst);
return 0;
}

 

[Barry Schwarz]

Yeah, I figured out my const mistake last night. I also made it one
line, but thanks for the pointers. I'm rusty, let me tell ya.

So, are you telling me I can't provide a qsort-like interface without
reinventing the wheel?

You don't need to reinvent a qsort. It is already sufficiently
general. You only need to define the appropriate compare function.

In general, would you say that data structures like my class are
avoided in C?

I have no idea. C doesn't have classes. You never showed us what the
type of person is.

snip a bunch of stuff I don't understand

We are currently analyzing possible approaches to take when writing
new features and reworking old ones. We are hoping to find an easily
repeatable process. Without a data structure, we have to do all of the
processing while looping through the SQL results. You can't even
determine how many results there were without running once through. We
can't use plain-Jane arrays because we don't necessarily have an upper
limit. We want to isolate any dynamic array allocation logic to a
single set of code.

Seems reasonable to me

Well, just thought I would share. If we really can't provide a qsort
interface, I suppose we'll just copy our libraries and tweak it.

Why do you think you can't provide the appropriate compare function?
What does it have to do with dynamic arrays?

 

[Barry Schwarz]

We want to reuse the same code for all pointer types. A little casting
here and there isn't a big deal.

If any call to qsort is for something other than an array of pointers
to person, you can't use the same code.

The signature is a const void *. But, that (const void *) is really a
const pointer to another (void *). That (void *) is really a (person
*). Since qsort sends a void * pointing to the element being sorted, I
am getting a void **, effectively. At least that's as far as I want to
wrap my mind around it.

Then you are doomed to perpetual confusion. qsort always sends a
pointer to an array element with type void*. You then need to cast
this pointer to the actual type of the array element. If the array
element is a pointer to "the real something" to be sorted, then you
dereference to get the correct pointer before doing the actual
compares.

 

[Alan Curry]

|>
|> >I want to avoid forcing clients of my class to do this double
|> >dereference. However, I have no clue how to transform what qsort sends
|> >to the comparison. I was thinking about creating a function that would
|> >dereference the void**'s and then call the comparison the user passed
|> >in with the dereferenced void*'s. In C++, I would accomplish using a
|> >functor, but I don't know how to do this in C. I'd like to avoid
|> >writing my own quick sort.

I've had some trouble figuring out what you are asking for. But I think
I've got it now. Let me summarize:

You want to provide a sorting interface as part of an array library. The
array library implements arrays of pointers only. You want to present
the simplest possible interface for the comparison function, which is
not the qsort interface because the qsort comparison interface is more
general (it handles arrays of any kind of object, not just arrays of
pointers).

So there are at least 3 layers of code which you are trying to make as
independent as possible. Ideally, the top layer would be the only one to
know about the "person" type. The middle layer would only do memory
management for your arrays, and the low layer would be the standard C
library providing qsort.

Your call tree looks like this:

+-------------------+ +-------------------+
| Application-level | | comparison |
| code | | function |
+-------------------+ +-------------------+
| ^
==========|==========================|===================
v |
+-------------------+ |
| array library | |
+-------------------+ |
| |
===================|=================|===================
v |
+-------------------+
| qsort |
+-------------------+

See what's missing? On the way into qsort, your array library is doing
something. On the callback, it's being bypassed. What you want is to put
something in the middle layer on the right. The only way to accomplish
that with qsort is to have a comparison function inside your array
library, and pass that down to qsort instead of the application level's
comparison function. This middle-layer comparison function would then do
the (first level of) dereferencing, and call the real comparison
function.

The hard part is how the array library's sort function communicates the
real comparison function pointer to the array library's comparison
function. If qsort was properly designed, it would have a context
parameter (something passed into qsort, which gets passed back up to the
comparison function) for this purpose. But it doesn't, so you have to
use a static variable visible by both functions in the array library.

It's probably more trouble than it's worth. The alternative - which
should be looking pretty attractive by now - is to learn to live with
the extra dereference in the application-level comparison function.

 

[Jehu Galeahsa]

|>
|> >I want to avoid forcing clients of my class to do this double
|> >dereference. However, I have no clue how to transform what qsort sends
|> >to the comparison. I was thinking about creating a function that would
|> >dereference the void**'s and then call the comparison the user passed
|> >in with the dereferenced void*'s. In C++, I would accomplish using a
|> >functor, but I don't know how to do this in C. I'd like to avoid
|> >writing my own quick sort.

I've had some trouble figuring out what you are asking for. But I think
I've got it now. Let me summarize:

You want to provide a sorting interface as part of an array library. The
array library implements arrays of pointers only. You want to present
the simplest possible interface for the comparison function, which is
not the qsort interface because the qsort comparison interface is more
general (it handles arrays of any kind of object, not just arrays of
pointers).

So there are at least 3 layers of code which you are trying to make as
independent as possible. Ideally, the top layer would be the only one to
know about the "person" type. The middle layer would only do memory
management for your arrays, and the low layer would be the standard C
library providing qsort.

Your call tree looks like this:

+-------------------+               +-------------------+
| Application-level |               |     comparison    |
|       code        |               |      function     |
+-------------------+               +-------------------+
          |                          ^
==========|==========================|===================
          v                          |
         +-------------------+       |
         |   array library   |       |
         +-------------------+       |
                   |                 |
===================|=================|===================
                   v                 |
                  +-------------------+
                  |       qsort       |
                  +-------------------+

See what's missing? On the way into qsort, your array library is doing
something. On the callback, it's being bypassed. What you want is to put
something in the middle layer on the right. The only way to accomplish
that with qsort is to have a comparison function inside your array
library, and pass that down to qsort instead of the application level's
comparison function. This middle-layer comparison function would then do
the (first level of) dereferencing, and call the real comparison
function.

The hard part is how the array library's sort function communicates the
real comparison function pointer to the array library's comparison
function. If qsort was properly designed, it would have a context
parameter (something passed into qsort, which gets passed back up to the
comparison function) for this purpose. But it doesn't, so you have to
use a static variable visible by both functions in the array library.

It's probably more trouble than it's worth. The alternative - which
should be looking pretty attractive by now - is to learn to live with
the extra dereference in the application-level comparison function.

You understood my dilemma perfectly. Thank you for taking the time.
Yes, double dereferences do seem attractive at this point. I'll just
have to be extra careful about how I explain its usage.

 

[Jehu Galeahsa]

You don't need to reinvent a qsort.  It is already sufficiently
general.  You only need to define the appropriate compare function.




I have no idea.  C doesn't have classes.  You never showed us what the
type of person is.

By class, I meant the struct and the functions that worked on it.
Sorry, C++ and C# on the brain.

I sent an example that defines person. It is a typedef of struct
person_.

 

[Alan Curry]

|
|You understood my dilemma perfectly. Thank you for taking the time.
|Yes, double dereferences do seem attractive at this point. I'll just
|have to be extra careful about how I explain its usage.

You can provide a macro for turning the comparison function's parameters
into the pointers you want the application layer to see. Documentation can
say that the only allowable operation on the comparison function's parameters
is BlessArrayElement(), defined as

#define BlessArrayElement(v) (*(void *const *)v)

So it would be used like this:

int cmpfunc(const void *v1, const void *v2)
{
struct person *p1 = BlessArrayElement(v1);
struct person *p2 = BlessArrayElement(v2);
...
}

which gives you the freedom to try other approaches later, without changing
the upper-level interface, by just changing BlessArrayElement to a noop once
you've fixed the lower layers.

 

[Jehu Galeahsa]

#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H

#include <stdlib.h>

/*
Represents a dynamically-growing, random-access collection.
*/
typedef struct array_list_
{
int count;
int capacity;
void ** elements;
} array_list;

/*
Initializes an array_list.
*/
void array_list_init(array_list * lst, size_t type_size, int reserve)
{
lst->count = 0;
lst->capacity = reserve;
lst->elements = (void **)calloc(reserve, type_size);
}

/*
Destroys an array_list.
*/
void array_list_destroy(array_list * lst)
{
int index;
for (index = 0; index != lst->count; ++index)
{
free(lst->elements[index]);
}
free(lst->elements);
}

/*
Removes all of the items from the array_list.
*/
void array_list_clear(array_list * lst)
{
int index;
for (index = 0; index != lst->count; ++index)
{
free(lst->elements[index]);
}
lst->count = 0;
}

/*
Gets the number of items in the list.
*/
int array_list_get_count(array_list * lst)
{
return lst->count;
}

/*
Gets the maximum number of items that can be added before more memory
is allocated.
*/
int array_list_get_capacity(array_list * lst)
{
return lst->capacity;
}

/*
Gets the item at the given index.
*/
void * array_list_get_item(array_list * lst, int index)
{
return lst->elements[index];
}

/*
Replaces the item at the given index with the given value. The
replaced
value is returned.
*/
void array_list_set_item(array_list * lst, int index, void * value)
{
void * replaced = lst->elements[index];
lst->elements[index] = value;
free(replaced);
}

/*
Inserts the given value at the given index.
*/
void array_list_insert(array_list * lst, int index, void * value)
{
int position;
if (lst->count == lst->capacity)
{
void ** temp;
lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
temp = (void **)calloc(lst->capacity, sizeof(void *));
for (position = 0; position != index; ++position)
{
temp[position] = lst->elements[position];
}
free(lst->elements);
lst->elements = temp;
}
for (position = lst->count; position != index; --position)
{
lst->elements[position] = lst->elements[position - 1];
}
lst->elements[index] = value;
++lst->count;
}

/*
Adds the given value to the end of the array_list.
*/
void array_list_add(array_list * lst, void * value)
{
if (lst->count == lst->capacity)
{
lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
lst->elements = (void **)realloc(lst->elements, lst->capacity *
sizeof(void *));
}
lst->elements[lst->count] = value;
++lst->count;
}

/*
Removes the item at the given index, but does free it. The
item is returned.
*/
void * array_list_detach(array_list * lst, int index)
{
void * detached = lst->elements[index];
for (; index < lst->count - 1; ++index)
{
lst->elements[index] = lst->elements[index + 1];
}
--lst->count;
return detached;
}

/*
Removes the item at the given index.
*/
void array_list_remove_at(array_list * lst, int index)
{
void * removed = array_list_detach(lst, index);
free(removed);
}

/*
Removes the last item in the array_list.
*/
void array_list_remove_last(array_list * lst)
{
--lst->count;
free(lst->elements[lst->count]);
}

/*
Shrinks the capacity of the array_list to the count.
*/
void array_list_trim(array_list * lst)
{
lst->capacity = lst->count;
lst->elements = (void **)realloc(lst->elements, lst->count *
sizeof(void *));
}

typedef void (*array_list_action)(void * item);

/*
Applies the given operation to every item in the list.
*/
void array_list_for_each(array_list * lst, array_list_action action)
{
int index;
for (index = 0; index != lst->count; ++index)
{
action(lst->elements[index]);
}
}

typedef int (*array_list_predicate)(void const* value);

/*
Finds the first occurrence of a value such that the comparison returns
non-zero.
If the value is not found, -1 is returned.
*/
int array_list_find(array_list const* lst, array_list_predicate
predicate)
{
int index;
for (index = 0; index != lst->count; ++index)
{
if (predicate(lst->elements[index]))
{
return index;
}
}
return -1;
}

/*
Finds the last occurrence of a value such that the comparison returns
non-zero.
If the value is not found, -1 is returned.
*/
int array_list_find_last(array_list * lst, array_list_predicate
predicate)
{
int index;
for (index = lst->count - 1; index >= 0; --index)
{
if (predicate(lst->elements[index]))
{
return index;
}
}
return -1;
}

#endif // ARRAY_LIST_H

 

[Barry Schwarz]

#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H

#include <stdlib.h>

/*
Represents a dynamically-growing, random-access collection.
*/
typedef struct array_list_
{
int count;
int capacity;
void ** elements;
} array_list;

/*
Initializes an array_list.
*/
void array_list_init(array_list * lst, size_t type_size, int reserve)
{
lst->count = 0;
lst->capacity = reserve;
lst->elements = (void **)calloc(reserve, type_size);

The cast is unnecessary in C. Using calloc to initialize an array of
pointers to all-bits-zero is perfectly legal but not necessarily
portable. There is no guarantee that the bit representation of null
pointer has this bit representation. When asking for help, it pays to
let as many people as possible do so. In this case, using malloc and
a loop to set each array element to NULL is cheap insurance.

}

/*
Destroys an array_list.
*/
void array_list_destroy(array_list * lst)
{
int index;
for (index = 0; index != lst->count; ++index)
{
free(lst->elements[index]);
}
free(lst->elements);

Don't you want to set capacity to zero here?

}

/*
Removes all of the items from the array_list.
*/
void array_list_clear(array_list * lst)
{
int index;
for (index = 0; index != lst->count; ++index)
{
free(lst->elements[index]);

Since you don't free elements itself in this case, it would make sense
to also set elements[index] to NULL. At the very least, it would
insure that your _destroy function above would not attempt to evaluate
an indeterminate value.

}
lst->count = 0;
}

/*
Gets the number of items in the list.
*/
int array_list_get_count(array_list * lst)
{
return lst->count;
}

/*
Gets the maximum number of items that can be added before more memory
is allocated.

Memory has already been allocated. When you exceed capacity, you need
to allocate (realloc) more. Misleading comments can really hurt when
you go back to the program after a long hiatus.

*/
int array_list_get_capacity(array_list * lst)
{
return lst->capacity;
}

/*
Gets the item at the given index.
*/
void * array_list_get_item(array_list * lst, int index)
{
return lst->elements[index];
}

/*
Replaces the item at the given index with the given value. The
replaced
value is returned.

The function never returns anything. Did you mean the previously
allocated memory is given back to the system?

*/
void array_list_set_item(array_list * lst, int index, void * value)
{
void * replaced = lst->elements[index];
lst->elements[index] = value;
free(replaced);
}

/*
Inserts the given value at the given index.
*/
void array_list_insert(array_list * lst, int index, void * value)
{
int position;
if (lst->count == lst->capacity)
{
void ** temp;
lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;

Don't you need to check capacity against count before deciding an
expansion is necessary. Does your code ever set capacity to 0?

temp = (void **)calloc(lst->capacity, sizeof(void *));

Is there some reason you are not willing to use realloc and let it do
all the hard work for you?

for (position = 0; position != index; ++position)
{
temp[position] = lst->elements[position];
}
free(lst->elements);
lst->elements = temp;
}
for (position = lst->count; position != index; --position)

What happens if index is greater than count (insert at end of list)?
You may want to use position>index here.

{
lst->elements[position] = lst->elements[position - 1];
}
lst->elements[index] = value;
++lst->count;
}

/*
Adds the given value to the end of the array_list.
*/
void array_list_add(array_list * lst, void * value)
{
if (lst->count == lst->capacity)
{
lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
lst->elements = (void **)realloc(lst->elements, lst->capacity *
sizeof(void *));
}
lst->elements[lst->count] = value;
++lst->count;
}

/*
Removes the item at the given index, but does free it. The

Did you intend to say "does not"?

item is returned.
*/
void * array_list_detach(array_list * lst, int index)
{
void * detached = lst->elements[index];
for (; index < lst->count - 1; ++index)
{
lst->elements[index] = lst->elements[index + 1];
}
--lst->count;
return detached;
}

/*
Removes the item at the given index.
*/
void array_list_remove_at(array_list * lst, int index)
{
void * removed = array_list_detach(lst, index);
free(removed);
}

/*
Removes the last item in the array_list.

Just my opinion but forcing the user of these functions to distinguish
between first, last, and intermediate elements is wrong. The user
should issue a generic remove request with the desired index and the
service functions should make any distinctions necessary.

*/
void array_list_remove_last(array_list * lst)
{
--lst->count;
free(lst->elements[lst->count]);
}

/*
Shrinks the capacity of the array_list to the count.
*/
void array_list_trim(array_list * lst)
{
lst->capacity = lst->count;
lst->elements = (void **)realloc(lst->elements, lst->count *
sizeof(void *));

Are you always guaranteed that only the first count elements contain
"active" pointers? If not, this causes memory leaks.

}

typedef void (*array_list_action)(void * item);

/*
Applies the given operation to every item in the list.
*/
void array_list_for_each(array_list * lst, array_list_action action)
{
int index;
for (index = 0; index != lst->count; ++index)
{
action(lst->elements[index]);
}
}

typedef int (*array_list_predicate)(void const* value);

/*
Finds the first occurrence of a value such that the comparison returns
non-zero.
If the value is not found, -1 is returned.
*/
int array_list_find(array_list const* lst, array_list_predicate
predicate)
{
int index;
for (index = 0; index != lst->count; ++index)
{
if (predicate(lst->elements[index]))
{
return index;
}
}
return -1;
}

/*
Finds the last occurrence of a value such that the comparison returns
non-zero.
If the value is not found, -1 is returned.
*/
int array_list_find_last(array_list * lst, array_list_predicate
predicate)
{
int index;
for (index = lst->count - 1; index >= 0; --index)
{
if (predicate(lst->elements[index]))
{
return index;
}
}
return -1;
}

#endif // ARRAY_LIST_H

Is there some reason you intend to #include this source in multiple
translation units rather than compile it once and let the linker
include the various functions as appropriate?

 

[Jehu Galeahsa]

The cast is unnecessary in C.  Using calloc to initialize an array of
pointers to all-bits-zero is perfectly legal but not necessarily
portable.  There is no guarantee that the bit representation of null
pointer has this bit representation.  When asking for help, it pays to
let as many people as possible do so.  In this case, using malloc and
a loop to set each array element to NULL is cheap insurance.

I could see where malloc would be more efficient. I am not actually
concerned what the pointer value is if it is greater than count.
Bogus, random data is fine with me.

}

/*
Destroys an array_list.
*/
void array_list_destroy(array_list * lst)
{
   int index;
   for (index = 0; index != lst->count; ++index)
   {
           free(lst->elements[index]);
   }
   free(lst->elements);

Don't you want to set capacity to zero here?

No. I do want users using my array list after it is destroyed. If they
want to reuse the same array_list, they MUST call init after destroy.

}

/*
Removes all of the items from the array_list.
*/
void array_list_clear(array_list * lst)
{
   int index;
   for (index = 0; index != lst->count; ++index)
   {
           free(lst->elements[index]);

Since you don't free elements itself in this case, it would make sense
to also set elements[index] to NULL.  At the very least, it would
insure that your _destroy function above would not attempt to evaluate
an indeterminate value.

The count field is responsible for managing what is destroyed. Since
count is set back to zero, destroy will not try to double free.

Memory has already been allocated.  When you exceed capacity, you need
to allocate (realloc) more.  Misleading comments can really hurt when
you go back to the program after a long hiatus.

I don't understand your problem with my comment above.

*/
int array_list_get_capacity(array_list * lst)
{
   return lst->capacity;
}

/*
Gets the item at the given index.
*/
void * array_list_get_item(array_list * lst, int index)
{
   return lst->elements[index];
}

/*
Replaces the item at the given index with the given value. The
replaced
value is returned.

The function never returns anything.  Did you mean the previously
allocated memory is given back to the system?

That is correct. I need to fix my comment.

*/
void array_list_set_item(array_list * lst, int index, void * value)
{
   void * replaced = lst->elements[index];
   lst->elements[index] = value;
   free(replaced);
}

/*
Inserts the given value at the given index.
*/
void array_list_insert(array_list * lst, int index, void * value)
{
   int position;
   if (lst->count == lst->capacity)
   {
           void ** temp;
           lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;

Don't you need to check capacity against count before deciding an
expansion is necessary.  Does your code ever set capacity to 0?

I check if count == capacity. When calling init, the capacity can be
set to 0.

Is there some reason you are not willing to use realloc and let it do
all the hard work for you?

The reason is that realloc will copy all my values to the new memory.
I can avoid unnecessary copying if I use malloc. If I insert in the
middle of a huge array_list, this might make a difference in
performance. Of course, I am using calloc, so my point is moot. I will
change to malloc; thanks for pointing that out.

           for (position = 0; position != index; ++position)
           {
                   temp[position] = lst->elements[position];
           }
           free(lst->elements);
           lst->elements = temp;
   }
   for (position = lst->count; position != index; --position)

What happens if index is greater than count (insert at end of list)?
You may want to use position>index here.

I am ignoring argument checking for now. You might have noticed that I
am doing no error checking either.

   {
           lst->elements[position] = lst->elements[position - 1];
   }
   lst->elements[index] = value;
   ++lst->count;
}

/*
Adds the given value to the end of the array_list.
*/
void array_list_add(array_list * lst, void * value)
{
   if (lst->count == lst->capacity)
   {
           lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
           lst->elements = (void **)realloc(lst->elements, lst->capacity *
sizeof(void *));
   }
   lst->elements[lst->count] = value;
   ++lst->count;
}

/*
Removes the item at the given index, but does free it. The

Did you intend to say "does not"?

Yup. I need to fix my comments.

item is returned.
*/
void * array_list_detach(array_list * lst, int index)
{
   void * detached = lst->elements[index];
   for (; index < lst->count - 1; ++index)
   {
           lst->elements[index] = lst->elements[index + 1];
   }
   --lst->count;
   return detached;
}

/*
Removes the item at the given index.
*/
void array_list_remove_at(array_list * lst, int index)
{
   void * removed = array_list_detach(lst, index);
   free(removed);
}

/*
Removes the last item in the array_list.

Just my opinion but forcing the user of these functions to distinguish
between first, last, and intermediate elements is wrong.  The user
should issue a generic remove request with the desired index and the
service functions should make any distinctions necessary.

Probably. I know I would expect the same performance if I called
remove_last and remove_at(count).

*/
void array_list_remove_last(array_list * lst)
{
   --lst->count;
   free(lst->elements[lst->count]);
}

/*
Shrinks the capacity of the array_list to the count.
*/
void array_list_trim(array_list * lst)
{
   lst->capacity = lst->count;
   lst->elements = (void **)realloc(lst->elements, lst->count *
sizeof(void *));

Are you always guaranteed that only the first count elements contain
"active" pointers?  If not, this causes memory leaks.

I am saying that is the case. If someone directly accesses my
elements, they are corrupting my data structure. If they only use my
functions to manipulate the data structure, they are a-okay.

}

typedef void (*array_list_action)(void * item);

/*
Applies the given operation to every item in the list.
*/
void array_list_for_each(array_list * lst, array_list_action action)
{
   int index;
   for (index = 0; index != lst->count; ++index)
   {
           action(lst->elements[index]);
   }
}

typedef int (*array_list_predicate)(void const* value);

/*
Finds the first occurrence of a value such that the comparison returns
non-zero.
If the value is not found, -1 is returned.
*/
int array_list_find(array_list const* lst, array_list_predicate
predicate)
{
   int index;
   for (index = 0; index != lst->count; ++index)
   {
           if (predicate(lst->elements[index]))
           {
                   return index;
           }
   }
   return -1;
}

/*
Finds the last occurrence of a value such that the comparison returns
non-zero.
If the value is not found, -1 is returned.
*/
int array_list_find_last(array_list * lst, array_list_predicate
predicate)
{
   int index;
   for (index = lst->count - 1; index >= 0; --index)
   {
           if (predicate(lst->elements[index]))
           {
                   return index;
           }
   }
   return -1;
}

#endif // ARRAY_LIST_H

Is there some reason you intend to #include this source in multiple
translation units rather than compile it once and let the linker
include the various functions as appropriate?

You mean, why don't I have a .c file? Because I am just experimenting
for now.

 

[Peter Nilsson]

..., qsort is sending a void** instead of a void*, so all the
comparison functions need to be written like this:

int person_comparison(void const* value1, void const* value2)
{
        person *const* t1 = (person *const*)value1;
        person *const* t2 = (person *const*)value2;
        person *const p1 = *t1;
        person *const p2 = *t2;
        /* compare the two people */
}

I generally try to avoid the casts...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define countof(x) ((size_t) (sizeof (x)/sizeof *(x)))
#define pp_cmp(a, b) (((b) < (a)) - ((a) < (b)))

typedef struct person
{
const char *name;
int beauty;
} person;

int by_age(const void *lv, const void *rv)
{
const void * const *lpv = lv;
const void * const *rpv = rv;
const person *lp = *lpv;
const person *rp = *rpv;
return strcmp(lp->name, rp->name);
}

int by_beauty(const void *lv, const void *rv)
{
const void * const *lpv = lv;
const void * const *rpv = rv;
const person *lp = *lpv;
const person *rp = *rpv;
return pp_cmp(lp->beauty, rp->beauty);
}

person peter = { "Peter", 38 };
person bob = { "Bob", 42 };
person alice = { "Alice", 24 };

int main(void)
{
size_t i;
void *a[] = { &peter, &bob, &alice };

puts("By name (lexical):");
qsort(a, countof(a), sizeof *a, by_age);
for (i = 0; i < countof(a); i++)
{
const person *p = a;
printf("%s: %d\n", p->name, p->beauty);
}

puts("\nBy beauty (relative):");
qsort(a, countof(a), sizeof *a, by_beauty);
for (i = 0; i < countof(a); i++)
{
const person *p = a;
printf("%s: %d\n", p->name, p->beauty);
}

return 0;
}