C Dynamic structures - Arrays or Lists?

[stallone3]

Hi,

My question is more of a perfomance or common practice doubt about dynamic structures usage:

I have a function that will be called to search a file for a certain condition in particular time windows. This function returns all the time windows that satisfy this condition.

The amount of time windows that satisfy the condition will rarely be high (suppose high is 1500), and it will normally have 1 or 2 orders of magnitude.

Considering I only need the time windows numbers, what is the best solution for the problem?

Should I pass the address to an array of int's (let's say with space for 10 int's allocated initially) and keep using realloc to increment the size, or should I create a list and malloc'ing with every new time window found? (don't know exactly why, but I'm feeling a list for just one int a bit of overkill)

Thanks in advance for any comments

[Banfa]

Whatever you do the allocation should remain in one function, not allocate outside the function and then reallocate inside the function, that is asking for trouble.

I think I would allocate and array inside the function (of a default size) and then as required reallocate it (I think a growth factor of between 1.3 and 1.6 produces an efficient reallocation algorithm, that is when you need more memory allocate current size *1.6)).

Whatever you do you will need to return the current pointer and the size of the current array, or rather the number of used entries, you are returning 2 things so at least one of them will have to be via a pointer parameter. I suspect I would return them both via pointer parameters and make the actual function return code a function status.

Remember to return a pointer to and int array via a parameter the parameter will need a type of int **.

[stallone3]

Thank you for the answer.

Two more question:

- A list would be a bad choice for this situation?
- The solution you specified is common programming practice for this type of situation?

[Banfa]

Well as a minimum a list will use at least twice as much memory as an allocated array of ints. However you talk about a maximum count in the order of 1500 so it isn't exactly memory intensive anyway unless you happen to be on a platform with only a few k of ram. So a list would probably work very well.

You only really need to worry about memory usage if you are in a very constrained environment (I have worked on platforms with 4k of ram, your list would not fit in it 4 * 1500 = 6000 bytes) or you are using a huge amount of memory (suppose rather than an int each item in the list was 50Mbytes).

Allocating an array in the manor I said is problematic because the caller has to remember to free the memory leaving room for them to forget and cause a memory leak and since they haven't allocated the memory why should they free it.

There is a 3rd option, an ADT (abstracted data type). In this method you don't let the user have access to the data directly by force them to use an interface (a set of functions). The code within the functions accesses the data and endures it's integrity and that all free operations required are carried out.

In many ways a list is a generic form of an ADT however in your case I would suggest functions for the following.

CreateADT
DeleteADT

AddItemToADT
GetADTItemCount
GetItemNInADT

Note replacing ADT with something more meaningful to you.

The implementation could be a list or a reallocated array, it is up to you. CreateADT would return a handle that is passed to the other functions to itemtify the instance to operate on, apart from that most of the calls only envolve passing or returning built-in types.

Additionally if the implementation needed to change (say from an allocated array to a sorted list) as long as you keep the interface the same then all the other code in the project wont need changing.

[stallone3]

Thanks again, this closes the questions.