| #ifndef _BTREE_BACKPORT_H_ |
| #define _BTREE_BACKPORT_H_ |
| |
| struct btree_head32 { |
| struct list_head head; |
| }; |
| |
| struct btree_node32 { |
| struct list_head entry; |
| u32 key; |
| void *val; |
| }; |
| |
| struct btree_head64 { |
| struct list_head head; |
| }; |
| |
| struct btree_node64 { |
| struct list_head entry; |
| u64 key; |
| void *val; |
| }; |
| |
| /** |
| * btree_init - initialise a btree |
| * |
| * @head: the btree head to initialise |
| * |
| * This function allocates the memory pool that the |
| * btree needs. Returns zero or a negative error code |
| * (-%ENOMEM) when memory allocation fails. |
| */ |
| static inline int __must_check btree_init32(struct btree_head32 *head) |
| { |
| INIT_LIST_HEAD(&head->head); |
| return 0; |
| } |
| |
| static inline int __must_check btree_init64(struct btree_head64 *head) |
| { |
| INIT_LIST_HEAD(&head->head); |
| return 0; |
| } |
| |
| /** |
| * btree_destroy - destroy mempool |
| * |
| * @head: the btree head to destroy |
| * |
| * This function destroys the internal memory pool, use only |
| * when using btree_init(), not with btree_init_mempool(). |
| */ |
| static inline void btree_destroy32(struct btree_head32 *head) |
| { |
| } |
| |
| static inline void btree_destroy64(struct btree_head64 *head) |
| { |
| } |
| |
| /** |
| * btree_lookup - look up a key in the btree |
| * |
| * @head: the btree to look in |
| * @geo: the btree geometry |
| * @key: the key to look up |
| * |
| * This function returns the value for the given key, or %NULL. |
| */ |
| static inline void *btree_lookup32(struct btree_head32 *head, u32 key) |
| { |
| struct btree_node32 *n; |
| |
| list_for_each_entry(n, &head->head, entry) { |
| if (n->key == key) |
| return n->val; |
| } |
| return NULL; |
| } |
| |
| static inline void *btree_lookup64(struct btree_head64 *head, u64 key) |
| { |
| struct btree_node64 *n; |
| |
| list_for_each_entry(n, &head->head, entry) { |
| if (n->key == key) |
| return n->val; |
| } |
| return NULL; |
| } |
| |
| /** |
| * btree_insert - insert an entry into the btree |
| * |
| * @head: the btree to add to |
| * @geo: the btree geometry |
| * @key: the key to add (must not already be present) |
| * @val: the value to add (must not be %NULL) |
| * @gfp: allocation flags for node allocations |
| * |
| * This function returns 0 if the item could be added, or an |
| * error code if it failed (may fail due to memory pressure). |
| */ |
| static inline int __must_check btree_insert32(struct btree_head32 *head, |
| u32 key, void *val, gfp_t gfp) |
| { |
| struct btree_node32 *n, *p; |
| |
| n = kmalloc(sizeof(*n), gfp); |
| if (IS_ERR(n)) |
| return PTR_ERR(n); |
| n->key = key; |
| n->val = val; |
| list_for_each_entry(p, &head->head, entry) { |
| if (p->key > key) |
| break; |
| } |
| list_add(&n->entry, p->entry.prev); |
| return 0; |
| } |
| |
| static inline int __must_check btree_insert64(struct btree_head64 *head, |
| u64 key, void *val, gfp_t gfp) |
| { |
| struct btree_node64 *n, *p; |
| |
| n = kmalloc(sizeof(*n), gfp); |
| if (IS_ERR(n)) |
| return PTR_ERR(n); |
| n->key = key; |
| n->val = val; |
| list_for_each_entry(p, &head->head, entry) { |
| if (p->key > key) |
| break; |
| } |
| list_add(&n->entry, p->entry.prev); |
| return 0; |
| } |
| |
| /** |
| * btree_update - update an entry in the btree |
| * |
| * @head: the btree to update |
| * @geo: the btree geometry |
| * @key: the key to update |
| * @val: the value to change it to (must not be %NULL) |
| * |
| * This function returns 0 if the update was successful, or |
| * -%ENOENT if the key could not be found. |
| */ |
| static inline int btree_update32(struct btree_head32 *head, u32 key, void *val) |
| { |
| struct btree_node32 *p; |
| |
| list_for_each_entry(p, &head->head, entry) { |
| if (p->key == key) { |
| p->val = val; |
| return 0; |
| } |
| } |
| return -ENOENT; |
| } |
| |
| /** |
| * btree_remove - remove an entry from the btree |
| * |
| * @head: the btree to update |
| * @geo: the btree geometry |
| * @key: the key to remove |
| * |
| * This function returns the removed entry, or %NULL if the key |
| * could not be found. |
| */ |
| static inline void *btree_remove32(struct btree_head32 *head, u32 key) |
| { |
| struct btree_node32 *p; |
| void *val; |
| |
| list_for_each_entry(p, &head->head, entry) { |
| if (p->key == key) { |
| val = p->val; |
| list_del(&p->entry); |
| kfree(p); |
| return val; |
| } |
| } |
| return NULL; |
| } |
| |
| static inline void *btree_remove64(struct btree_head64 *head, u64 key) |
| { |
| struct btree_node64 *p; |
| void *val; |
| |
| list_for_each_entry(p, &head->head, entry) { |
| if (p->key == key) { |
| val = p->val; |
| list_del(&p->entry); |
| kfree(p); |
| return val; |
| } |
| } |
| return NULL; |
| } |
| |
| /** |
| * btree_last - get last entry in btree |
| * |
| * @head: btree head |
| * @geo: btree geometry |
| * @key: last key |
| * |
| * Returns the last entry in the btree, and sets @key to the key |
| * of that entry; returns NULL if the tree is empty, in that case |
| * key is not changed. |
| */ |
| static inline void *btree_last32(struct btree_head32 *head, u32 *key) |
| { |
| struct btree_node32 *p; |
| |
| if (list_empty(&head->head)) |
| return NULL; |
| p = list_last_entry(&head->head, typeof(*p), entry); |
| *key = p->key; |
| return p->val; |
| } |
| |
| static inline void *btree_last64(struct btree_head64 *head, u64 *key) |
| { |
| struct btree_node64 *p; |
| |
| if (list_empty(&head->head)) |
| return NULL; |
| p = list_last_entry(&head->head, typeof(*p), entry); |
| *key = p->key; |
| return p->val; |
| } |
| |
| /** |
| * btree_get_prev - get previous entry |
| * |
| * @head: btree head |
| * @geo: btree geometry |
| * @key: pointer to key |
| * |
| * The function returns the next item right before the value pointed to by |
| * @key, and updates @key with its key, or returns %NULL when there is no |
| * entry with a key smaller than the given key. |
| */ |
| static inline void *btree_get_prev32(struct btree_head32 *head, u32 *key) |
| { |
| struct btree_node32 *p; |
| |
| list_for_each_entry_reverse(p, &head->head, entry) { |
| if (p->key < *key) { |
| *key = p->key; |
| return p->val; |
| } |
| } |
| return NULL; |
| } |
| |
| static inline void *btree_get_prev64(struct btree_head64 *head, u64 *key) |
| { |
| struct btree_node64 *p; |
| |
| list_for_each_entry_reverse(p, &head->head, entry) { |
| if (p->key < *key) { |
| *key = p->key; |
| return p->val; |
| } |
| } |
| return NULL; |
| } |
| |
| #define btree_for_each_safe32(head, key, val) \ |
| for (val = btree_last32(head, &key); \ |
| val; \ |
| val = btree_get_prev32(head, &key)) |
| |
| #define btree_for_each_safe64(head, key, val) \ |
| for (val = btree_last64(head, &key); \ |
| val; \ |
| val = btree_get_prev64(head, &key)) |
| |
| #endif /* _BTREE_BACKPORT_H_ */ |