CIS2750 Lecture 3 - List API, Creating Libraries PDF

CIS*2750 Lecture 3: List API; creating libraries Based on CIS*2750 notes from previous generations of CIS*2750 instructors  A review of a simple C library: List ADT Fixed-length arrays are not very useful for dealing with optional data, so we want something exible Many...

CIS*2750 Lecture 3: List API; creating libraries Based on CIS*2750 notes from previous generations of CIS*2750 instructors  A review of a simple C library: List ADT Fixed-length arrays are not very useful for dealing with optional data, so we want something exible Many data structure implementations rely on linked data records Obvious example: linked list Other examples: Trees Hash tables - linked elements are used to resolve collisions, when more than one element hashes into the same bucket We are using C and do not have equivalents to Java’s ArrayList or Vector, so we need something like a linked list fl Common list operations create a list insert a node at front/back remove a node from front/back retrieve an arbitrary node iterate through a list clear/delete list create a humanly-readable representation of the list with its data Storing data A good data structure implementation should be generic - i.e. be able to store any data of any type Re-declaring a new list ADT for every data type we might want to store is a non-starter In C, this means that we store data of type void* in the list So a list node has links to other nodes and a pointer to the data Storing data We do not know the data type at compile time, so we do not know how to Safely free the data (a single call to free() might not be enough) Compare data values if we want to sort the list or insert elements in order Convert the contents of a list to a humanly-readable representation think toString() in Java We do this by having the List structure contain a few function pointers These point to the functions for freeing and comparing data on the list, as well as converting that data into a string In essence, we are creating a pseudo-class with public members List API: C Check LinkedListAPI.h in the Week1-2 examples.zip on the course web page The example is extensively documented Common list operations create a list insert a node at front/back remove a node from front/back retrieve an arbitrary node iterate through a list clear/delete list Iterating through a list “Stepping through” every element in a data collection is a very common operation For an indexed collection (e.g. an array) we can use a loop with a counter For a linked data collection, we use An iterator A “smart” for-loop (which C doesn't have, so it will not help us) An iterator is an object that allows you to iterate through (traverse) a data collection Typically used with a linked data collection It allows us to have a generic way of traversing a list without relying on the list’s implementation Iterator example: Java ArrayList al = new ArrayList(); //Create and add strides records al.add(new StudentRecord(...) ); Iterator itr = al.iterator(); while(itr.hasNext()) { String element = itr.next(); System.out.print(element); } System.out.println(); Iterator example: C // Allocate the data. It must be dynamically allocated, since // our deleteFunc will try to free the contents of each node char* str; for (int i = 0; i < 4; i++){ str[i] = (char*)malloc(10*sizeof(char)); } //Initialize the string array strcpy(str, "Hello"); strcpy(str, " "); strcpy(str, "world"); strcpy(str, “!"); //Create and populate the list List* list = initializeList(&printFunc, &deleteFunc, &compareFunc); for (int i = 0; i < 4; i++){ insertBack(&list, (void*)str[i]); } Iterator example: C void* elem; //Create an iterator ListIterator iter = createIterator(list); //Traverse the list, examining one element at a time while ((elem = nextElement(&iter)) != NULL){ char* str = (char*)elem; printf("%s", str); } printf("\n"); deleteList(list); Iterator example: C See StructListDemo.c Libraries In this course, you will spend a lot of time developing libraries Libraries are reusable collection of precompiled functions and ancillary data - new types, enums, constants, etc.. A large part of software development involves designing the library API - application programming interface The API is the "interface" for the user of your library - i.e. another programmer It is made of all the public components of your interface - functions, constants, custom types, etc.. The List API we have just described is used as a library in StructListDemo.c Library design Programmer decides on what functionality goes into library components what each function does what arguments it takes and what it returns how it handles errors how to name it so its role is clear Since for the rst part of the course we are using C, we will focus on creating libraries of functions However, in an object-oriented languages we would be creating libraries of classes Later, we will use libraries in Python (which calls them "modules") fi Libraries in action You have been using libraries since you started programming in C For example, the standard C library has an API consisting of all functions and constants that you are familiar with: functions: printf()/scanf(), strcpy(), pow(), etc. constants (#de ne macros, actually): NULL, RAND_MAX, EOF, etc. fi Library design - public aspects Since the API is the public interface for your library, designing a good API is important Deciding what makes up the API is similar to deciding on public methods of a class For this course (A1 and A2) I have designed the API for you, and your job is to implement it In later courses, you will be learning to design the public API yourselves Think of the end-user (programmer) What does the library allow them to do? e.g. parse les in a speci c format, do math, manipulate strings, etc. You expose the important functionality to library users through functions Think of these as public functions in your interface fi fi Library design - private aspects It is equally important to decide what functionality you do not want other programmers to see / use - i.e. what components will be private This is the concept of information hiding you saw in object-oriented programming The purpose is to hide implementation details, so the user of the library does not mess things up e.g. why let the user manipulate the next pointer of a list struct - possibly incorrectly? instead, we create insertFront / insertBack methods for the user C has very limited tools for actually making library internals inaccessible - we will see them in an upcoming lecture Libraries in practice On Linux, system-wide libraries are normally stored in /lib and /usr/lib. They always have an associated header.h le which contains constants and function de nitions. Standard headers are normally located in /usr/include One library you would have used by now is the math library Library le is libm.so and the associated header le is math.h Notice they do not necessarily have the same name. fi fi fi Static and dynamic libraries There are two types of libraries: For static libraries, when a program is compiled, the library contents are copied into the executable and stored with it Library copy is stored in the executable le Compile-time linking For dynamic libraries, when the program is executed, the library is linked (connected) to the executable in memory The library copy is not stored in the executable le Run-time linking Also known as shared libraries in the Unix/Linux world, dynamically linked libraries (DLLs) in the Windows world fi Static and dynamic libraries Static libraries Pros: one self-contained executable, a bit more beginner-friendly Cons: executable can be very large; in exible - library cannot be updated Dynamic libraries Pros: exible - an executable can be linked to di erent versions of the library, as long as the library API is the same; executable is not bloated Cons: In some applications a single self-contained executable might be more convenient; require more experience to use Dynamic libraries tend to be the default in most real-world applications fl fl Naming libraries All library names begin with lib Static libraries end with.a Dynamic libraries end with.so (shared object on Linux) or.dll (dynamic linked library on Windows) Can also be.dylib (dynamic library) in addition to.so on macOS Shared objects can have version numbers after the.so: libm.so.3 libm.so.3.2 These would be version 3 and 3.2 of the math library Libraries and symbolic links Symbolic links may be used to create multiple names for the same library For example, liba.so.3.2 may have links liba.so.3 and liba.so which point to it The library itself is called "a" Some common library names: libm.so.6 - the math library, m libc.so.6 - the standard C library, c libstdc++.so.2.8 - the C++ standard library, stdc++ Creating a dynamic (shared) library Easy to do it with gcc We need to enable creation of Position-Independent Code (PIC). It works no matter where in memory it is placed the location of the library in memory will vary from program to program, and more than one program might be using it at any given time so we need to use appropriate compiler/linker arguments Done in two steps gcc -c -fpic record.c - creates the.o le gcc -shared -o librecord.so record.o - creates the.so le See the Make le in the List API sample code fi fi Creating a dynamic (shared) library requires two steps: source code le record.c gcc -c -fpic record.c compiled into an record.o object le gcc -shared -o librecord.so record.o librecord.so -shared ag creates a shared library -o ag speci es the output le name fl fi fl fi fi fi Creating an executable using a shared library Given a library and associated header le: librecord.so record.h And a program which uses the library: prog.c -source code which uses the library prog.h -header le associated with prog.h First compile the source code (prog.c) and then link the library (librecord.so). fi fi Creating an executable using a shared library need to include the header for the library record.h prog.c so the compiler knows the structure of the library function calls. We may need to specify the location of prog.h the header using the -I preprocessor command record.h (Lectures 3a and 3b) Compile Step gcc prog.c -o prog.o -c prog.o librecord.so Link Step gcc prog.o -o prog -lrecord -L. Converts the compiled program prog and library into an executable. Using a library The compile step converts the source code into an object le. Use -c with gcc. The link step links the library to the compiled program Use -lxyz (lower case L followed by the library name) You only need to provide the unique part of the library name. Do not use the entire library name. E.g. Correct: -lxml2 Incorrect: libxml2.so Do use -l (a lower case L) to identify the library Do not include lib or.so in the library name when you link with it