Search code examples
cuniqueidentifierid-generation

Creating a unique identifier - pure C

I'm writing a toy OS and I need a way to create a unique identifier (like Windows' HANDLE except not). This needs to be pure C/ASM mathematics; I don't want reliance on anything, not even the C standard library, if possible. I currently have a data structure that stores a 32-bit GUID1 as follows:

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

I have another structure that associates a GUID with actual data, but for the purposes of this post it isn't really that important:

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

My kernel will hopefully support 210 - 1 = 1023 types of GUIDs, with a maximum of 222 - 1 = 4194303 unique instances of each type of GUID (which is more than enough, right?). I subtract one because I want 0 to be an illegal value for the .type field and the .id field. My problem is that I have no idea how to develop an algorithm that will uniquely fill out the .id field of each GUID the kernel creates. The only algorithm I could think of would be to choose an id at random, then see if that id is taken for that particular class of GUID I want to create. But then I'd have to sort through all the GUIDs created of that particular type to see if it's taken, then if it is, do the whole thing all over again. I also thought of having an array of u32 where there's one for each used type of GUID (I'm sure I won't have 1023 types), and just increment the appropriate number each time I want a GUID, but then what happens when I've created 4194303 GUIDs of a particular type?

Would it be better to just give the user a pointer to the actual data, since this is guaranteed to be unique, and use typedef void* GUIDto let the API user know I don't want them messing with my data? Or do I need the abstraction the GUID provides?

1) This is in no way related to the GUID standard. I came up with this name independently, and when I discovered that there actually is something called a GUID, I tried coming up with a new name, but haven't had any success yet.

Solution

  • Here's a dynamic indexing algorithm:

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

    I hope this helps. I've been using similar algorithms for quite a long time.

    If this doesn't help, then I apologize for wasting your time.

    Edit

    Just to clarify, I'm a C++ programmer, so I'm not 100% aware of what is non-existent in the world of C, so feel free to correct me if any errors come up.

    Edit

    I have just thoroughly tested it and it works perfectly. All gaps will be filled before any new ids are allocated.