שאלות ותשובות - Homework Assignments - HW3 Frequently Asked Questions - Homework Assignments - HW3 Вопросы и Ответы - Homework Assignments - HW3 أسئلة وأجوبة - Homework Assignments - HW3

		.. (לתיקייה המכילה)

		Dry
	What is the map (מיפוי או מילון) data structure? The map data structures contains a set of key (by set we mean that keys are not ordered, and duplicates are not allowed). Every key in the map is mapped to a value. All keys must be of the same type, as well as all values, but the type of keys might be different from the type of the values (a mapping between numbers as keys and strings as values is possible). Again, there might not be two equal keys in the map, but two keys can be mapped to two equal values (mathematical function property). Common operations on a map: add a pair of key and value, change the value of some key, ask for the value of a given key, etc. For more information and details you can see the map.h given to you, and you can take a look at: קישור: Link: Ссылка: وصلة:    https://en.wikipedia.org/wiki/Associative_array In question 2.2 (MergeSort), what arguments do the function gets? It is up to you to decide what arguments must be passed in order to get a generic and correct function. But please make sure you explain what is the role of every one of them in 2.2.b. In Question 2.3., what should be the function behaviour in cases where n=1,0 ? If n=1, the function should return a copy of the only list in the input array. If n=0, the function should return NULL. In question 2.3. can we assume that there are no cycles in any list? Yes. In question 2.3. can we use the functions defined in list.h? No. The only thing that is defined by us is the given list structure (with no functionality). Should the functions check bad inputs? In mergeSort - you can assume all inputs are valid. In all other functions in the dry part you should return NULL in case of invalid arguments. How do we deal with memory allocation failures in mergeSort? Assume using assert that the allocations do not return NULL. In question 2.3.1. should we return a new list or just modify list1 (as might be understood from the drawing)? You should return a new allocated list. In question 2.3, can we wrap the list structure with an ADT with functionality? No. It is really unnecessary. Can we use listDestroy() function (as stated in notes)? Yes.

		Wet, General
	Can we write ADTs other than the ones required (my_set, cache, memcache)? Yes. You can define as many new ADTs as you want, but keep in mind that for every ADT you define (.c file + .h file implementing a special functionality over some premitive type or structure) you will have to write also unit tests file named adt_name_test.c under the tests folder Can we write any utility functions .c files? Yes. See previous question. When writing tests fot generic ADTs (like my_set, cache, etc.) how many different instances of the ADT should we test? It is sufficient to test only one instance of the generic ADT (for example: set of strings, or cache of complex numbers, etc.), but you have to test every functionality and every case (including edge cases, success, and failure) deep enough so the test will cover ~100% of the code you have written. What extension should the MakeFile file have? None. What should be the outcome of the makefile? Running 'make' command should generate execution files for all tests in the root directory of your submission folder. That means, that for every ADT test you wrote (including my_set's), an execution file must name 'ADT_test' should be generated. Of course, your makefile should be built as shown in class, i.e., by building a hierarchy of dependencies (this includes of course generating .o files - which could be done in the root directory).

		Wet, First Part: Implementing an ADT of a Set
	Can we use the list ADT implemented as a part of libmtm.a static library? No. The MySet ADT structure should be similar to the structure of a linked list, but you cannot use the list implemented by us, and you will have to implement one yourself if needed. In mySetIsIn, what should be the return value if the element passed as argument is NULL? False. In mySetRemove and mySetAdd, what should be the returned result code in case element is NULL? In both cases, MY_SET_NULL_ARGUMENT. Generally, if a NULL is passed as an argument in a place it shouldn't be, the result code should be NULL_ARGUMENT. The documentation about this issue in the my_set.h file might be confusing a little. In mySetAdd, what should be the return value in case the element already exists and allocation failed? MY_SET_ITEM_ALREADY_EXISTS, since in the beginning you check if the item exists, then you try to allocate a new element. Can we change the iterator's value in functions other than the iteration functions? Yes. But it is not a good property to have for such functions. Can we assume that the user does not change the set's elements when getting them via setGetFirst/Next/Current? Yes. Where should we put the my_set_test.c file in the submission? In the my_set folder.

		Wet, Second Part: Implementing the MemCache
	In the iteration functions of the Cache (cacheGetFirst, etc.) should we iterate also over cells with no elements (empty sets)? Yes. Are we required to use all three ADT given in the static library (set, list and map)? No, it is not necessary that you use them all, but make sure that the data structure you choose to use in every place is the most suitable one. That doesn't mean that an implementation that uses only some of the ADTs is incorrect. You can ask yourself questions like the one asked in the first question in the dry part to find the best match. In cacheFreeElement what should we return in case element's key is out of range? CACHE_ITEM_DOES_NOT_EXIST. In all relevant memcache functions, what should be the return value in case the username(s) passed as argument(s) is NULL? You should return USER_NOT_FOUND or ILLEGAL_USERNAME (according to the function). What should be the return value of memCacheFree in case the pointer passed points to NULL? MEMCACHE_BLOCK_NOT_ALLOCATED. Are memcache allocations of size 0 possible? No. In such case memCacheAllocate should return NULL. What is the difference between cache b that stores the "addresses" of the blocks, and cache a that stores the "blocks themselves"? It's up to your implementation. One option is that cache 'a' contains pointers to blocks, while in cache 'b' pointers to addresses of blocks (pointers to pointers to blocks) are stored. There is another option where cache 'b' contains just pointers to blocks, but in this kind of implementations it might be harder and unintuitive to manipulate cache 'b' (especially when trying to move a specific block from cache b to cache a). What you mean by the "key" of an element in the cache? The key of every element in the cache can be computed by the compute_key function passed to cacheCreate. The key of an element is the index (between 0 and size-1) of the set where the element should be in the container array. For example, all elements with key=0 can be found in the first set (index 0) in the cache. How should the system behave in case a user tries to add or remove himself from the group of users he himself trusts? The relevant functions should return MEMCACHE_SUCCESS in these cases, but of course it would be meaningless. No matter what permission mode a block is in (U G or A), its owner must be able to free it. Under the MakeFile section in the PDF, it can be understood that my_set_test.c must be in the tests folder. Is this the situation? No. my_set_test.c should be found in the my_set folder, and the MakeFile should assume it's there. What does mapGet returns? the element itself or a copy of it? The element itself. In which order should the iteration functions of memcache iterate over the blocks? The iteration functions should pass over the blocks in the order they appear in each of the caches. This means for example, that the iteration over free blocks should begin with all blocks with size 0, then pass over all blocks with size 1, etc. In the case of allocated blocks, the order will be defined by the modulo 2^16. The order between blocks with the same key (blocks which are stored in the same set in the cache) does not matter. What happens to the iterator when user remove or inserts blocks to memcache? The iterator in this case is undefined - meaning users cannot assume anything about its state, and about the return value of the iteration functions (except getFirst of course). When testing the submission folder, will you add test_utilities.h anywhere? Yes, we will add it to the tests folder. It's your responsibility to have it anywhere else in your submission folder. What is the best way for converting pointer to its numerical value for computing %2^16? Any method that works on t2 will be acceptable. Anyway, the recommended method to do that is casting to uintptr_t. For more details visit the link below: https://www.securecoding.cert.org/confluence/display/c/INT36-C.+Converting+a+pointer+to+integer+or+integer+to+pointer (Thanks to Nadav) Can we store copies of the blocks in the cache? No. The blocks themselves must be stored in both caches. In the memcache ADT, what should be the return value in case the function fails and there are two or more possible results? Return the first result following the order they appear in the PDF. Where should the execution files generated by the makefile (all *_test files) be? In the main submission directory.