How make a insertion sort on 2d linked list

Hi to all,
I am working on a code which makes a insertion sort on 2d linked list in my RAM .
But the run time error says that i am not making it right…
I tried a lot to figure out where i am wrong, but i am failed…

I have so many doubts on my code:D

The address returned by xalloc is 20 bits value.
physicalAdd = _xalloc(Node_size1, 12, XALLOC_ANY);
*p = (struct tnode *)physicalAdd;
How *p will hold 20 bits value?

Here is my code

struct tnode
{
int *dat;
struct tnode *left;
struct tnode *right;
};

void insertsort(struct tnode **p, int *value);
void print(struct tnode *root1);

int main(void)
{
int Datawrit[9], i;
int Dataread[9];
struct tnode *root1;
unsigned long physicalAdd;

Datawrit[0]= 5;
Datawrit[1]= 9;
Datawrit[2]= 2;
Datawrit[3]= 1;
Datawrit[4]= 7;
Datawrit[5]= 6;
Datawrit[6]= 8;
Datawrit[7]= 3;
Datawrit[8]= 4;

for(i = 0; i < 9; i++)
memset(Datawrit + i, Datawrit[i], 1);
physicalAdd = xalloc(18);
root2xmem(physicalAdd, Datawrit, 18);

 xmem2root(Dataread, physicalAdd, 18);
for(i = 0; i < 9; i++)
printf("

%d",Dataread[i]);

 root1 = NULL;
for(i = 0; i < 9; i++)
    insertsort(&root1, &Datawrit[i]);

 print(root1);

// return 0;
}

// call by reference … ! //
void insertsort(struct tnode **p, int *value)
{

if(!*p)
{

  Node_size1 = sizeof(struct tnode);
  physicalAdd = _xalloc(Node_size1, 12, XALLOC_ANY);
 *p = (struct tnode *)physicalAdd;
  root2xmem(physicalAdd, value, 2);
  root2xmem(physicalAdd + 2, NULL, 2);
 root2xmem(physicalAdd + 4, NULL, 2);
  printf("

%d",* value);
}

if ((value < *((*p)->dat)))
insertsort(&(*p)->left, value);
else
insertsort(&(*p)->right, value);
}

// inorder binary tree print … //
void print(struct tnode *root1)
{
if(root1 != NULL)
{
print(root1->left);
printf(“%d”, *(root1->dat));
print(root1->right);
}
}

please tell me whats the wrong and it would be great full to see the explanation of that.

Looks to me like you are only calling insertsort() with one value. You need to iterate through Datawrit either in main() or in insertsort() - not sure which is more appropriate because I don’t fully understand the code at this point.

Also, insertsort() takes a pointer to an int, and stores that in the tnode struct. But when you print, you’re printing the address instead of the value (root1->dat should be *(root1->dat)).

Also, in insertsort, you are comparing the pointers rather than the values when deciding to insert on the right or left.

Modified to dereference the pointers and iterate, this code seems to work:


struct tnode
{
    int *dat;
    struct tnode *left;
    struct tnode *right;
};

void insertsort(struct tnode **p, int *value);
void print(struct tnode *root1);

int main(void)
{
    int Datawrit[9], i;
    int Dataread[9];
    struct tnode *root1;
    unsigned long physicalAdd;

    Datawrit[0]= 5;
    Datawrit[1]= 9;
    Datawrit[2]= 2;
    Datawrit[3]= 1;
    Datawrit[4]= 7;
    Datawrit[5]= 6;
    Datawrit[6]= 8;
    Datawrit[7]= 3;
    Datawrit[8]= 4;

    for(i = 0; i &lt; 9; i++)
        memset(Datawrit + i, Datawrit[i], 1);
    physicalAdd = xalloc(18);
    root2xmem(physicalAdd, Datawrit, 18);

    xmem2root(Dataread, physicalAdd, 18);
    for(i = 0; i &lt; 9; i++)
        printf("
Dataread[%d] = %d",i, Dataread[i]);

    root1 = NULL;
    for(i = 0; i &lt; 9; i++)
        insertsort(&amp;root1, &amp;Datawrit[i]);

    printf("
------Sorted List------
");
    print(root1);
    // return 0;
}

// call by reference .. ! //
void insertsort(struct tnode **p, int *value)
{
    int i;
    unsigned long physicalAdd;
    int sumbuffer[9];

    if(!*p)
    {
        physicalAdd = xalloc(sizeof(struct tnode));
        *p = (struct tnode *)physicalAdd;
        (*p)-&gt;left = (*p)-&gt;right = NULL;
        (*p)-&gt;dat = value;//strdup(value);
        (*p)-&gt;dat = value;
        printf("
Insert: %d",*value);
        return;
    }

    if ((*value &lt; *((*p)-&gt;dat)))
        insertsort(&amp;(*p)-&gt;left, value);
    else
        insertsort(&amp;(*p)-&gt;right, value);
}

// inorder binary tree print ... //
void print(struct tnode *root1)
{
    if(root1 != NULL)
    {
        print(root1-&gt;left);
        printf("%d", *(root1-&gt;dat));
        print(root1-&gt;right);
    }
}

I have made some changes because my previous code never works.

I am only trying to make a root node with my first datawrit data.

[LEFT]
Node_size = sizeof(struct tnode);
physicalAdd = _xalloc(Node_size, 12, XALLOC_ANY);
*p = (struct tnode *)physicalAdd;
[/LEFT]

At 2nd line a run time error occurs that is Xmem allocation failed(out of memory)

Again my physicalAdd is a long variable which holds 20 bits value here. But I need to make root value using *p which holds only 16 bits.
So how can do this? is there any alternatives available???

Use the far qualifier for pointers to xmem. e.g.,


struct tnode
{
    far int *dat;
    far struct tnode *left;
    far struct tnode *right;
};

Also, note that _xalloc takes a pointer to a long for the first argument, so you need to have Node_size declared as a long and then use:

physicalAdd = _xalloc(&Node_size, 12, XALLOC_ANY);

and do you really need it to be aligned on a 4KB boundary (the 12 arg)?

Thank you for your reply sgt.

I made a structure for 12 bytes

typedef struct
{
	unsigned long rightchild;
	unsigned long data;
	unsigned long leftchild;
}btreenode;

and using unsigned long *p i store address of host every time. and updating the pointers using binary tree.

	  *p = _xalloc(&amp;Node_size, 0, XALLOC_ANY);
     node.left = node.right = 0;
     node.dat  = value;

	  root2xmem( *p, &amp;node, sizeof(node));

What i am trying to do with this is, When i add a user detail i am searching them in the xmem to be sure that my entering data is not exist. so after conformed this i am sortingthem using binary tree.

Though my value is a unsigned long variable which holds 4 byte data always. Hence 1 record holds 12 bytes in the memory i.e left pointer is 4 bytes , data is 4 bytes and right pointer is 4 bytes. i need to store 15000 records minimum. Since I have 512k RAM and 512k SF but i have some reserve space in RAM for some other purpose. RCM3720.

So my DC 9.25 doesnt support far pointer :(. RCM4000 onwards they have given this option. It would be great full if we have far pointer for my 3700.:mad:

Here binary tree makes my each record size as 12 bytes. So i am looking for some other alternatives to reduce my each record size. So help me on this.

Hmmm… I’ve only worked with the 4000 and 5000 so didn’t know far pointer was something new…

There is surely some overhead associated with _xalloc on top of the 12 bytes you allocate, so even though it seems like you should be OK with 15000 12-byte allocs (=180,000 bytes), it’s actually going to be quite a bit more than that. One thing you could do, if you know the maximum number of records you would ever need to have, is to do a single huge alloc and then treat it as an array of btreenodes. Then the leftchild & rightchild can become int values, because they will just hold the array index rather than the pointer. And you eliminate the extra overhead per record that _xalloc uses to keep track of the buffers it gives you. Keep a free list to handle allocating and freeing of the btreenode structures. Obviously, things get much harder if you can’t know in advance the maximum number of records that you will need. The array trick only works if you have a single contiguous buffer…

Actually, I just took a look at the _xalloc function in mem.lib. It looks like there is no additional overhead when you allocate a block (unless you request an odd number of bytes or request an alignment that is larger than the amount of memory you allocate). But as a result of this, xrelease has to be called in reverse order of how the blocks were allocated. So you won’t really save anything by allocating in larger chunks, like you would with a typical malloc call. But the idea of allocating a huge array and using the array index rather than the physical address in the structure can still save you some space…

yup. We cant fix the no of records. the minimum records we using is 15000. but we are expecting 50000 to 1Lac.

The same project we are developing on lpc2388(ARM7) where we can reduce the record size to 6 Bytes.

using binary tree makes my record size as 12B. Can we use any other alternatives which will reduce my record size as much as possible?

You’re going to have a hard time addressing more than 64K records in 2 bytes, but you could still get each of your child references down to 2 bytes if you could accept a limit of 64K records. For example, if you allocated 256 recrods at a time, then you could have a lookup table that kept track of the starting address for each block. This would have 256 entries, and each reference would have a byte identifying the block, and another byte identifying the specific entry within the block. This would use 1KB for the lookup table storage, but save you 4 bytes per node.

You could use a linked list instead of a binary tree to save space, but withy that many entries, the lookups would be horrible. But you can pretty much always trade off space for time in that manner…

Ya your idea is working for us. But still we have a problem that is if we need to delete any users record then how can we update the remaining records location?

And we are only storing the location of the users record in the RAM. So the 12 bytes data arent my final goal.

we are just storing the users details data about 30 bytes in serial flash as it is(I.e as not sorted). So to make a search on 15000*30 bytes data when we need a specific user details, we are sorting the location and keeping it in RAM. So it ill be easier to make a binary search on our original records to find my actual data.

But now if i need to delete any user profile, i have to update my RAM data and serial flash data to go on perfectly…

In the mater of deleting how can we manage to decrease or increase the array location in RAM and SF?

Hence it so difficult to do:(.

Here one more problem that if i want to delete a data i have to xrelease(). But it can delete only last allocated location by xalloc. So???:confused::o

Yeah, deleting items from a binary tree is nontrivial. But I’m going to leave it to you to figure out how to rebalance the tree… If you really want to get aheadache, try reading Knuth (I think it’s Volume 3).

I wouldn’t use xrelease - just keep a free list and put the items on that. When you need to allocate a node, first check if there are any items on the free list & if so, take one. Otherwise go to _xalloc… This might work for your user details data as well, especially if it is a fixed-size record.

I wouldn’t use xrelease - just keep a free list and put the items on that. When you need to allocate a node, first check if there are any items on the free list & if so, take one. Otherwise go to _xalloc… This might work for your user details data as well, especially if it is a fixed-size record.

Here what you mean by keeping free list??

And reading the data from SF makes much delays…

So can we increase the SPI access speed by loading any value to TimerA prescale? Which one we have to use either TimerA or PCLK/2. In the manual it says Timer A Prescale register(TAPR) bit 0 set to be 0 make The main clock for Timer A is the peripheral clock.

Is it the correct way to increase the speed of SPI?

if so then pls give an example…

in the SPI.LIB

	BitWrPortI(TACR, &amp;SF_SPI_TACRSHADOW, 0, SF_SERPORT_TR); //use pclk/2 for TATxR

where

SF_SERPORT_TR = 5

here they making Timer A5 clocked by the main Timer A clock.

Whats the use of that?
they dont have a option to prescale the Timer value…