← Back to branch summary

~ubuntu-branches/ubuntu/hardy/openmpi/hardy-updates

« back to all changes in this revision

Viewing changes to opal/class/opal_hash_table.c

  • Committer: Bazaar Package Importer
  • Author(s): Mark Hymers
  • Date: 2006-10-15 00:46:11 UTC
  • Revision ID: james.westby@ubuntu.com-20061015004611-uuhxnaxyjmuxfd5h
Tags: upstream-1.1
Import upstream version 1.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
opal/class/opal_hash_table.c
 
1
/*
 
2
 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
 
3
 *                         University Research and Technology
 
4
 *                         Corporation.  All rights reserved.
 
5
 * Copyright (c) 2004-2005 The University of Tennessee and The University
 
6
 *                         of Tennessee Research Foundation.  All rights
 
7
 *                         reserved.
 
8
 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, 
 
9
 *                         University of Stuttgart.  All rights reserved.
 
10
 * Copyright (c) 2004-2005 The Regents of the University of California.
 
11
 *                         All rights reserved.
 
12
 * $COPYRIGHT$
 
13
 * 
 
14
 * Additional copyrights may follow
 
15
 * 
 
16
 * $HEADER$
 
17
 */
 
18
 
 
19
#include "opal_config.h"
 
20
 
 
21
#include <string.h>
 
22
#include <stdlib.h>
 
23
 
 
24
#include "opal/util/output.h"
 
25
#include "opal/class/opal_list.h"
 
26
#include "opal/class/opal_hash_table.h"
 
27
#include "opal/constants.h"
 
28
 
 
29
/*
 
30
 * opal_hash_table_t
 
31
 */
 
32
 
 
33
#define HASH_MULTIPLIER 31
 
34
 
 
35
static void opal_hash_table_construct(opal_hash_table_t* ht);
 
36
static void opal_hash_table_destruct(opal_hash_table_t* ht);
 
37
 
 
38
 
 
39
OBJ_CLASS_INSTANCE(
 
40
    opal_hash_table_t, 
 
41
    opal_object_t,
 
42
    opal_hash_table_construct,
 
43
    opal_hash_table_destruct
 
44
);
 
45
 
 
46
 
 
47
static void opal_hash_table_construct(opal_hash_table_t* ht)
 
48
{
 
49
    OBJ_CONSTRUCT(&ht->ht_nodes, opal_list_t);
 
50
    ht->ht_table = NULL;
 
51
    ht->ht_table_size = 0;
 
52
    ht->ht_size = 0;
 
53
}
 
54
 
 
55
 
 
56
static void opal_hash_table_destruct(opal_hash_table_t* ht)
 
57
{
 
58
    size_t i;
 
59
    opal_hash_table_remove_all(ht);
 
60
    for(i=0; i<ht->ht_table_size; i++) {
 
61
        OBJ_DESTRUCT(ht->ht_table+i);
 
62
    }
 
63
    if(NULL != ht->ht_table) {
 
64
        free(ht->ht_table);
 
65
    }
 
66
    OBJ_DESTRUCT(&ht->ht_nodes);
 
67
}
 
68
 
 
69
 
 
70
int opal_hash_table_init(opal_hash_table_t* ht, size_t table_size)
 
71
{
 
72
    size_t i;
 
73
    size_t power2 = 1;
 
74
    size_t tmp = table_size;
 
75
    while(tmp) {
 
76
       tmp >>= 1;
 
77
       power2 <<= 1;
 
78
    }
 
79
 
 
80
    ht->ht_mask = power2-1;
 
81
    ht->ht_table = (opal_list_t *)malloc(power2 * sizeof(opal_list_t));
 
82
    if(NULL == ht->ht_table) {
 
83
        return OPAL_ERR_OUT_OF_RESOURCE;
 
84
    }
 
85
    for(i=ht->ht_table_size; i<power2; i++) {
 
86
        opal_list_t* list = ht->ht_table+i;
 
87
        OBJ_CONSTRUCT(list, opal_list_t);
 
88
    }
 
89
    ht->ht_table_size = power2;
 
90
    return OPAL_SUCCESS;
 
91
}
 
92
 
 
93
int opal_hash_table_remove_all(opal_hash_table_t* ht)
 
94
{
 
95
    size_t i;
 
96
    for(i=0; i<ht->ht_table_size; i++) {
 
97
        opal_list_t* list = ht->ht_table+i;
 
98
        while(opal_list_get_size(list)) {
 
99
            opal_list_item_t *item = opal_list_remove_first(list);
 
100
            OBJ_RELEASE(item);
 
101
        }
 
102
    }
 
103
 
 
104
    while(opal_list_get_size(&ht->ht_nodes)) {
 
105
        opal_list_item_t* item = opal_list_remove_first(&ht->ht_nodes);
 
106
        OBJ_RELEASE(item);
 
107
    }
 
108
    ht->ht_size = 0;
 
109
    return OPAL_SUCCESS;
 
110
}
 
111
 
 
112
/***************************************************************************/
 
113
 
 
114
/*
 
115
 *  opal_uint32_hash_node_t
 
116
 */
 
117
 
 
118
struct opal_uint32_hash_node_t
 
119
{
 
120
    opal_list_item_t super;
 
121
    uint32_t hn_key;
 
122
    void *hn_value;
 
123
};
 
124
typedef struct opal_uint32_hash_node_t opal_uint32_hash_node_t;
 
125
 
 
126
static OBJ_CLASS_INSTANCE(opal_uint32_hash_node_t,
 
127
                          opal_list_item_t,
 
128
                          NULL,
 
129
                          NULL);
 
130
 
 
131
 
 
132
int opal_hash_table_get_value_uint32(opal_hash_table_t* ht, uint32_t key,
 
133
                                     void **ptr)
 
134
{
 
135
    opal_list_t* list = ht->ht_table + (key & ht->ht_mask);
 
136
    opal_uint32_hash_node_t *node;
 
137
 
 
138
#if OMPI_ENABLE_DEBUG
 
139
    if(ht->ht_table_size == 0) {
 
140
        opal_output(0, "opal_hash_table_get_value_uint32:"
 
141
                   "opal_hash_table_init() has not been called");
 
142
        return OPAL_ERROR;
 
143
    }
 
144
#endif
 
145
    for(node =  (opal_uint32_hash_node_t*)opal_list_get_first(list);
 
146
        node != (opal_uint32_hash_node_t*)opal_list_get_end(list);
 
147
        node =  (opal_uint32_hash_node_t*)opal_list_get_next(node)) {
 
148
        if (node->hn_key == key) {
 
149
            *ptr = node->hn_value;
 
150
            return OPAL_SUCCESS;
 
151
        }
 
152
    } 
 
153
    return OPAL_ERR_NOT_FOUND;
 
154
}
 
155
 
 
156
 
 
157
int opal_hash_table_set_value_uint32(opal_hash_table_t* ht,
 
158
                                    uint32_t key, void* value)
 
159
{
 
160
    opal_list_t* list = ht->ht_table + (key & ht->ht_mask);
 
161
    opal_uint32_hash_node_t *node;
 
162
 
 
163
#if OMPI_ENABLE_DEBUG
 
164
    if(ht->ht_table_size == 0) {
 
165
        opal_output(0, "opal_hash_table_set_value_uint32:"
 
166
                   "opal_hash_table_init() has not been called");
 
167
        return OPAL_ERR_BAD_PARAM;
 
168
    }
 
169
#endif
 
170
    for(node =  (opal_uint32_hash_node_t*)opal_list_get_first(list);
 
171
        node != (opal_uint32_hash_node_t*)opal_list_get_end(list);
 
172
        node =  (opal_uint32_hash_node_t*)opal_list_get_next(node)) {
 
173
        if (node->hn_key == key) {
 
174
            node->hn_value = value;
 
175
            return OPAL_SUCCESS;
 
176
        }
 
177
    } 
 
178
 
 
179
    node = (opal_uint32_hash_node_t*)opal_list_remove_first(&ht->ht_nodes); 
 
180
    if(NULL == node) {
 
181
        node = OBJ_NEW(opal_uint32_hash_node_t);
 
182
        if(NULL == node)
 
183
            return OPAL_ERR_OUT_OF_RESOURCE;
 
184
    }
 
185
    node->hn_key = key;
 
186
    node->hn_value = value;
 
187
    opal_list_append(list, (opal_list_item_t*)node);
 
188
    ht->ht_size++;
 
189
    return OPAL_SUCCESS;
 
190
}
 
191
 
 
192
 
 
193
int opal_hash_table_remove_value_uint32(opal_hash_table_t* ht, uint32_t key)
 
194
{
 
195
    opal_list_t* list = ht->ht_table + (key & ht->ht_mask);
 
196
    opal_uint32_hash_node_t *node;
 
197
 
 
198
#if OMPI_ENABLE_DEBUG
 
199
    if(ht->ht_table_size == 0) {
 
200
        opal_output(0, "opal_hash_table_remove_value_uint32:"
 
201
                   "opal_hash_table_init() has not been called");
 
202
        return OPAL_ERR_BAD_PARAM;
 
203
    }
 
204
#endif
 
205
    for(node =  (opal_uint32_hash_node_t*)opal_list_get_first(list);
 
206
        node != (opal_uint32_hash_node_t*)opal_list_get_end(list);
 
207
        node =  (opal_uint32_hash_node_t*)opal_list_get_next(node)) {
 
208
        if (node->hn_key == key) {
 
209
            opal_list_remove_item(list, (opal_list_item_t*)node);
 
210
            opal_list_append(&ht->ht_nodes, (opal_list_item_t*)node);
 
211
            ht->ht_size--;
 
212
            return OPAL_SUCCESS;
 
213
        }
 
214
    } 
 
215
    return OPAL_ERR_NOT_FOUND;
 
216
}
 
217
 
 
218
/***************************************************************************/
 
219
 
 
220
/*
 
221
 *  opal_uint64_hash_node_t
 
222
 */
 
223
 
 
224
struct opal_uint64_hash_node_t
 
225
{
 
226
    opal_list_item_t super;
 
227
    uint64_t hn_key;
 
228
    void* hn_value;
 
229
};
 
230
typedef struct opal_uint64_hash_node_t opal_uint64_hash_node_t;
 
231
 
 
232
static OBJ_CLASS_INSTANCE(opal_uint64_hash_node_t,
 
233
                          opal_list_item_t,
 
234
                          NULL,
 
235
                          NULL);
 
236
 
 
237
 
 
238
int opal_hash_table_get_value_uint64(opal_hash_table_t* ht, uint64_t key,
 
239
                                     void **ptr)
 
240
{
 
241
    opal_list_t* list = ht->ht_table + (key & ht->ht_mask);
 
242
    opal_uint64_hash_node_t *node;
 
243
 
 
244
#if OMPI_ENABLE_DEBUG
 
245
    if(ht->ht_table_size == 0) {
 
246
        opal_output(0, "opal_hash_table_get_value_uint64:"
 
247
                   "opal_hash_table_init() has not been called");
 
248
        return OPAL_ERROR;
 
249
    }
 
250
#endif
 
251
    for(node =  (opal_uint64_hash_node_t*)opal_list_get_first(list);
 
252
        node != (opal_uint64_hash_node_t*)opal_list_get_end(list);
 
253
        node =  (opal_uint64_hash_node_t*)opal_list_get_next(node)) {
 
254
        if (node->hn_key == key) {
 
255
            *ptr = node->hn_value;
 
256
            return OPAL_SUCCESS;
 
257
        }
 
258
    } 
 
259
    return OPAL_ERR_NOT_FOUND;
 
260
}
 
261
 
 
262
 
 
263
int opal_hash_table_set_value_uint64(opal_hash_table_t* ht,
 
264
                                    uint64_t key, void* value)
 
265
{
 
266
    opal_list_t* list = ht->ht_table + (key & ht->ht_mask);
 
267
    opal_uint64_hash_node_t *node;
 
268
 
 
269
#if OMPI_ENABLE_DEBUG
 
270
    if(ht->ht_table_size == 0) {
 
271
        opal_output(0, "opal_hash_table_set_value_uint64:"
 
272
                   "opal_hash_table_init() has not been called");
 
273
        return OPAL_ERR_BAD_PARAM;
 
274
    }
 
275
#endif
 
276
    for(node =  (opal_uint64_hash_node_t*)opal_list_get_first(list);
 
277
        node != (opal_uint64_hash_node_t*)opal_list_get_end(list);
 
278
        node =  (opal_uint64_hash_node_t*)opal_list_get_next(node)) {
 
279
        if (node->hn_key == key) {
 
280
            node->hn_value = value;
 
281
            return OPAL_SUCCESS;
 
282
        }
 
283
    } 
 
284
 
 
285
    node = (opal_uint64_hash_node_t*)opal_list_remove_first(&ht->ht_nodes); 
 
286
    if(NULL == node) {
 
287
        node = OBJ_NEW(opal_uint64_hash_node_t);
 
288
        if(NULL == node) {
 
289
            return OPAL_ERR_OUT_OF_RESOURCE;
 
290
        }
 
291
    }
 
292
    node->hn_key = key;
 
293
    node->hn_value = value;
 
294
    opal_list_append(list, (opal_list_item_t*)node);
 
295
    ht->ht_size++;
 
296
    return OPAL_SUCCESS;
 
297
}
 
298
 
 
299
 
 
300
int opal_hash_table_remove_value_uint64(opal_hash_table_t* ht, uint64_t key)
 
301
{
 
302
    opal_list_t* list = ht->ht_table + (key & ht->ht_mask);
 
303
    opal_uint64_hash_node_t *node;
 
304
 
 
305
#if OMPI_ENABLE_DEBUG
 
306
    if(ht->ht_table_size == 0) {
 
307
        opal_output(0, "opal_hash_table_remove_value_uint64:"
 
308
                   "opal_hash_table_init() has not been called");
 
309
        return OPAL_ERR_BAD_PARAM;
 
310
    }
 
311
#endif
 
312
    for(node =  (opal_uint64_hash_node_t*)opal_list_get_first(list);
 
313
        node != (opal_uint64_hash_node_t*)opal_list_get_end(list);
 
314
        node =  (opal_uint64_hash_node_t*)opal_list_get_next(node)) {
 
315
        if (node->hn_key == key) {
 
316
            opal_list_remove_item(list, (opal_list_item_t*)node);
 
317
            opal_list_append(&ht->ht_nodes, (opal_list_item_t*)node);
 
318
            ht->ht_size--;
 
319
            return OPAL_SUCCESS;
 
320
        }
 
321
    } 
 
322
    return OPAL_ERR_NOT_FOUND;
 
323
}
 
324
 
 
325
/***************************************************************************/
 
326
 
 
327
/*
 
328
 *  opal_ptr_hash_node_t
 
329
 */
 
330
 
 
331
struct opal_ptr_hash_node_t
 
332
{
 
333
    opal_list_item_t super;
 
334
    void*  hn_key;
 
335
    size_t hn_key_size;
 
336
    void*  hn_value;
 
337
};
 
338
typedef struct opal_ptr_hash_node_t opal_ptr_hash_node_t;
 
339
 
 
340
static void opal_ptr_hash_node_construct(opal_ptr_hash_node_t* hn)
 
341
{
 
342
    hn->hn_key_size = 0;
 
343
    hn->hn_key = NULL;
 
344
    hn->hn_value = NULL;
 
345
}
 
346
 
 
347
static void opal_ptr_hash_node_destruct(opal_ptr_hash_node_t* hn)
 
348
{
 
349
    if(NULL != hn->hn_key) {
 
350
        free(hn->hn_key);
 
351
    }
 
352
}
 
353
 
 
354
static OBJ_CLASS_INSTANCE(opal_ptr_hash_node_t,
 
355
                          opal_list_item_t,
 
356
                          opal_ptr_hash_node_construct,
 
357
                          opal_ptr_hash_node_destruct);
 
358
 
 
359
 
 
360
static inline uint32_t opal_hash_value(size_t mask, const void *key,
 
361
                                       uint32_t keysize)
 
362
{
 
363
    uint32_t h, i;
 
364
    const unsigned char *p;
 
365
    
 
366
    h = 0;
 
367
    p = (const unsigned char *)key;
 
368
    for (i = 0; i < keysize; i++, p++)
 
369
        h = HASH_MULTIPLIER*h + *p;
 
370
    return (h & mask);
 
371
}
 
372
 
 
373
int opal_hash_table_get_value_ptr(opal_hash_table_t* ht, const void* key,
 
374
                                  size_t key_size, void **ptr)
 
375
{
 
376
    opal_list_t* list = ht->ht_table + opal_hash_value(ht->ht_mask, key, 
 
377
                                                       key_size);
 
378
    opal_ptr_hash_node_t *node;
 
379
 
 
380
#if OMPI_ENABLE_DEBUG
 
381
    if(ht->ht_table_size == 0) {
 
382
        opal_output(0, "opal_hash_table_get_value_ptr:"
 
383
                   "opal_hash_table_init() has not been called");
 
384
        return OPAL_ERROR;
 
385
    }
 
386
#endif
 
387
    for(node =  (opal_ptr_hash_node_t*)opal_list_get_first(list);
 
388
        node != (opal_ptr_hash_node_t*)opal_list_get_end(list);
 
389
        node =  (opal_ptr_hash_node_t*)opal_list_get_next(node)) {
 
390
        if (node->hn_key_size == key_size &&
 
391
            memcmp(node->hn_key, key, key_size) == 0) {
 
392
            *ptr = node->hn_value;
 
393
            return OPAL_SUCCESS;
 
394
        }
 
395
    } 
 
396
    return OPAL_ERR_NOT_FOUND;
 
397
}
 
398
 
 
399
 
 
400
int opal_hash_table_set_value_ptr(opal_hash_table_t* ht, const void* key,
 
401
                                  size_t key_size, void* value)
 
402
{
 
403
    opal_list_t* list = ht->ht_table + opal_hash_value(ht->ht_mask, key,
 
404
                                                       key_size);
 
405
    opal_ptr_hash_node_t *node;
 
406
 
 
407
#if OMPI_ENABLE_DEBUG
 
408
    if(ht->ht_table_size == 0) {
 
409
        opal_output(0, "opal_hash_table_set_value_ptr:"
 
410
                   "opal_hash_table_init() has not been called");
 
411
        return OPAL_ERR_BAD_PARAM;
 
412
    }
 
413
#endif
 
414
    for(node =  (opal_ptr_hash_node_t*)opal_list_get_first(list);
 
415
        node != (opal_ptr_hash_node_t*)opal_list_get_end(list);
 
416
        node =  (opal_ptr_hash_node_t*)opal_list_get_next(node)) {
 
417
        if (node->hn_key_size == key_size &&
 
418
            memcmp(node->hn_key, key, key_size) == 0) {
 
419
            node->hn_value = value;
 
420
            return OPAL_SUCCESS;
 
421
        }
 
422
    } 
 
423
 
 
424
    node = (opal_ptr_hash_node_t*)opal_list_remove_first(&ht->ht_nodes); 
 
425
    if(NULL == node) {
 
426
        node = OBJ_NEW(opal_ptr_hash_node_t);
 
427
        if(NULL == node) {
 
428
            return OPAL_ERR_OUT_OF_RESOURCE;
 
429
        }
 
430
    }
 
431
    node->hn_key = malloc(key_size);
 
432
    node->hn_key_size = key_size;
 
433
    node->hn_value = value;
 
434
    memcpy(node->hn_key, key, key_size);
 
435
    opal_list_append(list, (opal_list_item_t*)node);
 
436
    ht->ht_size++;
 
437
    return OPAL_SUCCESS;
 
438
}
 
439
 
 
440
 
 
441
int opal_hash_table_remove_value_ptr(opal_hash_table_t* ht,
 
442
                                     const void* key, size_t key_size)
 
443
{
 
444
    opal_list_t* list = ht->ht_table + opal_hash_value(ht->ht_mask,
 
445
                                                       key, key_size);
 
446
    opal_ptr_hash_node_t *node;
 
447
 
 
448
#if OMPI_ENABLE_DEBUG
 
449
    if(ht->ht_table_size == 0) {
 
450
        opal_output(0, "opal_hash_table_remove_value_ptr: "
 
451
                   "opal_hash_table_init() has not been called");
 
452
        return OPAL_ERR_BAD_PARAM;
 
453
    }
 
454
#endif
 
455
    for(node =  (opal_ptr_hash_node_t*)opal_list_get_first(list);
 
456
        node != (opal_ptr_hash_node_t*)opal_list_get_end(list);
 
457
        node =  (opal_ptr_hash_node_t*)opal_list_get_next(node)) {
 
458
        if (node->hn_key_size == key_size &&
 
459
            memcmp(node->hn_key, key, key_size) == 0) {
 
460
            free(node->hn_key);
 
461
            node->hn_key = NULL;
 
462
            node->hn_key_size = 0;
 
463
            opal_list_remove_item(list, (opal_list_item_t*)node);
 
464
            opal_list_append(&ht->ht_nodes, (opal_list_item_t*)node);
 
465
            ht->ht_size--;
 
466
            return OPAL_SUCCESS;
 
467
        }
 
468
    } 
 
469
 return OPAL_ERR_NOT_FOUND;
 
470
}
 
471
 
 
472
 
 
473
int 
 
474
opal_hash_table_get_first_key_uint32(opal_hash_table_t *ht, uint32_t *key, 
 
475
                                     void **value, void **node)
 
476
{
 
477
    size_t i;
 
478
    opal_uint32_hash_node_t *list_node;
 
479
 
 
480
    /* Go through all the lists and return the first element off the
 
481
       first non-empty list */
 
482
    
 
483
    for (i = 0; i < ht->ht_table_size; ++i) {
 
484
        if (opal_list_get_size(ht->ht_table + i) > 0) {
 
485
            list_node = (opal_uint32_hash_node_t*)
 
486
                opal_list_get_first(ht->ht_table + i);
 
487
            *node = list_node;
 
488
            *key = list_node->hn_key;
 
489
            *value = list_node->hn_value;
 
490
            return OPAL_SUCCESS;
 
491
        }
 
492
    }
 
493
 
 
494
    /* The hash table is empty */
 
495
 
 
496
    return OPAL_ERROR;
 
497
}
 
498
 
 
499
 
 
500
int 
 
501
opal_hash_table_get_next_key_uint32(opal_hash_table_t *ht, uint32_t *key,
 
502
                                    void **value, void *in_node, 
 
503
                                    void **out_node)
 
504
{
 
505
    size_t i;
 
506
    opal_list_t *list;
 
507
    opal_list_item_t *item;
 
508
    opal_uint32_hash_node_t *next;
 
509
 
 
510
    /* Try to simply get the next value in the list.  If there isn't
 
511
       one, find the next non-empty list and take the first value */
 
512
 
 
513
    next = (opal_uint32_hash_node_t*) in_node;
 
514
    list = ht->ht_table + (next->hn_key & ht->ht_mask);
 
515
    item = opal_list_get_next(next);
 
516
    if (opal_list_get_end(list) == item) {
 
517
        item = NULL;
 
518
        for (i = (list - ht->ht_table) + 1; i < ht->ht_table_size; ++i) {
 
519
            if (opal_list_get_size(ht->ht_table + i) > 0) {
 
520
                item = opal_list_get_first(ht->ht_table + i);
 
521
                break;
 
522
            }
 
523
        }
 
524
 
 
525
        /* If we didn't find another non-empty list after this one,
 
526
           then we're at the end of the hash table */
 
527
 
 
528
        if (NULL == item) {
 
529
            return OPAL_ERROR;
 
530
        }
 
531
    }
 
532
 
 
533
    /* We found it.  Save the values (use "next" to avoid some
 
534
       typecasting) */
 
535
 
 
536
    *out_node = (void *) item;
 
537
    next = (opal_uint32_hash_node_t *) *out_node;
 
538
    *key = next->hn_key;
 
539
    *value = next->hn_value;
 
540
 
 
541
    return OPAL_SUCCESS;
 
542
}
 
543
 
 
544
 
 
545
int 
 
546
opal_hash_table_get_first_key_uint64(opal_hash_table_t *ht, uint64_t *key,
 
547
                                     void **value, void **node)
 
548
{
 
549
    size_t i;
 
550
    opal_uint64_hash_node_t *list_node;
 
551
 
 
552
    /* Go through all the lists and return the first element off the
 
553
       first non-empty list */
 
554
    
 
555
    for (i = 0; i < ht->ht_table_size; ++i) {
 
556
        if (opal_list_get_size(ht->ht_table + i) > 0) {
 
557
            list_node = (opal_uint64_hash_node_t*)
 
558
                opal_list_get_first(ht->ht_table + i);
 
559
            *node = list_node;
 
560
            *key = list_node->hn_key;
 
561
            *value = list_node->hn_value;
 
562
            return OPAL_SUCCESS;
 
563
        }
 
564
    }
 
565
 
 
566
    /* The hash table is empty */
 
567
 
 
568
    return OPAL_ERROR;
 
569
}
 
570
 
 
571
 
 
572
int 
 
573
opal_hash_table_get_next_key_uint64(opal_hash_table_t *ht, uint64_t *key,
 
574
                                    void **value, void *in_node, 
 
575
                                    void **out_node)
 
576
{
 
577
    size_t i;
 
578
    opal_list_t *list;
 
579
    opal_list_item_t *item;
 
580
    opal_uint64_hash_node_t *next;
 
581
 
 
582
    /* Try to simply get the next value in the list.  If there isn't
 
583
       one, find the next non-empty list and take the first value */
 
584
 
 
585
    next = (opal_uint64_hash_node_t*) in_node;
 
586
    list = ht->ht_table + (next->hn_key & ht->ht_mask);
 
587
    item = opal_list_get_next(next);
 
588
    if (opal_list_get_end(list) == item) {
 
589
        item = NULL;
 
590
        for (i = (list - ht->ht_table) + 1; i < ht->ht_table_size; ++i) {
 
591
            if (opal_list_get_size(ht->ht_table + i) > 0) {
 
592
                item = opal_list_get_first(ht->ht_table + i);
 
593
                break;
 
594
            }
 
595
        }
 
596
 
 
597
        /* If we didn't find another non-empty list after this one,
 
598
           then we're at the end of the hash table */
 
599
 
 
600
        if (NULL == item) {
 
601
            return OPAL_ERROR;
 
602
        }
 
603
    }
 
604
 
 
605
    /* We found it.  Save the values (use "next" to avoid some
 
606
       typecasting) */
 
607
 
 
608
    *out_node = (void *) item;
 
609
    next = (opal_uint64_hash_node_t *) *out_node;
 
610
    *key = next->hn_key;
 
611
    *value = next->hn_value;
 
612
 
 
613
    return OPAL_SUCCESS;
 
614
}