Subversion Repositories Kolibri OS

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
1913 jaeger 1 
int tp_lua_hash(void const *v,int l) {
2 
    int i,step = (l>>5)+1;
3 
    int h = l + (l >= 4?*(int*)v:0);
4 
    for (i=l; i>=step; i-=step) {
5 
        h = h^((h<<5)+(h>>2)+((unsigned char *)v)[i-1]);
6 
    }
7 
    return h;
8 
}
9 
void _tp_dict_free(_tp_dict *self) {
10 
    tp_free(self->items);
11 
    tp_free(self);
12 
}
13 
 
14 
/* void _tp_dict_reset(_tp_dict *self) {
15 
       memset(self->items,0,self->alloc*sizeof(tp_item));
16 
       self->len = 0;
17 
       self->used = 0;
18 
       self->cur = 0;
19 
   }*/
20 
 
21 
int tp_hash(TP,tp_obj v) {
22 
    switch (v.type) {
23 
        case TP_NONE: return 0;
24 
        case TP_NUMBER: return tp_lua_hash(&v.number.val,sizeof(tp_num));
25 
        case TP_STRING: return tp_lua_hash(v.string.val,v.string.len);
26 
        case TP_DICT: return tp_lua_hash(&v.dict.val,sizeof(void*));
27 
        case TP_LIST: {
28 
            int r = v.list.val->len; int n; for(n=0; nlen; n++) {
29 
            tp_obj vv = v.list.val->items[n]; r += vv.type != TP_LIST?tp_hash(tp,v.list.val->items[n]):tp_lua_hash(&vv.list.val,sizeof(void*)); } return r;
30 
        }
31 
        case TP_FNC: return tp_lua_hash(&v.fnc.info,sizeof(void*));
32 
        case TP_DATA: return tp_lua_hash(&v.data.val,sizeof(void*));
33 
    }
34 
    tp_raise(0,"tp_hash(%s)",TP_CSTR(v));
35 
}
36 
 
37 
void _tp_dict_hash_set(TP,_tp_dict *self, int hash, tp_obj k, tp_obj v) {
38 
    tp_item item;
39 
    int i,idx = hash&self->mask;
40 
    for (i=idx; ialloc; i++) {
41 
        int n = i&self->mask;
42 
        if (self->items[n].used > 0) { continue; }
43 
        if (self->items[n].used == 0) { self->used += 1; }
44 
        item.used = 1;
45 
        item.hash = hash;
46 
        item.key = k;
47 
        item.val = v;
48 
        self->items[n] = item;
49 
        self->len += 1;
50 
        return;
51 
    }
52 
    tp_raise(,"_tp_dict_hash_set(%d,%d,%s,%s)",self,hash,TP_CSTR(k),TP_CSTR(v));
53 
}
54 
 
55 
void _tp_dict_tp_realloc(TP,_tp_dict *self,int len) {
56 
    tp_item *items = self->items;
57 
    int i,alloc = self->alloc;
58 
    len = _tp_max(8,len);
59 
 
60 
    self->items = (tp_item*)tp_malloc(len*sizeof(tp_item));
61 
    self->alloc = len; self->mask = len-1;
62 
    self->len = 0; self->used = 0;
63 
 
64 
    for (i=0; i
65 
        if (items[i].used != 1) { continue; }
66 
        _tp_dict_hash_set(tp,self,items[i].hash,items[i].key,items[i].val);
67 
    }
68 
    tp_free(items);
69 
}
70 
 
71 
int _tp_dict_hash_find(TP,_tp_dict *self, int hash, tp_obj k) {
72 
    int i,idx = hash&self->mask;
73 
    for (i=idx; ialloc; i++) {
74 
        int n = i&self->mask;
75 
        if (self->items[n].used == 0) { break; }
76 
        if (self->items[n].used < 0) { continue; }
77 
        if (self->items[n].hash != hash) { continue; }
78 
        if (tp_cmp(tp,self->items[n].key,k) != 0) { continue; }
79 
        return n;
80 
    }
81 
    return -1;
82 
}
83 
int _tp_dict_find(TP,_tp_dict *self,tp_obj k) {
84 
    return _tp_dict_hash_find(tp,self,tp_hash(tp,k),k);
85 
}
86 
 
87 
void _tp_dict_setx(TP,_tp_dict *self,tp_obj k, tp_obj v) {
88 
    int hash = tp_hash(tp,k); int n = _tp_dict_hash_find(tp,self,hash,k);
89 
    if (n == -1) {
90 
        if (self->len >= (self->alloc/2)) {
91 
            _tp_dict_tp_realloc(tp,self,self->alloc*2);
92 
        } else if (self->used >= (self->alloc*3/4)) {
93 
            _tp_dict_tp_realloc(tp,self,self->alloc);
94 
        }
95 
        _tp_dict_hash_set(tp,self,hash,k,v);
96 
    } else {
97 
        self->items[n].val = v;
98 
    }
99 
}
100 
 
101 
void _tp_dict_set(TP,_tp_dict *self,tp_obj k, tp_obj v) {
102 
    _tp_dict_setx(tp,self,k,v);
103 
    tp_grey(tp,k); tp_grey(tp,v);
104 
}
105 
 
106 
tp_obj _tp_dict_get(TP,_tp_dict *self,tp_obj k, const char *error) {
107 
    int n = _tp_dict_find(tp,self,k);
108 
    if (n < 0) {
109 
        tp_raise(tp_None,"%s: KeyError: %s\n",error,TP_CSTR(k));
110 
    }
111 
    return self->items[n].val;
112 
}
113 
 
114 
void _tp_dict_del(TP,_tp_dict *self,tp_obj k, const char *error) {
115 
    int n = _tp_dict_find(tp,self,k);
116 
    if (n < 0) { tp_raise(,"%s: KeyError: %s\n",error,TP_CSTR(k)); }
117 
    self->items[n].used = -1;
118 
    self->len -= 1;
119 
}
120 
 
121 
_tp_dict *_tp_dict_new(void) {
122 
    _tp_dict *self = (_tp_dict*)tp_malloc(sizeof(_tp_dict));
123 
    return self;
124 
}
125 
tp_obj _tp_dict_copy(TP,tp_obj rr) {
126 
    tp_obj obj = {TP_DICT};
127 
    _tp_dict *o = rr.dict.val;
128 
    _tp_dict *r = _tp_dict_new();
129 
    *r = *o; r->gci = 0;
130 
    r->items = (tp_item*)tp_malloc(sizeof(tp_item)*o->alloc);
131 
    memcpy(r->items,o->items,sizeof(tp_item)*o->alloc);
132 
    obj.dict.val = r;
133 
    return tp_track(tp,obj);
134 
}
135 
 
136 
int _tp_dict_next(TP,_tp_dict *self) {
137 
    if (!self->len) { tp_raise(0,"_tp_dict_next(...)",0); }
138 
    while (1) {
139 
        self->cur = ((self->cur + 1) & self->mask);
140 
        if (self->items[self->cur].used > 0) {
141 
            return self->cur;
142 
        }
143 
    }
144 
}
145 
 
146 
tp_obj tp_merge(TP) {
147 
    tp_obj self = TP_OBJ();
148 
    tp_obj v = TP_OBJ();
149 
    int i; for (i=0; ilen; i++) {
150 
        int n = _tp_dict_next(tp,v.dict.val);
151 
        _tp_dict_set(tp,self.dict.val,
152 
            v.dict.val->items[n].key,v.dict.val->items[n].val);
153 
    }
154 
    return tp_None;
155 
}
156 
 
157 
volatile tp_obj tp_dict(TP) {
158 
    tp_obj r = {TP_DICT};
159 
    r.dict.val = _tp_dict_new();
160 
    return tp ? tp_track(tp,r) : r;
161 
}
162 
 
163 
tp_obj tp_dict_n(TP,int n, tp_obj* argv) {
164 
    tp_obj r = tp_dict(tp);
165 
    int i; for (i=0; i
166 
    return r;
167 
}
168