Subversion Repositories HelenOS

Rev

Rev 2889 | Rev 2945 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2889 Rev 2890
Line 68... Line 68...
68
    link_t      freed_head;
68
    link_t      freed_head;
69
} unused_t;
69
} unused_t;
70
 
70
 
71
static LIST_INITIALIZE(unused_head);
71
static LIST_INITIALIZE(unused_head);
72
 
72
 
-
 
73
/**
73
/** Global hash table of all used fat_idx_t structures. */
74
 * Global hash table of all used fat_idx_t structures.
-
 
75
 * The index structures are hashed by the dev_handle, parent node's first
-
 
76
 * cluster and index within the parent directory.
-
 
77
 */
74
static hash_table_t used_hash;
78
static hash_table_t up_hash;
-
 
79
 
-
 
80
#define UPH_BUCKETS_LOG 12
-
 
81
#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)
-
 
82
 
-
 
83
#define UPH_DH_KEY  0
-
 
84
#define UPH_PFC_KEY 1
-
 
85
#define UPH_PDI_KEY 2
75
 
86
 
76
#define USED_HASH_BUCKETS_LOG   12
-
 
77
#define USED_HASH_BUCKETS   (1 << USED_HASH_BUCKETS_LOG)
-
 
78
 
-
 
79
#define USED_HASH_DH_KEY    0
-
 
80
#define USED_HASH_PFC_KEY   1
-
 
81
#define USED_HASH_PDI_KEY   2
-
 
82
 
-
 
83
static hash_index_t idx_hash(unsigned long key[])
87
static hash_index_t pos_hash(unsigned long key[])
84
{
88
{
85
    dev_handle_t dev_handle = (dev_handle_t)key[USED_HASH_DH_KEY];
89
    dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
86
    fat_cluster_t pfc = (fat_cluster_t)key[USED_HASH_PFC_KEY];
90
    fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
87
    unsigned pdi = (unsigned)key[USED_HASH_PDI_KEY];
91
    unsigned pdi = (unsigned)key[UPH_PDI_KEY];
88
 
92
 
89
    hash_index_t h;
93
    hash_index_t h;
90
 
94
 
91
    /*
95
    /*
92
     * The least significant half of all bits are the least significant bits
96
     * The least significant half of all bits are the least significant bits
Line 97... Line 101...
97
     * parent directory node.
101
     * parent directory node.
98
     *
102
     *
99
     * The most significant half of the most significant half of all bits
103
     * The most significant half of the most significant half of all bits
100
     * are the least significant bits of the device handle.
104
     * are the least significant bits of the device handle.
101
     */
105
     */
102
    h = pfc & ((USED_HASH_BUCKETS_LOG / 2) - 1);
106
    h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
103
    h |= (pdi & ((USED_HASH_BUCKETS_LOG / 4) - 1)) <<
107
    h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
104
        (USED_HASH_BUCKETS_LOG / 2);
108
        (UPH_BUCKETS_LOG / 2);
105
    h |= (dev_handle & ((USED_HASH_BUCKETS_LOG / 4) - 1)) <<
109
    h |= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
106
        (3 * (USED_HASH_BUCKETS_LOG / 4));
110
        (3 * (UPH_BUCKETS_LOG / 4));
107
 
111
 
108
    return h;
112
    return h;
109
}
113
}
110
 
114
 
111
static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
115
static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
112
{
116
{
113
    dev_handle_t dev_handle = (dev_handle_t)key[USED_HASH_DH_KEY];
117
    dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
114
    fat_cluster_t pfc = (fat_cluster_t)key[USED_HASH_PFC_KEY];
118
    fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
115
    unsigned pdi = (unsigned)key[USED_HASH_PDI_KEY];
119
    unsigned pdi = (unsigned)key[UPH_PDI_KEY];
116
    fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uh_link);
120
    fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
117
 
121
 
118
    return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&
122
    return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&
119
        (pdi == fidx->pdi);
123
        (pdi == fidx->pdi);
120
}
124
}
121
 
125
 
-
 
126
static void pos_remove_callback(link_t *item)
-
 
127
{
-
 
128
    /* nothing to do */
-
 
129
}
-
 
130
 
-
 
131
static hash_table_operations_t uph_ops = {
-
 
132
    .hash = pos_hash,
-
 
133
    .compare = pos_compare,
-
 
134
    .remove_callback = pos_remove_callback,
-
 
135
};
-
 
136
 
-
 
137
/**
-
 
138
 * Global hash table of all used fat_idx_t structures.
-
 
139
 * The index structures are hashed by the dev_handle and index.
-
 
140
 */
-
 
141
static hash_table_t ui_hash;
-
 
142
 
-
 
143
#define UIH_BUCKETS_LOG 12
-
 
144
#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)
-
 
145
 
-
 
146
#define UIH_DH_KEY  0
-
 
147
#define UIH_INDEX_KEY   1
-
 
148
 
-
 
149
static hash_index_t idx_hash(unsigned long key[])
-
 
150
{
-
 
151
    dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
-
 
152
    fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
-
 
153
 
-
 
154
    hash_index_t h;
-
 
155
 
-
 
156
    h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
-
 
157
    h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
-
 
158
        (UIH_BUCKETS_LOG / 2);
-
 
159
 
-
 
160
    return h;
-
 
161
}
-
 
162
 
-
 
163
static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
-
 
164
{
-
 
165
    dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
-
 
166
    fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
-
 
167
    fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
-
 
168
 
-
 
169
    return (dev_handle == fidx->dev_handle) && (index == fidx->index);
-
 
170
}
-
 
171
 
122
static void idx_remove_callback(link_t *item)
172
static void idx_remove_callback(link_t *item)
123
{
173
{
124
    /* nothing to do */
174
    /* nothing to do */
125
}
175
}
126
 
176
 
127
static hash_table_operations_t used_idx_ops = {
177
static hash_table_operations_t uih_ops = {
128
    .hash = idx_hash,
178
    .hash = idx_hash,
129
    .compare = idx_compare,
179
    .compare = idx_compare,
130
    .remove_callback = idx_remove_callback,
180
    .remove_callback = idx_remove_callback,
131
};
181
};
132
 
182
 
Line 262... Line 312...
262
        n->last = index;
312
        n->last = index;
263
        list_append(&n->link, &u->freed_head);
313
        list_append(&n->link, &u->freed_head);
264
    }
314
    }
265
}
315
}
266
 
316
 
-
 
317
fat_idx_t *
267
fat_idx_t *fat_idx_map(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
318
fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
268
{
319
{
269
    fat_idx_t *fidx;
320
    fat_idx_t *fidx;
270
    link_t *l;
321
    link_t *l;
271
    unsigned long key[] = {
322
    unsigned long pkey[] = {
272
        [USED_HASH_DH_KEY] = dev_handle,
323
        [UPH_DH_KEY] = dev_handle,
273
        [USED_HASH_PFC_KEY] = pfc,
324
        [UPH_PFC_KEY] = pfc,
274
        [USED_HASH_PDI_KEY] = pdi,
325
        [UPH_PDI_KEY] = pdi,
275
    };
326
    };
276
 
327
 
277
    l = hash_table_find(&used_hash, key);
328
    l = hash_table_find(&up_hash, pkey);
278
    if (l) {
329
    if (l) {
279
        fidx = hash_table_get_instance(l, fat_idx_t, uh_link);
330
        fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
280
    } else {
331
    } else {
281
        fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
332
        fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
282
        if (!fidx) {
333
        if (!fidx) {
283
            return NULL;
334
            return NULL;
284
        }
335
        }
285
        if (!fat_idx_alloc(dev_handle, &fidx->index)) {
336
        if (!fat_idx_alloc(dev_handle, &fidx->index)) {
286
            free(fidx);
337
            free(fidx);
287
            return NULL;
338
            return NULL;
288
        }
339
        }
-
 
340
       
-
 
341
        unsigned long ikey[] = {
-
 
342
            [UIH_DH_KEY] = dev_handle,
-
 
343
            [UIH_INDEX_KEY] = fidx->index,
-
 
344
        };
-
 
345
   
-
 
346
        link_initialize(&fidx->uph_link);
289
        link_initialize(&fidx->uh_link);
347
        link_initialize(&fidx->uih_link);
290
        fidx->dev_handle = dev_handle;
348
        fidx->dev_handle = dev_handle;
291
        fidx->pfc = pfc;
349
        fidx->pfc = pfc;
292
        fidx->pdi = pdi;
350
        fidx->pdi = pdi;
293
        fidx->nodep = NULL;
351
        fidx->nodep = NULL;
-
 
352
 
294
        hash_table_insert(&used_hash, key, &fidx->uh_link);
353
        hash_table_insert(&up_hash, pkey, &fidx->uph_link);
-
 
354
        hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
-
 
355
    }
-
 
356
 
-
 
357
    return fidx;
-
 
358
}
-
 
359
 
-
 
360
fat_idx_t *
-
 
361
fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)
-
 
362
{
-
 
363
    fat_idx_t *fidx = NULL;
-
 
364
    link_t *l;
-
 
365
    unsigned long ikey[] = {
-
 
366
        [UIH_DH_KEY] = dev_handle,
-
 
367
        [UIH_INDEX_KEY] = index,
-
 
368
    };
-
 
369
 
-
 
370
    l = hash_table_find(&ui_hash, ikey);
-
 
371
    if (l) {
-
 
372
        fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
295
    }
373
    }
296
 
374
 
297
    return fidx;
375
    return fidx;
298
}
376
}
299
 
377