tools/perf/util/pstack.c

   1 /*
   2  * Simple pointer stack
   3  *
   4  * (c) 2010 Arnaldo Carvalho de Melo <acme@redhat.com>
   5  */
   6
   7 #include "util.h"
   8 #include "pstack.h"
   9 #include <linux/kernel.h>
  10 #include <stdlib.h>
  11
  12 struct pstack {
  13         unsigned short  top;
  14         unsigned short  max_nr_entries;
  15         void            *entries[0];
  16 };
  17
  18 struct pstack *pstack__new(unsigned short max_nr_entries)
  19 {
  20         struct pstack *pstack = zalloc((sizeof(*pstack) +
  21                                        max_nr_entries * sizeof(void *)));
  22         if (pstack != NULL)
  23                 pstack->max_nr_entries = max_nr_entries;
  24         return pstack;
  25 }
  26
  27 void pstack__delete(struct pstack *pstack)
  28 {
  29         free(pstack);
  30 }
  31
  32 bool pstack__empty(const struct pstack *pstack)
  33 {
  34         return pstack->top == 0;
  35 }
  36
  37 void pstack__remove(struct pstack *pstack, void *key)
  38 {
  39         unsigned short i = pstack->top, last_index = pstack->top - 1;
  40
  41         while (i-- != 0) {
  42                 if (pstack->entries[i] == key) {
  43                         if (i < last_index)
  44                                 memmove(pstack->entries + i,
  45                                         pstack->entries + i + 1,
  46                                         (last_index - i) * sizeof(void *));
  47                         --pstack->top;
  48                         return;
  49                 }
  50         }
  51         pr_err("%s: %p not on the pstack!\n", __func__, key);
  52 }
  53
  54 void pstack__push(struct pstack *pstack, void *key)
  55 {
  56         if (pstack->top == pstack->max_nr_entries) {
  57                 pr_err("%s: top=%d, overflow!\n", __func__, pstack->top);
  58                 return;
  59         }
  60         pstack->entries[pstack->top++] = key;
  61 }
  62
  63 void *pstack__pop(struct pstack *pstack)
  64 {
  65         void *ret;
  66
  67         if (pstack->top == 0) {
  68                 pr_err("%s: underflow!\n", __func__);
  69                 return NULL;
  70         }
  71
  72         ret = pstack->entries[--pstack->top];
  73         pstack->entries[pstack->top] = NULL;
  74         return ret;
  75 }