6

我正在为我的 hashmap 数据结构设计一个迭代器接口。当前的设计如下所示：

// map.h
typedef struct map_iterator map_iterator;

// map.c
struct map_iterator
{
    // Implementation details
};

// client.c
map *m = map_new();
map_iterator *it = map_iterator_new(m);
void *key, *value;
while (map_iterator_next(it, &key, &value)) {
    // Use key, value
}
map_iterator_free(it);

但是，这需要为迭代器对象分配堆，并且客户端必须记住在完成后释放迭代器。如果我map_iterator_new返回堆栈上的迭代器，代码如下所示：

// map.h
typedef struct map_iterator
{
    // Implementation details
};

// client.c
map *m = map_new();
map_iterator it = map_iterator_new(m);
void *key, *value;
while (map_iterator_next(&it, &key, &value)) {
    // Use key, value
}

但是，这要求我map_iterator向客户端代码提供结构的定义（否则我会收到不完整的类型错误）。我想隐藏这个定义，只提供声明。

有没有办法做到这一点？本质上，我正在寻找一种方法来告诉客户端代码“此结构占用 X 字节，因此您可以在堆栈上分配它，但我不会告诉您如何访问它的成员”。

编辑：请仅使用标准 C！（没有编译器扩展/特定于平台的功能）

4

3 回答 3

2

使用序列化。

您始终可以将 T 的对象复制到 unsigned char 数组，然后再复制回 T 类型的对象。该对象将与原始对象相同。T 可以是任何对象类型，这可以通过自动存储持续时间（堆栈）来完成：

int value = 568;
unsigned char store[sizeof( int )];
memcpy( store , &value , sizeof( int ) );
int other;
memcpy( &other , store , sizeof( int ) );
assert( other == value ),

这可以（ab）用于向用户隐藏实现。定义两个结构，一个定义实际实现并且对用户不可见，另一个是可见的并且仅包含适当大小的 unsigned char 数组。

实现.c

#include "implementation.h"

struct invisible
{
    int element1;
    char element2
    float element3;
    void** element4;
};

_Static_assert( sizeof( struct invisible ) <= VISIBLE_SIZE );

struct visible New( void )
{
    struct invisible i = { 1 , '2' , 3.0F , NULL };
    struct visible v = { 0 };
    memcpy( &v , &i , sizeof(i) );
    return v;
}

void Next( struct visible* v )
{
    struct invisible i = { 0 };
    memcpy( &i , &v , sizeof(i) );
    i.element1++;    //make some changes
    const int next = i.element;  
    memcpy( &v , &i , sizeof(i) );
    return next;
}

实现.h

#define VISIBLE_SIZE 24    //make sure it greater or equal to the size of struct invisible
struct visible
{
    unsigned char[VISIBLE_SIZE];
};

struct visible New( void );
int Next( struct visible* v );

用户.c

#include "implementation.h"

void Func( void )
{
    struct visible v = New();
    while( 1 )
    {
         const int next = Next( &v );
         if( next == 10 )
         {
              break;
         }
         printf( "%d\n" , next );
    }
}

这个例子只涉及成员element1。在实际实现中，您可以自由修改不可见的结构。

于 2016-06-27T14:51:07.980 回答
2

简短的回答：没有好的方法。最好的办法是坚持让 API 返回调用者释放的对象。

长答案：这是一种替代方法，允许对不透明对象进行堆栈分配。有一些警告：

  1. 您需要知道实际对象的大小
  2. 您需要了解您的机器和工具包的对齐要求（一点点）
    • 字段对齐
    • 结构的结束填充，以实现字段对齐

警告 1 可以通过使用实用程序函数来打印大小（不导出到用户 API）以及用于捕获错误的断言来处理。

警告 2 可以通过在用户可见定义中添加具有最严格对齐要求的类型的元素来处理（尽管它不必在同一个位置。）

保持对齐避免了使用@2501 的答案中使用的序列化的需要。

在下面的示例中，您可以忽略“// trivial implementation”注释下方的代码。他们只是提供一个完整的工作示例，但算法与 OP 无关。

地图.h

#include <stdlib.h>

#define MAP_ITER_SIZE 16

typedef struct {
  void *p;          // force alignment to match implementation
  char space[MAP_ITER_SIZE-sizeof(void*)];
} map_iterator;

typedef struct map map;

map *map_new(void);
void map_iterator_init(map_iterator *iter, map *m);
int map_iterator_next(map_iterator *iter, int *p_key);

map_user.c

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

int main(int argc, char * argv[])
{
    map_iterator it;
    int key;

    map *m = map_new();
    map_iterator_init(&it, m);
    while (map_iterator_next(&it, &key)) {
        printf("%d\n", key);
    }
}

地图.c

#include <stdlib.h>
#include <assert.h>
#include "map.h"

#define INITIAL_KEY (-1)

struct map {
    int key_count;
    int first_key;
};

// Keep struct size consistent with MAP_ITER_SIZE in map.h
typedef struct {
    map *m;
    int cur_key;
} map_iterator_impl;

map *map_new(void) {
    map *m = malloc(sizeof(struct map));

    // trivial implementation for example only
    m->key_count = 2;
    m->first_key = 10;
}

void map_iterator_init(map_iterator *iter, map *m)
{
    map_iterator_impl *iter_impl = (map_iterator_impl *)iter;

    assert(sizeof(map_iterator) == sizeof(map_iterator_impl)); // optimizes out

    // trivial implementation for example only
    iter_impl->m = m;
    iter_impl->cur_key = INITIAL_KEY;      // not a valid key
}

int map_iterator_next(map_iterator *iter, int *p_key)
{
    map_iterator_impl *iter_impl = (map_iterator_impl *)iter;

    // trivial implementation for example only
    if (iter_impl->cur_key == INITIAL_KEY) {
        iter_impl->cur_key = iter_impl->m->first_key;
    } else {
        ++iter_impl->cur_key;
    }

    if (iter_impl->cur_key - iter_impl->m->first_key >= iter_impl->m->key_count) {
        return 0;
    }

    *p_key = iter_impl->cur_key;
    return 1;
}

unsigned int get_impl_size()
{
    return (unsigned int) sizeof(map_iterator_impl);
}

权威人士会反对这一点，他们会有很好的观点。主要论点是代码不可移植，除非跳过箍以使所有支持的（处理器，编译器）情况下的 SIZE 常量都正确。对于每种情况，您还需要知道哪种数据类型具有最大的对齐要求。

于 2020-02-26T17:12:20.643 回答
-2

有一个名为alloca的函数，它在调用者的堆栈上保留内存。所以你的代码可能看起来像：

// map.h
typedef struct map_iterator map_iterator;
extern int map_iterator_size;
// map.c
struct map_iterator
{
    // Implementation details
};
int map_iterator_size = sizeof(struct map_iterator);
// client.c
map *m = map_new();
map_iterator *it = alloca(map_iterator_size);
map_iterator_new(m, it);
void *key, *value;
while (map_iterator_next(it, &key, &value)) {
    // Use key, value
}
于 2016-06-27T10:00:43.250 回答