From 1e0a04b52070e2f5fd8d476fd2d22997104315a1 Mon Sep 17 00:00:00 2001 From: Thomas Hellstrom Date: Tue, 6 Jun 2006 14:12:51 +0000 Subject: Replace the hash table list with linux hlists for better memory usage. Fix copyright statement. --- linux-core/drm_hashtab.c | 247 ++++++++++++++++++++++++----------------------- linux-core/drm_hashtab.h | 41 ++++---- linux-core/drm_mm.c | 2 +- 3 files changed, 150 insertions(+), 140 deletions(-) diff --git a/linux-core/drm_hashtab.c b/linux-core/drm_hashtab.c index 6a76d132..3be781df 100644 --- a/linux-core/drm_hashtab.c +++ b/linux-core/drm_hashtab.c @@ -1,6 +1,6 @@ /************************************************************************** * - * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. + * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA. * All Rights Reserved. * * Permission is hereby granted, free of charge, to any person obtaining a @@ -36,80 +36,90 @@ #include "drm_hashtab.h" #include -int drm_ht_create(drm_open_hash_t * ht, unsigned int order) +int +drm_ht_create(drm_open_hash_t *ht, unsigned int order) { - unsigned int i; - - ht->size = 1 << order; - ht->order = order; - ht->fill = 0; - ht->table = vmalloc(ht->size * sizeof(*ht->table)); - if (!ht->table) { - DRM_ERROR("Out of memory for hash table\n"); - return -ENOMEM; - } - for (i = 0; i < ht->size; ++i) { - INIT_LIST_HEAD(&ht->table[i]); - } - return 0; + unsigned int i; + + ht->size = 1 << order; + ht->order = order; + ht->fill = 0; + ht->table = vmalloc(ht->size*sizeof(*ht->table)); + if (!ht->table) { + DRM_ERROR("Out of memory for hash table\n"); + return -ENOMEM; + } + for (i=0; i< ht->size; ++i) { + INIT_HLIST_HEAD(&ht->table[i]); + } + return 0; } -void drm_ht_verbose_list(drm_open_hash_t * ht, unsigned long key) +void +drm_ht_verbose_list(drm_open_hash_t *ht, unsigned long key) { - drm_hash_item_t *entry; - struct list_head *list, *h_list; - unsigned int hashed_key; - int count = 0; - - hashed_key = hash_long(key, ht->order); - DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); - h_list = &ht->table[hashed_key]; - list_for_each(list, h_list) { - entry = list_entry(list, drm_hash_item_t, head); - DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key); - } + drm_hash_item_t *entry; + struct hlist_head *h_list; + struct hlist_node *list; + unsigned int hashed_key; + int count = 0; + + hashed_key = hash_long(key, ht->order); + DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); + h_list = &ht->table[hashed_key]; + hlist_for_each(list, h_list) { + entry = hlist_entry(list, drm_hash_item_t, head); + DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key); + } } -static struct list_head -*drm_ht_find_key(drm_open_hash_t * ht, unsigned long key, int *found) +static struct hlist_node +*drm_ht_find_key(drm_open_hash_t *ht, unsigned long key) { - drm_hash_item_t *entry; - struct list_head *list, *h_list, *ret; - unsigned int hashed_key; - - hashed_key = hash_long(key, ht->order); - - *found = FALSE; - h_list = &ht->table[hashed_key]; - ret = h_list; - list_for_each(list, h_list) { - entry = list_entry(list, drm_hash_item_t, head); - if (entry->key == key) { - ret = list; - *found = TRUE; - break; - } - if (entry->key > key) { - ret = list; - break; - } - } - return ret; + drm_hash_item_t *entry; + struct hlist_head *h_list; + struct hlist_node *list; + unsigned int hashed_key; + + hashed_key = hash_long(key, ht->order); + h_list = &ht->table[hashed_key]; + hlist_for_each(list, h_list) { + entry = hlist_entry(list, drm_hash_item_t, head); + if (entry->key == key) + return list; + if (entry->key > key) + break; + } + return NULL; } + -int drm_ht_insert_item(drm_open_hash_t * ht, drm_hash_item_t * item) +int +drm_ht_insert_item(drm_open_hash_t *ht, drm_hash_item_t *item) { - int found; - struct list_head *list; - - list = drm_ht_find_key(ht, item->key, &found); - if (found) { - return -EINVAL; - } else { - list_add_tail(&item->head, list); - ht->fill++; - } - return 0; + drm_hash_item_t *entry; + struct hlist_head *h_list; + struct hlist_node *list, *parent; + unsigned int hashed_key; + unsigned long key = item->key; + + hashed_key = hash_long(key, ht->order); + h_list = &ht->table[hashed_key]; + parent = NULL; + hlist_for_each(list, h_list) { + entry = hlist_entry(list, drm_hash_item_t, head); + if (entry->key == key) + return -1; + if (entry->key > key) + break; + parent = list; + } + if (parent) { + hlist_add_after(parent, &item->head); + } else { + hlist_add_head(&item->head, h_list); + } + return 0; } /* @@ -117,69 +127,68 @@ int drm_ht_insert_item(drm_open_hash_t * ht, drm_hash_item_t * item) */ int -drm_ht_just_insert_please(drm_open_hash_t * ht, drm_hash_item_t * item, - unsigned long seed, int bits) +drm_ht_just_insert_please(drm_open_hash_t *ht, drm_hash_item_t *item, + unsigned long seed, int bits) { - int ret; - unsigned long mask = (1 << bits) - 1; - unsigned long first; - - item->key = hash_long(seed, bits); - first = item->key; - do { - ret = drm_ht_insert_item(ht, item); - if (ret) - item->key = (item->key + 1) & mask; - } while (ret && (item->key != first)); - - if (ret) { - DRM_ERROR("Available key bit space exhausted\n"); - return -EINVAL; - } - return 0; + int ret; + unsigned long mask = (1 << bits) - 1; + unsigned long first; + + item->key = hash_long(seed, bits); + first = item->key; + do{ + ret = drm_ht_insert_item(ht, item); + if (ret) + item->key = (item->key + 1) & mask; + } while(ret && (item->key != first)); + + if (ret) { + DRM_ERROR("Available key bit space exhausted\n"); + return -EINVAL; + } + return 0; } - + int -drm_ht_find_item(drm_open_hash_t * ht, unsigned long key, - drm_hash_item_t ** item) +drm_ht_find_item(drm_open_hash_t *ht, unsigned long key, drm_hash_item_t **item) { - int found; - struct list_head *list; - - list = drm_ht_find_key(ht, key, &found); - if (!found) { - return -1; - } else { - *item = list_entry(list, drm_hash_item_t, head); - return 0; - } -} + struct hlist_node *list; -int drm_ht_remove_key(drm_open_hash_t * ht, unsigned long key) + list = drm_ht_find_key(ht, key); + if (!list) + return -1; + + *item = hlist_entry(list, drm_hash_item_t, head); + return 0; +} + +int +drm_ht_remove_key(drm_open_hash_t *ht, unsigned long key) { - int found; - struct list_head *list; - - list = drm_ht_find_key(ht, key, &found); - if (found) { - list_del_init(list); - ht->fill--; - return 0; - } - return -1; + struct hlist_node *list; + + list = drm_ht_find_key(ht, key); + if (list) { + hlist_del_init(list); + ht->fill--; + return 0; + } + return -1; } -int drm_ht_remove_item(drm_open_hash_t * ht, drm_hash_item_t * item) +int +drm_ht_remove_item(drm_open_hash_t *ht, drm_hash_item_t *item) { - list_del_init(&item->head); - ht->fill--; - return 0; + hlist_del_init(&item->head); + ht->fill--; + return 0; } -void drm_ht_remove(drm_open_hash_t * ht) +void drm_ht_remove(drm_open_hash_t *ht) { - if (ht->table) { - vfree(ht->table); - ht->table = NULL; - } -} + if (ht->table) { + vfree(ht->table); + ht->table = NULL; + } +} + diff --git a/linux-core/drm_hashtab.h b/linux-core/drm_hashtab.h index 3154b1a8..7f457e74 100644 --- a/linux-core/drm_hashtab.h +++ b/linux-core/drm_hashtab.h @@ -1,6 +1,6 @@ /************************************************************************** * - * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. + * Copyright 2006 Tungsten Graphics, Inc., Bismack, ND. USA. * All Rights Reserved. * * Permission is hereby granted, free of charge, to any person obtaining a @@ -35,29 +35,30 @@ #ifndef DRM_HASHTAB_H #define DRM_HASHTAB_H -typedef struct drm_hash_item { - struct list_head head; - unsigned long key; +typedef struct drm_hash_item{ + struct hlist_node head; + unsigned long key; } drm_hash_item_t; -typedef struct drm_open_hash { - unsigned int size; - unsigned int order; - unsigned int fill; - struct list_head *table; +typedef struct drm_open_hash{ + unsigned int size; + unsigned int order; + unsigned int fill; + struct hlist_head *table; } drm_open_hash_t; -extern int drm_ht_create(drm_open_hash_t * ht, unsigned int order); -extern int drm_ht_insert_item(drm_open_hash_t * ht, drm_hash_item_t * item); -extern int drm_ht_just_insert_please(drm_open_hash_t * ht, - drm_hash_item_t * item, unsigned long seed, - int bits); -extern int drm_ht_find_item(drm_open_hash_t * ht, unsigned long key, - drm_hash_item_t ** item); -extern void drm_ht_verbose_list(drm_open_hash_t * ht, unsigned long key); -extern int drm_ht_remove_key(drm_open_hash_t * ht, unsigned long key); -extern int drm_ht_remove_item(drm_open_hash_t * ht, drm_hash_item_t * item); -extern void drm_ht_remove(drm_open_hash_t * ht); +extern int drm_ht_create(drm_open_hash_t *ht, unsigned int order); +extern int drm_ht_insert_item(drm_open_hash_t *ht, drm_hash_item_t *item); +extern int drm_ht_just_insert_please(drm_open_hash_t *ht, drm_hash_item_t *item, + unsigned long seed, int bits); +extern int drm_ht_find_item(drm_open_hash_t *ht, unsigned long key, drm_hash_item_t **item); + +extern void drm_ht_verbose_list(drm_open_hash_t *ht, unsigned long key); +extern int drm_ht_remove_key(drm_open_hash_t *ht, unsigned long key); +extern int drm_ht_remove_item(drm_open_hash_t *ht, drm_hash_item_t *item); +extern void drm_ht_remove(drm_open_hash_t *ht); + #endif + diff --git a/linux-core/drm_mm.c b/linux-core/drm_mm.c index 3063c9eb..a93760f9 100644 --- a/linux-core/drm_mm.c +++ b/linux-core/drm_mm.c @@ -1,6 +1,6 @@ /************************************************************************** * - * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., Texas. + * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. * All Rights Reserved. * * Permission is hereby granted, free of charge, to any person obtaining a -- cgit v1.2.3