0

我正在编写一个玩具操作系统，我需要一种创建唯一标识符的方法（如 WindowsHANDLE除外）。这需要是纯 C/ASM 数学；如果可能的话，我不想依赖任何东西，甚至是 C 标准库。我目前有一个存储 32 位 GUID 1的数据结构，如下所示：

//u32 = unsigned 32-bit integer, and so on
typedef union
  {
  struct { u32 type : 10; u32 id : 22; }; //Okay in C99 with gcc -fms-extensions
  u32 guid;
  } GUID;

我有另一个将 GUID 与实际数据相关联的结构，但就本文而言，它并不是那么重要：

typedef struct
  {
  GUID guid;
  void *data;
  } GUIDTblEntry;

我的内核有望支持各种类型的 GUID，每种类型的 GUID 最多具有唯一实例（这已经足够了，对吗？）。我减去一个是因为我想成为字段和字段的非法值。我的问题是我不知道如何开发一种算法来唯一地填充内核创建的每个字段。我能想到的唯一算法是随机选择一个 id，然后查看该 id 是否用于我要创建的特定 GUID 类。但是，我必须对所有为该特定类型创建的 GUID 进行排序，以查看它是否被占用，如果是，则重新执行整个操作。我也想过有一个数组210 - 1 = 1023222 - 1 = 41943030.type.id.idGUIDu32每种使用的 GUID 类型都有一个（我确定我不会有 1023 种类型），并且每次我想要一个 GUID 时只增加适当的数字，但是当我创建 4194303 个特定的 GUID 时会发生什么类型？

只给用户一个指向实际数据的指针会更好吗，因为这保证是唯一的，并typedef void* GUID用来让 API 用户知道我不希望他们弄乱我的数据？还是我需要 GUID 提供的抽象？

1)这与GUID 标准无关。我独立想出了这个名字，当我发现实际上有一个叫做 GUID 的东西时，我试着想出一个新名字，但还没有成功。

4

1 回答 1

1

这是一个动态索引算法：

// variables
int instanceCount = 0;
int* recycler = malloc(sizeof *recycler);

// allocate index
int index = recycler[0];
if (!index) {
    index = (instanceCount+=1);
    recycler = realloc(recycler, (instanceCount+1) * sizeof *recycler);
    recycler[instanceCount] = 0;
} else {
    recycler[0] = recycler[index];
}

// deallocate index
recycler[index] = recycler[0];
recycler[0] = index;

// on initialization
recycler[0] = 0;

我希望这有帮助。很长一段时间以来，我一直在使用类似的算法。

如果这没有帮助，那么我为浪费您的时间而道歉。

编辑

澄清一下，我是一名 C++ 程序员，所以我不是 100% 知道 C 世界中不存在什么，所以如果出现任何错误，请随时纠正我。

编辑

我刚刚对其进行了彻底的测试，并且效果很好。在分配任何新 id 之前，将填补所有空白。

于 2012-09-16T18:16:27.313 回答