C中的对象池和排序链接列表

Question

更新:落实了一些建议：

见GitHub：https://github.com/BostonBrooks/MathsGame/tree/master/Object_水池_演示

我正在实现一个游戏引擎，其中我有一个排序的无生命对象列表，以便在更远的对象上绘制更近的对象，并且我希望每次生成一个新对象时都使用一个对象池而不是调用malloc()。我不希望直接存储指向对象的指针，因为当我保存和恢复会话时，这些指针可能会移动。

我用高分表的形式写了这样的代码。给你，疯了。

#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

无警告/错误(几乎)

除了for (1; j < LEVEL2; j++)及其不需要的和好奇的1之外，我的编译中没有错误(如预期的那样)，也没有警告(很好)。

其他编译器/检查人员可能会说些什么，但至少我们已经有了一个良好的开端。

为什么不指点呢？

OP报告“.不是.直接存储指向对象的指针，因为当我保存和恢复会话时，这些指针可能会移动”，但是甚至不会发布Save_Object()或Restore_Object()的声明。

如果保存/还原在内存中，则没有什么理由不使用指针。

如果保存/还原在文件中，那么数据应该使用固定宽度的整数类型，而不是int作为可移植性的一步。安迪安将是另一个重要的问题。

提出这个问题的一个关键原因是，它会影响到Object，然后可能影响到所有的代码。

命名

很好的是，大多数函数都有一个公共的“对象”来收集这些函数并将其输入到一个内聚集合中。

更好的做法是在函数/类型/定义名称之前统一使用"Object_“或"Object”。

Documentation

我发现object_int通过(&(Pool[i / LEVEL2])[i % LEVEL2]被分成了两个部分，一个隐藏在代码中的井，并且不清楚。对于2 LEVEL1, LEVEL2和内存模型的一些解释在未来的Object.h中是值得的。

过于复杂(至少对我而言)

在DeList_Object()中有6例。我预计前2将进入if (object_address == NULL) return;，而最后4将转到更少的。

其他人也一样。

我需要更多的研究，看看如何改进，然而这是这个代码的一个根本弱点:它的方法不清楚。

.Prev不需要

当循环存在时，需要双链接列表，循环为“左”或“右”。这里的情况并非如此。循环只在.Next中移动“右”。

如果需要记住前一个节点以供以后使用，只需在循环进行到“右边”时记录它。代码不需要知道第N个前一个节点，因此不需要.Prev。

安全

在main()中，代码有strcpy(object_address->Name, Name); object_address->Score = Score;。这就迫使typedef struct { ... } Object;暴露于main()中。一个安全的方法将在Object.h中有一个不透明的声明，让所有人都可以看到。

typedef struct Object  Object;

..。然后只有Object.c才能看到这个定义。函数接口将为.Name, .Score提供get/set/access函数。

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

未成年人

存储器

按取消引用，而不是按类型分配：

考虑下面的两个:第二个是正确的，即使指向类型改变。更容易编写正确的代码，检查和维护。

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

Pool[i] = calloc(...)之后不进行内存不足检查.

没有相应的free()与*alloc()相匹配。我希望有一个Decrease/Destroy_Pool()

代码看起来像死了的

下面看上去不对。我希望至少有一个;的身体

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

列表意味着删除？

List_Object(int object_int)删除一个对象！我希望“列表”函数不会更改池，只需打印。

备选方案：

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

测试代码

分离

测试代码在实现的中间。相反，考虑3个文件，main.c, Object.c, Object.h。

scanf(%S，.

)

而不是scanf("%s", Name);，代码可以使用同样邪恶的gets()。最好是确保阅读不会破坏考试。

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