irqueue.c

linux 内核源代码

	if ( name )
		hashv = hash( name );
	bin = GET_HASHBIN( hashv );

	/* Synchronize */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */

	/*
	 * Store name and key
	 */
	entry->q_hash = hashv;
	if ( name )
		strlcpy( entry->q_name, name, sizeof(entry->q_name));

	/*
	 * Insert new entry first
	 */
	enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ],
		       entry);
	hashbin->hb_size++;

	/* Release lock */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */
}
EXPORT_SYMBOL(hashbin_insert);

/*
 *  Function hashbin_remove_first (hashbin)
 *
 *    Remove first entry of the hashbin
 *
 * Note : this function no longer use hashbin_remove(), but does things
 * similar to hashbin_remove_this(), so can be considered safe.
 * Jean II
 */
void *hashbin_remove_first( hashbin_t *hashbin)
{
	unsigned long flags = 0;
	irda_queue_t *entry = NULL;

	/* Synchronize */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */

	entry = hashbin_get_first( hashbin);
	if ( entry != NULL) {
		int	bin;
		long	hashv;
		/*
		 * Locate hashbin
		 */
		hashv = entry->q_hash;
		bin = GET_HASHBIN( hashv );

		/*
		 * Dequeue the entry...
		 */
		dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
				 (irda_queue_t*) entry );
		hashbin->hb_size--;
		entry->q_next = NULL;
		entry->q_prev = NULL;

		/*
		 *  Check if this item is the currently selected item, and in
		 *  that case we must reset hb_current
		 */
		if ( entry == hashbin->hb_current)
			hashbin->hb_current = NULL;
	}

	/* Release lock */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */

	return entry;
}


/*
 *  Function hashbin_remove (hashbin, hashv, name)
 *
 *    Remove entry with the given name
 *
 *  The use of this function is highly discouraged, because the whole
 *  concept behind hashbin_remove() is broken. In many cases, it's not
 *  possible to guarantee the unicity of the index (either hashv or name),
 *  leading to removing the WRONG entry.
 *  The only simple safe use is :
 *		hashbin_remove(hasbin, (int) self, NULL);
 *  In other case, you must think hard to guarantee unicity of the index.
 *  Jean II
 */
void* hashbin_remove( hashbin_t* hashbin, long hashv, const char* name)
{
	int bin, found = FALSE;
	unsigned long flags = 0;
	irda_queue_t* entry;

	IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);

	IRDA_ASSERT( hashbin != NULL, return NULL;);
	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);

	/*
	 * Locate hashbin
	 */
	if ( name )
		hashv = hash( name );
	bin = GET_HASHBIN( hashv );

	/* Synchronize */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */

	/*
	 * Search for entry
	 */
	entry = hashbin->hb_queue[ bin ];
	if ( entry ) {
		do {
			/*
			 * Check for key
			 */
			if ( entry->q_hash == hashv ) {
				/*
				 * Name compare too?
				 */
				if ( name ) {
					if ( strcmp( entry->q_name, name) == 0)
					{
						found = TRUE;
						break;
					}
				} else {
					found = TRUE;
					break;
				}
			}
			entry = entry->q_next;
		} while ( entry != hashbin->hb_queue[ bin ] );
	}

	/*
	 * If entry was found, dequeue it
	 */
	if ( found ) {
		dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
				 (irda_queue_t*) entry );
		hashbin->hb_size--;

		/*
		 *  Check if this item is the currently selected item, and in
		 *  that case we must reset hb_current
		 */
		if ( entry == hashbin->hb_current)
			hashbin->hb_current = NULL;
	}

	/* Release lock */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */


	/* Return */
	if ( found )
		return entry;
	else
		return NULL;

}
EXPORT_SYMBOL(hashbin_remove);

/*
 *  Function hashbin_remove_this (hashbin, entry)
 *
 *    Remove entry with the given name
 *
 * In some cases, the user of hashbin can't guarantee the unicity
 * of either the hashv or name.
 * In those cases, using the above function is guaranteed to cause troubles,
 * so we use this one instead...
 * And by the way, it's also faster, because we skip the search phase ;-)
 */
void* hashbin_remove_this( hashbin_t* hashbin, irda_queue_t* entry)
{
	unsigned long flags = 0;
	int	bin;
	long	hashv;

	IRDA_DEBUG( 4, "%s()\n", __FUNCTION__);

	IRDA_ASSERT( hashbin != NULL, return NULL;);
	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
	IRDA_ASSERT( entry != NULL, return NULL;);

	/* Synchronize */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */

	/* Check if valid and not already removed... */
	if((entry->q_next == NULL) || (entry->q_prev == NULL)) {
		entry = NULL;
		goto out;
	}

	/*
	 * Locate hashbin
	 */
	hashv = entry->q_hash;
	bin = GET_HASHBIN( hashv );

	/*
	 * Dequeue the entry...
	 */
	dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
			 (irda_queue_t*) entry );
	hashbin->hb_size--;
	entry->q_next = NULL;
	entry->q_prev = NULL;

	/*
	 *  Check if this item is the currently selected item, and in
	 *  that case we must reset hb_current
	 */
	if ( entry == hashbin->hb_current)
		hashbin->hb_current = NULL;
out:
	/* Release lock */
	if ( hashbin->hb_type & HB_LOCK ) {
		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
	} /* Default is no-lock  */

	return entry;
}
EXPORT_SYMBOL(hashbin_remove_this);

/*********************** HASHBIN ENUMERATION ***********************/

/*
 * Function hashbin_common_find (hashbin, hashv, name)
 *
 *    Find item with the given hashv or name
 *
 */
void* hashbin_find( hashbin_t* hashbin, long hashv, const char* name )
{
	int bin;
	irda_queue_t* entry;

	IRDA_DEBUG( 4, "hashbin_find()\n");

	IRDA_ASSERT( hashbin != NULL, return NULL;);
	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);

	/*
	 * Locate hashbin
	 */
	if ( name )
		hashv = hash( name );
	bin = GET_HASHBIN( hashv );

	/*
	 * Search for entry
	 */
	entry = hashbin->hb_queue[ bin];
	if ( entry ) {
		do {
			/*
			 * Check for key
			 */
			if ( entry->q_hash == hashv ) {
				/*
				 * Name compare too?
				 */
				if ( name ) {
					if ( strcmp( entry->q_name, name ) == 0 ) {
						return entry;
					}
				} else {
					return entry;
				}
			}
			entry = entry->q_next;
		} while ( entry != hashbin->hb_queue[ bin ] );
	}

	return NULL;
}
EXPORT_SYMBOL(hashbin_find);

/*
 * Function hashbin_lock_find (hashbin, hashv, name)
 *
 *    Find item with the given hashv or name
 *
 * Same, but with spinlock protection...
 * I call it safe, but it's only safe with respect to the hashbin, not its
 * content. - Jean II
 */
void* hashbin_lock_find( hashbin_t* hashbin, long hashv, const char* name )
{
	unsigned long flags = 0;
	irda_queue_t* entry;

	/* Synchronize */
	spin_lock_irqsave(&hashbin->hb_spinlock, flags);

	/*
	 * Search for entry
	 */
	entry = (irda_queue_t* ) hashbin_find( hashbin, hashv, name );

	/* Release lock */
	spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);

	return entry;
}
EXPORT_SYMBOL(hashbin_lock_find);

/*
 * Function hashbin_find (hashbin, hashv, name, pnext)
 *
 *    Find an item with the given hashv or name, and its successor
 *
 * This function allow to do concurrent enumerations without the
 * need to lock over the whole session, because the caller keep the
 * context of the search. On the other hand, it might fail and return
 * NULL if the entry is removed. - Jean II
 */
void* hashbin_find_next( hashbin_t* hashbin, long hashv, const char* name,
			 void ** pnext)
{
	unsigned long flags = 0;
	irda_queue_t* entry;

	/* Synchronize */
	spin_lock_irqsave(&hashbin->hb_spinlock, flags);

	/*
	 * Search for current entry
	 * This allow to check if the current item is still in the
	 * hashbin or has been removed.
	 */
	entry = (irda_queue_t* ) hashbin_find( hashbin, hashv, name );

	/*
	 * Trick hashbin_get_next() to return what we want
	 */
	if(entry) {
		hashbin->hb_current = entry;
		*pnext = hashbin_get_next( hashbin );
	} else
		*pnext = NULL;

	/* Release lock */
	spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);

	return entry;
}

/*
 * Function hashbin_get_first (hashbin)
 *
 *    Get a pointer to first element in hashbin, this function must be
 *    called before any calls to hashbin_get_next()!
 *
 */
irda_queue_t *hashbin_get_first( hashbin_t* hashbin)
{
	irda_queue_t *entry;
	int i;

	IRDA_ASSERT( hashbin != NULL, return NULL;);
	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);

	if ( hashbin == NULL)
		return NULL;

	for ( i = 0; i < HASHBIN_SIZE; i ++ ) {
		entry = hashbin->hb_queue[ i];
		if ( entry) {
			hashbin->hb_current = entry;
			return entry;
		}
	}
	/*
	 *  Did not find any item in hashbin
	 */
	return NULL;
}
EXPORT_SYMBOL(hashbin_get_first);

/*
 * Function hashbin_get_next (hashbin)
 *
 *    Get next item in hashbin. A series of hashbin_get_next() calls must
 *    be started by a call to hashbin_get_first(). The function returns
 *    NULL when all items have been traversed
 *
 * The context of the search is stored within the hashbin, so you must
 * protect yourself from concurrent enumerations. - Jean II
 */
irda_queue_t *hashbin_get_next( hashbin_t *hashbin)
{
	irda_queue_t* entry;
	int bin;
	int i;

	IRDA_ASSERT( hashbin != NULL, return NULL;);
	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);

	if ( hashbin->hb_current == NULL) {
		IRDA_ASSERT( hashbin->hb_current != NULL, return NULL;);
		return NULL;
	}
	entry = hashbin->hb_current->q_next;
	bin = GET_HASHBIN( entry->q_hash);

	/*
	 *  Make sure that we are not back at the beginning of the queue
	 *  again
	 */
	if ( entry != hashbin->hb_queue[ bin ]) {
		hashbin->hb_current = entry;

		return entry;
	}

	/*
	 *  Check that this is not the last queue in hashbin
	 */
	if ( bin >= HASHBIN_SIZE)
		return NULL;

	/*
	 *  Move to next queue in hashbin
	 */
	bin++;
	for ( i = bin; i < HASHBIN_SIZE; i++ ) {
		entry = hashbin->hb_queue[ i];
		if ( entry) {
			hashbin->hb_current = entry;

			return entry;
		}
	}
	return NULL;
}
EXPORT_SYMBOL(hashbin_get_next);