git.itanic.dy.fi Git - sdl-planets/blob - quadtree.h

   1 #ifndef _QUADTREE_H_
   2 #define _QUADTREE_H_
   3
   4 #include <string.h>
   5
   6 #include "utils.h"
   7
   8 struct quadtree {
   9         struct quadtree *child[4];
  10         struct quadtree *parent;
  11
  12         /* statistics */
  13         long int children;      /* The total number of children */
  14         long int depth;         /* The deepest subtree branch */
  15 };
  16
  17 struct quadtree_ops {
  18         /*
  19          * Comparison function that is needed to find out the correct
  20          * location for a node in the tree
  21          */
  22         int (*compare)(struct quadtree *a, struct quadtree *b);
  23
  24         /*
  25          * Calculates required statistical information for a node
  26          */
  27         void (*recalculate_stats)(struct quadtree *node);
  28 };
  29
  30 static inline void init_quadtree(struct quadtree *t)
  31 {
  32         memset(t, 0, sizeof(*t));
  33 }
  34
  35 #define QUADTREE_UPLEFT         0x1
  36 #define QUADTREE_UPRIGHT        0x2
  37 #define QUADTREE_DOWNLEFT       0x4
  38 #define QUADTREE_DOWNRIGHT      0x8
  39 #define QUADTREE_SELF           0x10
  40
  41 struct quadtree_iterator {
  42         struct quadtree *head;
  43         void *ptr;
  44
  45         int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
  46         void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
  47 };
  48
  49 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
  50                               struct quadtree_ops *ops);
  51
  52 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
  53
  54 int walk_quadtree(const struct quadtree_iterator *iterator);
  55
  56
  57 /* quadtree_find_parent - return the highest parent of the node */
  58 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
  59 {
  60         struct quadtree *t = (struct quadtree *)node;
  61         while (t->parent)
  62                 t = t->parent;
  63
  64         return t;
  65 }
  66
  67 /*
  68  * Recursively walk through the tree and propagate changes made to the
  69  * given node up until the highest parent.
  70  */
  71 static inline void quadtree_recalculate_parent_stats(struct quadtree *node,
  72                                                      struct quadtree_ops *ops)
  73 {
  74         int i;
  75
  76         while (node) {
  77                 node->depth = 0;
  78                 node->children = 0;
  79
  80                 for (i = 0; i < 4; i++) {
  81                         if (!node->child[i])
  82                                 continue;
  83
  84                         node->depth = MAX(node->depth,
  85                                           node->child[i]->depth + 1);
  86                         node->children += node->child[i]->children + 1;
  87                 }
  88
  89                 if (ops->recalculate_stats)
  90                         ops->recalculate_stats(node);
  91
  92                 node = node->parent;
  93         }
  94 }
  95
  96 #endif