10000 got hash maps working · dragoncoder047/pickle@3e1096a · GitHub
[go: up one dir, main page]
Skip to content

Commit 3e1096a

Browse files
dragoncoder047dragoncoder047
authored
got hash maps working
also changed to c++ reference based car and cdr from tinobsy weird, now c++ linter says: more than one instance of function "car" matches the argument list: pickle.hpp(52, 24): function "tinobsy::car(tinobsy::object *x)" (declared at line 3 of "tinobsy/cxxxr.h") pickle.hpp(52, 24): function "car(tinobsy::object *x)" (declared at line 3 of "tinobsy/cxxxr.h") pickle.hpp(52, 24): argument types are: (tinobsy::object *) what is it thinking?
1 parent 5298b00 commit 3e1096a

File tree

10 files changed

+345
-1736
lines changed

10 files changed

+345
-1736
lines changed

‎.vscode/settings.json

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,138 @@
11
{
22
"cSpell.words": [
33
"allocs",
4+
"caaaaaar",
5+
"caaaaadr",
6+
"caaaaar",
7+
"caaaadar",
8+
"caaaaddr",
9+
"caaaadr",
10+
"caaaar",
11+
"caaadaar",
12+
"caaadadr",
13+
"caaadar",
14+
"caaaddar",
15+
"caaadddr",
16+
"caaaddr",
17+
"caaadr",
18+
"caaar",
19+
"caadaaar",
20+
"caadaadr",
21+
"caadaar",
22+
"caadadar",
23+
"caadaddr",
24+
"caadadr",
25+
"caadar",
26+
"caaddaar",
27+
"caaddadr",
28+
"caaddar",
29+
"caadddar",
30+
"caaddddr",
31+
"caadddr",
32+
"caaddr",
33+
"caadr",
34+
"caar",
35+
"cadaaaar",
36+
"cadaaadr",
37+
"cadaaar",
38+
"cadaadar",
39+
"cadaaddr",
40+
"cadaadr",
41+
"cadaar",
42+
"cadadaar",
43+
"cadadadr",
44+
"cadadar",
45+
"cadaddar",
46+
"cadadddr",
47+
"cadaddr",
48+
"cadadr",
49+
"cadar",
50+
"caddaaar",
51+
"caddaadr",
52+
"caddaar",
53+
"caddadar",
54+
"caddaddr",
55+
"caddadr",
56+
"caddar",
57+
"cadddaar",
58+
"cadddadr",
59+
"cadddar",
60+
"caddddar",
61+
"cadddddr",
62+
"caddddr",
63+
"cadddr",
64+
"caddr",
65+
"cadr",
66+
"car",
67+
"cdaaaaar",
68+
"cdaaaadr",
69+
"cdaaaar",
70+
"cdaaadar",
71+
"cdaaaddr",
72+
"cdaaadr",
73+
"cdaaar",
74+
"cdaadaar",
75+
"cdaadadr",
76+
"cdaadar",
77+
"cdaaddar",
78+
"cdaadddr",
79+
"cdaaddr",
80+
"cdaadr",
81+
"cdaar",
82+
"cdadaaar",
83+
"cdadaadr",
84+
"cdadaar",
85+
"cdadadar",
86+
"cdadaddr",
87+
"cdadadr",
88+
"cdadar",
89+
"cdaddaar",
90+
"cdaddadr",
91+
"cdaddar",
92+
"cdadddar",
93+
"cdaddddr",
94+
"cdadddr",
95+
"cdaddr",
96+
"cdadr",
97+
"cdar",
98+
"cddaaaar",
99+
"cddaaadr",
100+
"cddaaar",
101+
"cddaadar",
102+
"cddaaddr",
103+
"cddaadr",
104+
"cddaar",
105+
"cddadaar",
106+
"cddadadr",
107+
"cddadar",
108+
"cddaddar",
109+
"cddadddr",
110+
"cddaddr",
111+
"cddadr",
112+
"cddar",
113+
"cdddaaar",
114+
"cdddaadr",
115+
"cdddaar",
116+
"cdddadar",
117+
"cdddaddr",
118+
"cdddadr",
119+
"cdddar",
120+
"cddddaar",
121+
"cddddadr",
122+
"cddddar",
123+
"cdddddar",
124+
"cddddddr",
125+
"cdddddr",
126+
"cddddr",
127+
"cdddr",
128+
"cddr",
129+
"cdr",
130+
"cxxxr",
4131
"defop",
5132
"eofp",
6133
"eqcmp",
7134
"intof",
135+
"mkcxxxr",
8136
"numof",
9137
"stringof",
10138
"tinobsy"

‎Makefile

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44

55
test: buildtest64 valgrind64 buildtest32 valgrind32 clean checkleaks
66

7-
VALGRINDOPTS = --track-origins=yes --leak-check=full --show-reachable=yes --main-stacksize=1000
7+
VALGRINDOPTS = -s --track-origins=yes --leak-check=full --show-reachable=yes --main-stacksize=1000
88

99
ifeq (,$(findstring raspberrypi,$(shell uname -a)))
1010
VALGRINDOPTS += --show-leak-kinds=all

‎pickle.cpp

Lines changed: 51 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -117,7 +117,7 @@ void pvm::start_thread() {
117117
void pvm::step() {
118118
next_inst:
119119
if (!this->queue) return;
120-
object* next_type = car(cdr(this->curr_thread()));
120+
object* next_type = cadr(this->curr_thread());
121121
object* op = this->pop_inst();
122122
if (!op) {
123123
object* last = this->queue;
@@ -133,12 +133,12 @@ void pvm::step() {
133133
}
134134
object* type = car(op);
135135
if (eqcmp(type, next_type) != 0) goto next_inst;
136-
object* inst_name = car(cdr(op));
137-
object* cookie = cdr(cdr(op));
136+
object* inst_name = cadr(op);
137+
object* cookie = cddr(op);
138138
object* pair = assoc(this->function_registry, inst_name);
139139
ASSERT(pair, "Unknown instruction %s", this->stringof(inst_name));
140140
next_type = this->fptr(cdr(pair))(this, cookie, next_type);
141-
car(cdr(this->curr_thread())) = next_type;
141+
cadr(this->curr_thread()) = next_type;
142142
this->queue = cdr(this->queue);
143143
}
144144

@@ -416,8 +416,9 @@ object* parse(pvm* vm, object* cookie, object* inst_type) {
416416
// ------------------------- HASHMAPS (OBJECTS) -------------------------------
417417

418418
// Returns the found node or nil if the hash is not found.
419-
static object* hashmap_find(pvm* vm, object* map, uint64_t hash) {
419+
static object* hashmap_get(pvm* vm, object* map, uint64_t hash) {
420420
// Each hashmap node is a 4-cons tree ((hash . (key . value)) . (left . right))
421+
// but this gets printed as ((hash key . value) left . right) when the map is printed as-is
421422
uint64_t hh = hash;
422423
DBG("Searching hashmap for hash %" PRId64 " {", hash);
423424
recurse:
@@ -427,13 +428,10 @@ static object* hashmap_find(pvm* vm, object* map, uint64_t hash) {
427428
}
428429
object* hash_pair = car(map);
429430
if (hash_pair) {
430-
printf("hash_pair = ");
431-
vm->dump(hash_pair);
432-
putchar(' ');
433-
vm->dump(car(hash_pair));
434431
int64_t this_hash = vm->intof(car(hash_pair));
432+
DBG("this_hash=%" PRId64, this_hash);
435433
if (this_hash == hash) {
436-
DBG("Found matching key for hash %" PRId64, hash);
434+
DBG("Found matching key for hash %" PRId64 " }", hash);
437435
return map;
438436
}
439437
}
@@ -454,6 +452,7 @@ static object* hashmap_find(pvm* vm, object* map, uint64_t hash) {
454452
static object* hashmap_set(pvm* vm, object** map, object* key, uint64_t hash, object* val) {
455453
DBG("Setting hash %" PRId64 " on hashmap. {", hash);
456454
uint64_t hh = hash;
455+
object* newnode = nil;
457456
recurse:
458457
if (*map == nil) {
459458
DBG("Tree is terminated -- add new node. }");
@@ -467,15 +466,17 @@ static object* hashmap_set(pvm* vm, object** map, object* key, uint64_t hash, ob
467466
if (!hash_pair) {
468467
DBG("Found tombstoned node. Inserting key.");
469468
car(*map) = vm->cons(vm->integer(hash), vm->cons(key, val));
469+
newnode = *map;
470+
if (!children) return newnode; // No children to search and kill
470471
goto killshadow;
471472
} else {
472473
// Check if the hashes match
473474
int64_t z = vm->intof(car(hash_pair));
474475
if (z == hash) {
475476
DBG("Found matching node. Re-setting it. }");
476477
if (!cdr(hash_pair)) cdr(hash_pair) = vm->cons(nil, nil);
477-
car(cdr(hash_pair)) = key;
478-
cdr(cdr(hash_pair)) = val;
478+
cadr(hash_pair) = key;
479+
cddr(hash_pair) = val;
479480
return *map;
480481
}
481482
}
@@ -495,6 +496,11 @@ static object* hashmap_set(pvm* vm, object** map, object* key, uint64_t hash, ob
495496
else map = &cdr(children);
496497
hh >>= 1;
497498
DBG("Continuing on %s", ll ? "LEFT" : "RIGHT");
499+
killagain:
500+
if ((*map) == nil) {
501+
DBG("Reached end of hash path. Done killing. }");
502+
return newnode;
503+
}
498504
hash_pair = car(*map);
499505
ll = hh & 1;
500506
children = cdr(*map);
@@ -505,15 +511,15 @@ static object* hashmap_set(pvm* vm, object** map, object* key, uint64_t hash, ob
505511
car(*map) = nil;
506512
}
507513
}
508-
if (!children) {
514+
if (children == nil) {
509515
DBG("Reached node with no children. Stopping }");
510-
return *map;
516+
return newnode;
511517
}
512518
if (ll) map = &car(children);
513519
else map = &cdr(children);
514520
hh >>= 1;
515521
DBG("Shadow recursing on %s", ll ? "LEFT" : "RIGHT");
516-
goto killshadow;
522+
goto killagain;
517523
}
518524

519525
object* pvm::get_property(object* obj, uint64_t hash, bool recurse) {
@@ -534,17 +540,17 @@ object* pvm::get_property(object* obj, uint64_t hash, bool recurse) {
534540
if (obj->type != &obj_type) return nil;
535541
// Search the hashmap.
536542
object* hashmap = cdr(obj);
537-
object* node = hashmap_find(this, obj, hash);
538-
if (node) return cdr(car(node));
543+
object* node = hashmap_get(this, hashmap, hash);
544+
if (node) return cddar(node);
539545
return nil;
540546
}
541547

542-
bool pvm::set_property(object* obj, object* val, uint64_t hash, object* value) {
548+
bool pvm::set_property(object* obj, object* key, uint64_t hash, object* value) {
543549
// Nil has no properties
544550
if (!obj) return false;
545551
// Check if it is an object-object (primitives have no own properties)
546552
if (obj->type != &obj_type) return false;
547-
hashmap_set(this, &cdr(obj), val, hash, value);
553+
hashmap_set(this, &cdr(obj), key, hash, value);
548554
return true;
549555
}
550556

@@ -553,7 +559,7 @@ bool pvm::remove_property(object* obj, uint64_t hash) {
553559
if (!obj) return false;
554560
// Check if it is an object-object (primitives have no own properties)
555561
if (obj->type != &obj_type) return false;
556-
bool had = hashmap_find(this, cdr(obj), hash) != nil;
562+
bool had = hashmap_get(this, cdr(obj), hash) != nil;
557563
// Try to set the node to nil, which will kill the shadow references
558564
object* node = hashmap_set(this, &cdr(obj), nil, hash, nil);
559565
// Then kill this node too
@@ -619,8 +625,7 @@ static void make_refs_list(pvm* vm, object* obj, object** alist) {
619625
return;
620626
}
621627
vm->push(vm->cons(obj, vm->integer(1)), *alist);
622-
if (obj->type == &obj_type) return; // hashmaps are guaranteed non disjoint, i guess
623-
make_refs_list(vm, car(obj), alist);
628+
if (obj->type != &obj_type) make_refs_list(vm, car(obj), alist); // hashmaps are guaranteed non disjoint, i guess
624629
obj = cdr(obj);
625630
goto again;
626631
}
@@ -652,13 +657,16 @@ static void print_with_refs(pvm*, object*, object*, int64_t*);
652657
static void print_hashmap(pvm* vm, object* node, object* alist, int64_t* counter) {
653658
recur:
654659
if (node) {
655-
print_with_refs(vm, car(cdr(car(node))), alist, counter);
656-
printf(": ");
657-
print_with_refs(vm, cdr(cdr(car(node))), alist, counter);
658-
printf(", ");
660+
if (car(node)) {
661+
object* hinfo = car(node);
662+
print_with_refs(vm, cadr(hinfo), alist, counter);
663+
printf(" -> ");
664+
print_with_refs(vm, cddr(hinfo), alist, counter);
665+
printf(" ;[hash=%" PRId64 "] ", vm->intof(car(hinfo)));
666+
}
659667
if (!cdr(node)) return;
660-
print_hashmap(vm, car(cdr(node)), alist, counter);
661-
node = cdr(cdr(node));
668+
print_hashmap(vm, cadr(node), alist, counter);
669+
node = cddr(node);
662670
goto recur;
663671
}
664672
}
@@ -668,8 +676,17 @@ static void print_with_refs(pvm* vm, object* obj, object* alist, int64_t* counte
668676
printf("NIL");
669677
return;
670678
}
679+
// test if it's in the table
680+
int64_t ref = reffed(vm, obj, alist, counter);
681+
if (ref < 0) {
682+
printf("#%" PRId64 "#", -ref);
683+
return;
684+
}
685+
if (ref) {
686+
printf("#%" PRId64 "=", ref);
687+
}
671688
#define PRINTTYPE(t, f, fmt) else if (obj->type == t) printf(fmt, obj->f)
672-
else if (obj->type == &string_type) {
689+
if (obj->type == &string_type) {
673690
putchar('"');
674691
for (char* c = obj->as_chars; *c; c++) {
675692
char e = escape(*c);
@@ -688,16 +705,7 @@ static void print_with_refs(pvm* vm, object* obj, object* alist, int64_t* counte
688705
PRINTTYPE(NULL, as_ptr, "<garbage %p>");
689706
#undef PRINTTYPE
690707
else if (obj->type == &cons_type) {
691-
// it's a cons
692-
// test if it's in the table
693-
int64_t ref = reffed(vm, obj, alist, counter);
694-
if (ref < 0) {
695-
printf("#%" PRId64 "#", -ref);
696-
return;
697-
}
698-
if (ref) {
699-
printf("#%" PRId64 "=", ref);
700-
}
708+
// it's a cons and unreffed
701709
// now print the object
702710
putchar('(');
703711
for (;;) {
@@ -723,14 +731,14 @@ static void print_with_refs(pvm* vm, object* obj, object* alist, int64_t* counte
723731
}
724732
else if (obj->type == &obj_type) {
725733
// Try to find the class name
726-
// TODO: String/symbol/int hash.
734+
// TODO: String/symbol/int static hash.
727735
const char* nm = "object";
728-
// if (car(obj) && !cdr(car(obj)) && car(car(obj))) {
736+
// if (car(obj) && car(car(obj))) {
729737
// object* super = car(car(obj));
730-
// object* name = vm->get_property(obj, vm->static_hash(vm->string("__name__")));
738+
// object* name = vm->get_property(super, vm->static_hash(vm->string("__name__")));
731739
// if (name->type == &symbol_type) nm = vm->stringof(name);
732740
// }
733-
printf("%s { ", nm);
741+
printf("%s{ ", nm);
734742
print_hashmap(vm, cdr(obj), alist, counter);
735743
putchar('}');
736744
}

‎pickle.hpp

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -129,10 +129,10 @@ class pvm : public tinobsy::vm {
129129
}
130130

131131
// create a cons cell
132-
inline object* cons(object* car, object* cdr) {
132+
inline object* cons(object* xar, object* xdr) {
133133
object* o = this->alloc(&cons_type);
134-
car(o) = car;
135-
cdr(o) = cdr;
134+
car(o) = xar;
135+
cdr(o) = xdr;
136136
return o;
137137
}
138138

0 commit comments

Comments
 (0)
0