From: Stephen H. <she...@os...> - 2003-10-03 19:03:24
|
Replace irqueue's linked list code with the standard hlist macros. Simpler, smaller, cleaner, faster... diff -Nru a/include/net/irda/irqueue.h b/include/net/irda/irqueue.h --- a/include/net/irda/irqueue.h Fri Oct 3 12:01:28 2003 +++ b/include/net/irda/irqueue.h Fri Oct 3 12:01:28 2003 @@ -57,8 +57,7 @@ typedef void (*FREE_FUNC)(void *arg); struct irda_queue { - struct irda_queue *q_next; - struct irda_queue *q_prev; + struct hlist_node q_node; char q_name[NAME_SIZE]; long q_hash; /* Must be able to cast a (void *) */ @@ -71,7 +70,7 @@ int hb_size; spinlock_t hb_spinlock; /* HB_LOCK - Can be used by the user */ - irda_queue_t* hb_queue[HASHBIN_SIZE] IRDA_ALIGN; + struct hlist_head hb_queue[HASHBIN_SIZE] IRDA_ALIGN; irda_queue_t* hb_current; } hashbin_t; @@ -93,7 +92,7 @@ static inline int hashbin_inlist(const irda_queue_t *entry) { - return (entry->q_next != NULL); + return (entry->q_node.pprev != NULL); } #define HASHBIN_GET_SIZE(hashbin) hashbin->hb_size diff -Nru a/net/irda/irqueue.c b/net/irda/irqueue.c --- a/net/irda/irqueue.c Fri Oct 3 12:01:28 2003 +++ b/net/irda/irqueue.c Fri Oct 3 12:01:28 2003 @@ -222,124 +222,6 @@ return h; } -/* - * Function enqueue_first (queue, proc) - * - * Insert item first in queue. - * - */ -static void enqueue_first(irda_queue_t **queue, irda_queue_t* element) -{ - - IRDA_DEBUG( 4, "%s()\n", __FUNCTION__); - - /* - * Check if queue is empty. - */ - if ( *queue == NULL ) { - /* - * Queue is empty. Insert one element into the queue. - */ - element->q_next = element->q_prev = *queue = element; - - } else { - /* - * Queue is not empty. Insert element into front of queue. - */ - element->q_next = (*queue); - (*queue)->q_prev->q_next = element; - element->q_prev = (*queue)->q_prev; - (*queue)->q_prev = element; - (*queue) = element; - } -} - - -/* - * Function dequeue (queue) - * - * Remove first entry in queue - * - */ -static irda_queue_t *dequeue_first(irda_queue_t **queue) -{ - irda_queue_t *ret; - - IRDA_DEBUG( 4, "dequeue_first()\n"); - - /* - * Set return value - */ - ret = *queue; - - if ( *queue == NULL ) { - /* - * Queue was empty. - */ - } else if ( (*queue)->q_next == *queue ) { - /* - * Queue only contained a single element. It will now be - * empty. - */ - *queue = NULL; - } else { - /* - * Queue contained several element. Remove the first one. - */ - (*queue)->q_prev->q_next = (*queue)->q_next; - (*queue)->q_next->q_prev = (*queue)->q_prev; - *queue = (*queue)->q_next; - } - - /* - * Return the removed entry (or NULL of queue was empty). - */ - return ret; -} - -/* - * Function dequeue_general (queue, element) - * - * - */ -static irda_queue_t *dequeue_general(irda_queue_t **queue, irda_queue_t* element) -{ - irda_queue_t *ret; - - IRDA_DEBUG( 4, "dequeue_general()\n"); - - /* - * Set return value - */ - ret = *queue; - - if ( *queue == NULL ) { - /* - * Queue was empty. - */ - } else if ( (*queue)->q_next == *queue ) { - /* - * Queue only contained a single element. It will now be - * empty. - */ - *queue = NULL; - - } else { - /* - * Remove specific element. - */ - element->q_prev->q_next = element->q_next; - element->q_next->q_prev = element->q_prev; - if ( (*queue) == element) - (*queue) = element->q_next; - } - - /* - * Return the removed entry (or NULL of queue was empty). - */ - return ret; -} - /************************ HASHBIN MANAGEMENT ************************/ /* @@ -351,6 +233,7 @@ hashbin_t *hashbin_new(int type) { hashbin_t* hashbin; + int i; /* * Allocate new hashbin @@ -365,7 +248,8 @@ memset(hashbin, 0, sizeof(hashbin_t)); hashbin->hb_type = type; hashbin->magic = HB_MAGIC; - //hashbin->hb_current = NULL; + for (i = 0; i < HASHBIN_SIZE; ++i) + INIT_HLIST_HEAD(&hashbin->hb_queue[i]); /* Make sure all spinlock's are unlocked */ if ( hashbin->hb_type & HB_LOCK ) { @@ -385,6 +269,7 @@ */ int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func) { + struct hlist_node *p, *n; irda_queue_t* queue; unsigned long flags = 0; int i; @@ -402,12 +287,11 @@ * it has been shown to work */ for (i = 0; i < HASHBIN_SIZE; i ++ ) { - queue = dequeue_first((irda_queue_t**) &hashbin->hb_queue[i]); - while (queue ) { + hlist_for_each_entry_safe(queue, p, n, &hashbin->hb_queue[i], + q_node) { + hlist_del_init(p); if (free_func) (*free_func)(queue); - queue = dequeue_first( - (irda_queue_t**) &hashbin->hb_queue[i]); } } @@ -469,8 +353,7 @@ /* * Insert new entry first */ - enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ], - entry); + hlist_add_head(&entry->q_node, &hashbin->hb_queue[bin]); hashbin->hb_size++; /* Release lock */ @@ -511,11 +394,8 @@ /* * Dequeue the entry... */ - dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ], - (irda_queue_t*) entry ); + hlist_del_init(&entry->q_node); hashbin->hb_size--; - entry->q_next = NULL; - entry->q_prev = NULL; /* * Check if this item is the currently selected item, and in @@ -550,9 +430,10 @@ */ void* hashbin_remove( hashbin_t* hashbin, long hashv, const char* name) { - int bin, found = FALSE; + int bin; unsigned long flags = 0; - irda_queue_t* entry; + struct hlist_node *p; + irda_queue_t* entry = NULL; IRDA_DEBUG( 4, "%s()\n", __FUNCTION__); @@ -574,45 +455,22 @@ /* * Search for entry */ - entry = hashbin->hb_queue[ bin ]; - if ( entry ) { - do { + hlist_for_each_entry(entry, p, &hashbin->hb_queue[bin], q_node) { + if (entry->q_hash == hashv) { + if (name && strcmp(entry->q_name, name)) + continue; + + hlist_del_init(p); + hashbin->hb_size--; + /* - * Check for key + * If this item is the currently selected item, + * reset hb_current */ - 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; + if ( entry == hashbin->hb_current) + hashbin->hb_current = NULL; + break; + } } /* Release lock */ @@ -620,13 +478,7 @@ spin_unlock_irqrestore(&hashbin->hb_spinlock, flags); } /* Default is no-lock */ - - /* Return */ - if ( found ) - return entry; - else - return NULL; - + return entry; } /* @@ -658,7 +510,7 @@ } /* Default is no-lock */ /* Check if valid and not already removed... */ - if((entry->q_next == NULL) || (entry->q_prev == NULL)) + if (!hashbin_inlist(entry)) return NULL; /* @@ -670,11 +522,8 @@ /* * Dequeue the entry... */ - dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ], - (irda_queue_t*) entry ); + hlist_del_init(&entry->q_node); hashbin->hb_size--; - entry->q_next = NULL; - entry->q_prev = NULL; /* * Check if this item is the currently selected item, and in @@ -702,7 +551,8 @@ void* hashbin_find( hashbin_t* hashbin, long hashv, const char* name ) { int bin; - irda_queue_t* entry; + irda_queue_t* entry = NULL; + struct hlist_node *node; IRDA_DEBUG( 4, "hashbin_find()\n"); @@ -719,29 +569,16 @@ /* * 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 ] ); + hlist_for_each_entry(entry, node, &hashbin->hb_queue[bin], q_node) { + if ( entry->q_hash == hashv ) { + if (name && strcmp(entry->q_name, name)) + continue; + /* found match */ + break; + } } - return NULL; + return entry; } /* @@ -823,6 +660,7 @@ irda_queue_t *hashbin_get_first( hashbin_t* hashbin) { irda_queue_t *entry; + struct hlist_node *node; int i; ASSERT( hashbin != NULL, return NULL;); @@ -832,8 +670,7 @@ return NULL; for ( i = 0; i < HASHBIN_SIZE; i ++ ) { - entry = hashbin->hb_queue[ i]; - if ( entry) { + hlist_for_each_entry(entry, node, &hashbin->hb_queue[i], q_node) { hashbin->hb_current = entry; return entry; } @@ -857,46 +694,32 @@ irda_queue_t *hashbin_get_next( hashbin_t *hashbin) { irda_queue_t* entry; + struct hlist_node *node; int bin; - int i; ASSERT( hashbin != NULL, return NULL;); ASSERT( hashbin->magic == HB_MAGIC, return NULL;); - if ( hashbin->hb_current == NULL) { - ASSERT( hashbin->hb_current != NULL, return NULL;); + if ( hashbin->hb_current == 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; + entry = hashbin->hb_current; + bin = GET_HASHBIN( entry->q_hash); + node = &entry->q_node; - return entry; + hlist_for_each_entry_continue(entry, node, q_node) { + goto found; } - /* - * 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; + while (++bin < HASHBIN_SIZE) { + hlist_for_each_entry(entry, node, + &hashbin->hb_queue[bin], q_node) { + goto found; } } + return NULL; + found: + hashbin->hb_current = entry; + return entry; } |