diff options
| author | Justus Winter <4winter@informatik.uni-hamburg.de> | 2015-03-18 12:25:26 +0100 |
|---|---|---|
| committer | Justus Winter <4winter@informatik.uni-hamburg.de> | 2015-05-20 11:08:29 +0200 |
| commit | 5a00790518773385e681e6430a4f85245fae957d (patch) | |
| tree | 739a06f7b8184b06c099d6c364f84f0927ad20aa /ipc/ipc_entry.h | |
| parent | aac601ac36c623247a51d442b2d6438b042d7515 (diff) | |
ipc: replace reverse hash table with a radix tree
Currently, there is a hash table mapping (space, object) tuples to
`ipc_entry' objects. This hash table is intertwined with the IPC
tables. There is one hash table per IPC space, but it is only for the
entries in the IPC table. This hash table is called `local' in the
source. All IPC entries being spilled into the splay tree are instead
mapped by a global hash table.
Replace the local (i.e. per IPC space) reverse hash table with a radix
tree.
* ipc/ipc_entry.c (ipc_entry_grow_table): Adjust accordingly.
* ipc/ipc_entry.h (struct ipc_entry): Adjust comment.
* ipc/ipc_hash.c: Adjust comment explaining the local lookup table.
(IPC_LOCAL_HASH_INVARIANT): New macro.
(ipc_hash_local_lookup): Use the new `ipc_reverse_lookup' function.
(ipc_hash_local_insert): Use the new `ipc_reverse_insert' function.
(ipc_hash_local_delete): Use the new `ipc_reverse_remove' function.
* ipc/ipc_space.c (ipc_space_create): Initialize radix tree.
(ipc_space_destroy): Free radix tree.
* ipc/ipc_space.h (struct ipc_space): Add radix tree.
(ipc_reverse_insert): New function.
(ipc_reverse_remove): Likewise.
(ipc_reverse_remove_all): Likewise.
(ipc_reverse_lookup): Likewise.
* ipc/ipc_right.c (ipc_right_clean): Update comment.
Diffstat (limited to 'ipc/ipc_entry.h')
| -rw-r--r-- | ipc/ipc_entry.h | 5 |
1 files changed, 0 insertions, 5 deletions
diff --git a/ipc/ipc_entry.h b/ipc/ipc_entry.h index cb6d3f9..0caa70b 100644 --- a/ipc/ipc_entry.h +++ b/ipc/ipc_entry.h @@ -54,11 +54,6 @@ * those entries. The cutoff point between the table and the tree * is adjusted dynamically to minimize memory consumption. * - * The ie_index field of entries in the table implements - * a ordered hash table with open addressing and linear probing. - * This hash table converts (space, object) -> name. - * It is used independently of the other fields. - * * Free (unallocated) entries in the table have null ie_object * fields. The ie_bits field is zero except for IE_BITS_GEN. * The ie_next (ie_request) field links free entries into a free list. |