arkhipenko / dictionary Goto Github PK
View Code? Open in Web Editor NEWA dictionary data type with a fast b-tree based search
License: BSD 3-Clause "New" or "Revised" License
A dictionary data type with a fast b-tree based search
License: BSD 3-Clause "New" or "Revised" License
Thanks for this useful library.
Some ideas to implement the deletion of an element in a pretty memory efficient way.
Add a bool deleted; to every node. This will increase the RAM memory usage. A more efficient way might be a shadow bit-array that can hold 8 bools per byte.
Set the most significant bit of the first char of the key.
keystr[0] ^= 0x80;
The key field typically contains ASCII so highest bit is not set normally.
This would not add memory and would allow for undelete as well.
For all methods the deleted nodes stay in memory (no difficult re balancing) and they could in theory be reused,
To be able to iterate over the dictionary, implement functions like these that skip deleted keys.
Just to share.
It would be interesting to have the dictionary be stored in persistent storage (LittleFS/SPIFFS) and lookup without loading into memory.
My application downloads a JSON string once an hour, which is used as a local cache. The data is around 400 entries of 10-digit numeric strings as keys, and booleans as values. There seems to be a memory leak that builds up over time, which eventually prevents the JSON from being parsed. This is on an ESP32. I do not have PSRAM on this particular board.
Following the documented advice to recreate the object rather than calling destroy()
, I initially did this by simply assigning the new cache to the old:
Dictionary *new_cache = new Dictionary( 8192 );
new_cache->jload( JSON );
cache = new_cache;
After a few iterations to have memory usage settle, this seems to leak 80 bytes per iteration. I also tried to add a cache->destroy()
before assigning the new cache, but this caused a fatal error on the ESP32:
===============
[START]
Heap available at start: 369460
1 attempt
Heap before rebuild: 369460
Heap after allocation: 369380
Heap after JSON parse: 299812
Guru Meditation Error: Core 1 panic'ed (LoadProhibited). Exception was unhandled.
Core 1 register dump:
PC : 0x400d0fb7 PS : 0x00060530 A0 : 0x800d1508 A1 : 0x3ffb1f60
A2 : 0x00000000 A3 : 0x3ffbfec0 A4 : 0x00000000 A5 : 0x00000003
A6 : 0x00000003 A7 : 0x00000000 A8 : 0x800d1b14 A9 : 0x3ffb1f40
A10 : 0x3ffb1f80 A11 : 0x00000006 A12 : 0x0000000a A13 : 0x0000ff00
A14 : 0x00ff0000 A15 : 0xff000000 SAR : 0x00000010 EXCCAUSE: 0x0000001c
EXCVADDR: 0x00000000 LBEG : 0x400014fd LEND : 0x4000150d LCOUNT : 0xffffffff
ELF file SHA256: 0000000000000000
Backtrace: 0x400d0fb7:0x3ffb1f60 0x400d1505:0x3ffb1f80 0x400d28b9:0x3ffb1fb0 0x400860ed:0x3ffb1fd0
Rebooting...
===============
Here's the output without calling destroy()
:
And the test program with data similar to what's being loaded in my full program:
Im looking for some help, I think its related to my lack of c++ knowledge and pointers.
I have the below code (cutdown version of it) and whenever I include the dictionary code inside the RFID task ( ... if (d[rfid_uid.substring(1)] != "") ), the esp32 panic's with the below message. The panic only happens sporadically, after a random number of minutes of playing mp3's, so I think what is happening is my RFID task is trying to access the dictionary which was populated during the setup() function and possibly these memory addresses have now been overwritten? I thought that since I had created the dictionary in the global section, this would not be the case, but this is my lack of knowledge.
Do you have any ideas how I can make this play nicely? Essentially I have a json file with key value pair (UID and SONG) and I am populating a dictionary which then maps the UID of a RFID card to a MP3 file.
I'm using a ESP32 wroom dev board and Platformio
########## PANIC ##############
Guru Meditation Error: Core 0 panic'ed (Unhandled debug exception).
Debug exception reason: Stack canary watchpoint triggered (RFID Task)
Core 0 register dump:
PC : 0x40084f25 PS : 0x00060c36 A0 : 0x00060c30 A1 : 0x3ffaefb0
A2 : 0x3ffb945c A3 : 0xffffffff A4 : 0x00000000 A5 : 0x00000001
A6 : 0x00060620 A7 : 0x00000001 A8 : 0x8008c88e A9 : 0xffffffff
A10 : 0x00000003 A11 : 0x00060c23 A12 : 0x00060c20 A13 : 0x00060623
A14 : 0x007b945c A15 : 0x003fffff SAR : 0x0000001b EXCCAUSE: 0x00000001
EXCVADDR: 0x00000000 LBEG : 0x40084a95 LEND : 0x40084a9d LCOUNT : 0x00000027
Backtrace:0x40084f22:0x3ffaefb00x00060c2d:0x3ffaf0b0 |<-CORRUPTED
ELF file SHA256: 0000000000000000
Rebooting...
############# END PANIC ##############
#include <Dictionary.h>
#include <DictionaryDeclarations.h>
// RFID UID mapping dictionary
Dictionary &d = *(new Dictionary(20));
// RFID Task
void RFIDTask(void *parameters) {
Serial.println("Starting RFID Task");
// Loop forever
while (1) {
// RFID testing
if (rfid.PICC_IsNewCardPresent()) { // new tag is available
if (rfid.PICC_ReadCardSerial()) { // NUID has been readed
MFRC522::PICC_Type piccType = rfid.PICC_GetType(rfid.uid.sak);
Serial.print("RFID/NFC Tag Type: ");
Serial.println(rfid.PICC_GetTypeName(piccType));
// print UID in Serial Monitor in the hex format
Serial.print("UID:");
String rfid_uid = "";
for (int i = 0; i < rfid.uid.size; i++) {
Serial.print(rfid.uid.uidByte[i] < 0x10 ? " 0" : " ");
Serial.print(rfid.uid.uidByte[i], HEX);
rfid_uid.concat(String(rfid.uid.uidByte[i] < 0x10 ? " 0" : " "));
rfid_uid.concat(String(rfid.uid.uidByte[i], HEX));
}
Serial.println();
rfid.PICC_HaltA(); // halt PICC
rfid.PCD_StopCrypto1(); // stop encryption on PCD
rfid_uid.toUpperCase();
// Check dictionary for UID value and send MP3 to audio queue
if (d[rfid_uid.substring(1)] != "") {
Serial.print("RFID matched the song: ");
Serial.println(d[rfid_uid.substring(1)]);
String story = d[rfid_uid.substring(1)];
String storyPath = "/stories/" + story;
Serial.println(storyPath);
next_song(storyPath);
} else {
Serial.print("No RFID match found for: ");
Serial.println(rfid_uid.substring(1));
Serial.println(d[rfid_uid.substring(1)]);
}
}
}
}
}
void setup() {
// Serial setup
Serial.begin(115200);
// Load RFID UID Dictionary
File myFile = SD.open("/stories/uid_mapping.json");
if (myFile) {
d.jload(myFile);
// d("04 17 67 A2 4C 68 80", "Goldilocks and the Three Bears.mp3");
// d("04 17 67 A2 4C 68 81", "Jack and the Beanstalk.mp3");
Serial.println("RFID Dictionary");
Serial.println(d["04 5A DC A2 4C 68 81"]);
myFile.close();
} else {
Serial.println("error opening /stories/uid_mapping.json");
}
// Start RFID Task
Serial.println("Starting RFID Task...");
xTaskCreatePinnedToCore(RFIDTask,
"RFID Task",
1024,
NULL,
0,
NULL,
0);
}
investigating...
Hi there,
I'm trying to do a code using Homespan library, and was interested by your library as it lets me store in one easy to find location all the elements I need (in my case, for a TV connected over RS232, I would have one dictionary for each input, in which I find the name, the index, the activation command, a confirmation command).
When working in one giant ino file, it works. However, I'd like to have the dictionary on a separated tab, and just it. How could I do this ? I understand it needs a function, but I can't make a dictionary permanent so it works everywhere in my full code right ?
Sorry for this stupid question, I very very new to this (inducing C++)... Though, already quite proud of what I already achieved ! ๐
Hi:
Don't know if this is the right place to ask this....
When tring to use yor library with MKR1010, one or zero I get this error:
In file included from C:...\Arduino\pista_x_mkr_V2\pista_x_mkr_V2.ino:21:0:
"c:....\Arduino\libraries\Dictionary\src/Dictionary.h: In member function 'arduino::String Dictionary::json()':
c:...\Arduino\libraries\Dictionary\src/Dictionary.h:566:9: error: ambiguous overload for 'operator=' (operand types are 'arduino::String' and 'char')"
In row 21 of "pista_x_mkr_V2.ino", I have: "#include <Dictionary.h>"
This issue happens to me even with the examples. Do you know what can be the issue?. I have tried old versions of the library, and below version 3.0.0 it compiles, but I can't use it as I need to use JSON strings.
Thanks in advance.
Great job, but I need sorted index function for my project.
It seems the current implementation is in the .h file. This is causing issue when I need to include the Dictionary.h file in a class header, which results in the implementation get compiled multiple times in the project and linker complains about the duplicate implementations found in multiple cpp files that include the header file.
Is it possible to separate out the implementation into .cpp file?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.