hash_table.c

来自「xen虚拟机源代码安装包」· C语言 代码 · 共 659 行 · 第 1/2 页

 *
 * @param z entry to free
 */
inline void HTEntry_free(HTEntry *z){
    if(z){
        deallocate(z);
    }
}

/** Free an entry in a hashtable.
 * The table's entry_free_fn is used is defined, otherwise 
 * the HTEntry itself is freed.
 *
 * @param table hashtable
 * @param entry to free
 */
inline void HashTable_free_entry(HashTable *table, HTEntry *entry){
    if(!entry) return;
    if(table && table->entry_free_fn){
        table->entry_free_fn(table, entry);
    } else {
        HTEntry_free(entry);
    }
}

/** Get the first entry satisfying a test from the bucket for the
 * given hashcode.
 *
 * @param table to look in
 * @param hashcode indicates the bucket
 * @param test_fn test to apply to elements
 * @param arg first argument to calls to test_fn
 * @return entry found, or 0
 */
inline HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
				      TableTestFn *test_fn, TableArg arg){
    HTBucket *bucket;
    HTEntry *entry = NULL;
    HTEntry *next;

    bucket = get_bucket(table, hashcode);
    for(entry = bucket->head; entry; entry = next){
        next = entry->next;
        if(test_fn(arg, table, entry)){
            break;
        }
    }
    return entry;
}

/** Test hashtable keys for equality.
 * Uses the table's key_equal_fn if defined, otherwise pointer equality.
 *
 * @param key1 key to compare
 * @param key2 key to compare
 * @return 1 if equal, 0 otherwise
 */
inline int HashTable_key_equal(HashTable *table, void *key1, void *key2){
    if(table->key_size){
        return memcmp(key1, key2, table->key_size) == 0;
    }
    return (table->key_equal_fn ? table->key_equal_fn(key1, key2) : key1 == key2);
}

/** Compute the hashcode of a hashtable key.
 * The table's key_hash_fn is used if defined, otherwise the address of
 * the key is hashed.
 *
 * @param table hashtable
 * @param key to hash
 * @return hashcode
 */
inline Hashcode HashTable_key_hash(HashTable *table, void *key){
    if(table->key_size){
        return _hash(key, table->key_size, 0);
    }
    return (table->key_hash_fn 
            ? table->key_hash_fn(key)
            : hash_hvoid(0, &key, sizeof(key)));
}

/** Test if an entry has a given key.
 *
 * @param arg containing key to test for
 * @param table the entry is in
 * @param entry to test
 * @return 1 if the entry has the key, 0 otherwise
 */
static inline int has_key(TableArg arg, HashTable *table, HTEntry *entry){
    return HashTable_key_equal(table, arg.ptr, entry->key);
}

/** Get an entry with a given key.
 *
 * @param table to search
 * @param key to look for
 * @return entry if found, null otherwise
 */
inline HTEntry * HashTable_get_entry(HashTable *table, void *key){
    Hashcode hashcode;
    HTBucket *bucket;
    HTEntry *entry = NULL;
    HTEntry *next;

    hashcode = HashTable_key_hash(table, key);
    bucket = get_bucket(table, hashcode);
    for(entry = bucket->head; entry; entry = next){
        next = entry->next;
        if(HashTable_key_equal(table, key, entry->key)){
            break;
        }
    }
    return entry;
}

/** Get the value of an entry with a given key.
 *
 * @param table to search
 * @param key to look for
 * @return value if an entry was found, null otherwise
 */
inline void * HashTable_get(HashTable *table, void *key){
    HTEntry *entry = HashTable_get_entry(table, key);
    return (entry ? entry->value : 0);
}

/** Print the buckets in a table.
 *
 * @param table to print
 */
void show_buckets(HashTable *table, IOStream *io){
    int i,j ;
    IOStream_print(io, "entry_count=%d buckets_n=%d\n", table->entry_count, table->buckets_n);
    for(i=0; i < table->buckets_n; i++){
        if(0 || table->buckets[i].count>0){
            IOStream_print(io, "bucket %3d %3d %10p ", i,
                        table->buckets[i].count,
                        table->buckets[i].head);
            for(j = table->buckets[i].count; j>0; j--){
                IOStream_print(io, "+");
            }
            IOStream_print(io, "\n");
        }
    }
    HashTable_print(table, io); 
}
    
/** Print an entry in a table.
 *
 * @param entry to print
 * @param arg a pointer to an IOStream to print to
 * @return 0
 */
static int print_entry(TableArg arg, HashTable *table, HTEntry *entry){
    IOStream *io = (IOStream*)arg.ptr;
    IOStream_print(io, " b=%4lx h=%08lx |-> e=%8p k=%8p v=%8p\n",
                entry->hashcode % table->buckets_n,
                entry->hashcode,
                entry, entry->key, entry->value);
    return 0;
}

/** Print a hash table.
 *
 * @param table to print
 */
void HashTable_print(HashTable *table, IOStream *io){
    IOStream_print(io, "{\n");
    HashTable_map(table, print_entry, (TableArg){ ptr: io });
    IOStream_print(io, "}\n");
}
/*==========================================================================*/

/** Add an entry to the bucket for the
 * given hashcode.
 *
 * @param table to insert in
 * @param hashcode indicates the bucket
 * @param key to add an entry for
 * @param value to add an entry for
 * @return entry on success, 0 on failure
 */
inline HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value){
    HTEntry *entry = HTEntry_new(hashcode, key, value);
    if(entry){
        push_on_bucket(table, hashcode, entry);
        table->entry_count++;
    }
    return entry;
}

/** Move the front entry for a bucket to the correct point in the bucket order as
 * defined by the order function. If this is called every time a new entry is added
 * the bucket will be maintained in sorted order.
 *
 * @param table to modify
 * @param hashcode indicates the bucket
 * @param order entry comparison function
 * @return 0 if an entry was moved, 1 if not
 */
int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order){
    HTEntry *new_entry = NULL, *prev = NULL, *entry = NULL;
    HTBucket *bucket;
    int err = 1;

    bucket = get_bucket(table, hashcode);
    new_entry = bucket->head;
    if(!new_entry || !new_entry->next) goto exit;
    for(entry = new_entry->next; entry; prev = entry, entry = entry->next){
        if(order(new_entry, entry) <= 0) break;
    }
    if(prev){
        err = 0;
        bucket->head = new_entry->next; 
        new_entry->next = entry;
        prev->next = new_entry;
    }
  exit:
    return err;
}

/** Add an entry to a hashtable.
 * The entry is added to the bucket for its key's hashcode.
 *
 * @param table to insert in
 * @param key to add an entry for
 * @param value to add an entry for
 * @return entry on success, 0 on failure
 */
inline HTEntry * HashTable_add(HashTable *table, void *key, void *value){
    return HashTable_add_entry(table, HashTable_key_hash(table, key), key, value);
}

/** Remove entries satisfying a test from the bucket for the
 * given hashcode. 
 *
 * @param table to remove from
 * @param hashcode indicates the bucket
 * @param test_fn test to apply to elements
 * @param arg first argument to calls to test_fn
 * @return number of entries removed
 */
inline int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
				  TableTestFn *test_fn, TableArg arg){
    HTBucket *bucket;
    HTEntry *entry, *prev = NULL, *next;
    int removed_count = 0;

    bucket = get_bucket(table, hashcode);
    for(entry = bucket->head; entry; entry = next){
        next = entry->next;
        if(test_fn(arg, table, entry)){
            if(prev){
                prev->next = next;
            } else {
                bucket->head = next;
            }
            bucket->count--;
            table->entry_count--;
            removed_count++;
            HashTable_free_entry(table, entry);
            entry = NULL;
        }
        prev = entry;
    }
    return removed_count;
}

/** Remove entries with a given key. 
 *
 * @param table to remove from
 * @param key of entries to remove
 * @return number of entries removed
 */
inline int HashTable_remove(HashTable *table, void *key){
    Hashcode hashcode;
    HTBucket *bucket;
    HTEntry *entry, *prev = NULL, *next;
    int removed_count = 0;

    hashcode = HashTable_key_hash(table, key);
    bucket = get_bucket(table, hashcode);
    for(entry = bucket->head; entry; entry = next){
        next = entry->next;
        if(HashTable_key_equal(table, key, entry->key)){
            if(prev){
                prev->next = next;
            } else {
                bucket->head = next;
            }
            bucket->count--;
            table->entry_count--;
            removed_count++;
            HashTable_free_entry(table, entry);
            entry = NULL;
        }
        prev = entry;
    }
    return removed_count;
}

/** Remove (and free) all the entries in a bucket.
 *
 * @param bucket to clear
 */
static inline void bucket_clear(HashTable *table, HTBucket *bucket){
    HTEntry *entry, *next;

    for(entry = bucket->head; entry; entry = next){
        next = entry->next;
        HashTable_free_entry(table, entry);
    }
    bucket->head = NULL;
    table->entry_count -= bucket->count;
    bucket->count = 0;
}

/** Remove (and free) all the entries in a table.
 *
 * @param table to clear
 */
void HashTable_clear(HashTable *table){
    int i, n = table->buckets_n;

    for(i = 0; i < n; i++){
        bucket_clear(table, table->buckets + i);
    }
}