3
\$\begingroup\$

I just started learning C fundamentals and started to write a List that is limited to integers for the beginning and has dynamic memory allocation according to its content.

I've written custom simple assertion functions that revealed, that upon reallocating less memory when shrinking the list, it is still possible to access the removed element - my guess is that there's no need to move the pointer when shrinking its allocation and realloc() does not free the memory? Is it right? Is this code C-ish? Thanks for your reviews!

list.h

typedef struct {
    long size;
    int* elements;
} intlist;

/**
 * Creates an empty list
 */
intlist il_create();

/**
 * Appends a value to a list and returns its index
 *
 * @return index of the item
 */
long il_push(intlist*, int);

/**
 * Retrieves a value by its index
 *
 * @return item of the list
 */
int il_get(intlist*, long);

/**
 * Removes the last element
 */
void il_pop(intlist*);

main.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

void assert(char* msg, long actual, char expression) {
  static int assert_nr = 0;
  ++assert_nr;

  if(!expression) {
    fprintf(stderr, "[ERROR] Assertion %d failed\n", assert_nr);
    fprintf(stderr, "[ERROR] Expected: %s\n", msg);
    fprintf(stderr, "[ERROR] Actual:   %ld\n", actual);
  }
}

void assertEquals(char *msg, long actual, long expected) {
  assert(msg, actual, actual == expected);
}

void assertNotEquals(char *msg, long actual, long expected) {
  assert(msg, actual, actual != expected);
}



int main(int argc, char const *argv[]) {
  // Create an empty list
  intlist list = il_create();

  { // List is initially empty
    assertEquals("Size is 0", list.size, 0);
  }

  { // The item is added to the list
    int index = il_push(&list, 123);
    int item = il_get(&list, 0);

    assertEquals("Size is 1", list.size,  1);
    assertEquals("First index is 0", index, 0);
    assertEquals("First element is 123", item, 123);
  }

  { // Another item is added to the list
    int index = il_push(&list, 456);
    int item2 = il_get(&list, 1);

    assertEquals("Size is 2", list.size, 2);
    assertEquals("Second index is 1", index, 1);
    assertEquals("Second element is 456", item2, 456);
  }

  { // Last element is removed and thus last = first
    il_pop(&list);

    assertEquals("Size is 1", list.size, 1);

    int first = il_get(&list, 0);
    int last = il_get(&list, list.size-1);

    assertEquals("First item is 123", first, 123);
    assertEquals("Last element is the first one", last, first);

    int deleted = il_get(&list, 1);
    assertNotEquals("Deleted item is not 456", deleted, deleted != 456);
  }

  { // Removed element is overwritten when pushing a new one
    int index = il_push(&list, 789);
    int item = il_get(&list, index);

    assertEquals("Index is 1", index, 1);
    assertEquals("Element is 789", item, 789);
  }

  return 0;
}


intlist il_create() {
  return (intlist){.size=0};
}

long il_push(intlist* list, int value) {
  int index = list->size;

  list->elements = realloc(list->elements, ++list->size * sizeof(int));
  *(list->elements + index) = value;

  return index;
}

int il_get(intlist* list, long index) {
  return *(list->elements + index);
}

void il_pop(intlist* list) {
  list->size -= 1;
  *(list->elements + list->size) = 0;
  list->elements = realloc(list->elements, list->size * sizeof(int));
}
\$\endgroup\$
4
\$\begingroup\$

It does. You directly assign list->elements to the result of realloc which can return NULL, in which case your original array is leaked (but it's okay since you immediately assign a value to a NULL-based array after that, which is UB).

Few more observations.

  1. The list itself can only be operated via its public interface that consists of methods that accept list object by pointer. Perhaps it makes sense to return by pointer from constructor, too; then you can make list's implementation an opaque struct, all its fields will be private.

  2. You should define a destructor to release the array, that otherwise (currently) leaks.

  3. Your current allocation strategy is inefficient. Reallocating the whole array per each new element raises push's complexity to O(N), so creating an array of N elements takes O(N²) time. A traditional approach to deal with it is adding capacity to the list object; capacity equals to the size of allocated space and grows exponentially: when list's size reaches capacity, on next element push capacity doubles, thus reducing push complexity to ammortized O(1).

  4. Elements are stored in a contiguous array, perhaps a better descriptive name? Traditionally, list is associated with linked lists in C family.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks a lot for taking the time and effort! But what stands UB for? \$\endgroup\$ – Jazzschmidt Apr 15 '20 at 13:33
  • \$\begingroup\$ And do you have any suggestions on how to test the leaking, so that I am able to write it test-driven? \$\endgroup\$ – Jazzschmidt Apr 15 '20 at 13:33
  • \$\begingroup\$ Undefined behaviour. Unsure about testing, running a static analysis perhaps? \$\endgroup\$ – bipll Apr 15 '20 at 21:47
2
\$\begingroup\$

Some stuff after @bipll good answer.

size type

The choice for long, as in member long size;, is arbitrary. Could have been int, char or what ever.

Yet size code is making an array, consider using the unsigned integer type size_t. That is the not too big/not too small type for array sizing and indexing.

const

Functions like il_get() that do not change the list are better with const to 1) indicate no change will occur, 2) helps some lessor compiler to make better code, 3) helps convey to the user that the list is unchanged.

// int il_get(intlist*, long);
int il_get(const intlist*, long);

Named parameters

Often a user of this code is only interested in the .h file. Providing informative names there helps them.

// long il_push(intlist*, int);
long il_push(intlist *list, int value);

.h include guard

To prevent re-evaluation of .h code: include_guards

No error checking

List of potential failures. If code should check them or not is up to you.

(Re-)allocation failure.  (recommend checking)
Passing in a null pointer for `intlist*`

list.c

I expected the il_...() definitions in their own list.c file, not main.c.

Uniform name space

Consider a common prefix for all external symbols, perhaps il_.

list.h --> il.h
list.c --> il.c

intlist --> il_type;

il_...() --> the same ( good usage here)

Weak prototype

The declaration of il_create() should include void, else il_create(42) and il_create("Hello World", 867-5309) will pass undetected as an error.

// intlist il_create();
intlist il_create(void);

Include order

OP's include order will fail to detect if "list.h" can not stand on its own without <stdio.h>, <stdlib.h>

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

I recommend the above in all files except list.c, so it can insure no include dependency.

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
\$\endgroup\$
3
  • \$\begingroup\$ That sure is some important information my book on ANSI C is missing. Thanks for also including best practices! \$\endgroup\$ – Jazzschmidt Apr 17 '20 at 7:04
  • \$\begingroup\$ Is there any meaningful difference in suggestion 1 and 3 of the const part? \$\endgroup\$ – Jazzschmidt Apr 17 '20 at 7:06
  • \$\begingroup\$ @Jazzschmidt Similar: 1) is an enforcement by the compiler. 2) information to the user. I could have worded different. \$\endgroup\$ – chux - Reinstate Monica Apr 17 '20 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.