Project

General

Profile

Feature #9614 ยป 0004-ihash-implement-rb_ihash_update-to-support-rb_fstrin.patch

normalperson (Eric Wong), 03/09/2014 02:22 AM

View differences:

ihash.c
227 227

  
228 228
    return 0;
229 229
}
230

  
231
int
232
rb_ihash_update(struct rb_ihash_tbl **tblp, struct rb_ihash_node *upd,
233
		rb_ihash_updater fn, void *arg)
234
{
235
    struct rb_ihash_tbl *tbl = *tblp;
236
    st_index_t hval = tbl->type->hash(upd);
237
    struct rb_ihash_node **bins = rb_ihash_bins(tbl);
238
    size_t i = rb_ihash_binpos(tbl, hval);
239
    struct rb_ihash_node *last = NULL;
240
    struct rb_ihash_node *cur = bins[i];
241

  
242
    while (cur) {
243
	if (tbl->type->cmp(upd, cur) == 0) {
244
	    struct rb_ihash_node *next = cur->ihash_next;
245

  
246
	    switch (fn(&cur, upd, arg)) {
247
	      case RB_IHASH_UPDATED:
248
		cur->ihash_next = next; /* preserve linkage */
249
		return 1;
250
	      case RB_IHASH_DESTROYED: /* do we need to support this? */
251
		if (last) last->ihash_next = next;
252
		else bins[i] = 0;
253
		return 1;
254
	    }
255
	}
256
	last = cur;
257
	cur = cur->ihash_next;
258
    }
259

  
260
    cur = 0;
261
    switch (fn(&cur, upd, arg)) {
262
      case RB_IHASH_UPDATED:
263
	rb_ihash_add_pos(tbl, cur, i);
264
	rb_ihash_added(tblp);
265
	return 0;
266
      case RB_IHASH_DESTROYED:
267
	rb_bug("RB_IHASH_DESTROYED unexpected");
268
    }
269
    return 0;
270
}
ihash.h
42 42
    RB_IHASH_UNLINKED /* user must deallocate this manually */
43 43
};
44 44

  
45
enum rb_ihash_updated {
46
    RB_IHASH_UPDATED = 0,
47
    RB_IHASH_DESTROYED /* user already deallocated */
48
};
49

  
45 50
typedef int (*rb_ihash_compare)(const struct rb_ihash_node *,
46 51
				const struct rb_ihash_node *);
47 52
typedef st_index_t (*rb_ihash_compute)(const struct rb_ihash_node *);
48 53
typedef enum rb_ihash_next (*rb_ihash_iterate)(struct rb_ihash_node *, void *);
49 54

  
55
typedef enum rb_ihash_updated (*rb_ihash_updater)(struct rb_ihash_node **cur,
56
						  struct rb_ihash_node *upd,
57
						  void *arg);
58

  
50 59
struct rb_ihash_type {
51 60
    rb_ihash_compare cmp;
52 61
    rb_ihash_compute hash;
......
85 94
}
86 95

  
87 96
size_t rb_ihash_memsize(const struct rb_ihash_tbl *);
97

  
98
int rb_ihash_update(struct rb_ihash_tbl **, struct rb_ihash_node *,
99
		    rb_ihash_updater, void *arg);
100

  
88 101
#if defined(__cplusplus)
89 102
#if 0
90 103
{ /* satisfy cc-mode */
string.c
15 15
#include "ruby/re.h"
16 16
#include "ruby/encoding.h"
17 17
#include "internal.h"
18
#include "ihash.h"
18 19
#include "probes.h"
19 20
#include <assert.h>
20 21

  
......
157 158
    return get_actual_encoding(ENCODING_GET(str), str);
158 159
}
159 160

  
160
static int fstring_cmp(VALUE a, VALUE b);
161
static int fstring_cmp(const struct rb_ihash_node *,
162
			const struct rb_ihash_node *);
161 163

  
162
static st_table* frozen_strings;
164
static struct rb_ihash_tbl* frozen_strings;
165
struct fstring {
166
    VALUE fstr;
167
    st_index_t hashval;
168
    struct rb_ihash_node fstr_node;
169
};
170

  
171
struct fstring *
172
fstring_of(const struct rb_ihash_node *node)
173
{
174
    return RB_CONTAINER_OF(node, struct fstring, fstr_node);
175
}
176

  
177
static st_index_t
178
fstring_hash(const struct rb_ihash_node *ptr)
179
{
180
    return fstring_of(ptr)->hashval; /* precomputed */
181
}
163 182

  
164
static const struct st_hash_type fstring_hash_type = {
183
static const struct rb_ihash_type fstring_hash_type = {
165 184
    fstring_cmp,
166
    rb_str_hash,
185
    fstring_hash,
167 186
};
168 187

  
169
static int
170
fstr_update_callback(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
188
static enum rb_ihash_updated
189
fstr_update_callback(struct rb_ihash_node **cur_node,
190
		     struct rb_ihash_node *upd_node, void *unused)
171 191
{
172
    VALUE *fstr = (VALUE *)arg;
173
    VALUE str = (VALUE)*key;
192
    struct fstring *upd = fstring_of(upd_node);
193
    struct fstring *ins;
194
    VALUE str;
174 195

  
175
    if (existing) {
176
	/* because of lazy sweep, str may be unmarked already and swept
196
    if (*cur_node) {
197
	const struct fstring *cur = fstring_of(*cur_node);
198

  
199
	/* because of lazy sweep, cur->fstr may be unmarked already and swept
177 200
	 * at next time */
178
	rb_gc_resurrect(*fstr = *key);
179
	return ST_STOP;
201
	rb_gc_resurrect(upd->fstr = cur->fstr);
202
	return RB_IHASH_UPDATED;
180 203
    }
181 204

  
205
    /* create new node */
206
    str = upd->fstr;
182 207
    if (STR_SHARED_P(str)) {
183 208
	/* str should not be shared */
184 209
	str = rb_enc_str_new(RSTRING_PTR(str), RSTRING_LEN(str), STR_ENC_GET(str));
......
188 213
	str = rb_str_new_frozen(str);
189 214
    }
190 215
    RBASIC(str)->flags |= RSTRING_FSTR;
216
    ins = ALLOC(struct fstring);
217
    ins->hashval = upd->hashval;
218
    upd->fstr = ins->fstr = str;
219
    *cur_node = &ins->fstr_node; /* trigger insert */
191 220

  
192
    *key = *value = *fstr = str;
193
    return ST_CONTINUE;
221
    return RB_IHASH_UPDATED;
194 222
}
195 223

  
196 224
VALUE
197 225
rb_fstring(VALUE str)
198 226
{
199
    VALUE fstr = Qnil;
227
    struct fstring fstr;
200 228
    Check_Type(str, T_STRING);
201 229

  
202 230
    if (!frozen_strings)
203
	frozen_strings = st_init_table(&fstring_hash_type);
231
	frozen_strings = rb_ihash_new(&fstring_hash_type, 0);
204 232

  
205 233
    if (FL_TEST(str, RSTRING_FSTR))
206 234
	return str;
207 235

  
208
    st_update(frozen_strings, (st_data_t)str, fstr_update_callback, (st_data_t)&fstr);
209
    return fstr;
236
    fstr.fstr = str;
237
    fstr.hashval = rb_str_hash(str);
238
    rb_ihash_update(&frozen_strings, &fstr.fstr_node, fstr_update_callback, 0);
239
    return fstr.fstr;
210 240
}
211 241

  
212
static int
213
fstring_set_class_i(st_data_t key, st_data_t val, st_data_t arg)
242
static enum rb_ihash_next
243
fstring_set_class_i(struct rb_ihash_node *node, void *arg)
214 244
{
215
    RBASIC_SET_CLASS((VALUE)key, (VALUE)arg);
216
    return ST_CONTINUE;
245
    VALUE klass = (VALUE)arg;
246
    struct fstring *fstr = fstring_of(node);
247

  
248
    RBASIC_SET_CLASS((VALUE)fstr->fstr, klass);
249
    return RB_IHASH_CONTINUE;
217 250
}
218 251

  
219 252
static int
220
fstring_cmp(VALUE a, VALUE b)
253
fstring_cmp(const struct rb_ihash_node *na, const struct rb_ihash_node *nb)
221 254
{
222
    int cmp = rb_str_hash_cmp(a, b);
255
    struct fstring *a = fstring_of(na);
256
    struct fstring *b = fstring_of(nb);
257
    int cmp;
258

  
259
    if (a->hashval != b->hashval) {
260
	return 1;
261
    }
262

  
263
    cmp = rb_str_hash_cmp(a->fstr, b->fstr);
223 264
    if (cmp != 0) {
224 265
	return cmp;
225 266
    }
226
    return ENCODING_GET(b) - ENCODING_GET(a);
267
    return ENCODING_GET(b->fstr) - ENCODING_GET(a->fstr);
227 268
}
228 269

  
229 270
static inline int
......
907 948
    if (s) rb_str_clear(s);
908 949
}
909 950

  
951
static void
952
fstring_delete(VALUE str)
953
{
954
    struct fstring fstr;
955
    struct rb_ihash_node *node;
956

  
957
    fstr.fstr = str;
958
    fstr.hashval = rb_str_hash(str);
959
    node = rb_ihash_unlink(frozen_strings, &fstr.fstr_node);
960
    if (node) {
961
	struct fstring *del = fstring_of(node);
962
	xfree(del);
963
    }
964
    else {
965
	rb_bug("RSTRING_FSTR consistency error"); /* do we need this? */
966
    }
967
}
968

  
910 969
void
911 970
rb_str_free(VALUE str)
912 971
{
913 972
    if (FL_TEST(str, RSTRING_FSTR)) {
914
	st_data_t fstr = (st_data_t)str;
915
	st_delete(frozen_strings, &fstr, NULL);
973
	fstring_delete(str);
916 974
    }
917 975

  
918 976
    if (!STR_EMBED_P(str) && !FL_TEST(str, STR_SHARED)) {
......
8841 8899
    rb_define_method(rb_cSymbol, "encoding", sym_encoding, 0);
8842 8900

  
8843 8901
    if (frozen_strings)
8844
	st_foreach(frozen_strings, fstring_set_class_i, rb_cString);
8902
	rb_ihash_foreach(&frozen_strings, fstring_set_class_i, (void *)rb_cString);
8845 8903
}
8846
-