summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2012-02-28 06:26:28 (GMT)
committerH. Peter Anvin <hpa@zytor.com>2012-02-28 06:26:28 (GMT)
commitcd619f94fae1040638af3cc10d480fe0fa9be2c4 (patch)
treed02bb27942f261130ec6e1f27287579c736fb05d
parent2b061d66d26d1a381aaf2cee0e629bb696e0c9f8 (diff)
downloadgrv-cd619f94fae1040638af3cc10d480fe0fa9be2c4.zip
grv-cd619f94fae1040638af3cc10d480fe0fa9be2c4.tar.gz
grv-cd619f94fae1040638af3cc10d480fe0fa9be2c4.tar.bz2
grv-cd619f94fae1040638af3cc10d480fe0fa9be2c4.tar.xz
action: Use a binary search for insertion
Linear searches make me cry.
-rw-r--r--action.c31
1 files changed, 21 insertions, 10 deletions
diff --git a/action.c b/action.c
index 1dec134..b592ea2 100644
--- a/action.c
+++ b/action.c
@@ -30,20 +30,31 @@ static uint64_t next_seq = 0;
void addaction(int x, int y, double when, enum actions what)
{
- int i = 0;
+ int a, b;
+ int i;
+
if ( action_count >= MAXACT )
return;
- while ( i < action_count && actions[i].when <= when && actions[i].what )
- i++;
+ a = 0;
+ b = action_count;
+ while (b > a) {
+ i = (a+b) >> 1;
+ if (actions[i].when <= when)
+ a = i+1;
+ else
+ b = i;
+ }
+
+ if (a < action_count)
+ memmove(&actions[a+1], &actions[a],
+ (action_count-a)*sizeof(struct action));
- memmove(&actions[i+1], &actions[i],
- (action_count-i)*sizeof(struct action));
- actions[i].x = x;
- actions[i].y = y;
- actions[i].when = when;
- actions[i].what = what;
- actions[i].seq = next_seq++;
+ actions[a].x = x;
+ actions[a].y = y;
+ actions[a].when = when;
+ actions[a].what = what;
+ actions[a].seq = next_seq++;
action_count++;
}