what will be the value of A->leftTree pointer?
Printable View
what will be the value of A->leftTree pointer?
a->leftTree = prevPtr->leftTree = currPtr
these are all equal...
so? it means...Quote:
Originally Posted by Nazgulled
I don't know...
Please, can't you just help me? I've been around this function for the past 4 hours, my brain is about to explode, I just can't find my way around to fix it...
if prevPtr->leftTree == currPtr
it means you are on the LEFT side of the parent
if prevPtr->rightTree == currPtr
it means you are on the RIGHT side of the parent
About the reading memory after freeing it etc. I'll try to shed some light on this topic, and I hope if the more experienced guys spot a problem in my explanation, they will further teach both me and you :)
I will be talking in linux point of view, but I assume that most modern systems do it in somewhat similar manner. Of course there's some realtime systems (like OSE), in which all memory is available to all brogram blocks (Eg. processes), but I assume you're talking about some desktop system.
So when we simplify enough we can say following. . Most modern OSes do map the real physical memory into virtual memory addresses, and give to each process their own virtual address space. Actually, in most modern computer systems, we have a hardware memory management unit which handles conversions from virtual addresses to physical memory and vice versa. So basically, at user space (which is basically all applications that aren't either part of the kernel, or a kernel module) it is not possible to access straight to hardware (memory or other hardware). Hardware is invisible for userspace processes, it can only be accessed via drivers written in kernel space. (drivers offer interface for user space applications). [[There is a workaround, but let's not mess with it now]].
So process cannot directly access to RAM.
When we launch a process, certain virtual address space is given to it (and certain physical ran corresponding to it, but the process has no means to get direct HW addresses). The process has no access outside of this sandbox. When we launch another process, it will have it's own virtual address space, and it's own corresponding physical ram. If process is running out of ram, kernel has means to increase it.
If another process tries to access outside of it's sandbox, Eg. requests reading from / writing to location which is not in it's address space, MMU will wake up the kernel, which will check out what is happening. If request was illegal, kernel will generate signal SIGSEGV, and send it to your program. => segmentation fault.
However physical ram is not cleaned, and the amount assigned to each process may change. There's also possibility of swapping, where some memory pages are written temporarily to hard disk, to free up some ram for other purposes.
So basically, it indeed is possible that there is leftowers of data written by your program in the memory. But there should be no traces where in the physical ram your data was, so knowing which bytes belonged to what program - not to mention what were these bytes used for - is quite close to impossible. I say quite close because I've never considered that, and I do not have any accurate information how possible it could be.
If I go a little further off topic to see if I have understood it correctly (I believe there is far more experienced fellows amongst us - who will correct me if I go wrong), there is at least following benefits of having physical addresses hidden:
1. Security. No user space process has access to go and mess the HW as they want - they need to use drivers, which should be written in such a manner that hugest hazards are not possible...
2. Per process memory mapping. If memory would be accessible between processes... Oh joy. If you have ever attempted to build huge and complicated multithreaded software you know what I mean. It really is a mess. Use of one uninitialized pointer may crash anything anywhere, or just make generally bizarre things to happen.
I guess steps 1 and 2 could be implemented even if the applications could access ram directly - but I am not sure how easy / difficult it would be.
3. Shared libraries. Shared libraries are loaded to memory during runtime. When each process has their own virtual address space, shared libraries can be downloaded to physical memory only once. The same physical memory block containing the library can then be mapped for each process' address space.
Finally, the inter process communication often uses "creature" called shared memory. processes can request a shared memory block from kernel, which will then map some physical memory chunk to more than one process' virtual address space. Note however that virtual addresses in different processes need not to be the same, even though they point at same physical ram. Hence shared memory is usually accessed according to the offsets from the start of the memory pool.
However, note that when you quit your program, the shared memory is not automatically freed. (thanks to brewbuck for confirmation ;) ). It will stay accessible (if it was created to be accessible).
And finally the [[]] which I wrote at the beginning. It is possible to write a driver, which can map some real hardware addresses to shared memory, which can then furthermore be mapped by a user space process. That way the HW can be accessed directly by a user space application.
And now that I read this, I am just thinking if I should press the submitt or delete - I am unsure whether this really clarifies anything :D
EDIT: It seems like someone had time to actually give adviece on topic, meanwhile I was babbling :/
I see what you mean now... I'm sorry but I'm waaaaaay behind schedule for this and when things like this take more time than it should and I can't figure it out after countless hours debugging, I begin to loose it...Quote:
Originally Posted by vart
That made see I could improve my function a little bit as per point A) but I wouldn't mind to improve it even further, anyway, here's the updated version, which I suppose has all those problems fixed:
The most important problem is C) of course, I need that fixed so the function fully works, at least... I can't understand why the string is not being copied...Code:bool deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return FALSE;
ClientTree currPtr = *cTree;
ClientTree prevPtr = NULL;
int nCompare;
while(currPtr) {
nCompare = strcmp(currPtr->clientName, cName);
if(nCompare > 0) {
prevPtr = currPtr;
currPtr = currPtr->leftTree;
} else if(nCompare < 0) {
prevPtr = currPtr;
currPtr = currPtr->rightTree;
} else {
/*
* A)
*
* The following cases have 3 lines in common, the free()
* calls and return statement. Is there anyway to improve
* this code and make it more compact?
*
* Of course, the printf's are to be removed...
*/
if(!prevPtr) {
printf("CASE #1\n");
*cTree = NULL;
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else if(!currPtr->leftTree || !currPtr->rightTree) {
printf("CASE #2\n");
if(prevPtr->leftTree == currPtr) {
prevPtr->leftTree = currPtr->rightTree;
} else {
prevPtr->rightTree = currPtr->leftTree;
}
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else {
printf("CASE #3\n");
ClientTree tempPtr = currPtr->rightTree;
while(tempPtr->leftTree) {
tempPtr = tempPtr->leftTree;
}
/*
* C)
*
* This has a big problem...
*
* If you take a look at the ClientProfile structure,
* in the first post, you'll see two ints
* (clientNIF/clientAge) and one char* (clientName).
*
* The problem is that the following code line is only
* copying the integer data, not the string. For some
* reason, the string remains the old one.
*
* I tried to use strdup() directly on clientName like:
* currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
* but it still doesn't work.
*
* Why everything is being copied but the strings?
*/
currPtr->clientProfile = tempPtr->clientProfile;
/*
* D)
*
* Is there anyway to not call the function itself
* and make the while loop once again and delete the
* corresponding leaf?
*/
return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
}
}
}
return FALSE;
}
Your case #1 and #3- D case has problems
try to delete A and see what will happen?Code:A
/ \
B C
\
D
Replacing:
By:Code:if(!prevPtr)
Fixes it right?Code:if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree)
My test tree is inserted in this order: H, F, P, G, L, Z and the output you see is in-order. In the following output I'm trying to remove "H", which is the root node... As you can see, first is called case #3 because there are 2 child nodes and then case #2.
As far as I can see, everything is working, apart from the string that is not copied... Element "L" (in-order successor) values (50 and 5000000) were copied to the "H" element, but no the string "L", I honestly can't understand why this isn't being copied...
Code:nazgulled ~/LI3 $ make && ./atulco
gcc -O2 -Wall -g -c atulco.c
gcc -O2 -Wall -g -o atulco atulco.o cities.o clients.o debug.o
F (20, 2000000)
G (40, 4000000)
H (10, 1000000)
L (50, 5000000)
P (30, 3000000)
Z (60, 6000000)
CASE #3
CASE #2
F (20, 2000000)
G (40, 4000000)
H (50, 5000000)
P (30, 3000000)
Z (60, 6000000)
I think I fixed all my problems, let's hope so...
Here's my (supposed) final code:
Is it ok now?Code:bool deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return FALSE;
ClientTree currPtr = *cTree;
ClientTree prevPtr = NULL;
int nCompare;
while(currPtr) {
nCompare = strcmp(currPtr->clientName, cName);
if(nCompare > 0) {
prevPtr = currPtr;
currPtr = currPtr->leftTree;
} else if(nCompare < 0) {
prevPtr = currPtr;
currPtr = currPtr->rightTree;
} else {
if(currPtr->leftTree && currPtr->rightTree) {
printf("CASE #3: NODE WITH 2 CHILDS\n");
ClientTree tempPtr = currPtr->rightTree;
while(tempPtr->leftTree) {
tempPtr = tempPtr->leftTree;
}
currPtr->clientName = tempPtr->clientProfile->clientName;
currPtr->clientProfile = newClientProfile(
tempPtr->clientProfile->clientName,
tempPtr->clientProfile->clientAge,
tempPtr->clientProfile->clientNIF
);
cName = tempPtr->clientProfile->clientName;
prevPtr = currPtr;
currPtr = currPtr->rightTree;
} else {
if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
printf("CASE #1: ROOT NODE\n");
*cTree = NULL;
} else {
printf("CASE #2: LEAF OR SINGLE CHILD\n");
if(prevPtr->leftTree == currPtr) {
prevPtr->leftTree = currPtr->rightTree;
} else {
prevPtr->rightTree = currPtr->leftTree;
}
}
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
}
}
}
return FALSE;
}
ClientProfile newClientProfile(char *cName, int cAge, int cNIF) {
ClientProfile cProfile = malloc(sizeof(nClientProfile));
if(!cProfile) perror("malloc");
cProfile->clientName = strdup(cName);
if(!cProfile->clientName) perror("strdup");
cProfile->clientAge = cAge;
cProfile->clientNIF = cNIF;
return cProfile;
}
/me crosses fingers!