i have a problem in my code when i try to use compelx structure in a generic sorting library on C lang: (you can find the complete code https://github.com/Tramontz/ASD_2023)
i have a binary-merge insertion sort, thatt take in imput a void pointer (first element of an array), and ,can work with array of int and string (all unity test pass).
Now i'm tryng to use it with an array of:
struct record{
int id;
char* string_field_1;
int integer_field_2;
double float_field_3;
};
stored in another struct
struct _StructArray{
void**array;
unsigned long el_num;
unsigned long array_capacity;
};
with subroutine
void struct_array_add(StructArray *struct_array, void* element){
if(struct_array->el_num >= struct_array->array_capacity){
printf("array too short, must be reallocate \n");
struct_array->array = (void**)realloc(struct_array->array,2*(struct_array->array_capacity)*sizeof(void*));
struct_array->array_capacity = 2*struct_array->array_capacity;
}
struct_array->array[struct_array->el_num] = element;
struct_array->el_num++;
}
void* struct_array_get(StructArray *struct_array, unsigned long index){
return &(struct_array->array)[index];
}
i must order the void**array of record.
this is an example of the data took from a csv file
<POSIZION:0, ID:0, String:noto, Integer:233460, Float:32209.073312 >
<POSIZION:1, ID:1, String:piangea, Integer:4741192, Float:81176.622633 >
<POSIZION:2, ID:2, String:spenti!, Integer:1014671, Float:4476.013614 >
<POSIZION:3, ID:3, String:misericordia, Integer:496325, Float:61628.929334 >
the ordering mode is choosed by
switch (field) {
case 1://struct_array_get(array,0) return the first element of the array
merge_binary_insertion_sort(struct_array_get(array,0), struct_array_size(array), sizeof(struct record), k, precedes_record_string_field);
so basically i store with a loop all my data in the record *array inside structArray.
the array is correctly loaded, because the print function
for(unsigned long i=0;i<el_num;i++){
array_element = (struct record *)struct_array_get(array, i);
printf("<POSIZION:%d, ID:%d, String:%s, Integer:%d, Float:%lf >\n",i,array_element->id,array_element->string_field_1,array_element->integer_field_2,array_element->float_field_3);
}
can show all the record in the array.
so the problem appear when the sorting function is called:
void bin_insertion_sort(void *arr, int n, size_t elementSize, CompareFunction compare) {
int i, loc, j;
void *selected = malloc(elementSize);
if (selected == NULL) {
fprintf(stderr, "Errore nell'allocazione di memoria per 'selected'\n");
exit(EXIT_FAILURE);
}
for (i = 1; i < n; ++i) {
j = i - 1;
memcpy(selected, arr + i * elementSize, elementSize);
// Find location where selected should be inserted
loc = binary_search(arr, selected, 0, j, compare, elementSize);
i store in the void *selected the item that i want to find location in the array, and call the binary search
int binary_search(void *arr, void *item, int low, int high, CompareFunction compare, size_t elementSize) {
if (high <= low){
return (compare(item, arr + low * elementSize) > 0) ? (low + 1) : low ;
We can focus only in the binary_search, here is the problem: when i call return (compare(item, arr + low * elementSize) > 0) ? (low + 1) : low ; for the records's array, with this compare function
static int precedes_record_string_field(const void* r1_p, const void* r2_p) {
if (r1_p == NULL || r2_p == NULL) {
fprintf(stderr, "precedes_record_string_field: one of the parameters is a null pointer\n");
exit(EXIT_FAILURE);
}
const struct record* rec1_p = (const struct record*)r1_p;
const struct record* rec2_p = (const struct record*)r2_p;
printf("Record 1: ID=%d, String=%s, Integer=%d, Float=%f\n", rec1_p->id, rec1_p->string_field_1, rec1_p->integer_field_2, rec1_p->float_field_3);
sleep(1);
printf("Record 2: ID=%d, String=%s, Integer=%d, Float=%f\n", rec2_p->id, rec2_p->string_field_1, rec2_p->integer_field_2, rec2_p->float_field_3);
sleep(5);
return strcmp(rec1_p->string_field_1, rec2_p->string_field_1);
}
it print the rec2 data, but not the rec1 data, so i suppose that it can cast the arr + low * elementSize pointer, but not the void item* pointer that I pass through the compare(item, arr + low * elementSize) and store in rec1(item) and rec2(arr + low * elementSize).
I'm doing something wrong in the memory adress management? maybe i'm adressing all the structArray with item, and not the second element of the record* array?
i'm stucked because all my unity test with single, null, and multiple string and integer arrays work correctly.
Thank you all.
It seems very very very complex the way you wrote.
Maybe you could test the functions first...
I will show you a methodical way of writing his,
using your `struct` and `qsort`,
that you can easily adapt...
EDIT: added a second part, PART II, below. In that I added code to use the same method below to sort a
void**array, and then aStructArrayas in the original question, as an example of a way to separate the container, the methods and the algorithm. This was a heavy use of copy and paste: the changes are only in the compare functions (2 lines in each) and a function added toStructArray(4 lines) to extract he base address of the array of pointers.
typedef struct
{
int id;
char* string;
int i_field;
double d_field;
} Target;
int cmp_1(const void*, const void*);
int cmp_2(const void*, const void*);
int cmp_3(const void*, const void*);
int cmp_4(const void*, const void*);
int so_show(unsigned, Target[], const char*);
Here we have your data record, the 4 required functions and a function to show the results
Use encapsulation and write code around your data.
See this :
Target some_value[] = {
[0] =
{.id = 42,
.string = "value 33",
.i_field = 4242,
.d_field = 42.42},
[1] =
{.id = 4,
.string = "stack",
.i_field = 42,
.d_field = 42.242},
[2] =
{.id = 342,
.string = "overflow",
.i_field = 4,
.d_field = 142.42},
[3] =
{.id = 412,
.string = "take the survey",
.i_field = 2,
.d_field = 2142.42},
};
This is data to test all your functions.
###' main for a test ###
Here:
so_show(4, some_value, "\nBefore sort:\t");
qsort(some_value, 4, sizeof(Target), cmp_1);
so_show(4, some_value, "\nAfter sort by id:\t");
qsort(some_value, 4, sizeof(Target), cmp_2);
so_show(
4, some_value, "\nAfter sort by string field:\t");
qsort(some_value, 4, sizeof(Target), cmp_3);
so_show(
4, some_value, "\nAfter sort by integer field:\t");
qsort(some_value, 4, sizeof(Target), cmp_4);
so_show(
4, some_value, "\nAfter sort by double field:\t");
Before sort: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 42 | " value 33" | 4242 | 42.4200 |
| 4 | " stack" | 42 | 42.2420 |
| 342 | " overflow" | 4 | 142.4200 |
| 412 | " take the survey" | 2 | 2142.4200 |
|=========================================================|
After sort by id: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 4 | " stack" | 42 | 42.2420 |
| 42 | " value 33" | 4242 | 42.4200 |
| 342 | " overflow" | 4 | 142.4200 |
| 412 | " take the survey" | 2 | 2142.4200 |
|=========================================================|
After sort by string field: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 342 | " overflow" | 4 | 142.4200 |
| 4 | " stack" | 42 | 42.2420 |
| 412 | " take the survey" | 2 | 2142.4200 |
| 42 | " value 33" | 4242 | 42.4200 |
|=========================================================|
After sort by integer field: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 412 | " take the survey" | 2 | 2142.4200 |
| 342 | " overflow" | 4 | 142.4200 |
| 4 | " stack" | 42 | 42.2420 |
| 42 | " value 33" | 4242 | 42.4200 |
|=========================================================|
After sort by double field: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 4 | " stack" | 42 | 42.2420 |
| 42 | " value 33" | 4242 | 42.4200 |
| 342 | " overflow" | 4 | 142.4200 |
| 412 | " take the survey" | 2 | 2142.4200 |
|=========================================================|
And it seems to be ok.
It is easier this way: first test all functions.
Since you said the code already works for integers, just make sure the sorting code really abstracted the data record. In general is just a case of writing correct swapping functions. And paying special attention to the navigating process...
C code#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
int id;
char* string;
int i_field;
double d_field;
} Target;
int cmp_1(const void*, const void*);
int cmp_2(const void*, const void*);
int cmp_3(const void*, const void*);
int cmp_4(const void*, const void*);
int so_show(unsigned, Target[], const char*);
int main(void)
{
Target some_value[] = {
[0] =
{.id = 42,
.string = "value 33",
.i_field = 4242,
.d_field = 42.42},
[1] =
{.id = 4,
.string = "stack",
.i_field = 42,
.d_field = 42.242},
[2] =
{.id = 342,
.string = "overflow",
.i_field = 4,
.d_field = 142.42},
[3] =
{.id = 412,
.string = "take the survey",
.i_field = 2,
.d_field = 2142.42},
};
so_show(4, some_value, "\nBefore sort:\t");
qsort(some_value, 4, sizeof(Target), cmp_1);
so_show(4, some_value, "\nAfter sort by id:\t");
qsort(some_value, 4, sizeof(Target), cmp_2);
so_show(
4, some_value, "\nAfter sort by string field:\t");
qsort(some_value, 4, sizeof(Target), cmp_3);
so_show(
4, some_value, "\nAfter sort by integer field:\t");
qsort(some_value, 4, sizeof(Target), cmp_4);
so_show(
4, some_value, "\nAfter sort by double field:\t");
}; // main
int cmp_1(void* one, void* other)
{
Target* a = one;
Target* b = other;
if (a->id < b->id) return -1;
if (a->id == b->id) return 0;
return 1;
};
int cmp_2(void* one, void* other)
{ // now for the string
Target* a = one;
Target* b = other;
return strcmp(a->string, b->string);
};
int cmp_3(void* one, void* other)
{
Target* a = one;
Target* b = other;
if (a->i_field < b->i_field) return -1;
if (a->i_field == b->i_field) return 0;
return 1;
};
int cmp_4(void* one, void* other)
{
Target* a = one;
Target* b = other;
if (a->d_field < b->d_field) return -1;
if (a->d_field == b->d_field) return 0;
return 1;
};
int so_show(unsigned N, Target r[], const char* msg)
{
if (r == NULL) return -1;
if (msg != NULL) printf("%s", msg);
printf("%d records\n", N);
const char* l0 =
"\
| id | string value | integer | double |";
const char* l1 =
"\
|=========================================================|";
printf("%s\n%s\n%s\n", l1,l0,l1);
for ( unsigned u=0;u<N;u+=1)
printf(
"| %4d | \"%20s\" | %8d | %12.4f |\n", r[u].id,
r[u].string, r[u].i_field, r[u].d_field);
printf("%s\n\n",l1);
return 0;
}
This is main.c for the second example:
int main(void)
{
Target some_value[] = {
[0] =
{.id = 42,
.string = "value 33",
.i_field = 4242,
.d_field = 42.42},
[1] =
{.id = 4,
.string = "stack",
.i_field = 42,
.d_field = 42.242},
[2] =
{.id = 342,
.string = "overflow",
.i_field = 4,
.d_field = 142.42},
[3] =
{.id = 412,
.string = "take the survey",
.i_field = 2,
.d_field = 2142.42},
};
const N = sizeof(some_value) / sizeof(some_value[0]);
test_with_struct_array(
N, some_value,
"\n\n\t***** using an array of structs *****\n\n");
test_with_voidp_array(
N, some_value,
"\n\n\t***** using a 'void**' *****\n\n");
test_with_Struct_Array(
N, some_value,
"\n\n\t***** using an original 'StructArray' "
"*****\n\n");
return 0;
}; // main
test_with_struct_array() is the original program. The 2nd function sorts the same array in a void** array, in order to test the mechanics in isolation, and the 3rd function uses the author's original StructArray --- with a minor modification, see code below.
void**This is the code to build the array using the original data:
Target** base = malloc(n * sizeof(Target*));
for (unsigned i = 0; i < n; i += 1)
base[i] = &some_value[i];
The compare funcions are all different, since there is a new level of indirection to accesss the actual data. The new functions are cmp_[5678] from cmp_[1234] and here is a pair, that compares the i_field from Target:
int cmp_3(const void* one, const void* other)
{
Target* a = (Target*)one;
Target* b = (Target*)other;
if (a->i_field < b->i_field) return -1;
if (a->i_field == b->i_field) return 0;
return 1;
};
int cmp_7(const void* one, const void* other)
{
Target* a = (Target*)*((const void**)one);
Target* b = (Target*)*((const void**)other);
if (a->i_field < b->i_field) return -1;
if (a->i_field == b->i_field) return 0;
return 1;
};
The difference is just in getting the data address. Since StructArray is also a void** thing, these functions are used there too.
Sister functions were added to display the data from the different sources, so the output is exactly the same, as expected.
int so_show_one(Target*);
int so_show(
unsigned, Target[], int (*show)(void*), const char*);
int so_show_from_StructArray(
StructArray*, int (*show)(void*), const char*);
int so_show_from_voidp_array(
unsigned, void**, int (*show)(void*), const char*);
The first function displays a single data record, so can be used by all 3 formats. It is passed as a parameter so it is easy to use an alternate display for each test if needed.
StructArrayvoid* struct_array_get_base(StructArray* x)
{
if (x == NULL) return NULL;
return &(x->array)[0];
}
This function was added in order to get the base address from inside StructArray
StructArray as a containerint test_with_Struct_Array(
unsigned n, Target some_value[], const char* msg)
{
if (msg != NULL) printf("%s", msg);
StructArray* tgt = struct_array_create();
for (size_t i = 0; i < n; i += 1)
struct_array_add(tgt, &some_value[i]);
fprintf(
stderr, "\n\t%u values inside target StructArray\n",
struct_array_size(tgt));
so_show_from_StructArray(
tgt, so_show_one,
"\n With data inside StructArray:\t");
// this is the base for sort
void* array_base = struct_array_get_base(tgt);
size_t size = struct_array_size(tgt);
qsort(array_base, size, sizeof(void*), cmp_5);
so_show_from_StructArray(
tgt, so_show_one, "\n\tAfter sort by id:\t");
This is how the container was abstracted for sorting, at the start of the test function. This should work for any sorting algorithm on the contiguous array of void*.
Hope it helps
#pragma pack(push, 1)
#pragma pack(show)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "struct_array.h"
typedef struct
{
int id;
char* string;
int i_field;
double d_field;
} Target;
int cmp_1(const void*, const void*);
int cmp_2(const void*, const void*);
int cmp_3(const void*, const void*);
int cmp_4(const void*, const void*);
int cmp_5(const void*, const void*);
int cmp_6(const void*, const void*);
int cmp_7(const void*, const void*);
int cmp_8(const void*, const void*);
int so_show_one(Target*);
int so_show(
unsigned, Target[], int (*show)(void*), const char*);
int so_show_from_StructArray(
StructArray*, int (*show)(void*), const char*);
int so_show_from_voidp_array(
unsigned, void**, int (*show)(void*), const char*);
int test_with_struct_array(unsigned, Target[], const char*);
int test_with_voidp_array(unsigned, Target[], const char*);
int test_with_Struct_Array(unsigned, Target[], const char*);
int main(void)
{
Target some_value[] = {
[0] =
{.id = 42,
.string = "value 33",
.i_field = 4242,
.d_field = 42.42},
[1] =
{.id = 4,
.string = "stack",
.i_field = 42,
.d_field = 42.242},
[2] =
{.id = 342,
.string = "overflow",
.i_field = 4,
.d_field = 142.42},
[3] =
{.id = 412,
.string = "take the survey",
.i_field = 2,
.d_field = 2142.42},
};
const N = sizeof(some_value) / sizeof(some_value[0]);
test_with_struct_array(
N, some_value,
"\n\n\t***** using an array of structs *****\n\n");
test_with_voidp_array(
N, some_value,
"\n\n\t***** using a 'void**' *****\n\n");
test_with_Struct_Array(
N, some_value,
"\n\n\t***** using an original 'StructArray' "
"*****\n\n");
return 0;
}; // main
int cmp_1(const void* one, const void* other)
{ // compare ids
Target* a = (Target*)one;
Target* b = (Target*)other;
if (a->id < b->id) return -1;
if (a->id == b->id) return 0;
return 1;
};
int cmp_2(const void* one, const void* other)
{ // now for the string
Target* a = (Target*)one;
Target* b = (Target*)other;
return strcmp(a->string, b->string);
};
int cmp_3(const void* one, const void* other)
{
Target* a = (Target*)one;
Target* b = (Target*)other;
if (a->i_field < b->i_field) return -1;
if (a->i_field == b->i_field) return 0;
return 1;
};
int cmp_4(const void* one, const void* other)
{ // for doubles
Target* a = (Target*)one;
Target* b = (Target*)other;
if (a->d_field < b->d_field) return -1;
if (a->d_field == b->d_field) return 0;
return 1;
};
int cmp_5(const void* one, const void* other)
{
Target* a = (Target*)*((const void**)one);
Target* b = (Target*)*((const void**)other);
if (a->id < b->id) return -1;
if (a->id == b->id) return 0;
return 1;
};
int cmp_6(const void* one, const void* other)
{ // now for the string
Target* a = (Target*)*((const void**)one);
Target* b = (Target*)*((const void**)other);
return strcmp(a->string, b->string);
};
int cmp_7(const void* one, const void* other)
{
Target* a = (Target*)*((const void**)one);
Target* b = (Target*)*((const void**)other);
if (a->i_field < b->i_field) return -1;
if (a->i_field == b->i_field) return 0;
return 1;
};
int cmp_8(const void* one, const void* other)
{ // sort as double
Target* a = *((void**)one);
Target* b = *((void**)other);
if (a->d_field < b->d_field) return -1;
if (a->d_field == b->d_field) return 0;
return 1;
};
int so_show(
unsigned N, Target r[], int (*show)(void*),
const char* msg)
{
if (r == NULL) return -1;
if (msg != NULL) printf("%s", msg);
printf("%d records\n", N);
const char* l0 =
"\
| id | string value | integer | double |";
const char* l1 =
"\
|=========================================================|";
printf("%s\n%s\n%s\n", l1, l0, l1);
for (unsigned u = 0; u < N; u += 1) show(r + u);
printf("%s\n\n", l1);
return 0;
}
int so_show_one(Target* one)
{
printf(
"| %4d | \"%20s\" | %8d | %12.4f |\n", one->id,
one->string, one->i_field, one->d_field);
return 0;
}
int so_show_from_StructArray(
StructArray* A, int (*show)(void*), const char* msg)
{
if (A == NULL) return -1;
if (show == NULL) return -2;
if (msg != NULL) printf("%s", msg);
unsigned long N = struct_array_size(A);
printf("%u records\n", N);
const char* l0 =
"\
| id | string value | integer | double |";
const char* l1 =
"\
|=========================================================|";
printf("%s\n%s\n%s\n", l1, l0, l1);
for (unsigned u = 0; u < N; u += 1)
show((Target*)struct_array_get(A, u));
printf("%s\n\n", l1);
return 0;
}
int so_show_from_voidp_array(
unsigned N, void** base, int (*show)(void*),
const char* msg)
{
if (base == NULL) return -1;
if (show == NULL) return -2;
if (N <= 0) return -3;
if (msg != NULL) printf("%s", msg);
printf("%u records\n", N);
const char* l0 =
"\
| id | string value | integer | double |";
const char* l1 =
"\
|=========================================================|";
printf("%s\n%s\n%s\n", l1, l0, l1);
for (unsigned u = 0; u < N; u += 1)
show((Target*)base[u]);
printf("%s\n\n", l1);
return 0;
}
int test_with_struct_array(
unsigned n, Target some_value[], const char* msg)
{
if (msg != NULL) printf("%s", msg);
so_show(
n, some_value, so_show_one, "\n Before sort:\t");
qsort(some_value, n, sizeof(Target), cmp_1);
so_show(
n, some_value, so_show_one,
"\n After sort by id:\t");
qsort(some_value, n, sizeof(Target), cmp_2);
so_show(
n, some_value, so_show_one,
"\n After sort by string field:\t");
qsort(some_value, n, sizeof(Target), cmp_3);
so_show(
n, some_value, so_show_one,
"\n After sort by integer field:\t");
qsort(some_value, n, sizeof(Target), cmp_4);
so_show(
n, some_value, so_show_one,
"\n After sort by double field:\t");
return 0;
}
int test_with_voidp_array(
unsigned n, Target some_value[], const char* msg)
{
if (msg != NULL) printf("%s", msg);
Target** base = malloc(n * sizeof(Target*));
for (unsigned i = 0; i < n; i += 1)
base[i] = &some_value[i];
so_show_from_voidp_array(
n, base, so_show_one, "\tbefore sort: ");
size_t sz_one = sizeof(Target*);
qsort(&base[0], n, sz_one, cmp_5);
so_show_from_voidp_array(
n, base, so_show_one, "\tsorted by id field: ");
qsort(&base[0], n, sz_one, cmp_8);
so_show_from_voidp_array(
n, base, so_show_one, "\tsorted by double field: ");
qsort(&base[0], n, sz_one, cmp_7);
so_show_from_voidp_array(
n, base, so_show_one,
"\tsorted by integer field: ");
qsort(&base[0], n, sz_one, cmp_6);
so_show_from_voidp_array(
n, base, so_show_one, "\tsorted by string field: ");
return 0;
}
int test_with_Struct_Array(
unsigned n, Target some_value[], const char* msg)
{
if (msg != NULL) printf("%s", msg);
StructArray* tgt = struct_array_create();
for (size_t i = 0; i < n; i += 1)
struct_array_add(tgt, &some_value[i]);
fprintf(
stderr, "\n\t%u values inside target StructArray\n",
struct_array_size(tgt));
so_show_from_StructArray(
tgt, so_show_one,
"\n With data inside StructArray:\t");
// this is the base for sort
void* array_base = struct_array_get_base(tgt);
size_t size = struct_array_size(tgt);
qsort(array_base, size, sizeof(void*), cmp_5);
so_show_from_StructArray(
tgt, so_show_one, "\n\tAfter sort by id:\t");
qsort(array_base, size, sizeof(void*), cmp_6);
so_show_from_StructArray(
tgt, so_show_one,
"\n\tAfter sort by string field:\t");
qsort(array_base, size, sizeof(void*), cmp_7);
so_show_from_StructArray(
tgt, so_show_one,
"\n After sort by integer field:\t");
qsort(array_base, size, sizeof(void*), cmp_8);
so_show_from_StructArray(
tgt, so_show_one,
"\n After sort by double field:\t");
return 0;
}
Not interesting since it is the same data 3 times, but generated by differen containers built from the same original data.
***** using an original 'StructArray' *****
4 values inside target StructArray
With data inside StructArray: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 4 | " stack" | 42 | 42.2420 |
| 42 | " value 33" | 4242 | 42.4200 |
| 342 | " overflow" | 4 | 142.4200 |
| 412 | " take the survey" | 2 | 2142.4200 |
|=========================================================|
After sort by id: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 4 | " stack" | 42 | 42.2420 |
| 42 | " value 33" | 4242 | 42.4200 |
| 342 | " overflow" | 4 | 142.4200 |
| 412 | " take the survey" | 2 | 2142.4200 |
|=========================================================|
After sort by string field: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 342 | " overflow" | 4 | 142.4200 |
| 4 | " stack" | 42 | 42.2420 |
| 412 | " take the survey" | 2 | 2142.4200 |
| 42 | " value 33" | 4242 | 42.4200 |
|=========================================================|
After sort by integer field: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 412 | " take the survey" | 2 | 2142.4200 |
| 342 | " overflow" | 4 | 142.4200 |
| 4 | " stack" | 42 | 42.2420 |
| 42 | " value 33" | 4242 | 42.4200 |
|=========================================================|
After sort by double field: 4 records
|=========================================================|
| id | string value | integer | double |
|=========================================================|
| 4 | " stack" | 42 | 42.2420 |
| 42 | " value 33" | 4242 | 42.4200 |
| 342 | " overflow" | 4 | 142.4200 |
| 412 | " take the survey" | 2 | 2142.4200 |
|=========================================================|