15db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#ifndef BTREE_H 25db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_H 35db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 45db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include <linux/kernel.h> 55db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include <linux/mempool.h> 65db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 75db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 85db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * DOC: B+Tree basics 95db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * A B+Tree is a data structure for looking up arbitrary (currently allowing 115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure 125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * is described at http://en.wikipedia.org/wiki/B-tree, we currently do not 135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * use binary search to find the key on lookups. 145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Each B+Tree consists of a head, that contains bookkeeping information and 165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * a variable number (starting with zero) nodes. Each node contains the keys 175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the 185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * tree entries. 195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Each node in this implementation has the following layout: 215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * [key1, key2, ..., keyN] [val1, val2, ..., valN] 225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Each key here is an array of unsigned longs, geo->no_longs in total. The 245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * number of keys and values (N) is geo->no_pairs. 255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * struct btree_head - btree head 295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @node: the first node in the tree 315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @mempool: mempool used for node allocations 325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @height: current of the tree 335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstruct btree_head { 355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *node; 365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel mempool_t *mempool; 375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int height; 385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel}; 395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* btree geometry */ 415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstruct btree_geo; 425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_alloc - allocate function for the mempool 455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @gfp_mask: gfp mask for the allocation 465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @pool_data: unused 475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid *btree_alloc(gfp_t gfp_mask, void *pool_data); 495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_free - free function for the mempool 525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @element: the element to free 535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @pool_data: unused 545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid btree_free(void *element, void *pool_data); 565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_init_mempool - initialise a btree with given mempool 595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: the btree head to initialise 615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @mempool: the mempool to use 625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * When this function is used, there is no need to destroy 645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * the mempool. 655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid btree_init_mempool(struct btree_head *head, mempool_t *mempool); 675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_init - initialise a btree 705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: the btree head to initialise 725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * This function allocates the memory pool that the 745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree needs. Returns zero or a negative error code 755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * (-%ENOMEM) when memory allocation fails. 765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelint __must_check btree_init(struct btree_head *head); 795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_destroy - destroy mempool 825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: the btree head to destroy 845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * This function destroys the internal memory pool, use only 865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * when using btree_init(), not with btree_init_mempool(). 875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid btree_destroy(struct btree_head *head); 895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_lookup - look up a key in the btree 925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: the btree to look in 945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @geo: the btree geometry 955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @key: the key to look up 965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * This function returns the value for the given key, or %NULL. 985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid *btree_lookup(struct btree_head *head, struct btree_geo *geo, 1005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key); 1015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 1035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_insert - insert an entry into the btree 1045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: the btree to add to 1065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @geo: the btree geometry 1075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @key: the key to add (must not already be present) 1085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @val: the value to add (must not be %NULL) 1095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @gfp: allocation flags for node allocations 1105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * This function returns 0 if the item could be added, or an 1125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * error code if it failed (may fail due to memory pressure). 1135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 1145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelint __must_check btree_insert(struct btree_head *head, struct btree_geo *geo, 1155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key, void *val, gfp_t gfp); 1165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 1175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_update - update an entry in the btree 1185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: the btree to update 1205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @geo: the btree geometry 1215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @key: the key to update 1225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @val: the value to change it to (must not be %NULL) 1235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * This function returns 0 if the update was successful, or 1255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * -%ENOENT if the key could not be found. 1265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 1275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelint btree_update(struct btree_head *head, struct btree_geo *geo, 1285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key, void *val); 1295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 1305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_remove - remove an entry from the btree 1315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: the btree to update 1335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @geo: the btree geometry 1345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @key: the key to remove 1355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * This function returns the removed entry, or %NULL if the key 1375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * could not be found. 1385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 1395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid *btree_remove(struct btree_head *head, struct btree_geo *geo, 1405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key); 1415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 1435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_merge - merge two btrees 1445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @target: the tree that gets all the entries 1465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @victim: the tree that gets merged into @target 1475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @geo: the btree geometry 1485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @gfp: allocation flags 1495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * The two trees @target and @victim may not contain the same keys, 1515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * that is a bug and triggers a BUG(). This function returns zero 1525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * if the trees were merged successfully, and may return a failure 1535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * when memory allocation fails, in which case both trees might have 1545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * been partially merged, i.e. some entries have been moved from 1555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @victim to @target. 1565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 1575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelint btree_merge(struct btree_head *target, struct btree_head *victim, 1585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct btree_geo *geo, gfp_t gfp); 1595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 1615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_last - get last entry in btree 1625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: btree head 1645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @geo: btree geometry 1655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @key: last key 1665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Returns the last entry in the btree, and sets @key to the key 1685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * of that entry; returns NULL if the tree is empty, in that case 1695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * key is not changed. 1705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 1715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid *btree_last(struct btree_head *head, struct btree_geo *geo, 1725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key); 1735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/** 1755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * btree_get_prev - get previous entry 1765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @head: btree head 1785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @geo: btree geometry 1795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @key: pointer to key 1805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * The function returns the next item right before the value pointed to by 1825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * @key, and updates @key with its key, or returns %NULL when there is no 1835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * entry with a key smaller than the given key. 1845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 1855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid *btree_get_prev(struct btree_head *head, struct btree_geo *geo, 1865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key); 1875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* internal use, use btree_visitor{l,32,64,128} */ 1905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelsize_t btree_visitor(struct btree_head *head, struct btree_geo *geo, 1915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long opaque, 1925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel void (*func)(void *elem, unsigned long opaque, 1935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key, size_t index, 1945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel void *func2), 1955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel void *func2); 1965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* internal use, use btree_grim_visitor{l,32,64,128} */ 1985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelsize_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, 1995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long opaque, 2005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel void (*func)(void *elem, unsigned long opaque, 2015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel unsigned long *key, 2025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel size_t index, void *func2), 2035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel void *func2); 2045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include <linux/btree-128.h> 2075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelextern struct btree_geo btree_geo32; 2095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_SUFFIX l 2105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_BITS BITS_PER_LONG 2115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_GEO &btree_geo32 2125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_KEYTYPE unsigned long 2135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include <linux/btree-type.h> 2145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define btree_for_each_safel(head, key, val) \ 2165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (val = btree_lastl(head, &key); \ 2175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel val; \ 2185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel val = btree_get_prevl(head, &key)) 2195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_SUFFIX 32 2215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_BITS 32 2225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_GEO &btree_geo32 2235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_KEYTYPE u32 2245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include <linux/btree-type.h> 2255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define btree_for_each_safe32(head, key, val) \ 2275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (val = btree_last32(head, &key); \ 2285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel val; \ 2295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel val = btree_get_prev32(head, &key)) 2305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelextern struct btree_geo btree_geo64; 2325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_SUFFIX 64 2335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_BITS 64 2345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_TYPE_GEO &btree_geo64 2355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define BTREE_KEYTYPE u64 2365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include <linux/btree-type.h> 2375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define btree_for_each_safe64(head, key, val) \ 2395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (val = btree_last64(head, &key); \ 2405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel val; \ 2415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel val = btree_get_prev64(head, &key)) 2425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#endif 244