Libs for database

Go To Last Post
17 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Freaks,

I need to implement a database on a system that currently uses fixed memory locations for data storage. The current setup is too inflexible for some upgrades I am planing. I need something that allows for dynamic memory allocation.

The system consists of an atmega640 with 32K of external BB ram.

Can anybody suggest a lib or some tools that might help me with this project. I familiar with linked lists but I do not want to write this one from scratch.

Thanks,

A.

PS. I searched database on the forum and could not find anything that was directly related.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'd agree that the linked list idea sounds like a simple solution. Not suer if it helps but see the attached. Although this is quite a technical program I wrote to analyze EXT3 disk structures the key thing in this is my data structure record_t{}

I create a linked list in the following:

					if (list_base == 0) {
						// the very start of the linked list when processing the
						// very first entry in /
						list_base = (record_t *) malloc( sizeof(record_t) );
						current = list_base;
					}
					else {
						// otherwise just keep adding to the list
						previous->next = (record_t *) malloc( sizeof(record_t) );
						current = previous->next;
					}
					// then fill in all the details for this entry
					current->inode = d_ptr->inode;
					current->ftype = d_ptr->file_type;
					strcpy(current->name, name);
					current->next = 0;
					current->parent = parent;

Then later process the list with something like:

		// show the list so far...
		process = list_base;
		while(process) {
			printf("this=%08X name=%s inode=%u ftype=%u, parent=%08X\n", 
				(unsigned int)process, process->name, process->inode, process->ftype, (unsigned int)process->parent);
			process = process->next;
		}

and finally delete it with:

	current = list_base;
	while(current) {
		to_free = current;
		current = current->next;
		free(to_free);
	}

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Cliff,

I will take a look at it and see if it fits.

Thanks again,

A.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

There has been questions here in the past about SQLite, but IIRC the outcome was that even that was too clumsy for an AVR.

Tenfold your RAM, and the company I currently work for might have something for you: http://www.enea.com/Templates/Pr... :D

Jokes aside: Yes, a linked list might be a good alternative. What requirements on e.g. performance do you have? Will this be a "database" that does all sorts of operations frequently, or will it "mostly lookups/reads with some updating and much less frequent new-writes, deletes" or what? If lookup-time is critical some kind of balanced tree might be an alternative.

Combinations could also be interesting, e.g. an index tree pointing out blocks of records (so the last part of the look-up is a sequential search in a block with, say, 10 records). We're closing in on the classical physical structures for DB systems now.. Good Google words might be "B tree", "B+ tree" and "B* tree" ('B' for "balanced") and similar.

Need sequential access also? In some specific sort order? Etc...

Much water under bridges since I had my fingers deep into this goo, but it is a fascinating and extremely stimulating subject. I'll watch this thread carefully!

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Johan,

Thanks for the response.

Essentially, I have an structure of (3) text strings (70 chars) plus some related data in an array of 100 structures. Although this works well, my requirements have changed.

I now need to be able to vary both the length of the strings and the number of stings in each structure. I often find that a user may only need to create two messages, each one consisting of a single line of much greater length than the fixed length will allow.
The system has more than enough memory for our application but the current implementation lacks the finesse to handle the data efficiently.

Access speed is not critical. Although the system is very busy, the actual data manipulation is at human interface speeds.

Thanks again for the feedback.

A.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Something like this maybe?

typedef struct data_t {
  char * str1;
  char * str2;
  char * str3;
  int n_data;
  long l_data;
  char c_data;
  struct data_t * next;
} data_t;

data_t * list_base = 0, *current, *previous;

void add_record(char * str1, char *str2, char *str3, int n, long l, char c) {
  // create new element at end of list
  if (list_base = 0) {
    // special case if list hasn't started yet
    list_base = (data_t *) malloc( sizeof(data_t) );
    current = list_base;
  }
  else {
    // otherwise add to the last one
    previous->next = (data_t *) malloc( sizeof(data_t) );
    current = previous->next;
  }
  // now fill in newly created record
  current->str1 = malloc(strlen(str1)+1);
  strcpy(current->str1, str1);
  current->str2 = malloc(strlen(str2)+1);
  strcpy(current->str2, str2);
  current->str3 = malloc(strlen(str3)+1);
  strcpy(current->str3, str3);
  current->n_data = n;
  current->l_data = l;
  current->c_data = c;
  // update previous to now point at this new one for next time
  previous = current;
}

int main(void) {
  add_record("hello", "good", "evening", 12345, 0xDEADBEEF, 'C');
  add_record("apples", "oranges", pears", 54321, 0xBEEFDEAD, 'X');
}

You'll also need a delete_record() and a find_record(). For the latter you need to pick one or more of the fields to be a "key" field. In my example perhaps the "char" might be used then you'd use something like:

data_t * found;
found = find_record('X');

In the simplest case the find just starts at list_base then follows the "check = list_base->next" pointer to walk the list, stopping at each and testing check->c_data to see if it matches. For 100 records this shouldn't be too onerous even if you have to walk through the previous 99 records to find it. (Of course 'A'..'Z' - if that's all you used in the c_data - might not be enough to uniquely identify all 100)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

OK, a bit further on. This ends with "oranges" in buffer[]:
(and this code actually compiles and runs unlike the last one)

#include 
#include 
#include 
#include 

typedef struct data_t {
  char * str1;
  char * str2;
  char * str3;
  int n_data;
  long l_data;
  char c_data;
  struct data_t * next;
} data_t;

data_t * list_base = 0, *current, *previous;

void add_record(char * str1, char *str2, char *str3, int n, long l, char c) {
  // create new element at end of list
  if (list_base == 0) {
    // special case if list hasn't started yet
    list_base = (data_t *) malloc( sizeof(data_t) );
    current = list_base;
  }
  else {
    // otherwise add to the last one
    previous->next = (data_t *) malloc( sizeof(data_t) );
    current = previous->next;
  }
  // now fill in newly created record
  current->str1 = malloc(strlen(str1)+1);
  strcpy(current->str1, str1);
  current->str2 = malloc(strlen(str2)+1);
  strcpy(current->str2, str2);
  current->str3 = malloc(strlen(str3)+1);
  strcpy(current->str3, str3);
  current->n_data = n;
  current->l_data = l;
  current->c_data = c;
  // make sure next pointer is 0 in case this isn't what malloc delivers as it marks end of list
  current->next = 0;
  // update previous to now point at this new one for next time
  previous = current;
}

data_t * find_record(char c) __attribute__((noinline));
data_t * find_record(char c) {
	data_t * check = list_base;
	// first check there is a list
	if (check) {
		// then walk the list until a NULL pointer is reached
		while (check) {
			// until we find what we're looking for
			if (check->c_data == c) {
				return check;
			}
			check = check->next;
		}
	}
	return 0; // return NULL at end of list
}

void delete_record(data_t * rec) {
  // tricky as we need to get back to the previous record to fix up its next link
}

int main(void) {
  char buffer[20];

  data_t * found;
  add_record("hello", "good", "evening", 12345, 0xDEADBEEF, 'C');
  add_record("apples", "oranges", "pears", 54321, 0xBEEFDEAD, 'X');
  found = find_record('X');
  if (found) {
    sprintf(buffer, "%s", found->str2);
  }
} 

I've just arbitrarily chosen to use the c_data in the record as the key field for the searching.

As the unfilled delete_record() function shows this is a bit tricky. That's because this is a singly linked list. Say you want to delete record N then you actually need to fix up the "next" pointer in N-1 to N+1 but when you enter delete_record() you know N and you can easily find N+1 (via N->next) but how do you find N-1 in the list? The only current way is either to keep a list of all the record addresses and given the address of N you look it up in the array/list and find out what its predecessor is. Or you start at list_base, walk the list, remember each time the previous record pointer and when you find N then "previous" contains N-1.

The other solution is (the one everyone actually uses) to make this into a doubly linked list where each record has both a "next" and a "prev"(ious) pointer then given N you can easily find N-1 and N+1 and join them together. The downside of double links is that it makes things more complicated when creating and deleting elements in the list. I didn't start with double links as it's easier to see what's going on with a single linked list to start with.

If you won't ever delete anything from the list - just add or update then the above should be enough.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Cliff,

Thank you for both the code and the explanation.

A couple of questions:

Why was this necessary? Why would "inline" code be a problem?

Quote:

data_t * find_record(char c) __attribute__((noinline));

How would I allow for a variable number of strings? There will be some limit ( Up to sixteen would fit ). I guess I just need to malloc() based on the number of strings. If I save the number of stings in the structure, is this the best method?

Thanks again,

A.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Cliff,

A couple of more questions:

How do I limit the memory area that will be accessed by malloc()?
Does malloc() prevent an overwrite of memory used by other variables?

Thanks again,

A.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Why was this necessary? Why would "inline" code be a problem?

I was battling the optimiser. If it inlines a function call in main() then "run to cursor" on the right click context menu won't allow you to select the call to the function. So I force it noinline simply to make the debugging experience in AS4 easier.

As for variable number of strings - you'd want the record to hold a pointer to a list of pointers which each point to char. Given that a pointer is 16bits (2 bytes) then to add 5 strings start by allocating 10 bytes then alloc 5 lots of memory for each string. Then fill in the 10 bytes with the 5 pointers. You will find yourself using char ** rather than the normal char * syntax and will be able to join an elite club of C programmers :-)

(to be honest, in my existing scheme, any "" string just uses a few bytes (mainly the 4 byte overhead of each malloc()) so I'd actually allow for the max expected number of strings then:

add_record("hello", "there", "". "". "". ...);

In fact the code that malloc() the string space can just say:

if (strlen(strN)) {
  current->strN = malloc(strlen(strN)+1);
}
else {
  current-strn = NULL;
}

to save any malloc overhead (all it wastes are the two bytes of the unused pointer).

Then again the pointers to pointers idea is the ultimate solution.

(left as an easy exercise for the reader ;-))

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Cliff,

A couple of more questions:

How do I limit the memory area that will be accessed by malloc()?
Does malloc() prevent an overwrite of memory used by other variables?

Thanks again,

A.

PS. My last post was just before yours, hence the double post.

Last Edited: Wed. Jun 29, 2011 - 05:54 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

OK, I couldn't help myself. Here's a (not perfect!) version that now uses double-links and implements delete_record(). It also allows a variable number of strings and uses the "char ** strings" I mentioned previously.

The one fault is the add_record() still requires three string parameters but there's a new parameter that tells it how many are actually valid. It also can only cope with up to 3. Really the add_record() itself should be passed a char** list of string pointers and it should not have the hard coded 3 limit or the fixed str1, str2, str3 names.

But for now it's headed in the right direction.

buffer[] still gets "oranges" and as far as I can tell - without extensive testing, the delete_record() works.

Note that the way all this is done is asking for heap fragmentation.

#include 
#include 
#include 
#include 

typedef struct data_t {
  char ** strings;
  int num_strings;
  int n_data;
  long l_data;
  char c_data;
  struct data_t * next;
  struct data_t * prev;
} data_t;

data_t * list_base = 0, *current, *previous;

void add_record(char * str1, char *str2, char *str3, int num_strings, int n, long l, char c) {
  // create new element at end of list
  if (list_base == 0) {
    // this is special case if list hasn't started yet
    list_base = (data_t *) calloc( sizeof(data_t), 1 );
    current = list_base;
  }
  else {
    // otherwise add to the last one
    previous->next = (data_t *) calloc( sizeof(data_t), 1 );
    current = previous->next;
  }
  // now fill in newly created record
  current->num_strings = num_strings;
  // First create an array of string pointers
  current->strings = calloc(2 * num_strings, 1);
  // then store any strings passed
  if (num_strings > 0) {
  	current->strings[0] = calloc(strlen(str1)+1, 1);
	strcpy(current->strings[0], str1);
  }
  if (num_strings > 1) {
  	current->strings[1] = calloc(strlen(str2)+1, 1);
	strcpy(current->strings[1], str2);
  }
  if (num_strings > 2) {
  	current->strings[2] = calloc(strlen(str3)+1, 1);
	strcpy(current->strings[2], str3);
  }

  current->n_data = n;
  current->l_data = l;
  current->c_data = c;
  // make sure next pointer is 0 in case this isn't what malloc delivers as it marks end of list
  current->next = 0;
  // fill in the backwards link too
  current->prev = previous;
  // update previous to now point at this new one for next time
  previous = current;
}

data_t * find_record(char c) __attribute__((noinline));
data_t * find_record(char c) {
	data_t * check = list_base;
	// first check there is a list
	if (check) {
		// then walk the list until a NULL pointer is reached
		while (check) {
			// until we find what we're looking for
			if (check->c_data == c) {
				return check;
			}
			check = check->next;
		}
	}
	return 0; // return NULL at end of list
}

void delete_record(data_t * rec) __attribute__((noinline));
void delete_record(data_t * rec) {
  data_t * prev, *next;
  int i = 0;
  // get the pointers to N-1 and N+1 (may be 0)
  next = rec->next;
  prev = rec->prev;
  prev->next = next;
  next->prev = prev;
  // now free() anything that was malloc'd
  for (i=0; inum_strings; i++) {
  	free(rec->strings[i]);
  }
  // and the pointer list
  free(rec->strings);
}

int main(void) {
  char buffer[20];

  data_t * found;
  add_record("hello", "good", "evening", 3, 12345, 0xDEADBEEF, 'C');
  add_record("apples", "oranges", "", 2, 54321, 0xBEEFDEAD, 'X');
  found = find_record('X');
  if (found) {
    sprintf(buffer, "%s", found->strings[1]);
  }
  delete_record(found);
  add_record("porsche", "ferrari", "", 2, 33333, 0xA5A5A5A5, 'F');
} 

BTW malloc() offers you all the RAM from the end of .bss to base of the stack. malloc() will return 0 if there's no memory left - I should be checking for this!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Cliff,

I gotta ask.

You are obsessed, right?

You have been a big help.

Thanks,

A.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

You are obsessed, right?

Just a nerd - what can I tell you! :?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks much!

ALL the other examples I found with google had the definition of the structure wrong, missing the name from either the beginning or end, leaving me with an "opaque" thingy I didn't know how to deal with. I didn't need double pointers 'cause I'm not adding or removing things from the middle.

Ok, it's dumb but I wanted to learn how...

#include 


typedef struct Event 
{
	struct Event *Next ;
	int E ;
	int V ;
}Event;

Event * Head = NULL ;
Event * Tail = NULL ;


void EventAdd(int E, int V)
{
    struct Event *temp;  
  
    temp=(Event*)malloc(sizeof(Event));  
	if (temp==NULL) return ;
    temp->E = E; 
	temp->V = V;
	temp->Next = NULL;
  
    if (Tail == NULL)  
    {  
       //List is Empty  
       Tail=temp;  
       Head=temp; 
    }  
    else  
    {  
	   Tail->Next = temp;
	   Tail = temp;
    }  
}

int EventTop(void)
{
	if (Head==NULL) return 0;
	return Head->E ;
}

int EventValue(void)
{
	if (Head==NULL) return 0;
	return Head->V;
}

void TakeEvent(void)
{
	if (Head == NULL) return ;
	Event *ThisOne;
	ThisOne = Head ;
	Head = Head->Next ;
        if (Head==NULL) Tail=NULL;
	free(ThisOne);
}

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for this, but didn't compile for me,

 

changed this line

for (i=0; inum_strings; i++) {

 

to

for (i=0; i < rec->num_strings; i++) {

and seems to work great!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That's the forum software. It has a habit of eating things between angle brackets because it thinks they are HTML tags. As this is an old post try reading it on the legacy site where the code should be intact.