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;
}

• chux: With for (1; j < LEVEL2; j++){, why the lone 1 versus omitting it like for (; j < LEVEL2; j++){? Never have seen that style before.
• BostonBrooks: Lol, um, I don't want to seem like a naive programmer, but I panicked and put that in.

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);

• BostonBrooks: Thank you for your advice and feedback. List_Object() inserts an object into the sorted list. Could you advise a new name for this function?
• chux: @BostonBrooks Not only does it insert into the list, it also deletes any prior entry. Perhaps Update_Object()?
• BostonBrooks: How about Sort_Object/Unsort_Object? Maybe change List_Head to Sorted_Head. And doublely linked lists are good if you expect the code to become more complex later. I want to have all my bases covered.
• chux: @BostonBrooks By using an opaque struct, the members and your functions of Object can change at a later build time and not break prior usage. At that later time, make it more complex. Do not focus on making code perfect today as much as making code improvable tomorrow and in the later future.
• chux: @BostonBrooks Your example case is unclear as to what you perceive as the limiting issue. I do not know the .c and .h file contents.

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.

• BostonBrooks: Do not focus on making code perfect today as much as making code improvable tomorrow and in the later future
• BostonBrooks: "Object" refers to any object of any class
• BostonBrooks: Do you think I should study C macros?