Object pool and sorted linked list in C

Question

Update: Have implemented some of the suggestions:

See GitHub: https://github.com/BostonBrooks/MathsGame/tree/master/Object_Pools_Demo

I am implementing a game engine where I have a sorted list of inanimate objects so that the closer objects get drawn over the further away objects, and I want to use an object pool rather than call malloc() every time a new object is spawned. I do not wish to store pointers directly to objects because these may move around when I save and restore the session.

I have written code that does this in the form of a high-scores list. Here it is, go nuts.

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

#define    LEVEL1   3
#define    LEVEL2   5

typedef struct {
    int Prev;
    int Next;
    char Name[16];
    int Score;
} Object;

Object* Pool[LEVEL1] = { 0 };

int Available_Head = -1;
int Available_Tail = -1;

int List_Head = -1;
int List_Tail = -1;

int Increase_Pool(void);

int New_Object(void);
void Delete_Object(int);

void List_Object(int);
void DeList_Object(int);

Object* Lookup_Object(int);

void Print_All(void);
void Print_None(void);

int main (void) {

    char Name[16];
    int Score;

    while(1) {

        Print_All();

        printf("Enter Name: ");
        scanf("%s", Name);

        printf("Enter Score: ");
        scanf("%d", &Score);


        int object_int = New_Object();

        printf("object_int %d\n", object_int);

        Object* object_address = Lookup_Object(object_int);

        strcpy(object_address->Name, Name);
        object_address->Score = Score;

        List_Object(object_int);

    }


}

void DeList_Object (int object_int){
    //Remove from list

    Object* object_address = Lookup_Object(object_int);

    if (List_Head == -1 && List_Tail == -1){
        //List Empty

    } else if (object_address->Prev == -1 && object_address->Next == -1) {
        //Object not in list


    } else if ( List_Head == object_int && List_Tail == object_int){
        //Only object in list

        List_Head = -1;
        List_Tail = -1;


        object_address->Prev = -1; 
        object_address->Next = -1; 

    } else if (List_Head == object_int) {
        // Object at top of list
        List_Head = object_address->Next;
        object_address->Next = -1;
        object_address->Prev = -1;

        object_address = Lookup_Object(List_Head);
        object_address->Prev = -1;

    } else if (List_Tail == object_int) {
        //Object at end of list
        List_Tail = object_address->Prev;
        object_address->Next = -1;
        object_address->Prev = -1;

        object_address = Lookup_Object(List_Tail);
        object_address->Next = -1;

    } else {
        //Object in middle of list
        Object* Next = Lookup_Object(object_address->Next);
        Object* Prev = Lookup_Object(object_address->Prev);

        Next->Prev = object_address->Prev;
        Prev->Next = object_address->Next;

        object_address->Prev = -1;
        object_address->Next = -1;
    }


}


void Delete_Object(int object_int){
     // Remove from list
     DeList_Object (object_int);

     //Return to Pool
     if (Available_Head == -1 && Available_Tail == -1){

         Available_Head = object_int;
         Available_Tail = object_int;

     } else{
         Object* object_address = Lookup_Object(object_int);

         object_address->Next = Available_Head;
//Available_Head->Prev = object_int;
         Available_Head = object_int;
     }

}


int New_Object(void){
    if (Available_Head == -1){ 
        assert (Available_Tail == -1);
        int success = Increase_Pool();
        assert(success == 1);
    }
    int object_int = Available_Head;
    Object* object_address = Lookup_Object(object_int);
    Available_Head = object_address->Next;

    object_address->Prev = -1;
    object_address->Next = -1;
    if (Available_Head != -1) {
        Object* Head = Lookup_Object(Available_Head);
        Head->Prev = -1;
    } else {
        Available_Tail = -1;
    }
    return object_int;
}

int Increase_Pool(void){ 
    int i;
    for (i = 0; i < LEVEL1 && Pool[i] != 0; i++){

    }


    if (i == LEVEL1) {
        printf("out of memory\n");
        return(0);
    } else {
        Pool[i] =  calloc(LEVEL2, sizeof(Object));
    }

    int j = 0;

    if (Available_Head == -1){
        assert (Available_Tail == -1);
        Available_Head = i * LEVEL2;
        Available_Tail = i * LEVEL2;

        Object* object = Lookup_Object(Available_Head);
        object->Prev = -1;
        object->Next = i * LEVEL2 + 1;
        j++;

    } else {

        Object* Tail = Lookup_Object(Available_Tail);
        Object* New = Lookup_Object(i * LEVEL2);

        Tail->Next = i * LEVEL2;
        New->Prev = Available_Tail;
        New->Next = i * LEVEL2 + 1;
        j++;
    }


    for (1; j < LEVEL2; j++){
    //add elements of Pool[i] to the Available list 
        Object* object_address = Lookup_Object(i * LEVEL2 + j);



        object_address->Prev = i * LEVEL2 + j - 1;
        object_address->Next = i * LEVEL2 + j + 1;


    } 

    Available_Tail = (i+1) * LEVEL2 - 1;

    Object* tail_address = Lookup_Object(Available_Tail);

    tail_address->Next = -1;

    return(1);
}

Object* Lookup_Object(int i){

    return (&(Pool[i / LEVEL2])[i % LEVEL2]);
}

void List_Object(int object_int){
    //Remove from list

    DeList_Object(object_int);


    //Add to list

    Object* object_address = Lookup_Object(object_int);

    if (List_Head == -1){ //list empty
        assert (List_Tail == -1);
        List_Head = object_int;
        List_Tail = object_int;
printf("### empty, %s, %d ##", object_address->Name, object_address->Score);
        return;
    }


    Object* head_address = Lookup_Object(List_Head);

    if (object_address->Score >= head_address->Score) {//add to start of list
        object_address->Prev = -1;
        object_address->Next = List_Head;
        head_address->Prev = object_int;
        List_Head = object_int;
printf("### head %s, %d ##", object_address->Name, object_address->Score);
        return;
    }

    Object* tail_address = Lookup_Object(List_Tail);

    if (object_address->Score <= tail_address->Score) {//add to end of list
        object_address->Next = -1;
        object_address->Prev = List_Tail;
        tail_address->Next = object_int;
        List_Tail = object_int;
printf("### tail %s, %d ##", object_address->Name, object_address->Score);
        return;
    }

    int target_int = List_Head;
    Object* target_address = Lookup_Object(target_int);

    //add to middle of list
    while(object_address->Score < target_address->Score){
        target_int = target_address->Next;
        target_address = Lookup_Object(target_int);
    }

    int target_prev_int = target_address->Prev;
    Object* target_prev_address = Lookup_Object(target_prev_int);

    target_prev_address->Next = object_int;
    object_address->Prev = target_prev_int;
    object_address->Next = target_int;
    target_address->Prev = object_int;


printf("### middle %s, %d ##", object_address->Name, object_address-> Score);

}

void Print_All(void){

    if (List_Head == -1){
        assert(List_Tail == -1);
        printf("\n List Empty\n\n");
        return;
    }

    int object_int = List_Head;
    Object* object_address;

    printf("\nName     Score\n");

    while (object_int != -1){

        object_address = Lookup_Object(object_int);
        printf("%s    %d\n", object_address->Name, object_address->Score);
        assert(object_int != object_address->Next);
        object_int = object_address->Next;

    }

    printf("\n");
    return;

}


//Print_None prints a list of available objects in the pool.
void Print_None(void){

    if (Available_Head == -1){
        assert(Available_Tail == -1);
        printf("\n List Empty\n\n");
        return;
    }

    int object_int = Available_Head;
    Object* object_address;

    printf("\nPrevious     Next\n");

    while (object_int != -1){

        object_address = Lookup_Object(object_int);
        printf("%d    %d\n", object_address->Prev, object_address->Next);
        assert(object_int != object_address->Next);
        object_int = object_address->Next;

    }

    printf("\n");
    return;

}

Answer 1

No warnings/errors (almost)

Aside from for (1; j < LEVEL2; j++) with its unneeded and curious 1, no errors (as expected) and no warnings (good) from my compilation.

Other compilers/checkers may say something, yet at least we are off to a good start.

Why not pointers?

OP reports "... not ... store pointers directly to objects because these may move around when I save and restore the session.", yet does not post even the declaration of a Save_Object() or Restore_Object().

If the save/restore is in memory, little reason to not use pointers.

If the save/restore is in a file, then data should could use fixed width integers types rather than int as a step toward portability. Endian would be another important concern.

A key reason to bring up this side issue is that it impacts the Object and then potentially all code so far.

Naming

It is good that most of the function have a common "Object" to collect these functions and type into a cohesive set.

Even better would precede the function/type/defines names uniformly with "Object_" or "Object".

Documentation

I found the object_int being broken in to 2 parts via (&(Pool[i / LEVEL2])[i % LEVEL2] a well buried in code and unclear. Some explanation of the 2 LEVEL1, LEVEL2 and memory model is deserved in a future Object.h

Overly complex (at least for me)

In DeList_Object() there are 6 cases. I'd expect the first 2 to roll into if (object_address == NULL) return; I'd expect the last 4 to roll into less.

Similar for others.

I'll need to study more to see how to improve, yet that is a fundamental weakness here of this code: its approach in not clear.

.Prev not needed

A double linked list is needed when loops exist going "left" or "right". That is not the case here. Loops only move "right" with .Next.

Should the previous node need to be remembered for later use, simply record it as the loop proceeds to the "right". Code never needs to know the Nth previous node, hence .Prev is not needed.

Security

In main(), code has strcpy(object_address->Name, Name); object_address->Score = Score;. This obliges typedef struct { ... } Object; to be exposed to main(). A secure approach would have an opaque declaration in Object.h for all to see

typedef struct Object  Object;

... and then a definition for only Object.c to see. The functional interface would provide get/set/access functions to .Name, .Score.

typedef struct Object{
  int Prev;
  int Next;
  char Name[16];
  int Score;
} Object;

Minor

Memory

Allocate by de-reference, not type:
Consider the 2 below: The 2nd is right, even if the pointed to type changes. Easier to code right, review and maintain.

// Pool[i] = calloc(LEVEL2, sizeof(Object));
Pool[i] = calloc(LEVEL2, sizeof Pool[i][0]);

Pool[i] = calloc(...) is not followed by an out-of-memory check.

No corresponding free() to mate with the *alloc(). I'd expect a Decrease/Destroy_Pool()

Code looks dead

The below looks wrong. I'd expect a body of at least ;

// for (i = 0; i < LEVEL1 && Pool[i] != 0; i++) {
//
// }

List means removal?

List_Object(int object_int) deletes an object! I'd expect a "list" function to not change pool and simply print.

Alternative:

for (i = 0; i < LEVEL1; i++) {
  if (Pool[i] == NULL) break;  // Clearly is an intended pointer compare
}

Test Code

Separate

Test code is in the middle of the implementation. Instead, consider 3 files, main.c, Object.c, Object.h.

scanf("%s", ...

Instead of scanf("%s", Name);, code could use the equally evil gets(). Better to insure that reading does not corrupt the test.

// scanf("%s", Name);
scanf("%15s", Name);

Answer 2

This list implementation seems to work only for one high score list. If the program need an another high score list in future, then this implementation won't be usable without modifications.

If you want to create a linked list, I recommend to create more re-usable implementation:

1. List can store any kind of types.
2. There can be zero, one or several linked lists in one application.
3. Put the list implementation to separate C and H file.