1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 单向链表
struct list_element
{
  void *data;
  struct list_element *next; *// 指向下一个*
};
// 双向链表
struct list_element
{
  void *data;
  struct list_element *next; *// 指向下一个*
  struct list_element *prev; *// 指向前一个*
};

1
2
3
4

// include/linux/list.h  19
struct list_head {
  struct list_head *next, *prev;
};

1
2

// include/linux/list.h  23行
#define LIST_HEAD_INIT(*name*) { &(name), &(name) }

1
2
3
4
5
6
7

struct fox
{
  unsigned long tail_length;
  unsigned long weight;
  bool is_fantastic;
  struct list_head list; *// 所有 fox 结构形成链表*
};

1
2
3

#define container_of(*ptr*, *type*, *member*) ({      \
  const typeof( ((type *)0)->member ) *__mptr = (ptr);   \ // 1
  (type *)( (char *)__mptr - offsetof(type,member) );})   // 2

1

#define offsetof(*TYPE*, *MEMBER*) ((size_t) &((TYPE *)0)->MEMBER)

1
2

#define list_entry(*ptr*, *type*, *member*) \
  container_of(ptr, type, member)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>
#define container_of(*ptr*, *type*, *member*) ({      \
  const typeof( ((type *)0)->member ) *__mptr = (ptr);   \
  (type *)( (char *)__mptr - offsetof(type,member) ); })
#define offsetof(*TYPE*, *MEMBER*) ((size_t) & ((TYPE *)0)->MEMBER)
struct typeabc
{
  int mem0;
  float mem2;
  double mem4;
  char mem6;
};
int main()
{
  struct typeabc abc, *pabc;
  abc.mem2 = 0.0;
  float *pmem2 = &abc.mem2;
  *//通过成员变量的地址得到它所在结构的首地址*
  pabc = container_of(pmem2, struct typeabc, mem2);
  printf("%p\n", pabc);
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// include/linux/list.h  34行
*/**
 ** Insert a* *new* *entry between two known consecutive entries.*
 ***
 ** This is only* *for* *internal* *list* *manipulation where we know*
 ** the prev/next entries already!*
 **/*
#ifndef CONFIG_DEBUG_LIST
static inline 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;
}
#else
extern void __list_add(struct list_head *new,
         struct list_head **prev*,
         struct list_head **next*);
#endif
*/***
 ** list_add - add a* *new* *entry*
 ** @**new**:* *new* *entry to be added*
 ** @head:* *list* *head to add it after*
 ***
 ** Insert a* *new* *entry after the specified head.*
 ** This is good* *for* *implementing stacks.*
 **/*
static inline void list_add(struct list_head *new, struct list_head **head*)
{
  __list_add(new, head, head->next);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

*/***
 ** list_add_tail - add a* *new* *entry*
 ** @**new**:* *new* *entry to be added*
 ** @head:* *list* *head to add it before*
 ***
 ** Insert a* *new* *entry before the specified head.*
 ** This is useful* *for* *implementing queues.*
 **/*
static inline void list_add_tail(struct list_head *new, struct list_head **head*)
{
  __list_add(new, head->prev, head);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

*/**
 ** Delete a* *list* *entry by making the prev/next entries*
 ** point to each other.*
 ***
 ** This is only* *for* *internal* *list* *manipulation where we know*
 ** the prev/next entries already!*
 **/*
static inline void __list_del(struct list_head * *prev*, struct list_head * *next*)
{
  next->prev = prev;
  prev->next = next;
}
*/***
 ** list_del - deletes entry from* *list**.*
 ** @entry: the element to* *delete* *from the* *list**.*
 ** Note: list_empty() on entry does* *not* *return* *true* *after* *this**, the entry is*
 ** in an undefined state.*
 **/*
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head **entry*)
{
  __list_del(entry->prev, entry->next);
  entry->next = LIST_POISON1;
  entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head **entry*);
#endif

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

*/***
 ** list_move - delete from one* *list* *and* *add* *as* *another**'s head*
 ** @**list**: the entry to move*
 ** @head: the head that will precede our entry*
 **/*
static inline void list_move(struct list_head **list*, struct list_head **head*)
{
  __list_del(list->prev, list->next);
  list_add(list, head);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

static inline void __list_splice(const struct list_head **list*,
         struct list_head **prev*,
         struct list_head **next*)
{
  struct list_head *first = list->next;
  struct list_head *last = list->prev;
  first->prev = prev;
  prev->next = first;
  last->next = next;
  next->prev = last;
}
*/***
 ** list_splice - join two lists, this is designed* *for* *stacks*
 ** @**list**: the* *new* *list* *to add.*
 ** @head: the place to add it in the first* *list**.*
 **/*
static inline void list_splice(const struct list_head **list*,
        struct list_head **head*)
{
  if (!list_empty(list))
    __list_splice(list, head, head->next);
}

1
2
3
4
5
6
7
8

*/***
 ** list_for_each   -  iterate over a* *list*
 ** @pos:   the &struct list_head to* *use* *as* *a* *loop* *cursor**.*
 ** @head:  the head* *for* *your* *list**.*
 **/*
#define list_for_each(*pos*, *head*) \
  for (pos = (head)->next; prefetch(pos->next), pos != (head); \
      pos = pos->next)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

*/***
 ** list_for_each_entry  -  iterate over* *list* *of given type*
 ** @pos:   the type \* to* *use* *as* *a* *loop* *cursor**.*
 ** @head:  the head* *for* *your* *list**.*
 ** @member: the name of the list_struct within the struct.*
 **/*
#define list_for_each_entry(*pos*, *head*, *member*)        \
  for (pos = list_entry((head)->next, typeof(*pos), member);  \
     &pos->member != (head);   \
     pos = list_entry(pos->member.next, typeof(*pos), member))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

*/**
 ** inotify_find_handle - find the watch associated with the given inode* *and*
 ** handle*
 ***
 ** Callers must hold inode->inotify_mutex.*
 **/*
static struct inotify_watch *inode_find_handle(struct inode **inode*,
              struct inotify_handle **ih*)
{
  struct inotify_watch *watch;
  list_for_each_entry(watch, &inode->inotify_watches, i_list) {
    if (watch->ih == ih)
      return watch;
  }
  return NULL;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 425行
*/***
 ** list_for_each_entry_reverse - iterate backwards over* *list* *of given type.*
 ** @pos:   the type \* to* *use* *as* *a* *loop* *cursor**.*
 ** @head:  the head* *for* *your* *list**.*
 ** @member: the name of the list_struct within the struct.*
 **/*
#define list_for_each_entry_reverse(*pos*, *head*, *member*)      \
  for (pos = list_entry((head)->prev, typeof(*pos), member);  \
     prefetch(pos->member.prev), &pos->member != (head);   \
     pos = list_entry(pos->member.prev, typeof(*pos), member))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 487行
*/***
 ** list_for_each_entry_safe - iterate over* *list* *of given type safe against removal of* *list* *entry*
 ** @pos:   the type \* to* *use* *as* *a* *loop* *cursor**.*
 ** @n:    another type \* to* *use* *as* *temporary* *storage*
 ** @head:  the head* *for* *your* *list**.*
 ** @member: the name of the list_struct within the struct.*
 **/*
#define list_for_each_entry_safe(*pos*, *n*, *head*, *member*)      \
  for (pos = list_entry((head)->next, typeof(*pos), member),  \
    n = list_entry(pos->member.next, typeof(*pos), member); \
     &pos->member != (head);           \
     pos = n, n = list_entry(n->member.next, typeof(*n), member))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

*/***
 ** inotify_inode_is_dead - an inode has been deleted, cleanup any watches*
 ** @inode: inode that is about to be removed*
 **/*
void inotify_inode_is_dead(struct inode **inode*)
{
  struct inotify_watch *watch, *next;
  mutex_lock(&inode->inotify_mutex);
  list_for_each_entry_safe(watch, next, &inode->inotify_watches, i_list) {
    struct inotify_handle *ih = watch->ih;
    mutex_lock(&ih->mutex);
    inotify_remove_watch_locked(ih, watch);
    mutex_unlock(&ih->mutex);
  }
  mutex_unlock(&inode->inotify_mutex);
}

1
2
3
4
5
6

struct kfifo {
  unsigned char *buffer;  */\* the buffer holding the data \*/*
  unsigned int size;  */\* the size of the allocated buffer \*/*
  unsigned int in;   */\* data is added at offset (in % size) \*/*
  unsigned int out;  */\* data is extracted from off. (out % size) \*/*
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

*/***
 ** kfifo_alloc - allocates a* *new* *FIFO internal buffer*
 ** @fifo: the fifo to assign then* *new* *buffer*
 ** @size: the size of the buffer to be allocated,* *this* *have to be a power of* *2.*
 ** @gfp_mask: get_free_pages mask,* *passed to* *kmalloc**()*
 ***
 ** This function dynamically allocates a* *new* *fifo internal buffer*
 ***
 ** The size will be rounded-up to a power of* *2.*
 *** *The buffer will be release with* *kfifo_free**()**.*
 ** Return* *0* *if* *no error, otherwise the an error code*
 **/*
int kfifo_alloc(struct kfifo **fifo*, unsigned int *size*, gfp_t *gfp_mask*)
{
  unsigned char *buffer;
  */**
   ** round up to the next power of* *2**, since our* *'let the indices*
   ** wrap' technique works only in* *this* *case**.*
   **/*
  if (!is_power_of_2(size)) {
    BUG_ON(size > 0x80000000);
    size = roundup_pow_of_two(size);
  }
  buffer = kmalloc(size, gfp_mask);
  if (!buffer) {
    _kfifo_init(fifo, NULL, 0);
    return -ENOMEM;
  }
  _kfifo_init(fifo, buffer, size);
  return 0;
}

1
2
3
4
5
6
7

static void _kfifo_init(struct kfifo **fifo*, void **buffer*,
    unsigned int *size*)
{
  fifo->buffer = buffer;
  fifo->size = size;
  kfifo_reset(fifo);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

*/***
 ** DECLARE_KFIFO - macro to* *declare* *a kfifo* *and* *the associated buffer*
 ** @name: name of the declared kfifo datatype*
 ** @size: size of the fifo buffer. Must be a power of two.*
 ***
 ** Note1: the macro can be used inside struct* *or* *union declaration*
 ** Note2: the macro creates two objects:*
 **  A kfifo object with the given name* *and* *a buffer* *for* *the kfifo*
 **  object named name**##kfifo_buffer*
 **/*
#define DECLARE_KFIFO(*name*, *size*) \
union { \
  struct kfifo name; \
  unsigned char name##kfifo_buffer[size + sizeof(struct kfifo)]; \
}

1
2
3
4
5
6
7
8

*/***
 ** INIT_KFIFO - Initialize a kfifo declared by DECLARE_KFIFO*
 ** @name: name of the declared kfifo datatype*
 **/*
#define INIT_KFIFO(*name*) \
  name = __kfifo_initializer(sizeof(name##kfifo_buffer) - \
        sizeof(struct kfifo), \
        name##kfifo_buffer + sizeof(struct kfifo))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

*/***
 ** kfifo_in - puts some data into the FIFO*
 ** @fifo: the fifo to be used.*
 ** @from: the data to be added.*
 ** @**len**: the length of the data to be added.*
 ***
 ** This function copies at most @**len* *bytes from the @from buffer into*
 ** the FIFO depending on the free space, and returns the number of*
 ** bytes copied.*
 ***
 ** Note that with only one concurrent reader and one concurrent*
 ** writer, you don**'t need extra locking to use these functions.*
 **/*
unsigned int kfifo_in(struct kfifo **fifo*, const void **from*,
        unsigned int *len*)
{
  len = min(kfifo_avail(fifo), len);
  __kfifo_in_data(fifo, from, len, 0);
  __kfifo_add_in(fifo, len);
  return len;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

static inline void __kfifo_in_data(struct kfifo **fifo*,
    const void **from*, unsigned int *len*, unsigned int *off*)
{
  unsigned int l;
  */**
   ** Ensure that we sample the fifo->out index -before- we*
   ** start putting bytes into the kfifo.*
   **/*
  smp_mb();
  off = __kfifo_off(fifo, fifo->in + off);
  */\* first put the data starting from fifo->in to buffer end \*/*
  l = min(len, fifo->size - off);
  memcpy(fifo->buffer + off, from, l);
  */\* then put the rest (if any) at the beginning of the buffer \*/*
  memcpy(fifo->buffer, from + l, len - l);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

*/***
 ** kfifo_out - gets some data from the FIFO*
 ** @fifo: the fifo to be used.*
 ** @to: where the data must be copied.*
 ** @**len**: the size of the destination buffer.*
 ***
 ** This function copies at most @**len* *bytes from the FIFO into the*
 ** @to buffer and returns the number of copied bytes.*
 ***
 ** Note that with only one concurrent reader and one concurrent*
 ** writer, you don**'t need extra locking to use these functions.*
 **/*
unsigned int kfifo_out(struct kfifo **fifo*, void **to*, unsigned int *len*)
{
  len = min(kfifo_len(fifo), len);
  __kfifo_out_data(fifo, to, len, 0);
  __kfifo_add_out(fifo, len);
  return len;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

*/***
 ** kfifo_out_peek - copy some data from the FIFO, but* *do* *not remove it*
 *** *@fifo**: the fifo to be used.*
 *** *@to**: where the data must be copied.*
 *** *@len**: the size of the destination buffer.*
 *** *@offset**: offset into the fifo*
 ***
 ** This function copies at most* *@len* *bytes at* *@offset* *from the FIFO*
 ** into the* *@to* *buffer and returns the number of copied bytes.*
 ** The data is not removed from the FIFO.*
 **/*
unsigned int kfifo_out_peek(struct kfifo **fifo*, void **to*, unsigned int *len*,
        unsigned *offset*)
{
  len = min(kfifo_len(fifo), len + offset);
  __kfifo_out_data(fifo, to, len, offset);
  return len;
}

1
2
3
4
5
6
7
8

*/***
 ** kfifo_size - returns the size of the fifo in bytes*
 ** @fifo: the fifo to be used.*
 **/*
static inline __must_check unsigned int kfifo_size(struct kfifo *fifo)
{
  return fifo->size;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

*/***
 ** kfifo_len - returns the number of used bytes in the FIFO*
 ** @fifo: the fifo to be used.*
 **/*
static inline unsigned int kfifo_len(struct kfifo **fifo*)
{
  register unsigned int  out;
  out = fifo->out;
  smp_rmb();
  return fifo->in - out;
}

1
2
3
4
5
6
7
8

*/***
 ** kfifo_reset - removes the entire FIFO contents*
 ** @fifo: the fifo to be emptied.*
 **/*
static inline void kfifo_reset(struct kfifo **fifo*)
{
  fifo->in = fifo->out = 0;
}

1
2
3
4
5
6
7
8
9

*/***
 ** kfifo_free - frees the FIFO internal buffer*
 ** @fifo: the fifo to be freed.*
 **/*
void kfifo_free(struct kfifo **fifo*)
{
  kfree(fifo->buffer);
  _kfifo_init(fifo, NULL, 0);
}

1
2
3
4
5
6
7

struct idr {
  struct idr_layer *top;
  struct idr_layer *id_free;
  int    layers; */\* only valid without concurrent changes \*/*
  int    id_free_cnt;
  spinlock_t   lock;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

*/***
 ** idr_init - initialize idr handle*
 ** @idp:   idr handle*
 ***
 *** *This function is use to* *set* *up the* *handle* *(@idp)* *that you will pass*
 ** to the rest of the functions.*
 **/*
void idr_init(struct idr **idp*)
{
  memset(idp, 0, sizeof(struct idr));
  spin_lock_init(&idp->lock);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

*/***
 ** idr_pre_get - reserver resources* *for* *idr allocation*
 ** @idp:   idr handle*
 ** @gfp_mask:  memory allocation flags*
 ***
 ** This function should be called prior to locking* *and* *calling the*
 ** idr_get_new\* functions. It preallocates enough memory to satisfy*
 ** the worst possible allocation.*
 ***
 ** If the system is REALLY out of memory* *this* *function returns* *0**,*
 ** otherwise* *1.*
 **/*
int idr_pre_get(struct idr **idp*, gfp_t *gfp_mask*)
{
  while (idp->id_free_cnt < IDR_FREE_MAX) {
    struct idr_layer *new;
    new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
    if (new == NULL)
      return (0);
    move_to_free_list(idp, new);
  }
  return 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

*/***
 ** idr_get_new - allocate* *new* *idr entry*
 *** *@idp**: idr handle*
 *** *@ptr**: pointer you want associated with the id*
 *** *@id**: pointer to the allocated handle*
 ***
 ** This is the allocate id function.  It should be called with any*
 ** required locks.*
 ***
 ** If memory is required, it will* *return* *-EAGAIN, you should unlock*
 *** *and go back to the* *idr_pre_get**()* *call.  If the idr is full, it will*
 *** *return* *-ENOSPC.*
 ***
 *** *@id* *returns a value in the range* *0* *...* *0x7fffffff*
 **/*
int idr_get_new(struct idr **idp*, void **ptr*, int **id*)
{
  int rv;
  rv = idr_get_new_above_int(idp, ptr, 0);
  */**
   ** This is a cheap hack until the IDR code can be fixed to*
   *** *return* *proper error values.*
   **/*
  if (rv < 0)
    return _idr_rc_to_errno(rv);
  *id = rv;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

*/***
 ** idr_find -* *return* *pointer* *for* *given id*
 ** @idp: idr handle*
 ** @id: lookup key*
 ***
 ** Return the pointer given the id it has been registered with.  A %**NULL*
 *** *return* *indicates that @id is* *not* *valid* *or* *you passed %**NULL* *in*
 ** idr_get_new().*
 ***
 *** *This function can be called under* *rcu_read_lock**()**, given that the leaf*
 ** pointers lifetimes are correctly managed.*
 **/*
void *idr_find(struct idr **idp*, int *id*)
{
  int n;
  struct idr_layer *p;
  p = rcu_dereference_raw(idp->top);
  if (!p)
    return NULL;
  n = (p->layer+1) * IDR_BITS;
  */\* Mask off upper bits we don't use for the search. \*/*
  id &= MAX_ID_MASK;
  if (id >= (1 << n))
    return NULL;
  BUG_ON(n == 0);
  while (n > 0 && p) {
    n -= IDR_BITS;
    BUG_ON(n != p->layer*IDR_BITS);
    p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
  }
  return((void *)p);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

*/***
 ** idr_remove - remove the given id* *and* *free it**'s slot*
 ** @idp: idr handle*
 ** @id: unique key*
 **/*
void idr_remove(struct idr **idp*, int *id*)
{
  struct idr_layer *p;
  struct idr_layer *to_free;
  */\* Mask off upper bits we don't use for the search. \*/*
  id &= MAX_ID_MASK;
  sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
  if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
    idp->top->ary[0]) {
    */**
     ** Single child at leftmost slot: we can shrink the tree.*
     ** This level is not needed anymore since when layers are*
     ** inserted, they are inserted at the top of the existing*
     ** tree.*
     **/*
    to_free = idp->top;
    p = idp->top->ary[0];
    rcu_assign_pointer(idp->top, p);
    --idp->layers;
    to_free->bitmap = to_free->count = 0;
    free_layer(to_free);
  }
  while (idp->id_free_cnt >= IDR_FREE_MAX) {
    p = get_from_free_list(idp);
    */**
     ** Note: we don**'t call the rcu callback here, since the only*
     ** layers that fall into the freelist are those that have been*
     ** preallocated.*
     **/*
    kmem_cache_free(idr_layer_cache, p);
  }
  return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

*/***
 ** idr_destroy - release all cached layers within an idr tree*
 ** idp: idr handle*
 **/*
void idr_destroy(struct idr **idp*)
{
  while (idp->id_free_cnt) {
    struct idr_layer *p = get_from_free_list(idp);
    kmem_cache_free(idr_layer_cache, p);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

struct rb_node
{
  unsigned long  rb_parent_color;
#define RB_RED    0
#define RB_BLACK   1
  struct rb_node *rb_right;
  struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
  */\* The alignment might seem pointless, but allegedly CRIS needs it \*/*
struct rb_root
{
  struct rb_node *rb_node;
};

1
2

// include/linux/rbtree.h 133行 通过指针寻找这个结构的地址
#define rb_entry(*ptr*, *type*, *member*) container_of(ptr, type, member)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

 *linux/include/linux/rbtree.h*
 *To* *use* *rbtrees you**'ll have to implement your own insert and search cores.*
 *This will avoid us to* *use* *callbacks* *and* *to* *drop* *drammatically performances.*
 *I know it's not the cleaner way,  but in C (not in C++) to get*
 *performances and genericity...*
 *Some example of* *insert* *and* *search* *follows* *here. The* *search* *is* *a plain*
 *normal search over an ordered tree. The* *insert* *instead must be implemented*
 *in two steps: First, the code must* *insert* *the* *element* *in* *order* *as* *a red leaf*
 *in the tree, and then the support library function rb_insert_color() must*
 *be called. Such function will* *do* *the* *not* *trivial* *work* *to* *rebalance the*
 *rbtree, if necessary.*

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

*static* *inline* *struct page ** *rb_search_page_cache**(struct inode \* inode,*
             *unsigned* *long* *offset)*
*{*
  *struct* *rb_node* *** *n* *=* *inode**->**i_rb_page_cache**.**rb_node**;*
  *struct* *page* *** *page**;*
  *while* *(n)*
  *{*
    *page = rb_entry(n, struct page, rb_page_cache);*
    *if* *(offset < page->offset)*
      *n = n->rb_left;*
    *else* *if* *(offset > page->offset)*
      *n = n->rb_right;*
    *else*
      *return* *page;*
  *}*
  *return* *NULL**;*
*}*

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

*static* *inline* *struct* *page* ** __**rb_insert_page_cache**(**struct* *inode* *** *inode**,*
              *unsigned* *long* *offset,*
              *struct* *rb_node* *** *node**)*
*{*
  *struct* *rb_node* **** *p* *= &**inode**->**i_rb_page_cache**.**rb_node**;*
  *struct* *rb_node* *** *parent* *=* *NULL**;*
  *struct* *page* *** *page**;*
  *while* *(\*p)*
  *{*
    *parent = \*p;*
    *page = rb_entry(parent, struct page, rb_page_cache);*
    *if* *(offset < page->offset)*
      *p = &(\*p)->rb_left;*
    *else* *if* *(offset > page->offset)*
      *p = &(\*p)->rb_right;*
    *else*
      *return* *page;*
  *}*
  *rb_link_node(node, parent, p);*
  *return* *NULL**;*
*}*
*static* *inline* *struct page ** *rb_insert_page_cache**(struct inode \* inode,*
             *unsigned* *long* *offset,*
             *struct* *rb_node* *** *node**)*
*{*
  *struct* *page* *** *ret**;*
  *if* *((ret = __rb_insert_page_cache(inode, offset, node)))*
    *goto* *out;*
  *rb_insert_color(node, &inode->i_rb_page_cache);*
 *out:*
  *return* *ret;*
*}*