Replace the hash table list with linux hlists for better memory usage. Fixdrm-sman-branch

    copyright statement.

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 <linux/hash.h>
 
-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