Hey, everyone. Welcome. I have one very short handout for you today. It is the handout that has two problems that wefll be going over during tomorrow afternoonfs discussion section. Remember, we donft have it at 3:15; that was just last week to accommodate what I assumed would be a large audience. Itfs at 4:15. Itfs actually permanently in the room down the hall, in Gates B03. So Ifm not teaching the section, Samaya is, who I think is here, who is handing out the handout. So look for that guy tomorrow at 4:15. Both of these are all the exam problems, so theyfre certainly good problems to understand the answers to. And if youfre not gonna watch the section or attend, just make sure you at least read the handouts. You may very well be able to do the problems yourself, and if so then thatfs fine, but if not, make sure you watch the discussion section at some point. When I left you on Friday, I was a quarter way, a third a way through the implementation of an int-specific stack. So therefs nothing technically cs107 level about this, except for the fact that wefre being careful to write it in pure C, as opposed to C++. Now, if you remember the details from Friday, about the interface file, the functions are, I mean, Ifll talk about those in a second. We actually expose the full struct. There are no classes, and therefs no public, and no private. So everything is implicitly public in the dot age. Thatfs a little weird. C++, when you learned about classes and objects, it was all about encapsulation and privacy of whatever could be private. We canft technically do that in C; although, we can certainly write tons and tons of documentation saying just pay attention to the type, use these functions to manipulate it, and pretend that these are invisible to you. You more or less operate as if this is a constructor, a destructor, and methods, but they happen to come in pure, top-level function form, where you pass in the structure being manipulated. So StackNew is supposed to take the struct, one of these things, addressed by s, and take it from a 12-byte block of question marks to be logically representing a stack of depth zero. This is supposed to kill a stack at that address. This is supposed to increase its depth. This is supposed to pop something off. I wrote StackNew and StackDispose. I certainly wrote StackNew, Ifm forgetting about StackDispose, but Ifll write them really quickly right now. This is the dot c file: Stack .c void StackNew Stack I add these three things: Stack logLength = 0 (thatfs because the stack is empty) Ifm going to make space for four elements, and then Ifm going to go ahead and allocate space for four elements using c as a raw dynamic memory allocator, called malloc. It doesnft take anything related to a data type. It doesnft know that anything related to a data type is coming in as an argument. You have to pass in the wrong number of bytes that are needed for your four integers. And thatfs how you do this. All that malloc feels is an incoming 16. It goes to the heap and finds a figure thatfs that big, puts a little halo around it saying itfs in use, and then returns the base address of it. I told you to get in the habit of using a certain macro, that was mentioned a little bit in Assignment 1, just to confirm that elems ? null. If malloc fails for some reason it rarely will fail because it runs out of memory, itfs more likely to fail because you called free on something you shouldnft have called freed on. So youfve messed up the whole memory allocator behind the scenes. Thatfs a good thing to do right there because it very clearly tells you where therefs a problem, as opposed to it just seg filtering or bus erroring or it crashing in some anonymous way, and you have not idea how to back trace to figure out where the problem started. As far as stackDispose is concerned, this is trivial. Although, therefs one thing I want to say about it, actually, two things I can think of. I want to go ahead and do the opposite of malloc. This corresponds to operator delete from C++. I want to free s-> elems so that it knows that whatever figure is identified by that address right there should be donated back to the heap. Thatfs just what I mean when I talk about free right here. Some people question whether or not I should go and actually free s itself. They ask whether or not that should happen. The answer is no. Nowhere during StackNew did you actually allocate space for a stack. You assumed that space for the stack had been set aside already, and that the address of it had been identified to the StackNew function. So you donft even know that it was dynamically allocated. In fact, the sample code I wrote last time declared a stack called s as a local variable. So it isnft dynamically allocated at all. So you definitely in this case do not want to do this. The other thing I want to mention is that regardless of whether or not the stack, at the moment this thing is called, is of depth zero or of depth 4500, the actual ints that are held inside the dynamically allocated rectangle of bytes, therefs no reason to zero them out. And therefs certainly no freeing needs held by those integers. I say that because just imagine this not being an int stack but imagine it being a char * stack, where Ifm storing dynamically allocated c strings, Fredsf and Wilmasf and things like that. If I did have that, in the case of the char *, I would have to for loop over all the strings that are still held by the stack at the time itfs being disposed and make sure I properly dispose of all of those strings. I donft have any of that with the int specific version. But the reason Ifm saying this is itfs going to have to accommodate that very scenario when we go generic on this thing and just deal with blobs as opposed to integers. The most interesting of the four functions is the StackPush. And itfs interesting not because of the algorithm to put an integer at the end of an array, but the algorithm thatfs in place to manage the extension of whatfs been allocated to be that much bigger because youfve saturated whatfs already there. I chose an initial allocated length of four, so Ifm certainly able to push four integers onto the stack and not meet any resistance whatsoever. But if I try to press a fifth in on the stack, it has to react and say, I donft have space for five integers I better go and allocate space for some more, copy over whateverfs been pushed, and dispose of the old array to make it look like I had space for 8 or 16 or 1,024 or whatever. So the implementation, assuming I do have enough space, would be this simple: StackPush. Pushing onto what stack? The one thatfs addressed by this variable called s. What number am I pushing on? The one that comes in via the value parameter. Let me leave some space here for what Ifll inline as the reallocation part. But if therefs enough memory, where down here I can assume that therefs definitely enough memory, I can do this: s-> elems of s-> logLength equals this value Think about the scenario where the stack is empty. The logLength happens to be zero, which happens to be the index where you should insert the next element. Once I do this for the next time, I have to go ahead and say, you know what, the logLength just increased by one. Not only does that tell me how deep the stack is, it also tells me the insertion index for the very next push call. It isnft that simple. Eighty percent of the code that gets written here has to deal with the one in two the end time scenarios where you actually are out of space. If it is the case that s-> logLength == s-> allocLength, then as an implementation youfre unhappy because youfre dealing with a stack and a value where the value has no home in the stack at the moment. Ifm trying to press on a 7. Letfs say that s points to this right here, and the logical length and the allocated length are both 4, and Ifve pushed these four numbers on there, the client doesnft have to know that therefs a temporary emergency. So right here Ifm just gonna react by saying, you know what, that 4 wasnft big enough, I want to go ahead and I want to, without writing code yet, I want to basically reallocate this array. Now, I say reallocate because there really is a function related to that word in the standard C library. In C++ you have to go ahead and allocate an array thatfs bigger. You donft have to use a doubling strategy; Ifm just using that as a heuristic to allocate something thatfs twice as big. You have to manually copy everything over, and then you have to dispose of this after setting elems equal to the new figure. It turns out C is more in touch with exposed memory than C++ is. So rather than calling malloc yourself, you can call a function thatfs like malloc except it takes a value, thatfs been previously handed back to you by malloc, and says please resize this previously issued dynamically allocated memory block. That is this: Let me write just one line right here. I want to take allocLength and I want to double it. I could do plus equals 10; I could do plus equals 4. I happen to use a doubling strategy. And then what I want to do is I want to call this function. Let me deallocate these so I have space to write code. s-> elems equals this function called realloc Therefs no equivalent of this in C++. Ifll explain it in a few weeks why there isnft. But realloc actually tries to take the pointer thatfs passed in and it deals with a couple of scenarios. It sees whether or not the dynamically allocated figure can be resized in place, because the memory that comes after it in the heap isnft in use. Therefs no reason to lift up a block of memory and replicate it somewhere else, to resize it if the part after the currently allocated block can just be extended very easily in constant time. The second argument to realloc is a raw number of bytes. So it would be: s-> allocLength times size of integer. I see a lot of people forgetting to pass in or forgetting to scale this byte size event. Even though that they know to do it with malloc, they forget with realloc for some reason. It takes this parameter right here, it assumes itfs pointing to a dynamically allocated block, and it just takes care of all the details to make that block this big. If it can resize it in place, all it does is it records that the block has been extended to include more space and it returns the same exact address. So that deals with the scenario where this is what you have, this is what you want, and it turns out that this is not in use so it can just do it. So it took this address in and it returns the same exact address. Well, you may question why does it return an address at all? In this case it doesnft need to. However, it may be the case that you pass that in and you want to double the size or make it bigger, and that space is in use. So it actually does a lot of work for you there. It says, okay, well, I canft use this so I have to just go, and it really calls malloc somewhere else on your behalf. Just assume thatfs twice as big as this. Whatever byte pattern happens to reside here is replicated right there. The remaining part of the figure isnft initialized to anything, because itfs uninitialized just like most C variables are. It actually frees this for you and it returns this address. So under the covers, beneath the hood of this realloc function, it just figures out how to take this array and logically resize it, and preserves all the meaningful content thatfs in there. If it has to move it it does free this. It turns out realloc actually defaults to a malloc call if you pass in null here. So technically you donft need the malloc call ever. That actually turns out to be convenient when you have entered a processes that have to keep resizing a node, and you donft want a special case it and call it malloc the very first time, you can just call it realloc every single time when the first parameter is null on the very first iteration. Itfs very easy to forget to catch the return value. If you forget to do that then you refer to s-> elems captures the original address, which may have changed, and you now after this call may be referring to dead memory thatfs been donated back to the heap manager. So itfs very important to catch it like this. If realloc fails itfll return null. So Ifm gonna put an assert right here. The one thing about realloc thatfs neat is that if you donft want to just end the program because it failed, it actually, if it returns null it wonft free the original block, it would only return null if it actually had to move it. Actually, thatfs not true. If it canft meet the realloc page in request itfll just leave the old memory alone and return null. In theory, you donft have to assert. And in the program here you could just check for null, and say, okay, well, maybe I wonft resize it, maybe Ifll just print a nice little error message saying, I actually cannot extend the stack at this time, my apologies, please do something else. Wefll learn a lot about how malloc and realloc and free all work together. Theyfre implemented in the same file. Theyfre implemented in the same file because even though that the actual blob of memory doesnft expose its size to you, like in a dot length field like in Java, somehow free knows how big it is. Well, therefs cataloging going on behind the scene so it knows how much memory to donate back to the heap every time you call free. But I donft want to focus on that. This right here, it doesnft get called very often. This doubling strategy is popular because it only gets invoked as a code block one out of every two to the n calls once you get beyond 4. Because of the doubling strategy [inaudible] only comes up once every power of 2; 512 wasnft big enough, okay, well, maybe 1,204 will be. And you have a lot of time before you need a second reallocation request. There are a couple of subtleties as to how this is copied. In this example right here, all of these little chicken scratch figures right there, they correspond to byte patterns for integers. So when I replicate them right there, I trust that the interpretation of those integers right there will be the same right there. So realloc is really moving my integers for me. If these happen to be not four integers but four char *fs, that means the byte patterns that were here would have actually been interpreted as addresses. When it replicates this byte pattern down here, it turns and it replicates the addresses verbatim. This would point to that; that will point to that; this will point to that; this will point to that. Do you understand what I mean when I do that? When I dispose of this it doesnft go in and free the pointers here. It doesnft even know there are pointers in the first place so how could it free them? So as this goes away, and these all point to where other pointers used to be pointing, you donft lose access to your character strings. This is certainly the most involved of all four functions. [Student:]If you could explain the assertion again. All assert is, for the moment just pretend that itfs a function. It takes a boolean. Its implementation is to do absolutely nothing and return immediately if it gets true, and if it gets false its implementation is to call exit after it prints an error message saying an assert failed online, such and such, in file stack dot c. [Student:]So actually [inaudible]. S-> elems ? null. You want to assert the truth of some condition that needs to be met in order for you to move forward. If realloc fails it will return null. You want to make sure that did not happen. Thatfs why there is a not equals there as opposed to a double equals. This isnft technically a function. Wefll rely on that knowledge later on. Itfs technically whatfs called a macro. Itfs like a #define that takes arguments. But, nonetheless, just pretend for the moment that it works like a function. [Student:]If the realloc has to move the array is it now or anytime? Yeah. The question is if realloc has to actually move the array it is time consuming. Itfs even more time consuming than o of m. It actually involves not only the size of the figure being copied, but the amount of time it takes to search the heap for a figure that big. So it really can, in theory, be o of m, where m is the size of a heap. Let me just quickly, just for completeness, write stackPop. It turns out itfs not very difficult. The most complicated part about it is making sure that the stack isnft empty. This continues on this board right here. I have this thing that returns an int stackPop. Ifm popping off of this stack right here. No other arguments assert that s-> logLength is greater than 0. If you get here then youfre happy because it has something you can pop off. So go ahead and do the following: s-> logLength -- and then return s-> elems of s-> logLength The delta by one and the array access are in the opposite order here. I think for pretty obvious reasons. Youfre effectively control zfing or command zfing the stack to pop off what was most recently pushed on. So if this came most recently, you want to say I didnft even do that. Oh, and by the way, therefs the element that I put there by mistake. Thatfs what I mean. You could say you see this as demanding a reallocation request and going from 100 percent to a new 100 percent, where the old 100 percent was actually 50 percent. You may ask whether or not if you fall below a 50 percent threshold that you should reallocate and say, oh, Ifm being a memory hog for no good reason and donate it back to the heap. You could if you want to. My understanding of the implementation of realloc, because it wants to execute as quickly as possible, it ignores any request to shrink an array. As long as it meets the size request, it doesnft actually care if it allocates a little bit more. So itfs like, oh, the size is 100 bytes and you just want 50. Okay, then only use 50 but Ifm gonna keep 100 here because itfs faster to do that. With regard to the stackPop prototype right there, it sounds like a dumb observation, but itfll become clear in a second when we go generic. This particular stackPop elects to return the value being popped off. I can do that very easily here because I know that the return value is a four-byte figure. If this were a double stack I would just make that leftmost int up there double and it would just return an eight-byte figure. When I go generic, and I stop dealing with int *fs and I start dealing with void *fs, Ifm gonna have to make the return type either void *, which means I return a dynamically allocated copy of the element, for reasons thatfll become clear in a little bit Ifm not gonna like that, or I have to return void and return the value by reference by passing in an int * or a void * right here. That will become more clear once I actually write the code for it. But we take advantage of a lot of the fact that we know that wefre returning a four-byte figure here so the return type can be expressed quite explicitly as in int. So now what I want to do is I want to start over. And I want to implement all of this stuff very generically. And I want to recognize that wefre trying to handle ints, and bools, and doubles, and struct fractions, and actually the most complicated part of it are char *fs because they have dynamically allocated memory associated with them. Let me redraw stack dot h. And we are going completely generic right here. Most of the boilerplate is the same. Typedef struct, and I donft want to commit to a data type, elems. Now, think about what I lost. I lost my ability to do pointer arithmetic without some char * casting. I also lost intimate knowledge about how big the elements themselves are. So I canft assume the size of int anymore because it may not be that; it probably wonft be. So Ifm gonna require the prototype of StackNew to change, to not only pass in the address of the stack being initialized, but please tell me how big the elements that Ifm storing are so that I can store it inside the struct. The logical length versus the allocated length and the need to store that, that doesnft change. I still want to maintain information about how many of these mystery elements I have. I also want to keep track of how much I am capable of storing, given my current allocation. And therefs gonna be one more element that we store on a byte. So Ifll leave that piece of spencil for the next 15 minutes and wefll come back to it. The prototype of the functions change a little bit. StackNew, same first argument, but now I take an elemSize. Void * stackDispose stack *s (That doesnft need to change. Itfs mostly the same, although, wefll have something to say about what happens when itfs storing char *fs.) Void stackPush stack s And then Ifm gonna pass in void * called elemAddr. I canft commit to a pointer type thatfs anymore specific right there ecause it may not be an int *, it may not be a char **, it may not be a structFraction *. It just needs to be some address that I trust because the information that I am holding is pointing to an s-> elemSize figure. So therefs that. This is the part that freaks people out. This is what Ifm going to elect to do, Ifll talk about the alternative in a second. But when I pop an element off the stack, I want to identify which stack Ifm popping off of, and I also want to supply Address. This is me supplying an address. Ifm actually gonna identify a place where one of my client elements, that was previously pushed on, should be laid down. Itfs like Ifm descending a little basket from a helicopter so somebody can lay an integer or a double or something in it so I can reel it back up to me. So void * elemAddr. And thatfs all Ifm gonna concern myself with. [Student:]Where is the struct named stack? Ifm sorry, I just forgot it. Itfs right there. So 70 percent of the code Ifm gonna write itfs all gonna be the same. Itfs gonna be slightly twisted to deal with generics as opposed to ints. But rather than using assignment, which works perfectly well when youfre taking one space for an int and assigning it to another int, wefre gonna have to rely on memcopy and things like that. StackNew is not hard. Void StackNew stack *s int elemSize (Same kind of stuff) s-> logLength = zero s-> allocLength = four s-> elemSize = elemSize s-> elem = malloc I donft have a hard data type so I canft use size of here, but I have no reason to. I have been told how big the elements are via the second parameter. So four times elemSize, just use the parameter as opposed to the field inside the struct. I can do a few things to make my life easier. S-> elems better not be equal to null or else I donft want to continue. And the assert will make sure of that. I also could benefit by doing this: assert that s-> elemSize -- this one is not as important because it takes a lot of work to pass in a negative value for elemSize. But, nonetheless, itfs not a bad thing to put there because if you try to allocate -40 bytes itfs not gonna work. That and implementation make sense. I think even if it makes sense, therefs some value in seeing a picture. It takes this stack right there, with its four fields inside at the moment, and letfs say I want to go ahead and allocate a stack to store doubles. That means the elemSize field would have an eight right there. Ifd set aside space for four of them. The logical length is zero. Ifm just making sure this is consistent with the way Ifve done this. Thatfs right. And then I would set this to Point 2. As far as the stack knows, it has no idea doubles are involved, it just knows that itfs a 32-byte wide figure. And it has all of the information it needs to compute the boundary between zero and one, one and two, and two and three. As far as stackDispose is concerned, stack *s, this is incomplete, but itfs complete for the moment given what Ifve talked about. I just want to go ahead and I want to free s-> elems, and not concern myself yet with the fact that the actual material stored inside the blob might be really complicated. Just for the moment think ints, and doubles, and plain characters. But the fact that Ifm leaving space there [inaudible] that this will change soon. Let me write stackPush right here. void stackPush stack *s void * elemAddr Ifm gonna simplify the implementation here a little bit by writing a helper function. I could have written the helper function on the int specific version but just didnft. Up front, if itfs the case that s-> logLength == s-> allocLength, then I want to cope by calling this function called stackGrow. And you know what stackGrowfs intentions are. And Ifm just gonna assume that stackGrow takes care of the reallocation part. Ifll write an int second, thatfs not the hard part. Once I get this far, whether or not stackGrow was involved or not, I want to somehow take the s-> elemSize bytes that are sitting right there and write into the next slot in memory that I know is there for me, because if it wasnft this would have been called. So what has to happen? Let me refer to this picture. Letfs just assume that this picture is good enough, because I obviously have enough space to accommodate this new element. Letfs say that I have three elements. So that these have been filled up with interesting material. And I somehow, in the context of that code over there, have a pointer to some other eight-byte figure that needs to be replicated in. This is gonna be the second argument to memcopy. This right there is gonna be the third argument. The only complexity is computing and figuring out what the first argument is. It has to be that. It doesnft need to know that itfs a double *, or a struct with two ints inside *, or whatever. It just needs to actually get the raw address and replicate a byte pattern. No matter what the byte pattern is, as long as itfs the same in both places, youfve replicated the value. So the hardest part about it is doing this: void * target = char * s-> elems + s-> logLength times s->elemSize This is why I demanded all of this stuff to be passed to my constructor function so it was available to me to do the manual pointer arithmetic later on. I donft think I messed this up. LogLength is right there for the same reasons it was in between the square brackets for the int specific implementation of this. Then what I want to do is I want to go ahead memcopy into the target space whateverfs that elemAddr. How many bytes? This many, s-> elemSize. Then I canft forget this, this was present at the other implementation as well. I have to note the fact that the logical length just increased by one. So thatfs how I managed that. Do you guys see just the bytes moving on your behalf in response to this function? Therefs a question back there. [Student:]The char * after void target equals? This right here, remember that s-> elems, unless I made a mistake, is typed to be a void *. So you canft do pointer arithmetic on the void *, so the trick -- therefs actually two tricks. I opt with this one because Ifm just more familiar with it, you can either cast it to be a char * so that pointer arithmetic defaults to regular arithmetic. This as an offset itfs still the offset, it just happened to involve multiplication. It is itself implicitly multiplied by size of char, which as far as multiplication is concerned, is a no op. I have also seen people, I think I mentioned this before, Ifve seen people cast that to be an unsigned long, so that it really is just plain math, and then they cast it to be void *. Pointers and unsigned longs are supposed to be the same size on 32-byte systems. A long is supposed to be the size of a word on the register set. So Ifve seen that as well. You can do whatever you want, I just -- all of my examples use the char * version so thatfs why I use that one. The stackGrow thing. The reason I want to do that is not because of the mem copying or the void *, I just want to explain what a student asked two seconds before class started. Youfre kind of already getting the idea that the word static has like 85 meanings in C and C++. Well, herefs one more. When you see the word static, decorating the prototype of a C or a C++ function, not a method in a class just a regular function, such as static void stackGrow, and it takes a stack *s. What that means is that it is considered to be a private function that should not be advertised outside this file. So in many ways it means private in the C++ sense. The technical explanation is that static marks this function for whatfs called internal linkage. You know how youfre generating all these dot o files, when you type make all this stuff appears in your directory, some of them are dot o files. Ifll show you a tool later on where you can actually look at whatfs exported and used internally by those dot o files. StackPush, and stackNew, and stackDispose are all marked as global functions, and that the symbols, or the names of those functions, should be exported and accessible from other dot o files, or made available to other dot o files. Something like this is marked as whatfs called local or internal. And even though the function name exists, it canft be called from other files. That may seem like it was a silly waste of time, but it really is not. Because you can imagine in a code base of say one million files, itfs not outlandish believe it or not. Think Microsoft Office, the whole thing, probably has on the order of hundreds of thousands of files, maybe tens of thousands, I donft know what it is, more than a few. You can imagine a lot of people defining their own little swap functions. And if theyfre not marked as internal functions at the time that everything is linked together to build Word or Excel or whatever, the linker is gonna freak out and say, which version of swap do I call? I canft tell. Because it has 70 million of them. But if all 70 million are marked as private, or static, then therefs none of those collisions going on at the time the applicationfs built. This is responsible for doing that reallocation. Assume itfs only being called if it understands that this is being met as a precondition. So it can internally just do this: s-> elems = realloc s-> allocLength times s-> elemSize Thatfs the cleaner way to write it. It makes this focus on the interesting part thatfs hard to get, and kind of puts this aside as uninteresting. Algorithmically, the function thatfs most different from the integer version actually is this StackPop call. This is how I want to implement it: void stackPop. Ifm popping from this stack right here. Ifm placing the element thatfs leaving the stack and coming back to me at this address. Therefs no stack shrink function to worry about. So what I want to do is declare this void *, not called target but called source = char * of s-> elems plus s-> logLength minus 1 times s-> elemSize. I forgot to do the minus minus beforehand so I recovered by doing a minus 1 right there. This is where wefre drawing a byte pattern from in the big blob behind the scenes. Wefre drawing byte patterns from there so we can replicate it into elemAddr. ElemAddr is the first argument. Ifm copying from that address right there how many bytes. This many. And then do what I should have done earlier, logLength --. This really should have been the first line, and I shouldnft have the -1 there, but this is still correct. Do you guys get whatfs going on here? If you understand the helicopter basket analogy? Wefre on actually identifying a space where itfs safe to write exactly one element so that when the function returns I can go, wow, thatfs been filled up with an interesting element to me. And I can go ahead and print it out or add it to something or replace the seventh character or whatever I want to do with it. This used to be int. If I wanted to I could have punted on this right here and just passed in one argument. And I could have returned a void * that pointed to a dynamically allocated element thatfs elemSize bytes wide. And I just would have copied not into elemAddr, but into the result of the malloc call. With very few exceptions, malloc and strdup and realloc being them, you usually donft like a function to dynamically allocate space for the call and then make it the responsibility of the person who called the function to free it. Therefs this asymmetry of responsibility, and you try to get in the habit as much as possible of making any function that allocates memory be the thing that deallocatefs it as well. Therefs just some symmetry there and itfs just easier to maintain dynamically allocated memory responsibilities. Itfs not wrong itfs just more difficult to maintain. It actually clogs up the heap with lots and lots of little void *fs pointing to s-> elemSize bytes, as opposed to just dealing with the one central figure thatfs held by the stack, and then locally defined variables of type int and double that are passed in as int * and double *fs recognized as void *fs. But because we laid down the right number of bytes, as long as everything is consistent we get back ints and doubles and things like that. [Student:]In this case do you have to with our elemAddr [inaudible] right? Yeah. Ifm not actually changing elemAddr Ifm just changing whatfs elemAddr. So let me actually make a sample call to this. Suppose I have a stack s. And I called StackNew with & of s, and I pass in size of int. That means that I have this thing, thatfs my stack and Ifm supposed to just take it as a black box and not really deal with it. But I know behind the scenes that it has a 4 there, and maybe my stack has 14 elements in it, and it can accommodate 16 elements. And that it points to this thing that has not 2 or 4 or 8, but 16 elements in it. And Ifm like, you know what, I did all this work, and I pushed on 14 elements right there, but Ifd like to now pop off the top element. When I do this stackPop, I have to pass in that. I have to pass in the address of an integer. So the stackPop call has a variable called elemAddr that points to my variable called top, and it relies on this variable to figure out where to write the element at position 13. It happens to reside right there. The memcopy says where do I write it? I write it at that address right there. You would replicate this byte pattern in the top space, this returns, and I print out top and that corresponds to the number 7,300 or something like that. If I really wanted to change this void *, I donft change the void * anywhere, I just use it as sort of a social security number or an ID number on the integer. If I really wanted to change this youfd have to pass in a void * *. There are scenarios where that actually turns out to be what you need, but this is not one of them. [Student:]For this pop, letfs say that this function doesnft work, that itfs popping the wrong stuff. How do we test to find out if we pop [inaudible]. Like, for instance, letfs say you wanted to pop something that was an integer, and you popped [inaudible], and then what if there was something wrong with the resizing, can we set that in that we just pop to like null or something and then -- You could. If you really want to exercise the implementation of the stack to make sure itfs doing everything correctly, youfll write these things, you may have heard this, what are called unit tests. Which are usually implemented -- therefs two different types of unit tests, therefs those that are written on the dot c end, which know about how everything works, and then those that are written as a client to make sure that itfs behaving like you think it should. If that were the case, and you wanted to protect against that, you could write all these very simple tests to make sure that things are working. Because in unit tests, as a client you might for loop over the integers one through a million. You might actually set the initial allocation length not to be four, but to be one, so that you get as many reallocations as possible. You could for loop and push the number one through a million on top. In a different function, you could actually pop everything off until itfs empty and make sure that they are descending from one million down to one. And if it fails, then you know that therefs something wrong. If it succeeds, you never know that something is completely working, but you have pretty good evidence that itfs probably pretty close if it isnft. You can change the implementation to kind of make sure that all of the parts that are really risky, like the reallocation, and the --, and the memcopy calls are working, one thing you could do, and Assignment 3 takes this approach a little bit, right here I use this doubling strategy. If I really wanted to test the reallocation business, I could actually do a ++ instead of a times two on the allocation size and to reallocate every single time. Not because you want it to work that way, but because you could just make sure that algorithmically everything else works regardless of how you resize them. Now, another answer to your question, if I didnft take that approach with the unit test answer, is that when youfre dealing with generics in C, and void *fs, and memcopy, and manual guests, you have to be that much more of an expert in a language to make sure that you donft make mistakes. Itfs very easy. Think about it this way, I know youfre not gonna believe this yet because you havenft coded in C that much, but Assignment 3 you will. I know how most of you program. You write the entire program and then you compile it. And you have 5,500 errors. And you get rid of them one by one, and it takes you like three days, and then it finally compiles. And you run it, and even if it doesnft quite run the way you want it to it rarely crashes. Most people donft even know what the word crash means until they get to 107. You will next week, trust me. As far as C++ is concerned, because itfs so much more strongly typed than C is, it is possible for you to write an entire program, to have it compile, because compilation does so much type checking for you in a C++ program that uses templates, itfs quite possible that once it compiles that it actually works as expected. It doesnft happen very often but itfs certainly possible. In a C program, where youfre using void *fs, and char *fs, and memcopy, and memmove, and bsearch, and all of these other functions youfre gonna need to use for Assignment 3, itfs actually very easy to get it to compile. Because itfs like, oh, void *, I can take that, yep, thatfs fine. It just does it on all the variables, and so it compiles. And youfre like, good, it wasnft three days, it was one day. And then you run it and it crashes because you did not deal with the raw exposed pointers properly. So thatfs what makes certainly the first assignment in pure C with dealing with void *fs difficult. But therefs an argument that can be made to say that itfs very hard to get all this stuff right every single time you program. Ifve already told you that right here I forget this s-> elemSize probably one out of every two times I teach this example. Thatfs because itfs very unnatural compared to the C++ way of allocating arrays to think in terms of raw bytes. And you think in terms of sizes of the figures, you see the pictures in your head as to how big things should be, so you just remember that number right there but you forget about this. If you forget this right here, it compiles, it runs. If youfre dealing with integers then your array is one-fourth as big as it needs to be to store all the integers you want there. You will learn this and feel it at 11:59 a week from Thursday. All these types of errors, because itfs gonna compile and itfs gonna run very often. But occasionally itfs gonna crash and youfre not gonna know why, and youfre gonna say, oh, itfs the compiler. Itfs not, itfs your code. Okay. So we will talk more on Wednesday.