From 262591ec1adc1badfcb36e9e6876dd81f2df9492 Mon Sep 17 00:00:00 2001 From: Dana Jansens Date: Mon, 29 Mar 2010 23:21:22 -0400 Subject: [PATCH] add BSEARCH() macros in obt/bsearch.h that to a binary search on an array, use it when searching for a group in obt_paths_try_exec() --- Makefile.am | 1 + obt/bsearch.h | 54 +++++++++++++++++++++++++++++++++++++++++++++++++++ obt/paths.c | 20 +++++++++++++++---- 3 files changed, 71 insertions(+), 4 deletions(-) create mode 100644 obt/bsearch.h diff --git a/Makefile.am b/Makefile.am index d919f65b..e8d5b462 100644 --- a/Makefile.am +++ b/Makefile.am @@ -126,6 +126,7 @@ obt_libobt_la_LIBADD = \ $(GLIB_LIBS) \ $(XML_LIBS) obt_libobt_la_SOURCES = \ + obt/bsearch.h \ obt/display.h \ obt/display.c \ obt/internal.h \ diff --git a/obt/bsearch.h b/obt/bsearch.h new file mode 100644 index 00000000..ca5ae5b2 --- /dev/null +++ b/obt/bsearch.h @@ -0,0 +1,54 @@ +/* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*- + + obt/bsearch.h for the Openbox window manager + Copyright (c) 2010 Dana Jansens + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + See the COPYING file for a copy of the GNU General Public License. +*/ + +#ifndef __obt_bsearch_h +#define __obt_bsearch_h + +#include + +G_BEGIN_DECLS + +#define BSEARCH_SETUP(t) \ + register t l_BSEARCH, r_BSEARCH, out_BSEARCH; + +#define BSEARCH(t, ar, start, size, val) \ +{ \ + l_BSEARCH = (start); \ + r_BSEARCH = (start)+(size)-1; \ + while (l_BSEARCH <= r_BSEARCH) { \ + /* m is in the middle, but to the left if there's an even number \ + of elements */ \ + out_BSEARCH = l_BSEARCH + (r_BSEARCH - l_BSEARCH)/2; \ + if ((val) == (ar)[out_BSEARCH]) { \ + break; \ + } \ + else if ((val) < (ar)[out_BSEARCH]) \ + r_BSEARCH = out_BSEARCH-1; /* search to the left side */ \ + else \ + l_BSEARCH = out_BSEARCH+1; /* search to the left side */ \ + } \ +} + +#define BSEARCH_FOUND() (l_BSEARCH <= r_BSEARCH) +#define BSEARCH_AT() (out_BSEARCH) + + + +G_END_DECLS + +#endif diff --git a/obt/paths.c b/obt/paths.c index f723ae2c..e2e4859b 100644 --- a/obt/paths.c +++ b/obt/paths.c @@ -16,9 +16,13 @@ See the COPYING file for a copy of the GNU General Public License. */ +#include "obt/bsearch.h" #include "obt/paths.h" #include "obt/util.h" +#ifdef HAVE_STDLIB_H +# include +#endif #ifdef HAVE_SYS_STAT_H # include #endif @@ -90,6 +94,12 @@ static GSList* split_paths(const gchar *paths) return list; } +int gid_cmp(const void *va, const void *vb) +{ + const gid_t a = *(const gid_t*)va, b = *(const gid_t*)vb; + return a>b ? 1 : (a == b ? 0 : -1); +} + static void find_uid_gid(uid_t *u, gid_t **g, guint *n) { struct passwd *pw; @@ -115,6 +125,8 @@ static void find_uid_gid(uid_t *u, gid_t **g, guint *n) } } endgrent(); + + qsort(*g, sizeof(gid_t), *n, gid_cmp); } ObtPaths* obt_paths_new(void) @@ -317,7 +329,7 @@ static inline gboolean try_exec(const ObtPaths *const p, const gchar *const path) { struct stat st; - guint i; + BSEARCH_SETUP(guint); stat(path, &st); @@ -325,9 +337,9 @@ static inline gboolean try_exec(const ObtPaths *const p, return FALSE; if (st.st_uid == p->uid) return st.st_mode & S_IXUSR; - for (i = 0; i < p->n_gid; ++i) - if (st.st_gid == p->gid[i]) - return st.st_mode & S_IXGRP; + BSEARCH(guint, p->gid, 0, p->n_gid, st.st_gid); + if (BSEARCH_FOUND()) + return st.st_mode & S_IXGRP; return st.st_mode & S_IXOTH; } -- 2.45.2