深度复制结构
Deep Copying Structs
我查看了 Stack Overflow 上有关深度复制结构的示例，但这些示例不适用于我的情况。我试图模拟一个简单的缓存，用户可以更改每组的设置数量和行数。但是，在设置集合时，我意识到每一行都指向相同的东西，因此当您更改集合 0 中的第 0 行时，它也会更改集合 1 中的第 0 行。关于如何使集合不具有相同行的任何建议或者更好的方法来设置缓存结构？
typedef struct Line {
unsigned int valid;
unsigned int tag;
unsigned int lru;
}Line;
typedef struct Set {
Line lines[0];
}Set;
Set *MakeSet(int n) {
Set *s;
s = malloc(sizeof s->lines *n);
return s;
}
typedef struct Cahce {
Set sets[0];
}Cache;
Cache *MakeCache(int n){
Cache *c;
c = malloc(sizeof c->sets *n);
return c;
}
int main(void) {
int lines_per_set =1;
int num_sets = 2;
Set *s = MakeSet(lines_per_set);
Line generic_line;
generic_line.valid = 0;
generic_line.tag =0;
generic_line.lru =0;
for(int i=0; i<lines_per_set; i++){
s->lines[i] = generic_line;
}
Cache *c = MakeCache(num_sets);
for(int j=0; j<num_sets; j++){
c->sets[j] = *s;
}
c->sets[0].lines[0].valid =1;
printf("%d", c->sets[1].lines[0].valid );
return 0;
}
在大多数 H/W 中，每个缓存的 集数 和每个集的 行数 是固定的。
但是，您的示例有点混乱 fixed/variable。所以，[对我来说]不清楚你想要什么复杂程度。
请注意，在下面的示例中，不是 重复 的函数。只是做初始创建。这是第一步。下面的代码应该给你一些关于如何继续的想法。
这是一个所有参数都固定的重构示例：
#include <stdio.h>
#include <stdlib.h>
enum {
LINES_PER_SET = 1,
NUM_SETS = 2
};
typedef struct {
unsigned int valid;
unsigned int tag;
unsigned int lru;
} Line;
typedef struct {
int set_linecount;
Line set_lines[LINES_PER_SET];
} Set;
typedef struct {
int cache_setcount;
Set cache_sets[NUM_SETS];
} Cache;
Cache *
MakeCache(void)
{
Cache *c;
c = calloc(1,sizeof(Cache));
return c;
}
int
main(void)
{
Cache *c = MakeCache();
c->cache_sets[0].set_lines[0].valid = 1;
printf("%d\n", c->cache_sets[0].set_lines[0].valid);
return 0;
}
这是一个允许动态定义集数和行数的重构示例：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
unsigned int valid;
unsigned int tag;
unsigned int lru;
} Line;
typedef struct {
int set_linecount;
Line *set_lines;
} Set;
typedef struct {
int cache_setcount;
Set *cache_sets;
} Cache;
Line *
MakeLine(Line *line)
{
if (line == NULL)
line = malloc(sizeof(Line));
line->valid = 0;
line->tag = 0;
line->lru = 0;
return line;
}
Set *
MakeSet(Set *s,int nline)
{
Line *line;
if (s == NULL)
s = malloc(sizeof(Set));
s->set_linecount = nline;
s->set_lines = malloc(sizeof(Line) * nline);
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx) {
line = &s->set_lines[lineidx];
MakeLine(line);
}
return s;
}
Cache *
MakeCache(Cache *c,int nset,int nline)
{
Set *s;
if (c == NULL)
c = malloc(sizeof(Cache));
c->cache_setcount = nset;
c->cache_sets = calloc(nset,sizeof(Set));
for (int setidx = 0; setidx < c->cache_setcount; ++setidx) {
s = &c->cache_sets[setidx];
MakeSet(s,nline);
}
return c;
}
int
main(void)
{
int lines_per_set = 1;
int num_sets = 2;
Cache *c = MakeCache(NULL,num_sets,lines_per_set);
c->cache_sets[0].set_lines[0].valid = 1;
printf("%d\n", c->cache_sets[0].set_lines[0].valid);
return 0;
}
这是使用额外间接级别的第三个示例：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
unsigned int valid;
unsigned int tag;
unsigned int lru;
} Line;
typedef struct {
int set_linecount;
Line **set_lines;
} Set;
typedef struct {
int cache_setcount;
Set **cache_sets;
} Cache;
Line *
MakeLine(void)
{
Line *line;
line = malloc(sizeof(Line));
line->valid = 0;
line->tag = 0;
line->lru = 0;
return line;
}
Set *
MakeSet(int nline)
{
Line *line;
Set *s;
s = malloc(sizeof(Set));
s->set_linecount = nline;
s->set_lines = malloc(sizeof(Line *) * nline);
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx)
s->set_lines[lineidx] = MakeLine();
return s;
}
Cache *
MakeCache(int nset,int nline)
{
Cache *c;
c = malloc(sizeof(Cache));
c->cache_setcount = nset;
c->cache_sets = calloc(nset,sizeof(Set *));
for (int setidx = 0; setidx < c->cache_setcount; ++setidx)
c->cache_sets[setidx] = MakeSet(nline);
return c;
}
int
main(void)
{
int lines_per_set = 1;
int num_sets = 2;
Cache *c = MakeCache(num_sets,lines_per_set);
c->cache_sets[0]->set_lines[0]->valid = 1;
printf("%d\n", c->cache_sets[0]->set_lines[0]->valid);
return 0;
}
更新：
Thank you for the explanation. I liked the second one the best. How would you free the allocated memory? I tried:
for (int i = 0; i < num_sets; i++) {
for (int j = 0; j < lines_per_set; j++)
free(c->sets[i].lines[j]);
}
free(c);
But is says that the elements in lines are not the right type. I thought they were pointers.
虽然可以一次释放所有东西，但最好使用几个子函数来完成这项工作。就像 Make* 个函数一样，我们可以创建 Free* 个函数。
一个好的格言可能是：如果函数[或语句]“看起来”过于复杂或容易出错，则可能需要将其拆分为更小的函数。
事实上，在下面的示例中，我拆分了 Make* 个函数来创建 Free* 个函数。
在最初的 Make* 函数中，函数被传递给它是 creating/initializing 的结构的指针。如果那个指针是NULL，它就是在做malloc。因此，它“知道”它是否正在执行 malloc。
这允许函数创建一个带有 malloc 的“独立”结构 [就像 MakeCache 所做的那样]，或者让该结构成为另一个结构的从属结构（例如 Set从属于 Cache，Line 从属于 Set）。这可能不是最好的方法[一个单独的“alloc”和“init”函数可能更干净]。
但是，对于 Free* 函数， 调用者 必须“告诉”函数是否执行结构指针的 free 或不是。这会很麻烦，因为调用者必须跟踪 [such] 事情。通常，跟踪是各个函数的范围。
所以，我为每个结构添加了一个额外的成员，它“记住”该结构是否已分配。然后，Free* 函数可以查看它以确定它是否可以释放它的指针。这是我在生产代码中经常使用的个人“交易技巧”。该字段可以只是一个布尔值 int（如 cache_alloced）。但是，我选择使用带有各种选项位的位掩码（例如 OPT_ALLOC）。这是为了将来需要时进行扩展。
我已经创建了一些辅助 CPP 宏来帮助实现这一点[小心你想要的，你可能真的会得到它:-)]。
您可能会注意到各种 FREEME* 宏首先检查“即将释放”指针是否为 NULL，如果是，则抑制对 free 的调用。这并不是真正必要的，因为它 是 允许使用空指针调用 free [即它是无害的。
他们做的另一件事是，在 free 之后，他们将指针设置为 NULL。这是捕获“已释放”指针的 misuse/reuse 的“安全”功能。它还可以防止 free 的“双重释放”中止（例如 free(ptr); free(ptr); 会导致这种情况）。
如果指针 未 为空，取消引用 可能会 成功并产生未定义的结果。那是 UB [未定义的行为]，但可能很难检测到。通过将指针清零，指针的任何后续取消引用都会立即触发 SIGSEGV [segfault]。
旁注：我遵循了您命名函数的惯例。而且，虽然我在这里没有这样做，但我发现将“宾语”和“动词”颠倒过来很有用。也就是说，而不是（例如）MakeCache 和 FreeCache，我会做：CacheMake 和 CacheFree。这样，如果有更多函数在给定的结构指针上运行，如果我们生成 all 函数的排序列表，它们将“排队”。
无论如何，我将如何释放结构：
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int u32;
#define OPT_ALLOC (1u << 0) // 1=struct has been malloc'ed
#define ALLOCME(_ptr) \
_ptr = malloc(sizeof(*_ptr))
#define ALLOCMEIF(_ptr,_opt) \
do { \
if (_ptr != NULL) { \
_ptr->_opt = 0; \
break; \
} \
ALLOCME(_ptr); \
_ptr->_opt = OPT_ALLOC; \
} while (0)
#define FREEME(_ptr) \
do { \
if (_ptr == NULL) \
break; \
free(_ptr); \
_ptr = NULL; \
} while (0)
#define FREEMEIF(_ptr,_opt) \
do { \
if (_ptr == NULL) \
break; \
if (_ptr->_opt & OPT_ALLOC) { \
free(_ptr); \
_ptr = NULL; \
} \
} while (0)
typedef struct {
u32 line_opt;
u32 valid;
u32 tag;
u32 lru;
} Line;
typedef struct {
u32 set_opt;
int set_linecount;
Line *set_lines;
} Set;
typedef struct {
u32 cache_opt;
int cache_setcount;
Set *cache_sets;
} Cache;
Line *
MakeLine(Line *line)
{
ALLOCMEIF(line,line_opt);
line->valid = 0;
line->tag = 0;
line->lru = 0;
return line;
}
Set *
MakeSet(Set *s,int nline)
{
Line *line;
ALLOCMEIF(s,set_opt);
s->set_linecount = nline;
s->set_lines = malloc(sizeof(Line) * nline);
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx) {
line = &s->set_lines[lineidx];
MakeLine(line);
}
return s;
}
Cache *
MakeCache(Cache *c,int nset,int nline)
{
Set *s;
ALLOCMEIF(c,cache_opt);
c->cache_setcount = nset;
c->cache_sets = calloc(nset,sizeof(Set));
for (int setidx = 0; setidx < c->cache_setcount; ++setidx) {
s = &c->cache_sets[setidx];
MakeSet(s,nline);
}
return c;
}
Line *
FreeLine(Line *line)
{
FREEMEIF(line,line_opt);
return line;
}
Set *
FreeSet(Set *s)
{
Line *line;
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx) {
line = &s->set_lines[lineidx];
FreeLine(line);
}
FREEME(s->set_lines);
FREEMEIF(s,set_opt);
return s;
}
Cache *
FreeCache(Cache *c)
{
Set *s;
for (int setidx = 0; setidx < c->cache_setcount; ++setidx) {
s = &c->cache_sets[setidx];
FreeSet(s);
}
FREEME(c->cache_sets);
FREEMEIF(c,cache_opt);
return c;
}
int
main(void)
{
int lines_per_set = 1;
int num_sets = 2;
Cache *c = MakeCache(NULL,num_sets,lines_per_set);
c->cache_sets[0].set_lines[0].valid = 1;
printf("%d\n", c->cache_sets[0].set_lines[0].valid);
c = FreeCache(c);
return 0;
}
我查看了 Stack Overflow 上有关深度复制结构的示例，但这些示例不适用于我的情况。我试图模拟一个简单的缓存，用户可以更改每组的设置数量和行数。但是，在设置集合时，我意识到每一行都指向相同的东西，因此当您更改集合 0 中的第 0 行时，它也会更改集合 1 中的第 0 行。关于如何使集合不具有相同行的任何建议或者更好的方法来设置缓存结构？
typedef struct Line {
unsigned int valid;
unsigned int tag;
unsigned int lru;
}Line;
typedef struct Set {
Line lines[0];
}Set;
Set *MakeSet(int n) {
Set *s;
s = malloc(sizeof s->lines *n);
return s;
}
typedef struct Cahce {
Set sets[0];
}Cache;
Cache *MakeCache(int n){
Cache *c;
c = malloc(sizeof c->sets *n);
return c;
}
int main(void) {
int lines_per_set =1;
int num_sets = 2;
Set *s = MakeSet(lines_per_set);
Line generic_line;
generic_line.valid = 0;
generic_line.tag =0;
generic_line.lru =0;
for(int i=0; i<lines_per_set; i++){
s->lines[i] = generic_line;
}
Cache *c = MakeCache(num_sets);
for(int j=0; j<num_sets; j++){
c->sets[j] = *s;
}
c->sets[0].lines[0].valid =1;
printf("%d", c->sets[1].lines[0].valid );
return 0;
}
在大多数 H/W 中，每个缓存的 集数 和每个集的 行数 是固定的。
但是，您的示例有点混乱 fixed/variable。所以，[对我来说]不清楚你想要什么复杂程度。
请注意，在下面的示例中，不是 重复 的函数。只是做初始创建。这是第一步。下面的代码应该给你一些关于如何继续的想法。
这是一个所有参数都固定的重构示例：
#include <stdio.h>
#include <stdlib.h>
enum {
LINES_PER_SET = 1,
NUM_SETS = 2
};
typedef struct {
unsigned int valid;
unsigned int tag;
unsigned int lru;
} Line;
typedef struct {
int set_linecount;
Line set_lines[LINES_PER_SET];
} Set;
typedef struct {
int cache_setcount;
Set cache_sets[NUM_SETS];
} Cache;
Cache *
MakeCache(void)
{
Cache *c;
c = calloc(1,sizeof(Cache));
return c;
}
int
main(void)
{
Cache *c = MakeCache();
c->cache_sets[0].set_lines[0].valid = 1;
printf("%d\n", c->cache_sets[0].set_lines[0].valid);
return 0;
}
这是一个允许动态定义集数和行数的重构示例：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
unsigned int valid;
unsigned int tag;
unsigned int lru;
} Line;
typedef struct {
int set_linecount;
Line *set_lines;
} Set;
typedef struct {
int cache_setcount;
Set *cache_sets;
} Cache;
Line *
MakeLine(Line *line)
{
if (line == NULL)
line = malloc(sizeof(Line));
line->valid = 0;
line->tag = 0;
line->lru = 0;
return line;
}
Set *
MakeSet(Set *s,int nline)
{
Line *line;
if (s == NULL)
s = malloc(sizeof(Set));
s->set_linecount = nline;
s->set_lines = malloc(sizeof(Line) * nline);
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx) {
line = &s->set_lines[lineidx];
MakeLine(line);
}
return s;
}
Cache *
MakeCache(Cache *c,int nset,int nline)
{
Set *s;
if (c == NULL)
c = malloc(sizeof(Cache));
c->cache_setcount = nset;
c->cache_sets = calloc(nset,sizeof(Set));
for (int setidx = 0; setidx < c->cache_setcount; ++setidx) {
s = &c->cache_sets[setidx];
MakeSet(s,nline);
}
return c;
}
int
main(void)
{
int lines_per_set = 1;
int num_sets = 2;
Cache *c = MakeCache(NULL,num_sets,lines_per_set);
c->cache_sets[0].set_lines[0].valid = 1;
printf("%d\n", c->cache_sets[0].set_lines[0].valid);
return 0;
}
这是使用额外间接级别的第三个示例：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
unsigned int valid;
unsigned int tag;
unsigned int lru;
} Line;
typedef struct {
int set_linecount;
Line **set_lines;
} Set;
typedef struct {
int cache_setcount;
Set **cache_sets;
} Cache;
Line *
MakeLine(void)
{
Line *line;
line = malloc(sizeof(Line));
line->valid = 0;
line->tag = 0;
line->lru = 0;
return line;
}
Set *
MakeSet(int nline)
{
Line *line;
Set *s;
s = malloc(sizeof(Set));
s->set_linecount = nline;
s->set_lines = malloc(sizeof(Line *) * nline);
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx)
s->set_lines[lineidx] = MakeLine();
return s;
}
Cache *
MakeCache(int nset,int nline)
{
Cache *c;
c = malloc(sizeof(Cache));
c->cache_setcount = nset;
c->cache_sets = calloc(nset,sizeof(Set *));
for (int setidx = 0; setidx < c->cache_setcount; ++setidx)
c->cache_sets[setidx] = MakeSet(nline);
return c;
}
int
main(void)
{
int lines_per_set = 1;
int num_sets = 2;
Cache *c = MakeCache(num_sets,lines_per_set);
c->cache_sets[0]->set_lines[0]->valid = 1;
printf("%d\n", c->cache_sets[0]->set_lines[0]->valid);
return 0;
}
更新：
Thank you for the explanation. I liked the second one the best. How would you free the allocated memory? I tried:
for (int i = 0; i < num_sets; i++) {
for (int j = 0; j < lines_per_set; j++)
free(c->sets[i].lines[j]);
}
free(c);
But is says that the elements in lines are not the right type. I thought they were pointers.
虽然可以一次释放所有东西，但最好使用几个子函数来完成这项工作。就像 Make* 个函数一样，我们可以创建 Free* 个函数。
一个好的格言可能是：如果函数[或语句]“看起来”过于复杂或容易出错，则可能需要将其拆分为更小的函数。
事实上，在下面的示例中，我拆分了 Make* 个函数来创建 Free* 个函数。
在最初的 Make* 函数中，函数被传递给它是 creating/initializing 的结构的指针。如果那个指针是NULL，它就是在做malloc。因此，它“知道”它是否正在执行 malloc。
这允许函数创建一个带有 malloc 的“独立”结构 [就像 MakeCache 所做的那样]，或者让该结构成为另一个结构的从属结构（例如 Set从属于 Cache，Line 从属于 Set）。这可能不是最好的方法[一个单独的“alloc”和“init”函数可能更干净]。
但是，对于 Free* 函数， 调用者 必须“告诉”函数是否执行结构指针的 free 或不是。这会很麻烦，因为调用者必须跟踪 [such] 事情。通常，跟踪是各个函数的范围。
所以，我为每个结构添加了一个额外的成员，它“记住”该结构是否已分配。然后，Free* 函数可以查看它以确定它是否可以释放它的指针。这是我在生产代码中经常使用的个人“交易技巧”。该字段可以只是一个布尔值 int（如 cache_alloced）。但是，我选择使用带有各种选项位的位掩码（例如 OPT_ALLOC）。这是为了将来需要时进行扩展。
我已经创建了一些辅助 CPP 宏来帮助实现这一点[小心你想要的，你可能真的会得到它:-)]。
您可能会注意到各种 FREEME* 宏首先检查“即将释放”指针是否为 NULL，如果是，则抑制对 free 的调用。这并不是真正必要的，因为它 是 允许使用空指针调用 free [即它是无害的。
他们做的另一件事是，在 free 之后，他们将指针设置为 NULL。这是捕获“已释放”指针的 misuse/reuse 的“安全”功能。它还可以防止 free 的“双重释放”中止（例如 free(ptr); free(ptr); 会导致这种情况）。
如果指针 未 为空，取消引用 可能会 成功并产生未定义的结果。那是 UB [未定义的行为]，但可能很难检测到。通过将指针清零，指针的任何后续取消引用都会立即触发 SIGSEGV [segfault]。
旁注：我遵循了您命名函数的惯例。而且，虽然我在这里没有这样做，但我发现将“宾语”和“动词”颠倒过来很有用。也就是说，而不是（例如）MakeCache 和 FreeCache，我会做：CacheMake 和 CacheFree。这样，如果有更多函数在给定的结构指针上运行，如果我们生成 all 函数的排序列表，它们将“排队”。
无论如何，我将如何释放结构：
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int u32;
#define OPT_ALLOC (1u << 0) // 1=struct has been malloc'ed
#define ALLOCME(_ptr) \
_ptr = malloc(sizeof(*_ptr))
#define ALLOCMEIF(_ptr,_opt) \
do { \
if (_ptr != NULL) { \
_ptr->_opt = 0; \
break; \
} \
ALLOCME(_ptr); \
_ptr->_opt = OPT_ALLOC; \
} while (0)
#define FREEME(_ptr) \
do { \
if (_ptr == NULL) \
break; \
free(_ptr); \
_ptr = NULL; \
} while (0)
#define FREEMEIF(_ptr,_opt) \
do { \
if (_ptr == NULL) \
break; \
if (_ptr->_opt & OPT_ALLOC) { \
free(_ptr); \
_ptr = NULL; \
} \
} while (0)
typedef struct {
u32 line_opt;
u32 valid;
u32 tag;
u32 lru;
} Line;
typedef struct {
u32 set_opt;
int set_linecount;
Line *set_lines;
} Set;
typedef struct {
u32 cache_opt;
int cache_setcount;
Set *cache_sets;
} Cache;
Line *
MakeLine(Line *line)
{
ALLOCMEIF(line,line_opt);
line->valid = 0;
line->tag = 0;
line->lru = 0;
return line;
}
Set *
MakeSet(Set *s,int nline)
{
Line *line;
ALLOCMEIF(s,set_opt);
s->set_linecount = nline;
s->set_lines = malloc(sizeof(Line) * nline);
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx) {
line = &s->set_lines[lineidx];
MakeLine(line);
}
return s;
}
Cache *
MakeCache(Cache *c,int nset,int nline)
{
Set *s;
ALLOCMEIF(c,cache_opt);
c->cache_setcount = nset;
c->cache_sets = calloc(nset,sizeof(Set));
for (int setidx = 0; setidx < c->cache_setcount; ++setidx) {
s = &c->cache_sets[setidx];
MakeSet(s,nline);
}
return c;
}
Line *
FreeLine(Line *line)
{
FREEMEIF(line,line_opt);
return line;
}
Set *
FreeSet(Set *s)
{
Line *line;
for (int lineidx = 0; lineidx < s->set_linecount; ++lineidx) {
line = &s->set_lines[lineidx];
FreeLine(line);
}
FREEME(s->set_lines);
FREEMEIF(s,set_opt);
return s;
}
Cache *
FreeCache(Cache *c)
{
Set *s;
for (int setidx = 0; setidx < c->cache_setcount; ++setidx) {
s = &c->cache_sets[setidx];
FreeSet(s);
}
FREEME(c->cache_sets);
FREEMEIF(c,cache_opt);
return c;
}
int
main(void)
{
int lines_per_set = 1;
int num_sets = 2;
Cache *c = MakeCache(NULL,num_sets,lines_per_set);
c->cache_sets[0].set_lines[0].valid = 1;
printf("%d\n", c->cache_sets[0].set_lines[0].valid);
c = FreeCache(c);
return 0;
}