Computer Science304 Interval Tree 특정한 구간을 의미함. 메모리 구간을 관리하기 위해서 사용함. 특정 메모리 구간을 찾음. arguments는 리프노드는 마지막 값. 부모노드는 왼쪽과 오른쪽, 자기 자신 중 큰 값을 가지고 있음. 2021. 4. 30. 증강 트리 O(logN) O(N) 알파벳 순서상 5번째 사람은? i = 5( 찾고싶은 것) k = 2 (왼쪽 트리의 갯수 + 1) 왼쪽으로 이동할 때는 i 변동 없으나, 오른쪽으로 이동하면 i = i-k; 임 i == k 일 때 찾고자 하는 값이 위치함. 동적 통계 트리임. 실제 코드를 짤 수 있는 정도 avl tree 까지 봐야 하는지.? my_select(x, i =5) { int k; k = size[left[x]]+1; if(i==k) return x; if(i 2021. 4. 30. Generic Hash 2 1000, 1096 % 8 은 2진수로 하였을 때 뒷자리 3개로 결정하게 됨. pid를 8개의 버킷으로 분리하겠다는 의미임. 그럼 항상 저 GOLDEN_RATIO_PRIME_32 를 사용해서 hash 값을 구하면 좋은 것인가? 언제 사용 할 수 있는지. #include #define GOLDEN_RATIO_PRIME_32 0x9e370001UL int main() { unsigned long long hash = 3 * GOLDEN_RATIO_PRIME_32; printf("%llu\n%lu", hash, GOLDEN_RATIO_PRIME_32); long long var = 0x1234567812345678; printf("\n%llu", var); return 0; } #include #include.. 2021. 4. 29. Generic Hash 타입 설계 void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { struct hlist_node *first = h->first; n->next = first; if(first) first->pprev = &n->next; h->first = n; n->pprev = &h->first; } h->first 가 포인터이기때문에 이것을 가리키기 위해서 이중 포인터를 사용함. first 는 기존 노드를 가리킴. 그래서 새로운 노드가 들어왔을떄. n->next = first; 했을 때 같은 곳을 가리킴 first->pprev . first가 기존 노드를 가리키는 포인터이므로 first->pprev 는 &n->next를 가리킴 노드가 오든 포인터이든 둘 다 가.. 2021. 4. 29. Generic Hash #define container_of(ptr, type, member) (type*)((char*)ptr-(unsigned long)&((type*)0)->member) : unsinged long 은 64비트 포인터가 8바이트이기 때문에 이것까지 커버할 수 있어야 함. 해당 타입 포인터가 가리키고 있는 멤버를 4비트 양수로 캐스팅을 하고 1바이트 크기의 캐릭터 변수로 캐스팅을 하고, 그것을 빼면 해당 멤버를 가리키는 메모리 주소가 나옴 그것을 다시 형변환하는 것임. 끝. SAWON *s ; s= (SAWON*)((char*)temp - 20); // 패딩이 있기 때문에 이렇게 빼면 안됨. s = (SAWON*) ((char*)temp - (sizeof(SAWON)-sizeof(NODE))); for (.. 2021. 4. 29. 최신 매크로 분석 container_of #include #include struct list_head { struct list_head* next, * prev; }; void __list_add(struct list_head* new, struct list_head* prev, struct list_head* next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new; } void list_add(struct list_head* new, struct list_head* head) { __list_add(new, head, head->next); } void list_add_tail(struct list_head* new, struct list_head* hea.. 2021. 4. 29. 타입의 의존성 제거(container_of 버전) SAWON *s; s = (SAWON*)((char*)temp - (sizeof(SAWON)-sizeof(NODE))); #include #include typedef struct _node { struct _node *next; struct _node *prev; } NODE; void __insert_data( NODE *temp, NODE *prev, NODE *next ) { temp->next = next; prev->next = temp; temp->prev = prev; next->prev = temp; } void insert_front( NODE *temp, NODE *head ) { __insert_data( temp, head, head->next ); } void insert_bac.. 2021. 4. 28. Generic swap int, float 가 바뀌면서 인풋으로 들어올 때 이것을 같이 처리하고 싶음. char* 받아서 하나의 바이트 마다 swap 을 돌릴 수 있음 for 문을 사용하여서 불법 !! 가독성 측면에서 정인님 코드 kernel 코드에서는 > 0 이랑 비교하는게 어셈블리상 유리함. #if 1 #include void generic_swap(void *a, void *b, int size) { char t; do { t = *(char *)a; *(char *)a++ = *(char *)b; *(char *)b++ = t; } while (--size > 0); } int main() { double ad=3., bd=4.; int a=3, b=4; generic_swap( &a, &b, sizeof(a) ); g.. 2021. 4. 24. Boyer-Moore Pattern Matching 뒤부터 매칭을 함 두 개의 suffice 중 더 쉬프트 많이 할 수 있는 것을 선택해서 이동 함. Bad suffice 는 패턴의 마지막 자리수에서 부터 얼마만큼 그 캐릭터가 떨어져 있는지 파악하는 것. Good suffice는 원하는 패턴이 만날 수 있도록. suff는 몇 칸 필었을 때 뒤에 패턴이 일치 하는가. 정해 둔 것. 맨 처음에 틀린 경우는 한 칸 을 밀면 되는 것임. #include #include #define OUTPUT(x) printf("%d\n", x ) #define MAX(a,b) (((a)>(b))?(a):(b)) #define ASIZE 256 #define XSIZE 256 void preBmBc(char *x, int m, int bmBc[]) { int i; for (i.. 2021. 4. 24. 이전 1 ··· 4 5 6 7 8 9 10 ··· 34 다음
