Welcome to LZN's Blog!

Wind extinguishes a candle but energizes fire.

Scratch Notes for Stanford CS107: Programming Paradigm Ch05

2020-10-20

LZN

technology

cs107 paradigm
- L5: Generic Lsearch - Prototype
  - Notes
    - LSearch
  - Appendix
  - Glossary
L5: Generic Lsearch - Prototype

Notes

LSearch

First review the lsearch function:
```
void *lsearch(void *k, void *base,
                int n, int elemSize,
                int(*cmpfn)(void *, void *))
{
    for (int i=0; i<n; i++){
        void *elemAddr= base+i*elemSize; //01
}
```
01: This is a strictly pointer arithmetic against a typeless (void *) pointer.

Appendix

Glossary
```
ebb 退潮 mantissa 尾数
```
Updated 2020-10-20
Read All
Scratch Notes for Stanford CS107: Programming Paradigm Ch04

2020-08-07

LZN

technology

cs107 paradigm
- L4: Creating a Generic Swap Function for Data Types of Arbitrary Size
  - Notes
    - Generic Swap
    - Generic lsearch
  - Qustions
  - Appendix
    - C++ Template
  - Glossary
L4: Creating a Generic Swap Function for Data Types of Arbitrary Size

Notes

Generic Swap

The generic swap function in the last lecture is useful for 4-byte figures. How to make it be a universial function? Look at the following realization:
```
void swap(void *vp1, void *vp2, int size)
{
    char buffer[size];
    memcpy(buffer, vp1, size);
    memcpy(vp1, vp2, size);
    memcpy(vp2, buffer, size);
};

int x=17; y=37;
swap(&x,&y,sizeof(int));
```
void * means a generic pointer. char buffer[size] is to set aside enough space to hold byte info. memcpy(target, source, size) is a more generic function to copy byte info with respect to the byte length. Most energy is used to dynamically allocate and deallocate buffer.

The perk of using this method compared to C++ template is that this way is lean and economical, while the C++ template will generate patches as much as the call times in the executables.

Wrong usage:
```
int i = 44;
short j=5;
swap(&i, &j, sizeof(short))
```
If using generic code, you have to be very careful about the type. The above usage will cause unexpected result as the short and int are different types with different byte lengthes.

Another example of the generic code (a very complicated case):
```
char * husband = strdup("Fred");
char * wife = strdup("Wilma");
// Right usage
swap(&husband, &wife, sizeof(char *))
```
Note here we are acturally swap the bit patterns (address stored in char *) of two char pointers. We still need the reference operator &. See the blackboard:

Some terrible errors:
```
swap(husband, wife, sizeof(char *))  // will swap the first 4 chars in heap
swap(husband, &wife, sizeof(char *)) // will make things chaos, the first 4 chars will be interpreted as an address!
```
Generic lsearch

An example for linear search:
```
int lsearch(int key, int array[], int size){
    for (i=0;i<size;i++){
        if (array[i]==key){
            return i;
        }
    }
    return -1;
}
```
Let’s make it generic! How about a undefinite type of array?
```
void *lsearch(void *key, void *base, int n, int elemSize){
    for (i=0;i<n;i++){
        void *elemAddr = (char *) base + i*elemSize;
        if (memcmp(key, elemAddr, elemSize)==0)
            return elemAddr;
        return NULL;
    }
}
```
It does not work for character pointers or C-strings.

Qustions

Appendix

C++ Template

Function templates are special functions that can operate with generic types. This allows us to create a function template whose functionality can be adapted to more than one type or class without repeating the entire code for each type.
```
template <class myType>
myType GetMax (myType a, myType b) {
 return (a>b?a:b);
 }

 int x, y;
 GetMax <int> (x, y);
```
Glossary
```
perk 额外好处 sedate v. 安慰 sentinel 哨兵
```
Updated 2020-08-06
Read All
Scratch Notes for Stanford CS107: Programming Paradigm Ch03

2020-07-16

LZN

technology

cs107 paradigm
- L3: Converting Between Types of Different Sizes and Bit Representations Using Pointers
L3: Converting Between Types of Different Sizes and Bit Representations Using Pointers

Notes

Forced Type Conversion
```
double d=3.1416;
char ch=*(char *)&d; // 1. &d get d ref --> 2. (char *) use char point to &d --> 3. * deref by `char`
```
Another dangerous test:
```
short s=45;
double d=*(double *) &s;
```
Note double need 8 bytes to store the value, while short only takes 2 bytes, so this operation is very dangerious.

Big Endian and Little Endian:

See this plot:

If copy a short type 1 from Big Endian machine to Little Endian machine, it will give a 256. Not a problem in forced type conversion.

Struct
```
struct fraction{
    int num;
    int denum;
};

fraction pi;
```
pattern:
```
||||pi.denum
||||pi.num
^
|
pointer
```
See the quirky syntax:
```
(fraction*)(&pi.denum))->num=12;
```
It first point to the original pi.denum (4 byte) and then interpret it to a fraction struct! What will happen? The orginal pi.denum is interpreted to a <new_struct> of fraction! Thus, ->num=12 will change the original `pi.denum` value!

Similar examples:
```
((fraction*)&(pi.denum))->denum=33;
```
What you will see:

Array

Actually, we need to accept the concept that verything in C/C++ is pointer, look at array:
```
array<=>&array[0]
array+k<=>&array[k]
*array<=>array[0]
*(array+k)<=>array[k]
```
If do this:
```
int array[10];
array[10]=1;
```
Be aware, this will not cause a compiler error as the C compiler is an efficiency-wise compiler, it will not do the bounce check. array[10] will be interpreted by 10*sizeof(a[0]), which is 40. Thus, from &array[0] and count for 40 bytes, that 4-byte space will be set to 1. This operation even tolerates negative numbers. (This is just code, not good code!) The neighbouring address is highly possible to be other variables. See activation record.

The above code is equivalent to:
```
*(array+10)=1;
```
There could be many crazy examples (Actually there is an error, you can find it):

Struct Array

Now we see the struct:

The corresponding bit patterns in memory: KCwj.jpg](https://s1.ax1x.com/2020/08/06/aRKCwj.jpg)

Try this:
```
pupils[2].name=strdup("Adam");
```
Here a linked table like thing will work:

And this:
```
pupils[3].name=pupils[0].suid+6;
```
You will see:

Another one:
```
strcpy(pupils[1].suid, "40415xx");
```
Null character \0 or NUL

Try a scary on:
```
strcpy(pupils[3].name,"123456")
```
See the result:

Generic Swap Important
```
void swap (int *ap, int *bp)
{
    int temp = *ap;
    *ap = *bp;
    *bp = temp;
}
int x=7;
int y=117;
swap(&7, &y);
```
See the flow:

Qustions

Glossary
```
Asterisk 星号 Ampersand 连i字符 synonymous 同义的 arithmetic 算数的 verbatim 逐字的 backslash 反斜线 jurisdiction 管辖权
two to the ninth 2^9 gibberish 胡言乱语 contrived (deliberately created rather than arising naturally or spontaneously)
phantom 幻影
```
Updated 2020-08-06
Read All