70,21 → 70,25 |
|
static LIST_INITIALIZE(unused_head); |
|
/** Global hash table of all used fat_idx_t structures. */ |
static hash_table_t used_hash; |
/** |
* Global hash table of all used fat_idx_t structures. |
* The index structures are hashed by the dev_handle, parent node's first |
* cluster and index within the parent directory. |
*/ |
static hash_table_t up_hash; |
|
#define USED_HASH_BUCKETS_LOG 12 |
#define USED_HASH_BUCKETS (1 << USED_HASH_BUCKETS_LOG) |
#define UPH_BUCKETS_LOG 12 |
#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG) |
|
#define USED_HASH_DH_KEY 0 |
#define USED_HASH_PFC_KEY 1 |
#define USED_HASH_PDI_KEY 2 |
#define UPH_DH_KEY 0 |
#define UPH_PFC_KEY 1 |
#define UPH_PDI_KEY 2 |
|
static hash_index_t idx_hash(unsigned long key[]) |
static hash_index_t pos_hash(unsigned long key[]) |
{ |
dev_handle_t dev_handle = (dev_handle_t)key[USED_HASH_DH_KEY]; |
fat_cluster_t pfc = (fat_cluster_t)key[USED_HASH_PFC_KEY]; |
unsigned pdi = (unsigned)key[USED_HASH_PDI_KEY]; |
dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY]; |
fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY]; |
unsigned pdi = (unsigned)key[UPH_PDI_KEY]; |
|
hash_index_t h; |
|
99,32 → 103,78 |
* The most significant half of the most significant half of all bits |
* are the least significant bits of the device handle. |
*/ |
h = pfc & ((USED_HASH_BUCKETS_LOG / 2) - 1); |
h |= (pdi & ((USED_HASH_BUCKETS_LOG / 4) - 1)) << |
(USED_HASH_BUCKETS_LOG / 2); |
h |= (dev_handle & ((USED_HASH_BUCKETS_LOG / 4) - 1)) << |
(3 * (USED_HASH_BUCKETS_LOG / 4)); |
h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1); |
h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << |
(UPH_BUCKETS_LOG / 2); |
h |= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << |
(3 * (UPH_BUCKETS_LOG / 4)); |
|
return h; |
} |
|
static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item) |
static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item) |
{ |
dev_handle_t dev_handle = (dev_handle_t)key[USED_HASH_DH_KEY]; |
fat_cluster_t pfc = (fat_cluster_t)key[USED_HASH_PFC_KEY]; |
unsigned pdi = (unsigned)key[USED_HASH_PDI_KEY]; |
fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uh_link); |
dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY]; |
fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY]; |
unsigned pdi = (unsigned)key[UPH_PDI_KEY]; |
fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link); |
|
return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) && |
(pdi == fidx->pdi); |
} |
|
static void pos_remove_callback(link_t *item) |
{ |
/* nothing to do */ |
} |
|
static hash_table_operations_t uph_ops = { |
.hash = pos_hash, |
.compare = pos_compare, |
.remove_callback = pos_remove_callback, |
}; |
|
/** |
* Global hash table of all used fat_idx_t structures. |
* The index structures are hashed by the dev_handle and index. |
*/ |
static hash_table_t ui_hash; |
|
#define UIH_BUCKETS_LOG 12 |
#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG) |
|
#define UIH_DH_KEY 0 |
#define UIH_INDEX_KEY 1 |
|
static hash_index_t idx_hash(unsigned long key[]) |
{ |
dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY]; |
fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY]; |
|
hash_index_t h; |
|
h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1); |
h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) << |
(UIH_BUCKETS_LOG / 2); |
|
return h; |
} |
|
static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item) |
{ |
dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY]; |
fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY]; |
fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link); |
|
return (dev_handle == fidx->dev_handle) && (index == fidx->index); |
} |
|
static void idx_remove_callback(link_t *item) |
{ |
/* nothing to do */ |
} |
|
static hash_table_operations_t used_idx_ops = { |
static hash_table_operations_t uih_ops = { |
.hash = idx_hash, |
.compare = idx_compare, |
.remove_callback = idx_remove_callback, |
264,19 → 314,20 |
} |
} |
|
fat_idx_t *fat_idx_map(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi) |
fat_idx_t * |
fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi) |
{ |
fat_idx_t *fidx; |
link_t *l; |
unsigned long key[] = { |
[USED_HASH_DH_KEY] = dev_handle, |
[USED_HASH_PFC_KEY] = pfc, |
[USED_HASH_PDI_KEY] = pdi, |
unsigned long pkey[] = { |
[UPH_DH_KEY] = dev_handle, |
[UPH_PFC_KEY] = pfc, |
[UPH_PDI_KEY] = pdi, |
}; |
|
l = hash_table_find(&used_hash, key); |
l = hash_table_find(&up_hash, pkey); |
if (l) { |
fidx = hash_table_get_instance(l, fat_idx_t, uh_link); |
fidx = hash_table_get_instance(l, fat_idx_t, uph_link); |
} else { |
fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t)); |
if (!fidx) { |
286,14 → 337,41 |
free(fidx); |
return NULL; |
} |
link_initialize(&fidx->uh_link); |
|
unsigned long ikey[] = { |
[UIH_DH_KEY] = dev_handle, |
[UIH_INDEX_KEY] = fidx->index, |
}; |
|
link_initialize(&fidx->uph_link); |
link_initialize(&fidx->uih_link); |
fidx->dev_handle = dev_handle; |
fidx->pfc = pfc; |
fidx->pdi = pdi; |
fidx->nodep = NULL; |
hash_table_insert(&used_hash, key, &fidx->uh_link); |
|
hash_table_insert(&up_hash, pkey, &fidx->uph_link); |
hash_table_insert(&ui_hash, ikey, &fidx->uih_link); |
} |
|
return fidx; |
} |
|
fat_idx_t * |
fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index) |
{ |
fat_idx_t *fidx = NULL; |
link_t *l; |
unsigned long ikey[] = { |
[UIH_DH_KEY] = dev_handle, |
[UIH_INDEX_KEY] = index, |
}; |
|
l = hash_table_find(&ui_hash, ikey); |
if (l) { |
fidx = hash_table_get_instance(l, fat_idx_t, uih_link); |
} |
|
return fidx; |
} |
|