Mercurial > repo

comparison src/ploki/venus.c @ 4223:ac0403686959

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<oerjan> rm -rf src/ploki; mv ploki src
author HackBot
date Fri, 20 Dec 2013 22:18:50 +0000
parents
children
comparison
equal deleted inserted replaced
4222:b0f3e267bb1e 4223:ac0403686959
1 #include "Str.h"
2 #include "hash.h"
3 #include "op.h"
4 #include "venus.h"
5 #include "xmalloc.h"
6 #include "zz.h"
7
8 #include <stddef.h>
9 #include <stdio.h>
10 #include <string.h>
11
12 enum {MAGIC = 23};
13
14 struct sorted {
15 size_t size, length;
16 struct op **array;
17 };
18
19 static size_t hash(const void *p, size_t seed) {
20 return St_hash(p, seed);
21 }
22
23 static int compar(const void *a, const void *b) {
24 return St_cmp(a, b);
25 }
26
27 static void delk(void *k) {
28 St_clear(k);
29 xfree(k);
30 }
31
32 static void delv(void *v) {
33 xfree(((struct sorted *)v)->array);
34 xfree(v);
35 }
36
37 void ve_init(struct venus *v) {
38 h_init(&v->table, hash, compar, delk, delv);
39 }
40
41 void ve_end(struct venus *v) {
42 h_end(&v->table);
43 }
44
45 void ve_enter(struct venus *v, const String *s, struct op *o) {
46 struct sorted *x;
47 void *tmp;
48 size_t a, z;
49
50 if (h_get(&v->table, s, &tmp) == H_NOENT) {
51 String *label;
52 x = xmalloc(1, sizeof *x);
53 x->array = xmalloc(x->size = MAGIC, sizeof *x->array);
54 x->array[0] = o;
55 x->length = 1;
56 label = xmalloc(1, sizeof *label);
57 St_init(label);
58 St_cpy(label, s);
59 h_put(&v->table, label, x, 1);
60 return;
61 }
62 x = tmp;
63
64 for (a = 0, z = x->length; a < z; ) {
65 if (x->array[(a + z) / 2]->line < o->line) {
66 a = (a + z) / 2 + 1u;
67 } else if (x->array[(a + z) / 2]->line > o->line) {
68 z = (a + z) / 2;
69 } else {
70 NOTREACHED;
71 }
72 }
73
74 if (x->length >= x->size) {
75 x->array = xrealloc(x->array, x->size *= 2);
76 }
77 memmove(x->array + a + 1u, x->array + a, x->length - a);
78 x->array[a] = o;
79 x->length++;
80 }
81
82 struct op *ve_findnext(struct venus *v, const String *s, size_t line) {
83 struct sorted *x;
84 void *tmp;
85 size_t a, z;
86
87 if (h_get(&v->table, s, &tmp) == H_NOENT) {
88 return NULL;
89 }
90 x = tmp;
91
92 for (a = 0, z = x->length; a < z; ) {
93 if (x->array[(a + z) / 2]->line < line) {
94 a = (a + z) / 2 + 1u;
95 } else if (x->array[(a + z) / 2]->line > line) {
96 z = (a + z) / 2;
97 } else {
98 a = (a + z) / 2 + 1u;
99 break;
100 }
101 }
102
103 return x->array[a % x->length];
104 }
105
106 struct op *ve_findprev(struct venus *v, const String *s, size_t line) {
107 struct sorted *x;
108 void *tmp;
109 size_t a, z;
110
111 if (h_get(&v->table, s, &tmp) == H_NOENT) {
112 return NULL;
113 }
114 x = tmp;
115
116 for (a = 0, z = x->length; a < z; ) {
117 if (x->array[(a + z) / 2]->line < line) {
118 a = (a + z) / 2 + 1u;
119 } else if (x->array[(a + z) / 2]->line > line) {
120 z = (a + z) / 2;
121 } else {
122 a = (a + z) / 2;
123 break;
124 }
125 }
126 a += x->length - 1u;
127 return x->array[a % x->length];
128 }
129
130 const String *ve_label(struct venus *v, const struct op *op) {
131 void *key, *value;
132
133 h_reset(&v->table);
134 while (h_nextkv(&v->table, &key, &value) == H_OK) {
135 const struct sorted *x = value;
136 size_t i;
137
138 for (i = 0; i < x->length; ++i) {
139 if (x->array[i] == op) {
140 return key;
141 }
142 }
143 }
144
145 return NULL;
146 }