title: Creating a unique identifier - pure C
body: <p>I'm writing a toy OS and I need a way to create a unique identifier (like Windows' <code>HANDLE</code> 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 GUID<sup><b>1</b></sup> as follows:</p>
  
  <pre><code>//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;
  </code></pre>
  
  <p>I have another structure that associates a GUID with actual data, but for the purposes of this post it isn't really that important:</p>
  
  <pre><code>typedef struct
    {
    GUID guid;
    void *data;
    } GUIDTblEntry;
  </code></pre>
  
  <p>My kernel will hopefully support <code>2<sup>10</sup> - 1 = 1023</code> types of GUIDs, with a maximum of <code>2<sup>22</sup> - 1 = 4194303</code> unique instances of each type of GUID (which is more than enough, right?).  I subtract one because I want <code>0</code> to be an illegal value for the <code>.type</code> field and the <code>.id</code> field.  My problem is that I have no idea how to develop an algorithm that will uniquely fill out the <code>.id</code> field of each <code>GUID</code> 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 <code>u32</code> 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?</p>
  
  <p>Would it be better to just give the user a pointer to the actual data, since this is guaranteed to be unique, and use <code>typedef void* GUID</code>to let the API user know I don't want them messing with my data?  Or do I need the abstraction the GUID provides?</p>
  
  <p><b>1)</b> This is in no way related to the <a href="http://en.wikipedia.org/wiki/GUID" rel="nofollow">GUID standard</a>. 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.</p>