%Data Types
%Thadeu Cascardo

# Macros

* include/linux/kernel.h
* ARRAY\\_SIZE
* FIELD\\_SIZEOF
* ALIGN
* PTR\\_ALIGN
* IS\\_ALIGNED

# More macros

* container\\_of
* offsetof

# krefs

Reference:

* Documentation/kref.txt

# API

* struct kref
* kref\\_init - struct kref pointer
* kref\\_get - struct kref pointer
* kref\\_put - struct kref pointer and release function

# Usage

* Embed struct kref into your own structure
* Do not forget to call kref\\_init when initializing your structure
* Pass a release function as parameter to kref\\_put, where you release your
  structure
* Follow the rules for calling kref\\_get and kref\\_put

# Rules

* Must increment count if passing a non-temporary copy
* May increment count without a lock if already has a valid pointer
* Must decrement when done with the pointer
* If code never tries to get a ref without a valid pointer, may be done without
  a lock
* Must serialize getting a ref without a valid pointer with putting a ref

# Basic Types

* include linux/types.h
* sXX, where XX is 8, 16, 32 or 64
* uXX

# Endianness

# Little endian and Big endian

* Little endian machines
	- Alpha
	- x86
* Big endian machines
	- PowerPC
	- SPARC
* Multi-endian machines
	- ARM
	- MIPS
	- SH

# Headers

* include asm/byteorder.h
* include/linux/byteorder/generic.h

# Macros

* cpu\\_to\\_beXX
* cpu\\_to\\_leXX
* beXX\\_to\\_cpu
* leXX\\_to\\_cpu
* All those with suffix p - use a pointer
* All those with suffix s - change in situ

# Lists

# Declaration

* include linux/list.h
* LIST\\_HEAD(head);
* Embed a struct list\\_head in your structure
* Use a struct list\\_head pointer to iterate

# Initialization

* INIT\\_LIST\\_HEAD - receives a pointer to the embedded list head

# Operations

* list\\_add - receives a pointer to the element and a head
* list\\_add\\_tail
* list\\_del - receives only the pointer to the element
* list\\_empty

# Access

* list\\_entry(entry, type, member); -- uses container\\_of
* list\\_first\\_entry(head, type, member);

# Iteration macros

* list\\_for\\_each(lhptr, head);
* list\\_for\\_each\\_entry(iptr, head, member)
* list\\_for\\_each\\_safe(lhptr, head);

# Bitmaps

# Declaration

* include linux/types.h
* include linux/bitops.h
* DECLARE\\_BITMAP

# API

* All atomic, prefix \\_ to use non-atomic
* set\\_bit
* clear\\_bit
* change\\_bit
* test\\_and\\_set\\_bit
* test\\_and\\_clear\\_bit
* test\\_and\\_change\\_bit

# Lookup

* find\\_first\\_bit
* find\\_first\\_zero\\_bit
* find\\_last\\_bit
* find\\_next\\_bit
* find\\_next\\_zero\\_bit
* for\\_each\\_set\\_bit

# Reb-black tree

# Files

* Documentation/rbtree.txt
* lib/rbtree.c
* include linux/rbtree.h

# Usage

* Embed struct rb\\_node into your data structure
* There's no callback for comparison, write your own lookup and insertion
  functions
* Locking is up to the user

# API

* rb\\_entry is the same as container\\_of
* Create the root with struct rb\\_root name = RB\\_ROOT;
* Lookup function (see example) uses rb\\_left and rb\\_right members
* Insertion: lookup insertion point, save the parent and use the functions
  rb\\_link\\_node and rb\\_insert\\_color (example in Documentation)
* Erase with rb\\_erase
* Iterate with functions rb\\_first, rb\\_last, rb\\_next and rb\\_prev

# Hashes

* No hash table
* There are hash functions found at
	- include linux/hash.h
	- include linux/jhash.h
* Users usually do chaining to resolve collisions

# Other data types

* IDR
* Flexible Array
* Plist
* Radix tree
* Btree