Issue with malloc() in array initialisation

Question

I'm currently working on a task which makes use of sparse sets. In a particular function I am asked to initialise a sparse set data structure in the range of [0..max_value]. Hence I assume that malloc() must be used. However I believe that I am implementing this function incorrectly, as the unit-tests do not work. (capacity is the maximum number of elements that can be stored, while max_value is the maximum integer value to be stored)

sparse_set_ptr ss_init(sparse_set_index_t capacity, sparse_set_elem_t max_value) {

    struct sparse_set *d_arr = malloc(sizeof(capacity));
    struct sparse_set *s_arr = malloc(sizeof(max_value) + 1);

    return d_arr->sparseSetPtr, s_arr->sparseSetPtr;
}

And this is the struct in question:

struct sparse_set {
    int *d_arr;
    int *s_arr;
    sparse_set_ptr sparseSetPtr;
};

Any help is appreciated :)

EDIT: The given definition of a sparse set is the following:

A sparse set is a data structure used to store small sets of data. Its main use is in applications where a fixed number of items/elements need to be tracked. Sparse sets are used in compilers, development frameworks and more. This data structure offers extremely fast lookup, insertion and deletion times while also being cache-friendly. As with normal sets, duplicate items are not accepted in sparse sets.

A sparse set consists of two arrays working in tandem. These two arrays are referred to as the dense array and the sparse array.

The dense array, as its name suggests, is a compact array that stores its elements sequentially, with no gaps between the elements.

On the other hand, the sparse array is used as a lookup list, and stores indices that map to elements in the dense array. Whenever an operation is performed, the dense and the sparse array must be kept in sync. For example, consider a sparse set ranging over the numbers [0..7]. This means it can only store the elements 0, 1, 2, 3, 4, 5, 6, and 7. Suppose we want to store a maximum of four elements. This means that the sparse set will contain a sparse array of size 8 and a dense array of size 4.

Luca Polito · Accepted Answer · 2021-08-18 21:18:03Z

2

I have not 100% understood what the function is supposed to do, but maybe this could help:

// NOTE: ss_init() name is unclear: does this function have to initialize
//   arrays d_arr and s_arr with values?
// NOTE 2: I assume sparse_set_ptr is typedef struct sparse_set*
sparse_set_ptr ss_init(sparse_set_index_t capacity, sparse_set_elem_t max_value) {
  struct sparse_set* result = malloc(sizeof(struct sparse_set));

  if (result == NULL) {
    return NULL;
  }

  result->d_arr = malloc(sizeof(int) * capacity);

  if (result->d_arr == NULL) {
    free(result);
    return NULL;
  }

  result->s_arr = malloc(sizeof(int) * (max_value + 1));

  if (result->s_arr == NULL) {
    free(result->d_arr);
    free(result);
    return NULL;
  }

  // TODO: do we fill d_arr with values?
  // TODO: do we fill s_arr with values?

  // I don't understand the purpose of member "sparseSetPtr"
  result->sparseSetPtr = NULL;
  // or maybe
  result->sparseSetPtr = result;

  return result;
}

EDIT: I updated the code since the question is not so clear.

EDIT 2: damn you, missing semicolon. Now fixed.

EDIT 3: I made some clarifications.

edited Aug 18, 2021 at 21:18

answered Aug 18, 2021 at 20:16

Luca Polito

2,99719 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Luca Polito Over a year ago

It could be that this function may only have to allocate space for the arrays, and that another function has the purpose of filling the arrays with values.

n. m. could be an AI Over a year ago

The function is called ss_init, so if it allocates and doeesn't do init, the author needs to be fired and escorted outta campus by security.

Luca Polito Over a year ago

@n.1.8e9-where's-my-sharem. You're so dramatic, I've seen much worse names for functions. sarcasm off But you could be right about the purpose of the function.

n. m. could be an AI Over a year ago

I've seen my fair share of bad names too, but we don't need to write answers which imply that bad names are acceptable.

Luca Polito Over a year ago

@n.1.8e9-where's-my-sharem. You're right, I have updated my answer asking for clarifications about the function's name and purpose.

John Bollinger · Accepted Answer · 2021-08-18 21:33:02Z

In the first place, the function signature you have presented demands that a sparse_set_ptr be returned. You have been coy about what type that actually is, but it seems reasonable to suppose that it is struct sparse_set *. In that case, you need to dynamically allocate space for a (one) struct sparse_set, initialize it, and return a pointer to it:

struct sparse_set *ss_init(sparse_set_index_t capacity, sparse_set_elem_t max_value) {
    // ... maybe validate parameters ...

    struct sparse_set *the_set = malloc(sizeof *the_set);

    // ... initialize here (see below) ...

    return the_set;
}

Note well that your ...

    return d_arr->sparseSetPtr, s_arr->sparseSetPtr;

... is surely wrong, at minimum because it leaks memory. It is equivalent to just ...

    return s_arr->sparseSetPtr;

.

In the second place, in a sparse set implementation such as you describe, the dense array will be large enough to hold as many elements as the set's capacity, and the sparse array will have at least one more element than the maximum element value that the set can accommodate. That's not what you are providing. The wanton use of unnecessary typedefs obscures things a bit, but maybe you are providing enough space in the dense array for a capacity of one or two elements, and enough space in the sparse array for a maximum value of one or two, the actual values of capacity and max_value notwithstanding. You probably want something more like this:

    the_set->d_arr = calloc(capacity * sizeof(*the_set->d_arr));
    the_set->s_arr = calloc((max_value + 1) * sizeof(*the_set->s_arr));
    // ... check for and handle allocation failure ...

Using calloc() instead of malloc() causes the space to be zero-filled, which is necessary to ensure proper behavior of membership testing for all valid values of capacity. The sizeof subexpressions evaluate to the sizes, in bytes, of the objects to which the pointers being initialized point (whatever those happen to be, and even if they are later changed from whatever they are now), and those sizes are multiplied by the number of elements required.

The purpose and intended use of the sparseSetPtr member is unclear. There should instead be a member conveying the current number of elements of the set (which should be set to 0) and a member conveying the maximum value the set permits. Conventionally, there would also be a member conveying the set's capacity. If you go without that then you have to rely on the set's users to not try to add more elements than its capacity. For example, given this alternative version of struct sparse_set ...

struct sparse_set {
    int *d_arr;
    int *s_arr;
    sparse_set_elem_t max_value;
    sparse_set_index_t capacity;
    sparse_set_index_t size;
};

... you would probably finish up the initialization with:

    the_set->max_value = max_value;
    the_set->capacity = capacity;
    the_set->size = 0;

Collectives™ on Stack Overflow

Issue with malloc() in array initialisation

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related