If you don't want to change the linked list's structure, change how you hold the list. Instead of using one pointer to hold the list, use an array of pointers. Basically, make a hash table. Super simple version:
Code:
/* super lazy mode, use the last digit as what list you end up in */
#define HASHSIZE 10
struct node *dc_head[ HASHSIZE ]; /* instead of just one pointer, an array... */
...
double is_dependent(unsigned long long which_inst, enum stall_reason *where)
{
struct dependency *temp, *prev;
double ret_val = 0;
size_t which_bucket = which_inst % HASHSIZE;
// Scan the chain for the dependent line
for(prev=NULL, temp=dc_head[ which_bucket ]; temp && temp->which_inst != which_inst; prev=temp, temp=temp->next);
// Found. Unlink node and return when_satisfied
if(temp)
{
if(prev)
{
prev->next = temp->next;
}
else
{
dc_head[ which_bucket ] = temp->next;
}
ret_val = temp->when_satisfied;
*where = temp->reason;
free(temp);
}
return ret_val;
}
Pretty much all you've done is split your list into HASHSIZE smaller lists. Now everything that ends in a 1 goes in array[ 1 ], everything that ends in a 9 goes in array[ 9 ], etc.
This is just an extremely simplified example. That's not the best number to use for hashing, but it's easy to understand, which is why I use it for examples. Now, you've cut your search time by 10.
Either way, if you use this, a tree, or something better, you're going to end up putting some work in. I think this would probably require the least amount of work, because really all you have to do is find everywhere you use dc_head and make it use an array instead. It's not the fastest method, but it's really simple.
Quzah.
Originally Posted by iMalc
