// The required structs
struct linkedlist
{
linkedlist * next;
particle_t * value;
};
typedef struct linkedlist linkedlist_t;
struct grid
{
int size;
linkedlist_t ** grid;
pthread_mutex_t * lock;
};
typedef struct grid grid_t;
// Other used methods
inline static int grid_coord(double c)
{
return (int)floor(c / cutoff);
}
inline static int grid_coord_flat(int size, double x, double y)
{
return grid_coord(x) * size + grid_coord(y);
}
//
// Removes a particle from the grid
//
bool grid_remove(grid_t & grid, particle_t * p)
{
int gridCoord = grid_coord_flat(grid.size, p->x, p->y);
// No elements?
if (grid.grid[gridCoord] == 0)
{
return false;
}
// Special case for first element
pthread_mutex_lock(&grid.lock[gridCoord]); // Beginning of critical section
if (grid.grid[gridCoord]->value == p)
{
linkedlist_t * tmp = grid.grid[gridCoord];
grid.grid[gridCoord] = tmp->next;
free(tmp);
pthread_mutex_unlock(&grid.lock[gridCoord]); // End of critical section
return true;
}
linkedlist_t * prev = grid.grid[gridCoord];
linkedlist_t * current = prev->next;
while(current != 0)
{
if (current->value == p)
{
prev->next = current->next;
free(current);
pthread_mutex_unlock(&grid.lock[gridCoord]); // End of critical section
return true;
}
prev = current;
current = current->next;
}
pthread_mutex_unlock(&grid.lock[gridCoord]); // End of critical section
return false;
}
Refactorings
No refactoring yet !
Ants
March 7, 2011, March 07, 2011 04:48, permalink
1 rating.
Login to rate!
I'm assuming pointer comparisons against p at line 44 and 58 in the code above are intentional. If not both should derefence the pointers and compare the particle_t instance values.
typedef struct linkedlist
{
linkedlist * next;
particle_t * value;
} linkedlist_t;
typedef struct
{
int size;
linkedlist_t ** grid;
pthread_mutex_t * lock;
} grid_t;
bool grid_remove(grid_t & grid, particle_t * p)
{
int gridCoord = grid_coord_flat(grid.size, p->x, p->y);
linkedlist_t ** nodePointer = &(grid.grid[gridCoord]);
linkedlist_t * current = grid.grid[gridCoord];
pthread_mutex_lock(&grid.lock[gridCoord]);
while(current && (current->value != p))
{
nodePointer = &(current->next);
current = current->next;
}
if (current)
{
*nodePointer = current->next;
free(current);
}
pthread_mutex_unlock(&grid.lock[gridCoord]);
return !!current;
}
Morningcoffee
March 7, 2011, March 07, 2011 10:07, permalink
No rating.
Login to rate!
Yes, they are intentional. Your code works, except for that line 17 and 18 must be moved inside the mutex lock. Thanks.
Ants
March 7, 2011, March 07, 2011 18:39, permalink
1 rating.
Login to rate!
Good find Morningcoffee!
Here's the update:
typedef struct linkedlist
{
linkedlist * next;
particle_t * value;
} linkedlist_t;
typedef struct
{
int size;
linkedlist_t ** grid;
pthread_mutex_t * lock;
} grid_t;
bool grid_remove(grid_t & grid, particle_t * p)
{
int gridCoord = grid_coord_flat(grid.size, p->x, p->y);
pthread_mutex_lock(&grid.lock[gridCoord]);
linkedlist_t ** nodePointer = &(grid.grid[gridCoord]);
linkedlist_t * current = grid.grid[gridCoord];
while(current && (current->value != p))
{
nodePointer = &(current->next);
current = current->next;
}
if (current)
{
*nodePointer = current->next;
free(current);
}
pthread_mutex_unlock(&grid.lock[gridCoord]);
return !!current;
}
I'm really concerned about this method, grid_remove, that I have for removing a struct from an array of linked lists. I'm writing in C with a little help from the C++ compiler.