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 
#include 
 
#define hlist_for_each_entry_rcu(pos, head, member)                     \
    for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
               typeof(*(pos)), member);                        \
            pos;                                                    \
            pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
                  &(pos)->member)), typeof(*(pos)), member))
 
 
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 4104	Rev 5060
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	40	#include
41		41
42	#define hlist_for_each_entry_rcu(pos, head, member) \	42	#define hlist_for_each_entry_rcu(pos, head, member) \
43	for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\	43	for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
44	typeof(*(pos)), member); \	44	typeof(*(pos)), member); \
45	pos; \	45	pos; \
46	pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\	46	pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
47	&(pos)->member)), typeof(*(pos)), member))	47	&(pos)->member)), typeof(*(pos)), member))
48		48
49		49
50	int drm_ht_create(struct drm_open_hash *ht, unsigned int order)	50	int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
51	{	51	{
52	unsigned int size = 1 << order;	52	unsigned int size = 1 << order;
53		53
54	ht->order = order;	54	ht->order = order;
55	ht->table = NULL;	55	ht->table = NULL;
56	ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);	56	ht->table = kcalloc(size, sizeof(*ht->table), GFP_KERNEL);
57	if (!ht->table) {	57	if (!ht->table) {
58	DRM_ERROR("Out of memory for hash table\n");	58	DRM_ERROR("Out of memory for hash table\n");
59	return -ENOMEM;	59	return -ENOMEM;
60	}	60	}
61	return 0;	61	return 0;
62	}	62	}
63	EXPORT_SYMBOL(drm_ht_create);	63	EXPORT_SYMBOL(drm_ht_create);
64		64
65	void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)	65	void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
66	{	66	{
67	struct drm_hash_item *entry;	67	struct drm_hash_item *entry;
68	struct hlist_head *h_list;	68	struct hlist_head *h_list;
69	unsigned int hashed_key;	69	unsigned int hashed_key;
70	int count = 0;	70	int count = 0;
71		71
72	hashed_key = hash_long(key, ht->order);	72	hashed_key = hash_long(key, ht->order);
73	DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);	73	DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
74	h_list = &ht->table[hashed_key];	74	h_list = &ht->table[hashed_key];
75	hlist_for_each_entry(entry, h_list, head)	75	hlist_for_each_entry(entry, h_list, head)
76	DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);	76	DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
77	}	77	}
78		78
79	static struct hlist_node drm_ht_find_key(struct drm_open_hash ht,	79	static struct hlist_node drm_ht_find_key(struct drm_open_hash ht,
80	unsigned long key)	80	unsigned long key)
81	{	81	{
82	struct drm_hash_item *entry;	82	struct drm_hash_item *entry;
83	struct hlist_head *h_list;	83	struct hlist_head *h_list;
84	unsigned int hashed_key;	84	unsigned int hashed_key;
85		85
86	hashed_key = hash_long(key, ht->order);	86	hashed_key = hash_long(key, ht->order);
87	h_list = &ht->table[hashed_key];	87	h_list = &ht->table[hashed_key];
88	hlist_for_each_entry(entry, h_list, head) {	88	hlist_for_each_entry(entry, h_list, head) {
89	if (entry->key == key)	89	if (entry->key == key)
90	return &entry->head;	90	return &entry->head;
91	if (entry->key > key)	91	if (entry->key > key)
92	break;	92	break;
93	}	93	}
94	return NULL;	94	return NULL;
95	}	95	}
96		96
97	static struct hlist_node drm_ht_find_key_rcu(struct drm_open_hash ht,	97	static struct hlist_node drm_ht_find_key_rcu(struct drm_open_hash ht,
98	unsigned long key)	98	unsigned long key)
99	{	99	{
100	struct drm_hash_item *entry;	100	struct drm_hash_item *entry;
101	struct hlist_head *h_list;	101	struct hlist_head *h_list;
102	unsigned int hashed_key;	102	unsigned int hashed_key;
103		103
104	hashed_key = hash_long(key, ht->order);	104	hashed_key = hash_long(key, ht->order);
105	h_list = &ht->table[hashed_key];	105	h_list = &ht->table[hashed_key];
106	hlist_for_each_entry_rcu(entry, h_list, head) {	106	hlist_for_each_entry_rcu(entry, h_list, head) {
107	if (entry->key == key)	107	if (entry->key == key)
108	return &entry->head;	108	return &entry->head;
109	if (entry->key > key)	109	if (entry->key > key)
110	break;	110	break;
111	}	111	}
112	return NULL;	112	return NULL;
113	}	113	}
114		114
115	int drm_ht_insert_item(struct drm_open_hash ht, struct drm_hash_item item)	115	int drm_ht_insert_item(struct drm_open_hash ht, struct drm_hash_item item)
116	{	116	{
117	struct drm_hash_item *entry;	117	struct drm_hash_item *entry;
118	struct hlist_head *h_list;	118	struct hlist_head *h_list;
119	struct hlist_node *parent;	119	struct hlist_node *parent;
120	unsigned int hashed_key;	120	unsigned int hashed_key;
121	unsigned long key = item->key;	121	unsigned long key = item->key;
122		122
123	hashed_key = hash_long(key, ht->order);	123	hashed_key = hash_long(key, ht->order);
124	h_list = &ht->table[hashed_key];	124	h_list = &ht->table[hashed_key];
125	parent = NULL;	125	parent = NULL;
126	hlist_for_each_entry(entry, h_list, head) {	126	hlist_for_each_entry(entry, h_list, head) {
127	if (entry->key == key)	127	if (entry->key == key)
128	return -EINVAL;	128	return -EINVAL;
129	if (entry->key > key)	129	if (entry->key > key)
130	break;	130	break;
131	parent = &entry->head;	131	parent = &entry->head;
132	}	132	}
133	if (parent) {	133	if (parent) {
134	hlist_add_after_rcu(parent, &item->head);	134	hlist_add_behind_rcu(&item->head, parent);
135	} else {	135	} else {
136	hlist_add_head_rcu(&item->head, h_list);	136	hlist_add_head_rcu(&item->head, h_list);
137	}	137	}
138	return 0;	138	return 0;
139	}	139	}
140	EXPORT_SYMBOL(drm_ht_insert_item);	140	EXPORT_SYMBOL(drm_ht_insert_item);
141		141
142	/*	142	/*
143	* Just insert an item and return any "bits" bit key that hasn't been	143	* Just insert an item and return any "bits" bit key that hasn't been
144	* used before.	144	* used before.
145	*/	145	*/
146	int drm_ht_just_insert_please(struct drm_open_hash ht, struct drm_hash_item item,	146	int drm_ht_just_insert_please(struct drm_open_hash ht, struct drm_hash_item item,
147	unsigned long seed, int bits, int shift,	147	unsigned long seed, int bits, int shift,
148	unsigned long add)	148	unsigned long add)
149	{	149	{
150	int ret;	150	int ret;
151	unsigned long mask = (1 << bits) - 1;	151	unsigned long mask = (1 << bits) - 1;
152	unsigned long first, unshifted_key;	152	unsigned long first, unshifted_key;
153		153
154	unshifted_key = hash_long(seed, bits);	154	unshifted_key = hash_long(seed, bits);
155	first = unshifted_key;	155	first = unshifted_key;
156	do {	156	do {
157	item->key = (unshifted_key << shift) + add;	157	item->key = (unshifted_key << shift) + add;
158	ret = drm_ht_insert_item(ht, item);	158	ret = drm_ht_insert_item(ht, item);
159	if (ret)	159	if (ret)
160	unshifted_key = (unshifted_key + 1) & mask;	160	unshifted_key = (unshifted_key + 1) & mask;
161	} while(ret && (unshifted_key != first));	161	} while(ret && (unshifted_key != first));
162		162
163	if (ret) {	163	if (ret) {
164	DRM_ERROR("Available key bit space exhausted\n");	164	DRM_ERROR("Available key bit space exhausted\n");
165	return -EINVAL;	165	return -EINVAL;
166	}	166	}
167	return 0;	167	return 0;
168	}	168	}
169	EXPORT_SYMBOL(drm_ht_just_insert_please);	169	EXPORT_SYMBOL(drm_ht_just_insert_please);
170		170
171	int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,	171	int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
172	struct drm_hash_item **item)	172	struct drm_hash_item **item)
173	{	173	{
174	struct hlist_node *list;	174	struct hlist_node *list;
175		175
176	list = drm_ht_find_key_rcu(ht, key);	176	list = drm_ht_find_key_rcu(ht, key);
177	if (!list)	177	if (!list)
178	return -EINVAL;	178	return -EINVAL;
179		179
180	*item = hlist_entry(list, struct drm_hash_item, head);	180	*item = hlist_entry(list, struct drm_hash_item, head);
181	return 0;	181	return 0;
182	}	182	}
183	EXPORT_SYMBOL(drm_ht_find_item);	183	EXPORT_SYMBOL(drm_ht_find_item);
184		184
185	int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)	185	int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
186	{	186	{
187	struct hlist_node *list;	187	struct hlist_node *list;
188		188
189	list = drm_ht_find_key(ht, key);	189	list = drm_ht_find_key(ht, key);
190	if (list) {	190	if (list) {
191	hlist_del_init_rcu(list);	191	hlist_del_init_rcu(list);
192	return 0;	192	return 0;
193	}	193	}
194	return -EINVAL;	194	return -EINVAL;
195	}	195	}
196		196
197	int drm_ht_remove_item(struct drm_open_hash ht, struct drm_hash_item item)	197	int drm_ht_remove_item(struct drm_open_hash ht, struct drm_hash_item item)
198	{	198	{
199	hlist_del_init_rcu(&item->head);	199	hlist_del_init_rcu(&item->head);
200	return 0;	200	return 0;
201	}	201	}
202	EXPORT_SYMBOL(drm_ht_remove_item);	202	EXPORT_SYMBOL(drm_ht_remove_item);
203		203
204	void drm_ht_remove(struct drm_open_hash *ht)	204	void drm_ht_remove(struct drm_open_hash *ht)
205	{	205	{
206	if (ht->table) {	206	if (ht->table) {
207	kfree(ht->table);	207	kfree(ht->table);
208	ht->table = NULL;	208	ht->table = NULL;
209	}	209	}
210	}	210	}
211	EXPORT_SYMBOL(drm_ht_remove);	211	EXPORT_SYMBOL(drm_ht_remove);

Subversion Repositories Kolibri OS

(root)/drivers/video/drm/drm_hashtab.c – Rev 4104 → 5060