WebSVN – Kolibri OS – Diff – /drivers/video/drm/drm_hashtab.c


/**************************************************************************
 *
 * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sub license, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice (including the
 * next paragraph) shall be included in all copies or substantial portions
 * of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
 * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
 * USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 *
 **************************************************************************/
/*
 * Simple open hash tab implementation.
 *
 * Authors:
 * Thomas Hellström 
 */
 
#include 
#include 
#include 
#include 
#include 
 
 
 
 
 
 
 
 
 
 
int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
{
	unsigned int size = 1 << order;
 
	ht->order = order;
	ht->table = NULL;
    ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);
	if (!ht->table) {
		DRM_ERROR("Out of memory for hash table\n");
		return -ENOMEM;
	}
	return 0;
}
EXPORT_SYMBOL(drm_ht_create);
 
void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
{
	struct drm_hash_item *entry;
	struct hlist_head *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];
	hlist_for_each_entry(entry, h_list, head)
		DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
}
 
static struct hlist_node *drm_ht_find_key(struct drm_open_hash *ht,
					  unsigned long key)
{
	struct drm_hash_item *entry;
	struct hlist_head *h_list;
	unsigned int hashed_key;
 
	hashed_key = hash_long(key, ht->order);
	h_list = &ht->table[hashed_key];
	hlist_for_each_entry(entry, h_list, head) {
		if (entry->key == key)
			return &entry->head;
		if (entry->key > key)
			break;
	}
	return NULL;
}
 
static struct hlist_node *drm_ht_find_key_rcu(struct drm_open_hash *ht,
					      unsigned long key)
{
	struct drm_hash_item *entry;
	struct hlist_head *h_list;
	unsigned int hashed_key;
 
	hashed_key = hash_long(key, ht->order);
	h_list = &ht->table[hashed_key];
	hlist_for_each_entry_rcu(entry, h_list, head) {
		if (entry->key == key)
			return &entry->head;
		if (entry->key > key)
			break;
	}
	return NULL;
}
 
int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
{
	struct drm_hash_item *entry;
	struct hlist_head *h_list;
	struct hlist_node *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_entry(entry, h_list, head) {
		if (entry->key == key)
			return -EINVAL;
		if (entry->key > key)
			break;
		parent = &entry->head;
	}
	if (parent) {
		hlist_add_behind_rcu(&item->head, parent);
	} else {
		hlist_add_head_rcu(&item->head, h_list);
	}
	return 0;
}
EXPORT_SYMBOL(drm_ht_insert_item);
 
/*
 * Just insert an item and return any "bits" bit key that hasn't been
 * used before.
 */
int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
			      unsigned long seed, int bits, int shift,
			      unsigned long add)
{
	int ret;
	unsigned long mask = (1 << bits) - 1;
	unsigned long first, unshifted_key;
 
	unshifted_key = hash_long(seed, bits);
	first = unshifted_key;
	do {
		item->key = (unshifted_key << shift) + add;
		ret = drm_ht_insert_item(ht, item);
		if (ret)
			unshifted_key = (unshifted_key + 1) & mask;
	} while(ret && (unshifted_key != first));
 
	if (ret) {
		DRM_ERROR("Available key bit space exhausted\n");
		return -EINVAL;
	}
	return 0;
}
EXPORT_SYMBOL(drm_ht_just_insert_please);
 
int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
		     struct drm_hash_item **item)
{
	struct hlist_node *list;
 
	list = drm_ht_find_key_rcu(ht, key);
	if (!list)
		return -EINVAL;
 
	*item = hlist_entry(list, struct drm_hash_item, head);
	return 0;
}
EXPORT_SYMBOL(drm_ht_find_item);
 
int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
{
	struct hlist_node *list;
 
	list = drm_ht_find_key(ht, key);
	if (list) {
		hlist_del_init_rcu(list);
		return 0;
	}
	return -EINVAL;
}
 
int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
{
	hlist_del_init_rcu(&item->head);
	return 0;
}
EXPORT_SYMBOL(drm_ht_remove_item);
 
void drm_ht_remove(struct drm_open_hash *ht)
{
	if (ht->table) {
        kfree(ht->table);
		ht->table = NULL;
	}
}
EXPORT_SYMBOL(drm_ht_remove);

Rev 5060	Rev 7144
1	/**************************************************************************	1	/**************************************************************************
2	*	2	*
3	* Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.	3	* Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.
4	* All Rights Reserved.	4	* All Rights Reserved.
5	*	5	*
6	* Permission is hereby granted, free of charge, to any person obtaining a	6	* Permission is hereby granted, free of charge, to any person obtaining a
7	* copy of this software and associated documentation files (the	7	* copy of this software and associated documentation files (the
8	* "Software"), to deal in the Software without restriction, including	8	* "Software"), to deal in the Software without restriction, including
9	* without limitation the rights to use, copy, modify, merge, publish,	9	* without limitation the rights to use, copy, modify, merge, publish,
10	* distribute, sub license, and/or sell copies of the Software, and to	10	* distribute, sub license, and/or sell copies of the Software, and to
11	* permit persons to whom the Software is furnished to do so, subject to	11	* permit persons to whom the Software is furnished to do so, subject to
12	* the following conditions:	12	* the following conditions:
13	*	13	*
14	* The above copyright notice and this permission notice (including the	14	* The above copyright notice and this permission notice (including the
15	* next paragraph) shall be included in all copies or substantial portions	15	* next paragraph) shall be included in all copies or substantial portions
16	* of the Software.	16	* of the Software.
17	*	17	*
18	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR	18	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,	19	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20	* FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL	20	* FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
21	* THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,	21	* THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
22	* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR	22	* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
23	* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE	23	* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
24	* USE OR OTHER DEALINGS IN THE SOFTWARE.	24	* USE OR OTHER DEALINGS IN THE SOFTWARE.
25	*	25	*
26	*	26	*
27	**************************************************************************/	27	**************************************************************************/
28	/*	28	/*
29	* Simple open hash tab implementation.	29	* Simple open hash tab implementation.
30	*	30	*
31	* Authors:	31	* Authors:
32	* Thomas Hellström	32	* Thomas Hellström
33	*/	33	*/
34		34
35	#include	35	#include
36	#include	36	#include
37	#include	37	#include
38	#include	38	#include
39	#include	39	#include
40	#include	-
41		-
42	#define hlist_for_each_entry_rcu(pos, head, member) \	-
43	for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\	-
44	typeof(*(pos)), member); \	-
45	pos; \	-
46	pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\	-
47	&(pos)->member)), typeof(*(pos)), member))	-
48		-
49		40
50	int drm_ht_create(struct drm_open_hash *ht, unsigned int order)	41	int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
51	{	42	{
52	unsigned int size = 1 << order;	43	unsigned int size = 1 << order;
53		44
54	ht->order = order;	45	ht->order = order;
55	ht->table = NULL;	46	ht->table = NULL;
56	ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);	47	ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);
57	if (!ht->table) {	48	if (!ht->table) {
58	DRM_ERROR("Out of memory for hash table\n");	49	DRM_ERROR("Out of memory for hash table\n");
59	return -ENOMEM;	50	return -ENOMEM;
60	}	51	}
61	return 0;	52	return 0;
62	}	53	}
63	EXPORT_SYMBOL(drm_ht_create);	54	EXPORT_SYMBOL(drm_ht_create);
64		55
65	void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)	56	void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
66	{	57	{
67	struct drm_hash_item *entry;	58	struct drm_hash_item *entry;
68	struct hlist_head *h_list;	59	struct hlist_head *h_list;
69	unsigned int hashed_key;	60	unsigned int hashed_key;
70	int count = 0;	61	int count = 0;
71		62
72	hashed_key = hash_long(key, ht->order);	63	hashed_key = hash_long(key, ht->order);
73	DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);	64	DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
74	h_list = &ht->table[hashed_key];	65	h_list = &ht->table[hashed_key];
75	hlist_for_each_entry(entry, h_list, head)	66	hlist_for_each_entry(entry, h_list, head)
76	DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);	67	DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
77	}	68	}
78		69
79	static struct hlist_node drm_ht_find_key(struct drm_open_hash ht,	70	static struct hlist_node drm_ht_find_key(struct drm_open_hash ht,
80	unsigned long key)	71	unsigned long key)
81	{	72	{
82	struct drm_hash_item *entry;	73	struct drm_hash_item *entry;
83	struct hlist_head *h_list;	74	struct hlist_head *h_list;
84	unsigned int hashed_key;	75	unsigned int hashed_key;
85		76
86	hashed_key = hash_long(key, ht->order);	77	hashed_key = hash_long(key, ht->order);
87	h_list = &ht->table[hashed_key];	78	h_list = &ht->table[hashed_key];
88	hlist_for_each_entry(entry, h_list, head) {	79	hlist_for_each_entry(entry, h_list, head) {
89	if (entry->key == key)	80	if (entry->key == key)
90	return &entry->head;	81	return &entry->head;
91	if (entry->key > key)	82	if (entry->key > key)
92	break;	83	break;
93	}	84	}
94	return NULL;	85	return NULL;
95	}	86	}
96		87
97	static struct hlist_node drm_ht_find_key_rcu(struct drm_open_hash ht,	88	static struct hlist_node drm_ht_find_key_rcu(struct drm_open_hash ht,
98	unsigned long key)	89	unsigned long key)
99	{	90	{
100	struct drm_hash_item *entry;	91	struct drm_hash_item *entry;
101	struct hlist_head *h_list;	92	struct hlist_head *h_list;
102	unsigned int hashed_key;	93	unsigned int hashed_key;
103		94
104	hashed_key = hash_long(key, ht->order);	95	hashed_key = hash_long(key, ht->order);
105	h_list = &ht->table[hashed_key];	96	h_list = &ht->table[hashed_key];
106	hlist_for_each_entry_rcu(entry, h_list, head) {	97	hlist_for_each_entry_rcu(entry, h_list, head) {
107	if (entry->key == key)	98	if (entry->key == key)
108	return &entry->head;	99	return &entry->head;
109	if (entry->key > key)	100	if (entry->key > key)
110	break;	101	break;
111	}	102	}
112	return NULL;	103	return NULL;
113	}	104	}
114		105
115	int drm_ht_insert_item(struct drm_open_hash ht, struct drm_hash_item item)	106	int drm_ht_insert_item(struct drm_open_hash ht, struct drm_hash_item item)
116	{	107	{
117	struct drm_hash_item *entry;	108	struct drm_hash_item *entry;
118	struct hlist_head *h_list;	109	struct hlist_head *h_list;
119	struct hlist_node *parent;	110	struct hlist_node *parent;
120	unsigned int hashed_key;	111	unsigned int hashed_key;
121	unsigned long key = item->key;	112	unsigned long key = item->key;
122		113
123	hashed_key = hash_long(key, ht->order);	114	hashed_key = hash_long(key, ht->order);
124	h_list = &ht->table[hashed_key];	115	h_list = &ht->table[hashed_key];
125	parent = NULL;	116	parent = NULL;
126	hlist_for_each_entry(entry, h_list, head) {	117	hlist_for_each_entry(entry, h_list, head) {
127	if (entry->key == key)	118	if (entry->key == key)
128	return -EINVAL;	119	return -EINVAL;
129	if (entry->key > key)	120	if (entry->key > key)
130	break;	121	break;
131	parent = &entry->head;	122	parent = &entry->head;
132	}	123	}
133	if (parent) {	124	if (parent) {
134	hlist_add_behind_rcu(&item->head, parent);	125	hlist_add_behind_rcu(&item->head, parent);
135	} else {	126	} else {
136	hlist_add_head_rcu(&item->head, h_list);	127	hlist_add_head_rcu(&item->head, h_list);
137	}	128	}
138	return 0;	129	return 0;
139	}	130	}
140	EXPORT_SYMBOL(drm_ht_insert_item);	131	EXPORT_SYMBOL(drm_ht_insert_item);
141		132
142	/*	133	/*
143	* Just insert an item and return any "bits" bit key that hasn't been	134	* Just insert an item and return any "bits" bit key that hasn't been
144	* used before.	135	* used before.
145	*/	136	*/
146	int drm_ht_just_insert_please(struct drm_open_hash ht, struct drm_hash_item item,	137	int drm_ht_just_insert_please(struct drm_open_hash ht, struct drm_hash_item item,
147	unsigned long seed, int bits, int shift,	138	unsigned long seed, int bits, int shift,
148	unsigned long add)	139	unsigned long add)
149	{	140	{
150	int ret;	141	int ret;
151	unsigned long mask = (1 << bits) - 1;	142	unsigned long mask = (1 << bits) - 1;
152	unsigned long first, unshifted_key;	143	unsigned long first, unshifted_key;
153		144
154	unshifted_key = hash_long(seed, bits);	145	unshifted_key = hash_long(seed, bits);
155	first = unshifted_key;	146	first = unshifted_key;
156	do {	147	do {
157	item->key = (unshifted_key << shift) + add;	148	item->key = (unshifted_key << shift) + add;
158	ret = drm_ht_insert_item(ht, item);	149	ret = drm_ht_insert_item(ht, item);
159	if (ret)	150	if (ret)
160	unshifted_key = (unshifted_key + 1) & mask;	151	unshifted_key = (unshifted_key + 1) & mask;
161	} while(ret && (unshifted_key != first));	152	} while(ret && (unshifted_key != first));
162		153
163	if (ret) {	154	if (ret) {
164	DRM_ERROR("Available key bit space exhausted\n");	155	DRM_ERROR("Available key bit space exhausted\n");
165	return -EINVAL;	156	return -EINVAL;
166	}	157	}
167	return 0;	158	return 0;
168	}	159	}
169	EXPORT_SYMBOL(drm_ht_just_insert_please);	160	EXPORT_SYMBOL(drm_ht_just_insert_please);
170		161
171	int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,	162	int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
172	struct drm_hash_item **item)	163	struct drm_hash_item **item)
173	{	164	{
174	struct hlist_node *list;	165	struct hlist_node *list;
175		166
176	list = drm_ht_find_key_rcu(ht, key);	167	list = drm_ht_find_key_rcu(ht, key);
177	if (!list)	168	if (!list)
178	return -EINVAL;	169	return -EINVAL;
179		170
180	*item = hlist_entry(list, struct drm_hash_item, head);	171	*item = hlist_entry(list, struct drm_hash_item, head);
181	return 0;	172	return 0;
182	}	173	}
183	EXPORT_SYMBOL(drm_ht_find_item);	174	EXPORT_SYMBOL(drm_ht_find_item);
184		175
185	int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)	176	int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
186	{	177	{
187	struct hlist_node *list;	178	struct hlist_node *list;
188		179
189	list = drm_ht_find_key(ht, key);	180	list = drm_ht_find_key(ht, key);
190	if (list) {	181	if (list) {
191	hlist_del_init_rcu(list);	182	hlist_del_init_rcu(list);
192	return 0;	183	return 0;
193	}	184	}
194	return -EINVAL;	185	return -EINVAL;
195	}	186	}
196		187
197	int drm_ht_remove_item(struct drm_open_hash ht, struct drm_hash_item item)	188	int drm_ht_remove_item(struct drm_open_hash ht, struct drm_hash_item item)
198	{	189	{
199	hlist_del_init_rcu(&item->head);	190	hlist_del_init_rcu(&item->head);
200	return 0;	191	return 0;
201	}	192	}
202	EXPORT_SYMBOL(drm_ht_remove_item);	193	EXPORT_SYMBOL(drm_ht_remove_item);
203		194
204	void drm_ht_remove(struct drm_open_hash *ht)	195	void drm_ht_remove(struct drm_open_hash *ht)
205	{	196	{
206	if (ht->table) {	197	if (ht->table) {
207	kfree(ht->table);	198	kfree(ht->table);
208	ht->table = NULL;	199	ht->table = NULL;
209	}	200	}
210	}	201	}
211	EXPORT_SYMBOL(drm_ht_remove);	202	EXPORT_SYMBOL(drm_ht_remove);

Subversion Repositories Kolibri OS

(root)/drivers/video/drm/drm_hashtab.c @ 6104 – Rev 5060 → 7144