4223
|
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 }
|