title: data structure for page-aligned entries
body: <p>I need to store many page-aligned entries, each entry is page-sized; basically I need to collect/bind together memory pages. The only requirement that I need to be able to check whether entry already exists upon adding by matching the machine-word-sized key. It is not possible to override the entry; if the same key is used, the existing entry must be found.</p>
  
  <p>The function to add/replace the entry receives some machine-word-sized key (32/64 bits), checks if there is a page-aligned entry which contains the same key. If there is no entry, it is created via mmap, and is added with the required key. The C declaration of the entry looks like this:</p>
  
  <pre><code>struct entry {
      uintptr_t key; /* machine-word-sized key */
      unsigned char meta[]; /* this space may be used for storing in data structure */
  };
  </code></pre>
  
  <p>The caller receives the key and takes the decision whether to use the existing entry or to allocate a new one. That is, the key must be looked up, and pages must be just collected to allow removal in a loop.</p>
  
  <p>All I need are adding the entry and removing all entries (no specific order imposed); since I use each entry as epoll.data.ptr, I don't need even fast lookup after adding the entry. Given that each entry has some space for meta-data, I'm OK to dedicate some of this space to payload required to store the entry in the data structure.</p>
  
  <p>I thought about using a hash table. I have no math or crypto background, so generating a good hash is a problem. I tried looking at several well-known hashes, but it seems that they are quite generic, i.e. intended to work with any data. However, my case seems to be very specific: there is no way user would use the table directly and conditions (page-aligned and page-sized entries plus word-sized key) are unlikely to change.</p>
  
  <p>The questions are:</p>
  
  <ol>
  <li>Am I right that hash table is OK for this case? If yes, what kind of hash would you suggest? If the hash table is linked-list based, it'd better be intrusive (i.e. all required meta is better to be inside the entry, not outside, like Linux kernel's <code>struct list_head</code>).</li>
  <li>I was also looking at page tables, like described at <a href="https://wiki.osdev.org/Paging" rel="nofollow noreferrer">https://wiki.osdev.org/Paging</a>. However, it concentrates mostly on how MMU does its job, and I'm not sure whether I can adopt it to purely software implementation and how can I apply these concepts. Since machine-word-sized key must be used for inserting the entry, the concepts from this link only show how to organize pages effectively for page-to-page mappings.</li>
  </ol>
  
  <p>I currently need to care only of 4096-bytes pages, but generic case is better (i.e. some algorithm which operates on PAGE_SIZE, be it 4K, 8K or whatever). It would be also nice the data structure does not assume page-sized (though page-aligned is a strict requirement, since all memory is obtained via mmap).</p>